geometry - 自相交/复杂多边形中的点

Question

我已阅读 How can I determine whether a 2D Point is within a Polygon?但我不确定该解决方案是否适用于被内部段从中间划分的多边形。想想一个平方的数字 8 或者只是两个相互堆叠的正方形。任何一个正方形内的点肯定会在多边形“内部”，但交叉计数会根据您前进的方向(以及您是否穿过该内部线段)而有所不同。



我想处理这个问题的一种方法是将多边形视为两个单独的多边形......(在这种情况下，我需要一种算法将复杂的多边形划分为一组更简单的多边形？)

或者是否对光线转换算法或另一种多边形点算法进行了改进，以处理我所描述的情况？

Answer 1

所描述的算法会很好地工作，因为如果你仔细观察它，你会发现它只是交叉的数量。如果我们从“8”的任何一个“子多边形”开始，在最坏的情况下，我们将穿过边缘 3 次，通常是一次。它确实在里面。否则就在外面。

但是，人们可能会假设存在一种特殊情况。如果光线完全通过一个交叉点。但请注意，在这种情况下，您还将获得 2 个交叉点:)。