 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第五节 简单多边形的三角剖分 | |||
现在一般地说明所要使用的剖分方法。引人记号 ,表示一个子多边形 的最小三角剖分问题。子多边形由 开始的S个顶点按顺时针向排列围成。每个子问题 中都仅涉及原多边形一条对角线。为了解,必须考虑如下三种情况:
1. 选择顶点  ,这时构成一个三角形 ,得到一个子问题 2. 选择顶点  ,这时构成一个三角形 ,得到一个子问题 。3. 对2≤k≤S-3,选择Vi+k这时构成一个三角形  ,得到两个子问题 和 。
实际上可以把三种情况概括为一句话,即对1≤k≤S-2,把 分解成两个子问题和。容易验证k=1和k=S-2时,各自有一个子问题不成其为问题,但这不影响一般的讨论。
|
|||
 |
|||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
