algorithm - 为什么在非凸多边形中找到点比在凸多边形中更难？

Question

我听说很多人说以编程方式在非凸多边形中找到一个点比在凸多边形中找到一个点更难。我很难解决这个问题。这是真的？如果是这样，为什么？

Answer 1

所以你想检查点 P 是在多边形内部还是外部。

如果多边形是凸的，那么您可以遍历构成多边形的每个线段，并检查该线 P 位于哪一侧。如果 P 位于每条线段的右侧，则 P 位于多边形的内侧，顺时针方向。

如果多边形是凹的，则此算法不起作用。一种适用于凹多边形的算法是从 P 沿任意方向追踪到无穷大，并计算多边形边缘被交叉的次数。当且仅当交叉数为奇数时，P 在多边形内。这个算法有很多边缘情况需要考虑，而且通常更复杂，所以编写算法需要更多的程序员努力。

从某种意义上说，算法更难正确编写，是的，更难。

在计算复杂度的意义上，两种算法都有 Θ(N) 的渐近运行时间。从这个意义上说，这两个问题同样困难。

Answer 2

对于凸多边形，您可以选择多边形内的任意点p（例如所有顶点的质心），然后根据顶点与p 所成的角度将顶点排序为圆形数组。然后，给定一个查询点 x，您可以计算从 p 到 x 的角度，并在数组中搜索并找到数组中与 x 的角度在与两个顶点的角度之间的两个相邻顶点。然后计算从 p 到 x 的线之间的交点，以及两个顶点之间的边。如果 p 到交点的距离大于或等于 p 到 x 的距离，则 x 在多边形内，否则 x 在多边形外。这给了 O(log n) 时间来确定一个点是在凸多边形内部还是外部。另一方面，确定一个点是在非凸多边形内部还是外部的最著名的算法是 O(n) 时间。但是请注意，您可以根据多边形中有多少“非凸性”来制作混合算法。您始终可以通过添加额外的内部边将多边形分解为凸多边形的并集；假设你的多边形里面只有几个“转弯”，你可以分解成 k 个小的凸多边形。然后您可以使用凸多边形的策略来确定一个点在 O(k log n) 时间内是在内部还是外部。因此，一般而言，您拥有的“凸度越大”，您确定一个点是否在多边形内的速度就越快。您始终可以通过添加额外的内部边将多边形分解为凸多边形的并集；假设你的多边形里面只有几个“转弯”，你可以分解成 k 个小的凸多边形。然后您可以使用凸多边形的策略来确定一个点在 O(k log n) 时间内是在内部还是外部。因此，一般而言，您拥有的“凸度越大”，您确定一个点是否在多边形内的速度就越快。您始终可以通过添加额外的内部边将多边形分解为凸多边形的并集；假设你的多边形里面只有几个“转弯”，你可以分解成 k 个小的凸多边形。然后您可以使用凸多边形的策略来确定一个点在 O(k log n) 时间内是在内部还是外部。因此，一般而言，您拥有的“凸度越大”，您确定一个点是否在多边形内的速度就越快。