如何将自相交多边形划分为简单的多边形？

Question

我有一个由点列表定义的多边形。该多边形可以与多个交点交叉。我用蛮力找到了所有的点。 （尚未实施Bentley-Ottmann扫描方法）。例如， http://i.imgur.com/3F3LbfB.png 我有4个顶点，边1-2与边4-0（点A）相交，边2-3与边4-0（点B）相交。我简单的多边形0-1-A-0和休息，这休息也分为两个多边形：A-B-2-A 和B-3-4-B 一般algortithm是如何？

Answer 1

一个简单的方法是通过细分交叉点处的多边形线段（Bentley - Ottmann自然延伸以同时执行此操作）来计算planar straight-line graph (PSLG)，然后枚举其有限面。后者可以通过准备组合嵌入然后traversing it as described in this previous answer of mine来完成。