距离之间的两个
分而治之:
定义表示一对折线的和最低限度的距离他们的axis-aligned minimum bounding boxes (AAMBB)之间的数据结构:
pair = (poly_a, poly_b, d_ab)
)创建
pair
数据estructures空队列,使用距离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) }
使两者本身叉积TS,创建4层新
pair
数据结构,然后推入队列Q.
-
在平均情况下,复杂度为O(N *日志N),最坏的情况下可能是O( N²)。
更新:在Perl中实现的algorithm。
这种问题的“标准”方式是构造几何实体的Voronoi图。这可以在时间O(N日志N)中完成。
但是这种线段图的构建很困难,您应该使用现成的解决方案,例如CGAL。
voronoi克作为一个查找表可用于查找从任何地方最近的点,如果这些点不是将要改变,你必须从许多其他点查找最近的一个,它可能是值得的产生voronoi加快查找。但我没有看到它如何帮助计算两条多段线之间的距离? – gordy
这看起来像[quadtrees](https://en.wikipedia.org/wiki/Quadtree)可能会有所帮助 - 但是除了我的头顶之外,我没有比这更有用的了。 – hnefatl
不知道答案,但我猜测一些基于四叉树的算法必须是可能的,其中只计算附近元素之间的点线距离。 – jdehesa
基于边界框的方法可能会有所帮助。计算部分多段线的边界框(例如,A的点1 ... 4,4 ... 7和B的8 ... 10,10 ... 12)。对于每一对盒子,你可以计算最小和最大距离,并丢弃无法与最佳对成对竞争的对,递归地提炼盒子,直到它们都是2点(1行)盒子,你可以精确地计算。似乎是O(N logN)。 –