trovare la distanza più breve tra un punto e segmenti (non line)

Question

Ho regolato di segmenti (non linee), (A1, B1), (A2, B2), (A3, B3), dove A, B sono finendo punti del segmento di linea. Ogni A e B ha coordinate (x,y).

DOMANDA: Ho bisogno di conoscere la distanza più breve tra point O e line segments come mostrato nella figura mostrata attuato in linea di codici. Il codice che posso veramente capire è pseudo-codice o Python.

CODICE: Ho provato a risolvere il problema con questo codice, sfortunatamente, non funziona correttamente.

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)] 

Grazie in anticipo.

Answer 1

Algoritmo di base: fingere di avere linee, così orientato che A si trova a sinistra di B.

Trova il punto più vicino come al solito. Se il punto è compreso tra A e B, il gioco è fatto. Se si trova a sinistra di A, il punto più vicino è A. Se il punto è a destra di B, il punto più vicino è B.

Il caso in cui A, B e O si trovano tutti sulla stessa linea può o non può richiedere particolare attenzione. Assicurati di includere alcuni test di questa posizione.

Answer 2

Ho dovuto risolvere anche questo problema, quindi per motivi di disponibilità pubblicherò il mio codice qui. Ho fatto una breve convalida, ma niente di particolarmente serio. La tua domanda mi ha effettivamente aiutato a identificare un bug nel mio dove un segmento di linea verticale o orizzontale avrebbe infranto il codice e scavalcato il punto di intersezione sulla logica di segmento.

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)) 

Answer 3

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