algorithm - Snap point to nearest line -

algorithm - Snap point to nearest line -

i have start , end point of every line. every line can vertical or horizontal.

example:

lines = [ ((1, 1), (1, 7)), // (start, end) ((1, 1), (7, 1)), ((4, 1), (4, 7)) ] point = (6, 6) nearestpointonline = (4, 6) // magic here

how calculate closest point on line point?

iterating segment segment, each segment, find closest point segment point (a,b)

there 3 cases:

horizontal line (x1, y) (x2, y) , point (a,b) has x1 <= <= x2, closest point (a,y)

vertical line (x, y1) (x, y2) , point (a,b) has y1 <= b <= y2, closest point (x,b)

none of these 2 above cases,in case, closest point either start or end point of segment. can determine calculate distance (a,b) start , end.

after getting point, homecoming point has shortest distance compared others. formula calculate distance point (a,b) point(c,d):

int x = - c; int y = b - d; double dist = sqrt(x*x + y*y);

algorithm 2d point lines