algorithm - 如何使用 boost 将复杂的多边形划分为简单的多边形？

Question

我正在寻找将复杂的多边形(自相交多边形)转换为简单的凸多边形。

----------------------------- -                        -                  -                    -     -                -       -            -         -        -           -    -             -           -    -         -        -       -            -     -               -    -                 -   -                   -   ----------------------

上图应该是两个多边形(三角形)

我正在研究 boost 库并寻找使用 boost 库的解决方案。

Answer 1

让我们假设您的初始多边形是 ...xa,xb,....,xc,xd,....(其中 xi 是顶点)，边 xa,xb 和 xc,xd 相交。然后你有两个多边形:....xa,xe,xd,...和 ​​xe,xb,...,xd。

现在，如果两个多边形相交，它们必须在两个地方(或偶数个地方)相交。如果两个多边形....xa,xb,...xc,xd,....和...xe,xf,....xg,xh,...相交于 (xa,xb) (xe ,xf) 和 (xc,xd) (xg,xh) 你有两组新的多边形，它们有两个新的顶点 xi 和 xj(我会让你弄清楚这些多边形的确切性质)。

然后有算法计算出相交线段对的列表。

将这三个部分结合起来，您就得到了您的算法。