 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第五节 简单多边形的三角剖分 | |||
| SIMPLE
POLYGON TRIANGULATION 1.〔准备〕  ;2.〔剖分〕若n>3，则做2.1~2.2,否则转到步3: 2.1  ←点序列中Q0的下一个顶点; ←点序列中的下一个顶点;2.2 若Test(  ,,)为真,则做:输出△ ;
从点序列中删除顶点  ;n←n-1; 返回步2开头; 否则做 ←,返回步2.1;3.〔最后输出〕输出点序列中剩下三点为最后一个三角形,然后算法结束。 函数Test是对△ 进行检查，分两步实现,第一步检查,,是否是一个在的左转,若不然,是右转,则在多边形外部而可以回答假而结束。第二步可对原多边形中除去,,这三点的其它点，对每一点都考查它对三角形的包含性,若有一点被包含则就可以回答假而结束,只有其它点都在三角形外部时才能回答真而结束。
最小权三角剖分或最小三角剖分 如果一个三角剖分中选取的对角线的总长度最小。 任意的凸多边形最小三角剖分 |
|||
 |
|||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
