通过添加对角线来分解简单多边形

Question

我面临的问题是通过在初始多边形中添加对角线（它们本身并不相交），将简单多边形（即没有孔的多边形）有效地分解为较小的简单多边形。 在其它方面，这里是函数的Java的签名，我想有效地实现（线性时间或的n * log（n））的：

public static List<SimplePolygon> addDiagonals(SimplePolygon polygon, List<Edge> diagonals); 

其中多边形是由表示初期多边形双连接边列表和对角线是边的列表，其中边只由开始和结束节点组成。该函数必须返回多边形中添加对角线所产生的子多边形列表。这里是一个图像显示我想要的东西：

起始多边形是在左上角，和另外5人是通过添加对角线产生的子多边形。 我很难找到如何有效地实现这种分解，因为它很容易重复节点事件对角线，但如果大量的对角线是从同一个节点出去，我总是要检查与节点相邻的顶点是否重复如果是这种情况，那么我将对角线添加到副本（假设原始属于另一个子多边形），那么我必须再次检查这个重复节点是否也没有重复（如果已经有一个对角线与此节点相邻）等。 您有关于如何有效地进行这种分解的想法吗？对不起，如果解释不够清楚。 谢谢！

Answer 1

如果对角线被索引，则可以使用矢量辅助程序，该矢量辅助程序计算为每个对角线生成的sp（子多边形）的数量。每个对角线必须产生2个多边形...

1. 大小为启动这个辅助（每个对角线的SP）=对角线的数量和零填充。
2. 选取下一个对角线：如果sp == 2的数目，移动到下一个对角线。如果不是：
3. 增加sp（在助手向量中）的数量，并生成第一个多边形，它以对角线开始，并访问相邻边和对角线，直到它再次到达第一个对角线，如果在此过程中sp生成器访问另一个对角线，增加为该对角线生成的sp的数量。
4. 如果第一个对角线的sp数为1，则再次运行第3步。
5. 如果还有未访问的对角线，回到步骤2

这样你保证生成每个子多边形只有一次，不重复。 最好。