1

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

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

上图应生成两个多边形（三角形）。

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

4

1 回答 1

0

让我们假设您的初始多边形是 ...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（我会让你弄清楚这些多边形的确切性质）。

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

结合这三部分，你就得到了你的算法。

于 2013-03-06T03:30:47.940 回答