找到距离点最近的线段的最佳方法

Question

如下图所示，我有一些连接任意两个关节（红点）的线段（有限长度），例如关节J1和J2之间的线段。我还有一些点，如P1和P2。

我有点和关节的坐标。因此，可以计算出线段方程（y=mx+b）。因此，可以计算出点到任何线段的距离。因此，最小距离给出了距离该点最近的线段。

由于在这个问题中有大量的点，需要进行大量的计算。我正在寻找一种高效快速的方法。

使用重心坐标系，可以找到任何点周围的线段。这一技巧将减少计算量。但是，我正在寻找更多的技巧来使其更快。

- ard24ie

---

你考虑过使用四叉树吗？这可以帮助你快速确定需要检查的线段子集。 - Martin Wickman

或者R树（边界框树）。有时比四叉树更有效。 - Ilya

最近的直线不一定会触及最近的点。 沃罗诺伊图无法工作。 对于每条线进行暴力计算将给出O(n)。 - user7778925

实际上，当您要求每个点的最近线段时，其顺序为O（mxn），其中m =＃点，n =＃线段。 当这些数字非常大时，这可能是不可接受的，而最佳选择之一是使用PMRQuadTree。 参见：https://pdfs.semanticscholar.org/fcec/dd32bd3b181298f979fdef24a02a148e8bf4.pdf - Clon

Answer 1

一个Voronoi图可以让你快速查找。我认为你可以使用红点来构建Voronoi图。在我看来，最近的线就像最近的点一样。

- Micromega

---

我可以想象你会在这里使用 Voronoi 图，但我不确定这会如何加速处理速度。此外，找到包含给定点的 Voronoi 单元需要一些非常类似于问题描述中所述的操作。- 你能提供更多细节吗？ - mbschenkel

可能线段的中心点对于 Voronoi 图会比较合适（只要没有交叉）。但是你还需要一个高效利用 Voronoi 图来查找最近邻的算法（类似于这个：http://infolab.usc.edu/papers/VorTree.pdf），这本质上就回到了像上面建议的 R 树... - mbschenkel

好观点。在我看来，这只是为了可视化事物。我也认为R树很好，或者更简单的层次聚类或树状图。 - Micromega

Answer 2

你不能使用Voronoi图来表示线段的端点。

- user8011403