 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第五节 简单多边形的三角剖分 | |||
 记子问题 的解
的公式如下: 
,1≤k≤S-2如果  是对角线,则D()是它的长度;若是原多边形的边,则D()=0;如果S<4,则=0。这因为是最小三角剖分中引人对角线的总长度,原多边形的边不是对角线,当S<4时也不必引入对角线。
对前面说明的凸七边形,要计算的各 ,有
0≤i≤6, 4≤S≤6。可用填表的方式逐个计算。 |
|||
 |
|||
 的计算由公式应该计算下面三个值:
代入数值进行计算，注意到 
在表中己求出, 为0于是算出上述三式的值分别为38.09,38.52,43.97。所以知道 =38.09,可以把这个值填入表中,并知道按第一式子问题 分解出一个子问题 ,另一个 不成为子问题。
|
|||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
