昨天说到判定多边形的对角线。到此为止,我们为解决多边形的三角形划分问题,做了足够的准备工作。
首先,不能按照多边形的三角形划分的定义来做。
对一个有n个顶点的多边形,可能的对角线有O(n^2)条。
判定一条线段是否对角线的复杂度为O(n),这已经是O(n^3)的复杂度。
n个顶点的多边形的三角形划分需n-3条对角线,所以总体的复杂度是O(n^4)。
显然这个方法是不实用的。
方法二是用“切耳朵”的方法。
一个多边形的三角形划分,必然有至少2个耳朵。
(证明是通过多边形的三角形划分的偶图,这个偶图是一棵树,它有至少两个叶节点。)
一个n个顶点的多边形,可能构成耳朵的对角线仅有n条:(v[i],v[i+2]),其中i=0,1,2,...,n。
每次切掉一个耳朵之后,被切掉的耳朵也无需再递归划分——它是一个三角形,已经无需再分。
这个算法的复杂度是O(n^3),还是不实用。
其实可以进一步简化。上面的“切耳朵”方法中,注意到
如果耳朵“尖”是vi,那么它被切掉之后,
只有和它相邻的v[i-1]和v[i+1]会受影响。
此外的所有顶点是否构成“耳朵”,不会因为vi被切掉而发生变化。
因此可以在算法一开始用O(n^2)的时间算出所有顶点是不是耳朵,
并且将其记录下来。之后每次切掉一个耳朵,不用全部重新计算,
而是只要重新确定与被切掉的耳朵尖相邻的两个顶点的状态即可。
这样算法的总体复杂度就下降到了O(n^2)。
代码
首先对所有顶点进行初始化,记录其是否“耳朵尖”。
void EarInit( void ) {
tVertex v0, v1, v2; /* 连续的三个顶点 */
/* Initialize v1->ear for all vertices. */
v1 = vertices;
do {
v2 = v1->next;
v0 = v1->prev;
v1->ear = Diagonal( v0, v2 );
v1 = v1->next;
} while ( v1 != vertices );
}
三角形划分。注意这里去掉了错误处理。
void Triangulate( void ) {
tVertex v0, v1, v2, v3, v4; /* 连续的5个顶点 */
int n = nvertices; /* 顶点数目,随着算法进行,最后减少到3 */
EarInit();
while ( n > 3 ) { /* 每次循环切掉一个耳朵 */
v2 = vertices;
do {
if (v2->ear) {
v3 = v2->next; v4 = v3->next;
v1 = v2->prev; v0 = v1->prev;
PrintDiagonal( v1, v3 );
/* v1和v3是否耳朵尖,需要重新确定 */
v1->ear = Diagonal( v0, v3 );
v3->ear = Diagonal( v1, v4 );
/* 切掉v2 */
v1->next = v3; v3->prev = v1;
/* v2可能是链表头指针指向的节点。修改链表头指针,保证头指针不悬空。 */
vertices = v3;
n--;
break;
} /* end if */
v2 = v2->next;
} while ( v2 != vertices );
} /* end while */
}
阅读(582) | 评论(0) | 转发(0) |