13.多边形的三角剖分 (Triangulation) ： Triangulation

目录

1.Existence

2.Ear-cutting

3.Two-Ear  Theorem

4.Well-Order

5. Ear Candiadte

6.Induction

7.Well-Order(Again)

8.Properties

1.Existence

只讨论简单多边形

外边界逆时针进行，内部hole顺时针进行描述。这样做能够保证无论是沿着外边界还是内边界行径，这个多边形内部总是在左手边

2.Ear-cutting

convex:在里面表现为吐

reflex:在里面表现为土

empty:表示里面没有包含多边形其它的点

dirty: 包含多边形其它的点

3.Two-Ear  Theorem

至少存在2只耳朵

4.Well-Order

等价划分

5. Ear Candiadte

如何寻找第一个顶点

6.Induction

如果存在点落在IKJ组成的三角形中，找到落在内部点中，举例IK最远的点

7.Well-Order(Again)

不论是否有洞，都可以进行三角拋分

8.Properties

三角剖分复杂度？

怎么确认是否有洞？

通过对偶图，如果不带洞，对偶图必然是一棵树；否则会存在环