计算几何（三）

计算几何（三） (2012-01-26 20:12)转载

标签:  计算几何  三角形划分  耳朵  分类： 读书笔记

昨天说到判定多边形的对角线。到此为止，我们为解决多边形的三角形划分问题，做了足够的准备工作。

首先，不能按照多边形的三角形划分的定义来做。
对一个有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 */
}