两条折线之间的距离
Distance between two polylines
我想计算两条折线之间的距离 d:
显然我可以检查所有线段对的距离并选择最小距离，但这样算法的运行时间将为 O(n2)。有没有更好的方法？
解决此类问题的"standard"方法是构造几何实体的维诺图。这可以在 O(N Log N) 的时间内完成。
但是为线段构建这样的图表是困难的，你应该求助于现成的解决方案，比如在 CGAL 中。
分而治之：
定义一个数据结构表示一对折线和它们之间的最小距离axis-aligned minimum bounding boxes (AAMBB):pair = (poly_a, poly_b, d_ab))
为 pair 数据结构创建一个空队列，使用距离 d_ab 作为键。
用初始多段线创建一个pair数据结构并将其推入队列。
我们将保留一个变量，其中包含目前找到的折线之间的最小距离 (min_d)。设置为无限。
重复：
从队列中弹出距离最小的元素d_ab.
如果 d_ab 大于 min_d 我们就完成了。
如果任何折线 poly_a 或 poly_b 包含唯一的线段：
- 使用蛮力找到 then 之间的最小距离并相应地更新
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²)。
更新: algorithm 在 Perl 中实现。
我想计算两条折线之间的距离 d:
显然我可以检查所有线段对的距离并选择最小距离，但这样算法的运行时间将为 O(n2)。有没有更好的方法？
解决此类问题的"standard"方法是构造几何实体的维诺图。这可以在 O(N Log N) 的时间内完成。
但是为线段构建这样的图表是困难的，你应该求助于现成的解决方案，比如在 CGAL 中。
分而治之：
定义一个数据结构表示一对折线和它们之间的最小距离axis-aligned minimum bounding boxes (AAMBB):
pair = (poly_a, poly_b, d_ab))为
pair数据结构创建一个空队列，使用距离d_ab作为键。用初始多段线创建一个
pair数据结构并将其推入队列。我们将保留一个变量，其中包含目前找到的折线之间的最小距离 (
min_d)。设置为无限。重复：
从队列中弹出距离最小的元素
d_ab.如果
d_ab大于min_d我们就完成了。如果任何折线
poly_a或poly_b包含唯一的线段：- 使用蛮力找到 then 之间的最小距离并相应地更新
min_d。
- 使用蛮力找到 then 之间的最小距离并相应地更新
否则：
将折线
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²)。
更新: algorithm 在 Perl 中实现。