_delaunay_tree.c

数据类型和算法库LEDA 数据类型和算法库LEDA

					&&	(l->item->bpere->s[j] != l->item->s[W] ) ) break;
			l->item->bpere->voisin[j] = l->item;
		} else {
		/* il faut trouver un nouveau pere */
			u = l->item->bpere;
			for( i=U; i<=W; i++) if (u->s[i] == l->item->s[V]) break;
			for( j=U; j<=W; j++) if (u->s[j] == l->item->s[W]) break;
			i = U+V+W -i -j;
			u= l->item->pere = u->special[i];
			for( i=U; i<=W; i++) if (u->s[i] == l->item->s[V]) break;
			for( j=U; j<=W; j++) if (u->s[j] == l->item->s[W]) break;
			i = U+V+W -i -j;
			u->fils[i] = l->item;
		}
	/* traitement des noeuds detruits */
	if ( ! n->detruit1 ) return;
	x1 =  ( n->detruit1->s[V] == p ) ? n->detruit1->s[W] : n->detruit1->s[V];
	x2 =  ( n->detruit2->s[V] == p ) ? n->detruit2->s[W] : n->detruit2->s[V];
	s1 = loc_Star(x1);
	s2 = loc_Star(x2)->previous ;
	u = s1->triangle;
	/* Cas 1 (triangle x x1 x2 a creer) u n'est pas en conflit avec x */
	if ( ! conflit(u, n->x) ) {
			/* u est le beau pere de x x1 x2 a cree */
			for( i=U; i<=W; i++) if (u->s[i] == x1) break;
			for( j=U; j<=W; j++) if (u->s[j] == x2) break;
			k = U+V+W -i -j;
			u = u->voisin[k] ;
			/* u est le pere */
			for( i=U; i<=W; i++) if (u->s[i] == x1) break;
			for( j=U; j<=W; j++) if (u->s[j] == x2) break;
			i = U+V+W -i -j;
			n->x->cree =ww = creenoeud(u ,i,n->x);
		/* ww est le fils de son pere */
			u->voisin[i] = ww->bpere;		/* voisin a la mort */
		/* voisinage beau-fils beau-pere */
			ww->bpere->voisin[k] = ww;
		/* voisinage avec les "freres" du nouveau */
			i = ( ww->s[V] == x1 ) ? V : W ;
			u = n->detruit2->creation[(n->detruit2->s[V]==p)?V:W] ;
			ww->voisin[i] = ww->creation[i] = u;
			for( j=U; j<=W; j++) if ( u->creation[j] == n->detruit2 ) break;
			u->creation[j] = u->special[j] = ww ;
			if ( u->voisin[j]->detruire == flag ) u->voisin[j] = ww ;
			if ( u->voisin[j]->visite == flag ) u->voisin[j] = ww ;
			u = n->detruit1->creation[(n->detruit1->s[V]==p)?V:W] ;
			ww->voisin[V+W-i] = ww->creation[V+W-i] = u;
			for( j=U; j<=W; j++) if ( u->creation[j] == n->detruit1 ) break;
			u->creation[j] = u->special[j] = ww ;
			if ( u->voisin[j]->detruire == flag ) u->voisin[j] = ww ;
			if ( u->voisin[j]->visite == flag ) u->voisin[j] = ww ;
		/* mise a jour de Star */
			poubelle_noeud(n->detruit1);
			poubelle_noeud(n->detruit2);
			split_Star(s1,s2); s2=s1->next;
			s1->triangle = ww;
			s2->triangle = ww;
			for( i=U; i<=W; i++) if (ww->s[i] == x1)    s1->p = s2->arete = i;
						else	 if (ww->s[i] == n->x ) s1->n = s2->p = i;
						else						   s1->arete = s2->n = i;
			ww->star[s1->arete] = s1;
			ww->star[s2->arete] = s2;
	return;
	}
	/* Cas 2  */
	v = u; w1=NULL;
	w = n->detruit1->creation[(n->detruit1->s[V]==p)?V:W] ;
	a = s1->p ;
	c = s1->n ;
	b = s1->arete ;
	do {
	/* on tourne dans le sens inverse */
		while ( conflit( v->voisin[c], n->x ) ) {
			a1 = a; b1 = b; c1 = c;
			for (j=U; j<=W; j++) if ( v->voisin[c1]->s[j] == v->s[a1]) a = j;
						else	 if ( v->voisin[c1]->s[j] == v->s[b1]) c = j;
						else										   b = j;
			v = v->voisin[c1];
			v->meurtrier = n->x;
		}
			v->meurtrier = n->x;
			ww = creenoeud(v,c,n->x);
		/* voisinage beau-fils beau-pere */
			for (j=U; j<=W; j++)
					if (	( ww->bpere->s[j] != ww->s[V] )
						&&	( ww->bpere->s[j] != ww->s[W] ) ) break;
			if ( ww->bpere->visite == flag ){ /* le beau-pere est dans A */
				ww->bpere->voisin[j] = ww;
			} else {
				ww->bpere->special[j] = ww;
				if ( ww->bpere->voisin[j]->detruire == flag )
												ww->bpere->voisin[j] = ww ;
				if ( ww->bpere->voisin[j]->visite == flag )
												ww->bpere->voisin[j] = ww ;
			}
		/* voisinage nouvelle arete */
			for (j=U;j<=W;j++) if((ww->s[j]!=n->x)&&(ww->s[j]!=v->s[a]))break;
			ww->voisin[j] = ww->creation[j] = w ;
			if ( !w1 ) {
			  for (j=U;j<=W;j++) if((w->s[j]!=n->x)&&(w->s[j]!=v->s[a]))break;
			  w1 = w->special[j] = w->creation[j] = ww ;
			  if (w->voisin[j]->visite == flag ) w->voisin[j] = ww ;
			  if (w->voisin[j]->detruire == flag ) w->voisin[j] = ww ;
			} else {
			  for (j=U;j<=W;j++) if((w->s[j]!=n->x)&&(w->s[j]!=v->s[a]))break;
			  w->voisin[j] = w->creation[j] = ww ;
			}
			w = ww;
		/* mise a jour de Star */
			if ( ww->bpere->visite != flag ){/* le beau-pere n'est pas dans A */
				v->star[c]->triangle = ww;
				ww->star[U] = v->star[c];
				ww->star[U]->arete = U;
				ww->star[U]->n = (v->s[a] == w->s[V] ) ? V : W ;
				ww->star[U]->p = V+W-ww->star[U]->n ;
			}
		j = a ; a = b ; b = c ; c = j ;
	} while ( v->s[a] != x2) ; 
		/* voisinage autour de x x2 */
			n->x->cree = w2 = w;
			ww = n->detruit2->creation[(n->detruit2->s[V]==p)?V:W] ;
			for (j=U; j<=W; j++) if((ww->s[j]!=n->x)&&(ww->s[j]!=v->s[a]))break;
			if (ww->voisin[j]->visite == flag ) ww->voisin[j] = w ;
			if (ww->voisin[j]->detruire == flag ) ww->voisin[j] = w ;
			ww->creation[j] = ww->special[j] = w ;
			for (j=U; j<=W; j++) if((w->s[j]!=n->x)&&(w->s[j]!=v->s[a]))break;
			w->voisin[j] = w->creation[j] = ww ;
	do {
	/* on tourne toujours dans le sens inverse */
		while ( conflit( v->voisin[c], n->x ) ) {
			a1 = a; b1 = b; c1 = c;
			for (j=U; j<=W; j++) if ( v->voisin[c1]->s[j] == v->s[a1]) a = j;
						else	 if ( v->voisin[c1]->s[j] == v->s[b1]) c = j;
						else										   b = j;
			v = v->voisin[c1];
			v->meurtrier = n->x;
		}
			v->meurtrier = n->x;
		j = a ; a = b ; b = c ; c = j ;
	} while ( v->s[a] != x1) ; 
		/* mise a jour de Star */
			split_Star(s1,s2); s2=s1->next;
			s1->triangle = w1;
			s2->triangle = w2;
			poubelle_noeud(n->detruit1);
			poubelle_noeud(n->detruit2);
			for( i=U; i<=W; i++) if (w1->s[i] == x1)    s1->p = i;
						else	 if (w1->s[i] == n->x ) s1->n = i;
						else						    s1->arete = i;
			w1->star[s1->arete] = s1;
			for( i=U; i<=W; i++) if (w2->s[i] == x2)    s2->n = i;
						else	 if (w2->s[i] == n->x ) s2->p = i;
						else						    s2->arete = i;
			w2->star[s2->arete] = s2;
}

