The best way for finding the closest line segment

问题:

As can be seen in figure below, I have some lines (finite length) between any two joints (red points), such as the line between joints J1 and J2. I have also some points such as P1 and P2.

I have the coordinates of points and joints. So, it is possible to calculate the line equations (y=mx+b). So, it is possible to calculate the distance between a point to any line. So, the lowest distance gives me the closest line to the point.

Since there are a huge number of points in this problem, it takes a huge calculations. I am looking for an efficient and fast method for that.

Using the Barycentric coordinate system, I can find any point is surrounded with which lines. This trick will decrease the number of calculations. But, I am looking for more tricks to make it faster.

回答1:

A voronoi diagram can gives you fast lookup. I think you can use the red points for the voronoi diagram. IMO the closest line is the same like the closest point.

回答2:

You can't use Voronoi diagram for ending points of segments.