为什么在非凸多边形中找到比凸多边形更硬的点？

Question

我听到很多人说，以编程方式在非凸多边形中找到一个点比在凸多边形中找到一个点要困难。我无法绕过这个包裹。这是真的？如果是这样，为什么？

Answer 1

所以你想检查点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个小的k个凸多边形。然后，您可以使用凸多边形策略来确定O（k log n）时间内的点是内部还是外部。因此，一般来说，您拥有的“更凸面”，您可以更快地确定点是否在多边形内。