Finden Sie die kürzeste Entfernung zwischen einem Punkt und die Liniensegmente (nicht line)

Ich haben eine Menge der Liniensegmente (nicht Linien), (A1, B1), (A2, B2), (A3, B3), wo A,B sind die Endpunkte des Liniensegments. Jeder A und B hat (x,y) Koordinaten.

FRAGE:
Ich muss wissen, die kürzeste Entfernung zwischen point O und line segments wie gezeigt, in der gezeigt Abbildung umgesetzt Zeile des codes. Der code, den ich wirklich nachvollziehen kann, ist entweder pseudo-code oder Python.

CODE: ich habe versucht, das problem zu lösen mit diesem code, leider funktioniert es nicht richtig.

def dist(A, B, O):
    A_ = complex(*A)
    B_ = complex(*B)
    O_= complex(*O)
    OA = O_ - A_
    OB = O_ - B_
    return min(OA, OB)
# coordinates are given
A1, B1 = [1, 8], [6,4]
A2, B2 = [3,1], [5,2]
A3, B3 = [2,3], [2, 1]
O = [2, 5]
A = [A1, A2, A3]
B = [B1, B2, B3]
print [ dist(i, j, O)  for i, j in zip(A, B)]

Vielen Dank im Voraus.

Bitte posten Sie, was Sie bisher ausprobiert haben.
Ich habe einige codes, die ich ausprobiert habe um das problem zu lösen. Was würden Sie denken ?

InformationsquelleAutor Spider | 2014-11-27

4

Grundlegende Algorithmus: behaupten Sie, dass Sie Linien haben, so orientiert, dass A liegt Links von B.

Finden nächsten Punkt als normal. Wenn der Punkt zwischen A und B haben, sind Sie fertig. Wenn es Links von A, der nächste Punkt ist A. Wenn der Punkt rechts von B, der nächste Punkt ist B.

Dann der Fall, wenn A, B, und O alle liegen auf der gleichen Linie kann oder kann nicht die Besondere Aufmerksamkeit erfordern. Werden Sie sicher, dass Sie ein paar tests dieser position.
- Ich danke Ihnen sehr. Das problem ist, ich bin ein bisschen weit Weg von der Mathematik. und ich bin nicht in der Lage sich zu bewegen in Bezug auf coding (preferably Python). Können Sie mir einen Aufzug?
- Ich bin sicher, Sie werden in der Lage sein, um code diese Formel. Reihenfolge der Punkte und Sonderfälle sind immer noch auf Sie. Sorry, diese Seite ist in der Regel nicht über das schreiben von code für Sie, es sei denn, Sie haben genug geschrieben-code selbst, obwohl Ausnahmen vorkommen.
- Eine großartige Bereicherung. Ich Schätze, viel besser und kürzer ist Fall. Ich hoffe, es umfasst alle kniffligen Ausnahmefällen..!
- Ein Hinweis darauf, dass: wenn ein Punkt N liegt zwischen zwei anderen Punkten A und B jede Koordinate N liegt zwischen den entsprechenden Koordinaten A und B. Wenn der nächste Punkt nicht zwischen A und B sind, können Sie einfach berechnen (Quadrate) Entfernungen Formular Punkt O zu A, dann B, und wählen Sie die kürzeste ist.
- Das Tat ich, aber kann Sie sich anschauen, was ich gepostet unten in dem link. Ich denke, alle Fälle enthalten sind, in diesem kurzen code. Und als Spezialist können Sie bestätigen, dass es funktioniert in allen Fällen(Python-code)? Großen Dank
InformationsquelleAutor 9000

Die Erklärung ist in den docstring der Funktion:

def point_to_line_dist(point, line):
    """Calculate the distance between a point and a line segment.

    To calculate the closest distance to a line segment, we first need to check
    if the point projects onto the line segment.  If it does, then we calculate
    the orthogonal distance from the point to the line.
    If the point does not project to the line segment, we calculate the 
    distance to both endpoints and take the shortest distance.

    :param point: Numpy array of form [x,y], describing the point.
    :type point: numpy.core.multiarray.ndarray
    :param line: list of endpoint arrays of form [P1, P2]
    :type line: list of numpy.core.multiarray.ndarray
    :return: The minimum distance to a point.
    :rtype: float
    """
    # unit vector
    unit_line = line[1] - line[0]
    norm_unit_line = unit_line / np.linalg.norm(unit_line)

    # compute the perpendicular distance to the theoretical infinite line
    segment_dist = (
        np.linalg.norm(np.cross(line[1] - line[0], line[0] - point)) /
        np.linalg.norm(unit_line)
    )

    diff = (
        (norm_unit_line[0] * (point[0] - line[0][0])) + 
        (norm_unit_line[1] * (point[1] - line[0][1]))
    )

    x_seg = (norm_unit_line[0] * diff) + line[0][0]
    y_seg = (norm_unit_line[1] * diff) + line[0][1]

    endpoint_dist = min(
        np.linalg.norm(line[0] - point),
        np.linalg.norm(line[1] - point)
    )

    # decide if the intersection point falls on the line segment
    lp1_x = line[0][0]  # line point 1 x
    lp1_y = line[0][1]  # line point 1 y
    lp2_x = line[1][0]  # line point 2 x
    lp2_y = line[1][1]  # line point 2 y
    is_betw_x = lp1_x <= x_seg <= lp2_x or lp2_x <= x_seg <= lp1_x
    is_betw_y = lp1_y <= y_seg <= lp2_y or lp2_y <= y_seg <= lp1_y
    if is_betw_x and is_betw_y:
        return segment_dist
    else:
        # if not, then return the minimum distance to the segment endpoints
        return endpoint_dist

