带洞平面三角分割结果的逆向算法

先标不重复点，按最近逐个插入。

只说原理。

不带洞的

1 2 4

2 3 4 两个三角形

结果

1 2 3 4

无重复 无洞

1 2 6

1 2 3 6

1 2 3 7 6

1 2 3 4 7 6

1 2 3 4 5 7 6

1 2 3 4 1 5 7 6

1 2 3 4 1 6 5 7 6

最终结果

1 2 3 4 1 6 5 7 6

按重复分割

1 2 3 4 1

6 5 7 6

可分割出一个洞

1 2 6

1 2 7 6

1 2 3 7 6

1 2 3 10 7 6

1 2 3 4 10 7 6

1 2 3 4 9 10 7 6

1 2 3 4 1 9 10 7 6

1 2 3 4 1 5 9 10 7 6

1 2 3 4 1 6 5 9 10 7 6

1 2 3 4 1 6 5 8 9 10 7 6

1 2 3 4 1 6 5 7 8 9 10 7 6

1 2 3 4 1 6 5 7 10 8 9 10 7 6

最终结果

1 2 3 4 1 6 5 7 10 8 9 10 7 6

按重复分割

1 2 3 4 1

6 5 7 10 8 9 10 7 6

有包含关系

10 8 9 10

剔除包含

6 5 7 7 6

剔除相邻重复点

6 5 7 6

结果

1 2 3 4

10 9 8

6 5 7

同理

1 2 3 4 1 6 5 7 9 8 12 13 11 12 8 10 9 7 6

分割 1 2 3 4 1

12 13 11 12

9 8 12 13 11 12 8 10 9 剔除前面

9 8 8 10 9

合并重复相邻点

9 8 10 9

下一个剔除包含 与相邻重复点

6 5 7 6

最终分割 1 2 3 4

12 13 11

9 8 10

6 5 7

像这种内部图形没有相交点 按两个图形分割

有交点，但无邻边，同样处理