两条折线之间的距离 [英] Distance between two polylines

问题描述

我想计算两条折线之间的距离 d :

I want to calculate the distance d between two polylines:

很明显，我可以检查所有线段对的距离并选择最小距离，但是这样，algorithmn的运行时间为 O(n ² ).有没有更好的方法?

Obviously I could check the distance for all pairs of line-segments and choose the smallest distance, but this ways the algorithmn would have a runtime of O(n²). Is there any better approach?

推荐答案

划分并征服:

• 定义表示一对折线及其与轴对齐的最小边界框(AAMBB):pair = (poly_a, poly_b, d_ab))

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

Create an empty queue for pair data estructures, using the distance d_ab as the key.

使用初始折线创建pair数据结构并将其推入队列.

Create a pair data estructure with the initial polylines and push it into the queue.

我们将保留一个变量，该变量具有到目前为止找到的折线之间的最小距离(min_d).将其设置为无限.

We will keep a variable with the minimum distance between the polylines found so far (min_d). Set it to infinite.

重复:

• 以最小距离d_ab从队列中弹出元素.

如果d_ab大于min_d，我们完成了.

If d_ab is greater than min_d we are done.

如果折线poly_a或poly_b中的任何一条仅包含一个线段:

If any of the polylines poly_a or poly_b contains an only segment:

• 使用蛮力找到之间的最小距离，并相应地更新min_d.

否则:

• 将折线poly_a和poly_b都分成两半，例如:

• Divide both polylines poly_a and poly_b in half, for instance:

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

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

制作两组的叉积，创建4个新的pair数据结构，然后将其推入队列Q.

Make the cross product of both sets, create 4 new pair data structures and push then into the queue Q.

一般情况下，复杂度为O(N * log N)，最坏情况可能为O(N²).

On the average case, complexity is O(N * log N), worst case may be O(N²).

更新:

Update: The algorithm implemented in Perl.

这篇关于两条折线之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！