Keine Erklärung. Bitte keine post-code-nur Antworten.
Die Erklärung ist in der docstring.

InformationsquelleAutor Roman

Hier ist die Antwort. Dieser code gehört zu Malcolm Kesson, die Quelle ist hier. Sofern ich es vorher mit nur link selbst, und es war gelöscht durch moderator. Ich gehe davon aus, dass der Grund dafür ist nicht zu erbringen, den code (als Antwort).

import math

def dot(v,w):
    x,y,z = v
    X,Y,Z = w
    return x*X + y*Y + z*Z

def length(v):
    x,y,z = v
    return math.sqrt(x*x + y*y + z*z)

def vector(b,e):
    x,y,z = b
    X,Y,Z = e
    return (X-x, Y-y, Z-z)

def unit(v):
    x,y,z = v
    mag = length(v)
    return (x/mag, y/mag, z/mag)

def distance(p0,p1):
    return length(vector(p0,p1))

def scale(v,sc):
    x,y,z = v
    return (x * sc, y * sc, z * sc)

def add(v,w):
    x,y,z = v
    X,Y,Z = w
    return (x+X, y+Y, z+Z)


# Given a line with coordinates 'start' and 'end' and the
# coordinates of a point 'pnt' the proc returns the shortest 
# distance from pnt to the line and the coordinates of the 
# nearest point on the line.
#
# 1  Convert the line segment to a vector ('line_vec').
# 2  Create a vector connecting start to pnt ('pnt_vec').
# 3  Find the length of the line vector ('line_len').
# 4  Convert line_vec to a unit vector ('line_unitvec').
# 5  Scale pnt_vec by line_len ('pnt_vec_scaled').
# 6  Get the dot product of line_unitvec and pnt_vec_scaled ('t').
# 7  Ensure t is in the range 0 to 1.
# 8  Use t to get the nearest location on the line to the end
#    of vector pnt_vec_scaled ('nearest').
# 9  Calculate the distance from nearest to pnt_vec_scaled.
# 10 Translate nearest back to the start/end line. 
# Malcolm Kesson 16 Dec 2012

def pnt2line(pnt, start, end):
    line_vec = vector(start, end)
    pnt_vec = vector(start, pnt)
    line_len = length(line_vec)
    line_unitvec = unit(line_vec)
    pnt_vec_scaled = scale(pnt_vec, 1.0/line_len)
    t = dot(line_unitvec, pnt_vec_scaled)    
    if t < 0.0:
        t = 0.0
    elif t > 1.0:
        t = 1.0
    nearest = scale(line_vec, t)
    dist = distance(nearest, pnt_vec)
    nearest = add(nearest, start)
    return (dist, nearest)

InformationsquelleAutor Spider

Auf meiner Seite, ich habe festgestellt, dass die beiden anderen Antworten waren kaputt, vor allem, wenn Sie die Zeile rein vertikale oder horizontale. Hier ist, was ich Tat, um das problem richtig lösen.

Python-code:

def sq_shortest_dist_to_point(self, other_point):
    dx = self.b.x - self.a.x
    dy = self.b.y - self.a.y
    dr2 = float(dx ** 2 + dy ** 2)

    lerp = ((other_point.x - self.a.x) * dx + (other_point.y - self.a.y) * dy) / dr2
    if lerp < 0:
        lerp = 0
    elif lerp > 1:
        lerp = 1

    x = lerp * dx + self.a.x
    y = lerp * dy + self.a.y

    _dx = x - other_point.x
    _dy = y - other_point.y
    square_dist = _dx ** 2 + _dy ** 2
    return square_dist

def shortest_dist_to_point(self, other_point):
    return math.sqrt(self.sq_shortest_dist_to_point(other_point))

Ein test-Fall:

