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

Question

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

Answer 1

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

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

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

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

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