我需要实现缠绕数算法来确定(不一定是简单的)多边形的内部和外部区域。
我想到的是将多边形分解为简单的区域(这样就不会将任何区域分解为2个区域)，然后对每个区域中的1个点使用缠绕数算法，从而确定整个区域的性质。然而，我很难想出一个算法来计算所述区域，然后我需要在每个区域内获得一个点(从那里开始，实现缠绕数算法非常简单)。
有没有一种简单有效的算法可以将复杂的多边形分割成这样的区域？
在维基百科关于多边形中的点的文章的参考文献中，您可以找到一篇关于缠绕数算法的有效实现的非常有用的文章。这篇文章写得很清楚！它包括几个例子、伪代码和(幸运的是)该算法在c++中的完整实现。要理解该算法，你可以跳过缠绕数的数学背景(文章简要解释了如何将其解释为单位球面的同伦类)，只需阅读缠绕数在这种情况下如何以及为什么可以更容易地表达。
顺便说一句，缠绕数算法在非简单多边形上运行得非常好。为什么要先将它们划分为简单的区域？上面链接的文章还解释了如何使用交叉号来确定点是否位于简单(！)多边形内。所以我希望这能给你足够的信息来决定你是否真的想先分割多边形。