def test_distance_to_other_point(self):
    # Parametrize test with multiple cases:
    segments_and_point_and_answer = [
        [Segment(Point(1.0, 1.0), Point(1.0, 3.0)), Point(2.0, 4.0), math.sqrt(2.0)],
        [Segment(Point(1.0, 1.0), Point(1.0, 3.0)), Point(2.0, 3.0), 1.0],
        [Segment(Point(0.0, 0.0), Point(0.0, 3.0)), Point(1.0, 1.0), 1.0],
        [Segment(Point(1.0, 1.0), Point(3.0, 3.0)), Point(2.0, 2.0), 0.0],
        [Segment(Point(-1.0, -1.0), Point(3.0, 3.0)), Point(2.0, 2.0), 0.0],
        [Segment(Point(1.0, 1.0), Point(1.0, 3.0)), Point(2.0, 3.0), 1.0],
        [Segment(Point(1.0, 1.0), Point(1.0, 3.0)), Point(2.0, 4.0), math.sqrt(2.0)],
        [Segment(Point(1.0, 1.0), Point(-3.0, -3.0)), Point(-3.0, -4.0), 1],
        [Segment(Point(1.0, 1.0), Point(-3.0, -3.0)), Point(-4.0, -3.0), 1],
        [Segment(Point(1.0, 1.0), Point(-3.0, -3.0)), Point(1, 2), 1],
        [Segment(Point(1.0, 1.0), Point(-3.0, -3.0)), Point(2, 1), 1],
        [Segment(Point(1.0, 1.0), Point(-3.0, -3.0)), Point(-3, -1), math.sqrt(2.0)],
        [Segment(Point(1.0, 1.0), Point(-3.0, -3.0)), Point(-1, -3), math.sqrt(2.0)],
        [Segment(Point(-1.0, -1.0), Point(3.0, 3.0)), Point(3, 1), math.sqrt(2.0)],
        [Segment(Point(-1.0, -1.0), Point(3.0, 3.0)), Point(1, 3), math.sqrt(2.0)],
        [Segment(Point(1.0, 1.0), Point(3.0, 3.0)), Point(3, 1), math.sqrt(2.0)],
        [Segment(Point(1.0, 1.0), Point(3.0, 3.0)), Point(1, 3), math.sqrt(2.0)]
    ]

    for i, (segment, point, answer) in enumerate(segments_and_point_and_answer):
        result = segment.shortest_dist_to_point(point)
        self.assertAlmostEqual(result, answer, delta=0.001, msg=str((i, segment, point, answer)))

Hinweis: ich nehme an, diese Funktion ist in einem Segment Klasse.
Im Fall, dass Ihre Linie ist unendlich, nicht die Grenze lerp von 0 bis 1 nur, aber immer noch wenigstens zwei unterschiedliche a und b Punkte.

InformationsquelleAutor Guillaume Chevalier

-1

Hatte ich dieses problem zu lösen, so dass aus Gründen der Verfügbarkeit poste ich meinen code hier. Ich habe einige oberflächliche überprüfung, aber nichts besonders ernstes. Deine Frage tatsächlich geholfen, mich zu identifizieren, ein bug in der mine, wo eine vertikale oder horizontale Linie segment hätte den code gebrochen und umgangen, wird der Schnittpunkt auf segment-Logik.

from math import sqrt

def dist_to_segment(ax, ay, bx, by, cx, cy):
    """
    Computes the minimum distance between a point (cx, cy) and a line segment with endpoints (ax, ay) and (bx, by).
    :param ax: endpoint 1, x-coordinate
    :param ay: endpoint 1, y-coordinate
    :param bx: endpoint 2, x-coordinate
    :param by: endpoint 2, y-coordinate
    :param cx: point, x-coordinate
    :param cy: point, x-coordinate
    :return: minimum distance between point and line segment
    """
    # avoid divide by zero error
    a = max(by - ay, 0.00001)
    b = max(ax - bx, 0.00001)
    # compute the perpendicular distance to the theoretical infinite line
    dl = abs(a * cx + b * cy - b * ay - a * ax) / sqrt(a**2 + b**2)
    # compute the intersection point
    x = ((a / b) * ax + ay + (b / a) * cx - cy) / ((b / a) + (a / b))
    y = -1 * (a / b) * (x - ax) + ay
    # decide if the intersection point falls on the line segment
    if (ax <= x <= bx or bx <= x <= ax) and (ay <= y <= by or by <= y <= ay):
        return dl
    else:
        # if it does not, then return the minimum distance to the segment endpoints
        return min(sqrt((ax - cx)**2 + (ay - cy)**2), sqrt((bx - cx)**2 + (by - cy)**2))

Ihre Mathematik ist gebrochen. Führen Sie einige tests mit verschiedenen Linien und Punkte
Ich habe Ihre Vorlage und fixiert es, so dass keine künstlichen Konstante Hinzugefügt werden muss, und auch inline-Werte sind nun korrekt

InformationsquelleAutor Will

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.