我正在寻找将复杂多边形(自相交多边形)转换为简单凸多边形的方法。
<>之前------------------------------ -- -- -- -- -- --- -- -- -- -- -- -----------------------之前上面的图片应该是两个多边形(三角形)。
我正在研究boost库并寻找使用boost库的解决方案。
假设您的初始多边形是…xa,xb，....，xc,xd，....(其中xi是顶点)，并且边xa,xb和xc,xd相交。然后你有两个多边形:....xa xe xd…xb, xe…,xd。
现在，如果两个多边形相交，它们必须在两个地方相交(或偶数个地方)。如果两个多边形....xa,xb，…xc,xd，....xf,……xe…xg, xh,……相交于(xa,xb) (xe,xf)和(xc,xd) (xg,xh)你就得到了两组新的多边形，有两个新的顶点xi和xj(我会让你弄清楚这些多边形的确切性质)
然后有算法来计算相交线段对的列表。
把这三部分结合起来，你就得到了你的算法