void delaunay_tree::parcours( reinserer n, DT_item p)
{
	if ( ! n ) return;
	parcours(n->finf,p);
	reinsertion(n,p);
	parcours(n->fsup,p);
}


void delaunay_tree::trace_items(noeud n, delaunay_f2* trace_item)
/* exploration recursive pour le trace des points */
{
  noeud* stack = new noeud[counter+10];
  int top = 0;
  stack[0] = n;
  n->stacked = flag;

  while (top >= 0)
  { n = stack[top--];   //pop
	n->visite = flag;
	for (int i=U; i<=W; i++)
	  if ( n->s[i] && n->s[i]->visite != flag )
            { n->s[i]->visite = flag ;
              trace_item(n->s[i]->x, n->s[i]->y);
             }

	for (i=W; i>=U; i--)
        { noeud v = n->voisin[i];
	  if ( v->stacked != flag )
           { stack[++top] = v;          //push
             v->stacked = flag;
            }
         }

   } // while stack not empty

 delete stack;

}

void delaunay_tree::list_items(noeud n, list<DT_item>& L)
/* exploration recursive pour le trace des points */
{
  noeud* stack = new noeud[counter+10];
  int top = 0;
  stack[0] = n;
  n->stacked = flag;

  while (top >= 0)
  { n = stack[top--];   //pop
	n->visite = flag;
	for (int i=U; i<=W; i++)
	  if ( n->s[i] && n->s[i]->visite != flag )
            { n->s[i]->visite = flag ;
              L.append(n->s[i]);
             }

	for (i=W; i>=U; i--)
        { noeud v = n->voisin[i];
	  if ( v->stacked != flag )
           { stack[++top] = v;          //push
             v->stacked = flag;
            }
         }

   } // while stack not empty

 delete stack;

}

