/* Comparaisons */ int compare_x(const void *p1, const void *p2) {Point *pp1=*(Point **)p1; Point *pp2=*(Point **)p2; int comp; if (pp1->x < pp2->x) comp=-1; else if (pp1->x==pp2->x) comp=0; else comp=1; /* printf("(%d,%d,%d)< (%d,%d,%d) donne %d\n",pp1->x,pp1->y,pp1->z,pp2->x,pp2->y,pp2->z,comp); */ return(comp);} int compare_moinsx(const void *p1, const void *p2) {Point *pp1=*(Point **)p1; Point *pp2=*(Point **)p2; int comp; if (pp1->x > pp2->x) comp=-1; else if (pp1->x==pp2->x) comp=0; else comp=1; /* printf("(%d,%d,%d)< (%d,%d,%d) donne %d\n",pp1->x,pp1->y,pp1->z,pp2->x,pp2->y,pp2->z,comp); */ return(comp);} int index_max(void *tab, int imin, int imax, int sizeofelt, int(*cmp)(const void *,const void *)) { int i,vainqueur; vainqueur=imin; for (i=imin; i<= imax;i++) if ((*cmp)((tab + i*sizeofelt),(tab + vainqueur*sizeofelt))==1) vainqueur=i; return(vainqueur); } int succ(int i) {if (i==NA-1) return(0); else return(i+1);} int pred(int i) {if (i==0) return(NA-1); else return(i-1);} /* geometrie */ Arete *arete_init(int imin, int imax1, int imax2) {int i1,i2; /* index des points de depart*/ int fini=0; /* booleen */ Arete *Ainit1,*Ainit2; /* aretes de depart */ Arete *Acour1,*Acour2; /* aretes courantes */ Arete *vq1,*vq2; /* vainqueurs */ Arete *A=Aalloc();Arete *Ainv=Aalloc(); /* l'arete la plus haute en y et son inverse */ A->inv=Ainv;Ainv->inv=A; i1=index_max(POINTS,imin,imax1,sizeof(Point *),compare_x); i2=index_max(POINTS,imax1+1,imax2,sizeof(Point *),compare_moinsx); A->ori=Ainv->ext=POINTS[i1];A->ext=Ainv->ori=POINTS[i2]; while(!fini) {vq1=Ainit1=A->ori->art; vq2=Ainit2=A->ext->art; Acour1=Ainit1->suiv;Acour2=Ainit2->suiv; while(Acour1 != Ainit1) {if ((detaff2(A->ori,A->ext,Acour1->ori,Acour1->ext)>0) && ((detaff2(A->ori,A->ext,vq1->ori,vq1->ext) <=0) || (detaff2(Acour1->ori,Acour1->ext,vq1->ori,vq1->ext)>0))) /* Acour1 est meilleur que vq1 */ vq1=Acour1; Acour1=Acour1->suiv;} while(Acour2 != Ainit2) {if ((detaff2(A->ori,A->ext,Acour2->ori,Acour2->ext)>0) && ((detaff2(A->ori,A->ext,vq2->ori,vq2->ext) <=0) || (detaff2(Acour2->ori,Acour2->ext,vq2->ori,vq2->ext)<0))) /* Acour2 est meilleur que vq2 */ vq2=Acour2; Acour2=Acour2->suiv;} if (detaff2(A->ori,A->ext,vq1->ori,vq1->ext) >0) A->ori=Ainv->ext=vq1->ext; else if(detaff2(A->ori,A->ext,vq2->ori,vq2->ext) >0) A->ext=Ainv->ori=vq2->ext; else fini=1;} return(A);}