algorithm - 找到最接近点的线段的最佳方法

Question

如下图所示，我在任意两个关节(红点)之间有一些线(有限长度)，例如关节 J1 和 J2 之间的线。我还有一些要点，例如 P1 和 P2。

我有点和关节的坐标。因此，可以计算线方程 (y=mx+b)。因此，可以计算点到任何线之间的距离。因此，最短距离为我提供了距该点最近的线。

由于这个问题的点数非常多，计算量很大。我正在为此寻找一种高效快速的方法。

使用 Barycentric coordinate system ，我可以找到任何点被哪些线包围。这个技巧将减少计算次数。但是，我正在寻找更多技巧来使其更快。

Answer 1

voronoi 图可以让您快速查找。我认为您可以将红点用于 voronoi 图。 IMO 最近的线与最近的点相同。