algorithm - 两个二维凹多边形之间最近的一对特征

Question

问题是找到两个 2d 凹多边形之间最接近的特征。特征可以是顶点、边。所以结果可以是特征的任意组合。有没有复杂度优于 O(m*n) 的简单解决方案？其中 m, n - 分别是多边形的边数。多边形共面。

Answer 1

O(n.log(m)) 中的算法似乎存在，请参阅this paper , 和 this question .

您可以尝试我的优化: (未测试)

如果你的多边形大部分时间相距足够远，你可以构建两个凸包并回退到最简单的问题上，即找到两个凸多边形之间的 Hausdorff 距离(O(n+m) 中的解决方案)。如果距离为 0，您必须退回到 O(m.log(n)) 的情况，但如果您大部分时间都在具有正距离的“凸包”情况。

后脚本。我刚刚意识到，为了使假设起作用，您还需要检查凸包中最接近的特征是否属于原始凹多边形。如果不是，很容易找到一个反例(想象一个字母 C 形状的多边形，附近有另一个圆:CO)。

那么更新后的假设是:两个凹多边形之间的豪斯多夫距离 d 是它们凸包之间的豪斯多夫距离，如果 d > 0，并且两个最接近的特征都是原始多边形的一部分。

这个证明作为练习留给读者。