c++ - 实现绕组数算法来计算内部和外部区域(OpenGL，c++)

Question

我需要实现缠绕数算法来确定(不一定是简单的)多边形的内部和外部区域。

我的想法是将多边形分解成简单的区域(这样任何区域都不能分解成2个区域)，然后在每个区域中对1个点使用绕数算法，从而确定整个区域的性质.但是，我无法想出一种算法来计算所述区域，然后我需要在每个区域内获取一个点(从那里开始，实现绕组数算法非常简单)。

是否有一种简单有效的算法可以将复杂的多边形分解为这样的区域？

Answer 1

在关于 points in polygons 的维基百科文章的引用资料中你可以找到一个非常有用的article关于绕组数算法的有效实现。这篇文章很清楚，写得很好!它包括几个示例、伪代码和(对您来说幸运的是)算法在 C++ 中的完整实现。要理解该算法，您可以跳过绕数的数学背景(文章简要解释了如何将它们解释为单位球体的同伦类)，只需阅读如何以及为什么可以更轻松地表达绕数案例。

顺便说一句，缠绕数算法在非简单多边形上工作得很好。为什么要先将它们分成简单的区域？上面链接的文章还解释了如何使用交叉数来确定一个点是否位于简单(!)多边形内。所以我希望这能给你足够的信息来决定你是否真的想先分割你的多边形。