Find the shortest distance between points and line segments (not a line)

Question

I have a set of segments (not lines), (A1, B1) , (A2, B2) , (A3, B3) , where A , B are the end points of the line segment. Each A and B has (x,y) coordinates.

Question: I need to know the shortest distance between point O and line segments , as shown in the figure. implemented in the line of codes. The code I can really understand is either pseudo code or Python.

CODE: I tried to solve the problem with this code, unfortunately, it does not work properly.

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

Thanks in advance.

Answer 1

The main algorithm: pretend that you have lines, so it is oriented that A lies to the left of B

Find the nearest point as usual. If the point is between A and B , everything is ready. If it is to the left of A , the nearest point is A If the point is to the right of B , the nearest point is B

The case when A , B and O all on the same line may or may not need special attention. Be sure to include some tests for this item.

Answer 2

 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 

Answer 3

I also had to solve this problem, so for the sake of accessibility, I will post my code here. I did some quick check, but nothing particularly serious. Your question really helped me determine the error in the mine, where a vertical or horizontal line segment would break the code and bypass the intersection point of the segment logic.

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