距离之间的两个

我想计算的距离d折线两者之间：距离之间的两个

很显然，我可以检查所有对线段的距离，选择最小的距离，但是这算法n的运行方式将具有O（n ）。有没有更好的方法？

2017-08-24 user2033412

这看起来像[quadtrees]（https://en.wikipedia.org/wiki/Quadtree）可能会有所帮助 - 但是除了我的头顶之外，我没有比这更有用的了。 – hnefatl

不知道答案，但我猜测一些基于四叉树的算法必须是可能的，其中只计算附近元素之间的点线距离。 – jdehesa

基于边界框的方法可能会有所帮助。计算部分多段线的边界框（例如，A的点1 ... 4,4 ... 7和B的8 ... 10,10 ... 12）。对于每一对盒子，你可以计算最小和最大距离，并丢弃无法与最佳对成对竞争的对，递归地提炼盒子，直到它们都是2点（1行）盒子，你可以精确地计算。似乎是O（N logN）。 –

分而治之：

定义表示一对折线的和最低限度的距离他们的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。

来源

2017-08-29 09:19:07 salva

这种问题的“标准”方式是构造几何实体的Voronoi图。这可以在时间O（N日志N）中完成。

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

来源

2017-08-27 15:36:58

voronoi克作为一个查找表可用于查找从任何地方最近的点，如果这些点不是将要改变，你必须从许多其他点查找最近的一个，它可能是值得的产生voronoi加快查找。但我没有看到它如何帮助计算两条多段线之间的距离？ – gordy

距离之间的两个

回答

相关问题