void delaunay_tree::clear_items(noeud n)
{
  noeud* stack = new noeud[counter+10];
  int top = 0;
  stack[0] = n;
  n->stacked = flag;

  while (top >= 0)
  { n = stack[top--];   //pop
	n->visite = flag;
	for (int i=U; i<=W; i++)
	  if ( n->s[i] && n->s[i]->visite != flag )
            { n->s[i]->visite = flag ;
              clear_inf(n->s[i]->i);
             }

	for (i=W; i>=U; i--)
        { noeud v = n->voisin[i];
	  if ( v->stacked != flag )
           { stack[++top] = v;          //push
             v->stacked = flag;
            }
         }

   } // while stack not empty

 delete stack;
}


void delaunay_tree::del_noeud( noeud n, delaunay_f4* trace_segment,int both)
/* exploration recursive de delaunay_tree */
{
  noeud* stack = new noeud[counter+10];
  int top = 0;
  stack[0] = n;
  n->stacked = flag;

  int i;

  while (top >= 0)
  { n = stack[top--];   //pop

	n->visite = flag;

	for (i=U; i<=W; i++)
          if ( both || n->voisin[i]->visite != flag ) 
           { int j = (i==U) ? V : U ; 
             int k = U + V + W -i -j ;
	     if (( n->type == Fini ) || ((i == W) && (n->type==Infini1) ) )
                trace_segment(n->s[j]->x,n->s[j]->y, n->s[k]->x, n->s[k]->y);
	    }

	for (i=W; i>=U; i--)
        { noeud v = n->voisin[i];
	  if ( v->stacked != flag )
           { stack[++top] = v;          //push
             v->stacked = flag;
            }
         }

   } // while stack not empty

 delete stack;

 }


void delaunay_tree::vor( noeud n, delaunay_f6* trace_segment, delaunay_F6* pt_infi, int both)
{

  int i,j;
  coord x,y,mx,my;
  int order[3];

  int top = 0;
  noeud* stack = new noeud[counter+10];
  stack[0] = n;
  n->stacked = flag;

  while (top >= 0)
  { 
    n = stack[top--];   //pop

    n->visite = flag;

        if (n->direct)
         { order[0] = 0;
           order[1] = 1;
           order[2] = 2;
          }
        else 
         { order[0] = 2;
           order[1] = 1;
           order[2] = 0;
          }

	for (j=0; j<3; j++)
        { 
          int i = order[j];

               if (both ||  n->voisin[i]->visite != flag )
		{   int k;
                    if (n->direct)
                       k = (i==2) ? 0 : i+1; 
                    else 
                       k = (i==0) ? 2 : i-1; 

		    coord sx0 = n->s[k]->x;
                    coord sy0 = n->s[k]->y;

			switch (n->type){
			case Fini :
			if (! n->degenere ) {
				switch ( n->voisin[i]->type ){
				case Fini : if ( ! n->voisin[i]->degenere ){
trace_segment(n->cx,n->cy, n->voisin[i]->cx, n->voisin[i]->cy,sx0,sy0); 
                                            break;
				}
				case Infini1  : 
				  pt_infi(n->cx,n->cy, n->voisin[i]->cx, n->voisin[i]->cy,&x,&y);
                                  trace_segment(n->cx, n->cy,x,y,sx0,sy0);
				  break ;
				}
				break;
			}
			case Infini1  :
				if ( n->degenere &&  n->voisin[i]->degenere ) break;
				switch ( n->voisin[i]->type ){
				case Fini :
				if ( ! n->voisin[i]->degenere ) 
                                { pt_infi(n->voisin[i]->cx, 
                                          n->voisin[i]->cy, 
                                          n->cx,n->cy,&x,&y);
                                  trace_segment(x,y,
                                                n->voisin[i]->cx, 
                                                n->voisin[i]->cy,
                                                sx0,sy0);
				  break ;
				 }
				case Infini1  :
				  if (i == W)
                                  { mx = ( n->s[U]->x + n->s[V]->x )/2 ;
				    my = ( n->s[U]->y + n->s[V]->y )/2 ;
				    pt_infi(mx,my, n->cx,n->cy,&x,&y);
				    pt_infi(mx,my, n->voisin[i]->cx, 
                                                   n->voisin[i]->cy,&mx, &my);
				    trace_segment(mx,my, x,y,sx0,sy0);
				   }
				}
				break;

			} //switch

                  } //if

           }  // for

	for (i=W; i>=U; i--)
        { noeud v = n->voisin[i];
	  if ( v->stacked != flag )
           { stack[++top] = v;          //push
             v->stacked = flag;
            }
         }

   } // while stack not empty

 delete stack;

}

