如何在O(n)以下的时间内检查凸多边形是否相交？

Question

我有两个凸多边形（2D），我想检查这两个多边形是否相交。实际上，我会多次移动和旋转这些多边形，因此我可以进行一些预计算，以便快速解决此问题。

我正在寻找一个低复杂度的算法。

我知道可以在O(log(n))时间内检查一个点是否在凸多边形中，我想知道是否可以在另一个多边形的点周围进行某种二分法来获得结果。是否有任何关于这个主题的现有算法/论文？

- Renaud

---

可以使用O(log(n))的时间复杂度实现，参考链接为：https://www.cs.princeton.edu/~chazelle/pubs/IntersectConvexObjects2-3Dim.pdf。 - Niklas B.

典型的n值是多少？第一种方法是通过紧密边界圆来确定。轴对齐边界框（然后旋转）是另一种选择。 - user1196549

n 可能是大约 500 点左右。是的，我会先进行一些测试来排除快速的情况。 - Renaud

Answer 1

Gilbert-Johnson-Keerthi(GJK)算法正是您需要的。它非常容易实现，并且在O(log(n))内检测碰撞。

- Ivaylo Strandjev

---

@YvesDaoust 我找不到关于这个复杂度的参考资料，但这是我几年前在大学学习过的界限。 - Ivaylo Strandjev

原始论文指出：“在R3中，对广泛的多面体进行大量数值实验表明，计算成本与指定两个多面体的总顶点数近似呈线性关系。” - user1196549

我一直在使用爬山算法，但这不是特定于2D的，同样的方法也可以用于3D。我认为有两个选择 - 我们研究了一个优化版本，它具有更好的复杂度，或者我错了，复杂度是线性的。我正在尝试寻找更多信息。 - Ivaylo Strandjev

@IvayloStrandjev：您能保证使用山峰爬升算法的时间复杂度为O(Log(n))吗？ 我对此表示怀疑。 - user1196549

你可以通过爬山算法在O(log(n))的时间复杂度内找到极值，就像你使用三分搜索一样。 - Ivaylo Strandjev