Найти кратчайшее расстояние между точкой и линейными сегментами (не линия)

Question

я набор линейных сегментов (не линии), (A1, B1), (A2, B2), (A3, B3), где A, B заканчиваются точки отрезка линии. Каждый A и B имеет (x,y) координаты.

ВОПРОС: мне нужно знать, самое короткое расстояние между point O и line segments, как показано на рисунке, показанном , реализованной в строке кодов. Код, который я действительно могу понять, это либо псевдокод, либо Python.

КОД: Я пытался решить эту проблему с этим кодом, к сожалению, он не работает должным образом.

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

Спасибо заранее.

Answer 1

Основной алгоритм: притворитесь, что у вас есть линии, поэтому ориентированы на то, что A лежит слева от B.

Найти ближайший пункт как обычно. Если точка находится между A и B, все готово. Если он находится слева от A, ближайшей точкой является A. Если точка находится справа от B, ближайшей точкой является B.

В случае, когда A, B и O все лежат на одной линии, может потребоваться или не потребоваться особое внимание. Обязательно включите несколько тестов этой позиции.

Answer 2

Мне также пришлось решить эту проблему, поэтому, ради доступности, я отправлю свой код здесь. Я сделал некоторую беглую проверку, но ничего особенно серьезного. Ваш вопрос действительно помог мне определить ошибку в шахте, где вертикальный или горизонтальный сегмент линии сломал бы код и обошел точку пересечения по логике сегмента.

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