两条折线之间的距离

Question

我希望计算两条折线段之间的距离d:

显然，我可以检查所有线段对的距离并选择最小距离，但这种方法的算法时间复杂度为O(n²)。有更好的方法吗？

- user2033412

---

这看起来像是四叉树可以胜任的任务 - 但就我目前所知，除此之外没有更有用的建议了。 - hnefatl

不知道答案，但我猜测可能可以使用基于四叉树的算法，在其中仅计算相邻元素之间的点线距离。 - jdehesa

一种基于边界框的方法可能有所帮助。计算部分折线的边界框（例如从A中的点1...4、4...7和从B中的点8...10、10...12）。对于每一对边界框，可以计算出最小距离和最大距离，并丢弃无法与最佳匹配竞争的对，递归地细化边界框，直到它们全部变成2点（1条线）的边界框，在这里您可以进行精确的计算。似乎是O（N logN）的复杂度。 - Ralf Kleberhoff

在你的例子中，最接近的点位于折线的顶点，这只是一个特殊情况吗？如果两条线段相交但没有顶点，距离是否为零？ - ROX

如果两个线段相交，则它们之间的距离为零。 - user2033412

Answer 1

分而治之：

• 定义一种数据结构，代表一对折线以及它们的轴对齐最小边界框(AAMBB)之间的最小距离：pair = (poly_a, poly_b, d_ab)。

• 为pair数据结构创建一个空队列，使用距离d_ab作为关键字。

• 创建一个初始折线对的pair数据结构，并将其推入队列中。

• 我们将保留迄今为止找到的折线之间的最小距离(min_d)。将其设置为无穷大。

• 重复：

  • 从队列中弹出距离d_ab最小的元素。

  • 如果d_ab大于min_d，我们就完成了。

  • 如果任何一个折线poly_a或poly_b只包含一个线段：

    • 使用暴力法查找它们之间的最小距离，并相应地更新min_d。

  • 否则：

    • 将折线poly_a和poly_b分为两半，例如：

      (1-7) --> { (1-4), (4-7) }

      (8-12) --> { (8-10), (10-12) }

    • 对两组进行叉乘，创建4个新的pair数据结构，并将它们推入队列Q中。

平均情况下，复杂度为O(N * log N)，最坏情况可能为O(N²)。

更新：用Perl实现的算法。

- salva

---

谢谢分享您的设计。我不熟悉Perl，你能举个例子说明一下如何计算距离d_ab（即AAMBB之间的最小距离）吗？ - Beanocean

Answer 2

“标准”的解决此类问题的方法是构建几何实体的 Voronoi 图。这可以在 O(N Log N) 的时间内完成。

但是，对于线段的这种图的构建是困难的，您应该使用现成的解决方案，例如 CGAL。

- user1196549

---

Voronoi图是一个有用的查找表，用于在任何地方查找最近的点，如果这些点不会改变并且您必须从许多其他点中查找最近的点，则生成Voronoi图以加速查找可能很值得。但我看不出它如何帮助计算两条折线之间的距离？ - gordy