我听很多人说，编程找到非凸多边形内的点比凸多边形难。我对此感到困惑。这是真的吗？如果是，为什么呢？
2个回答
11
所以您想要检查点P是否在多边形内部或外部。
如果该多边形是凸的，那么您可以迭代每个构成该多边形的线段，并检查P位于该线段的哪一侧。如果它沿逆时针方向在所有线段的右侧，则P在多边形内部。
如果该多边形是凹的，则此算法无法工作。适用于凹多边形的算法是从P开始沿任意方向向无限追踪，并计算穿过多边形的边的次数。如果穿越次数为奇数，则P在多边形内部。此算法有许多需要考虑的边缘情况，通常更加复杂，因此编写此算法需要更多的程序员努力。
就算法正确编写难度而言，确实更难些。
就计算复杂度而言，两种算法都具有Θ（N）渐近运行时间。在这个意义上，两个问题同样困难。
- Dietrich Epp
1
2如果凸多边形的顶点按排序顺序给出，则存在一种O(log n)时间算法。 - David Eisenstat
4
对于一个凸多边形，你可以选择任何一个点p在多边形内部(比如所有顶点的重心)，然后按照它们与p的夹角将顶点排序成一个圆形数组。然后，给定查询点x，可以计算从p到x的角度，并在数组中搜索找到两个相邻的顶点，使得x到这两个顶点间的角度介于它们之间。接着，计算从p到x的直线与这两个顶点连成的边的交点。如果从p到交点的距离大于或等于从p到x的距离，则x在多边形内部，否则x在多边形外部。这样就可以在O(log n)时间内确定一个点是否在凸多边形内部。另一方面，目前已知判断点是否在非凸多边形内部的最佳算法时间复杂度是O(n)。但是请注意，您可以根据多边形的“不凸性”程度制定混合算法。您可以通过添加额外的内部边缘将多边形分解为若干个凸多边形；假设您的多边形只有几个“拐角”，并且您可以将其分解为k个凸多边形，其中k很小。然后，您可以使用凸多边形的策略，在O(k log n)时间内确定一个点是否在多边形内部或外部。因此，一般来说，您拥有的“凸性”越多，就能越快地确定一个点是否在多边形内部。
- user2566092
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接