DT_item delaunay_tree::neighbor(double x,double y)
/* recherche du plus proche voisin de (x,y) */
{
	DT_POINT requete;
	DT_item reponse;

	flag++;
	if (arbre == nouveau) return NULL;
	requete.x = x; requete.y = y;
	reponse = localise(Insert(arbre,&requete), &requete);
	return  reponse;
}

void delaunay_tree::del(double x, double y)
{ DT_item p = neighbor(x,y);
  if (p==nil || p->x != x || p->y != y) return;
  del_item(p);
 }

void delaunay_tree::del_item( DT_item ppp)
{
	DT_item p;

	if (!ppp) return;

	flag++;
	p = (DT_item) ppp ;
	nouveau = p->cree->pere;	/* pour si on supprime le dernier */
	recherche(p);
	last = nouveau ;
	parcours(Reinsert,p);
        clear_inf(p->i);
        counter--;
	poubelle_point(p);
}

DT_item delaunay_tree::insert( coord x, coord y, void* inf)
/* procedure d'insertion d'un point dans l'arbre */
{
	DT_item p;

	flag++;
	p = alloc_point();
	p->x = x;
	p->y = y;
        p->i = inf;
	p->n = flag;
	if (! creation( Insert(arbre,p), p )) 
        { poubelle_point(p); 
          return neighbor(x,y);
         }
        copy_inf(inf);
        counter++;
	last = nouveau ;
	return p;
}

void delaunay_tree::all_items(list<DT_item>& L)
/* procedure tracant tous les points */
{
	if (arbre == nouveau) return;
	flag++;
	arbre->s[U]->visite = flag;
	arbre->s[V]->visite = flag;
	arbre->s[W]->visite = flag;
	list_items(nouveau, L);
}

void delaunay_tree::trace_triang_edges( delaunay_f4 *seg,int both)
/* procedure de trace de delaunay */
{
	if (arbre == nouveau) return;
	flag++;
	del_noeud(nouveau,seg, both);
}

void delaunay_tree::trace_voronoi_sites(delaunay_f2 *trace_item)
{
	if (arbre == nouveau) return;
	flag++;
	trace_items(nouveau,trace_item);
}

void delaunay_tree::trace_voronoi_edges(delaunay_f6 *trace_seg, delaunay_F6 *pt_infi, int both)
{
	if (arbre == nouveau) return;
	flag++;
	vor(nouveau,trace_seg,pt_infi, both);
}

void delaunay_tree::convex_hull(list<DT_item>& CH)
{ 
 CH.clear();

 if (arbre == nouveau) return;

 for (int j=2;j>=0;j--)
 { noeud v = arbre->voisin[0];

   int i = (j == 0) ? 2 : j-1;

   DT_item start = v->s[i];

   do
   { int k;
     if (v->type == Infini1) CH.append(v->s[i]);
     if (v->direct)
        k = (i == 0) ? 2 : i-1;
     else
        k = (i == 2) ? 0 : i+1;
     noeud w = v->voisin[k];
     for(i=0;w->voisin[i] != v;i++); 
     v = w;
    } while (v->s[i] != start);

  }
}