两条折线之间的距离

Question

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

显然,我可以检查所有线段对的距离并选择最小距离,但这样算法运算符的运行时间为O(n ²).有没有更好的方法？

Answer 1

分而治之：

\n\n

\n

• 定义一个数据结构，表示一对折线以及它们的轴对齐最小边界框之间的最小距离 (AAMBBpair = (poly_a, poly_b, d_ab) ) :)

\n

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

\n

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

\n

• 我们将保留一个变量，其中包含迄今为止找到的折线之间的最小距离 ( min_d)。将其设置为无限。

\n

• 重复：

  \n\n
  \n

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

  \n

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

  \n

  • 如果任何折线poly_a或poly_b包含唯一的线段：

    \n\n
    \n
    • 使用蛮力找到那时之间的最小距离并进行min_d相应更新。
    \n
  \n

  • 否则：

    \n\n
    \n

    • 将两条折线poly_a和poly_b一分为二，例如：

      \n\n

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

      \n\n

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

    \n

    • 对两组数据进行叉积，创建 4 个新的pair数据结构，然后将其推入队列 Q 中。

    \n
  \n
\n

\n\n

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

\n\n

更新：用 Perl 实现的算法。

\n