/* LMI/lmi06/ALGOGEOM/TD/TPtriang/MYTRIANG/triang.c */ /* programme ecrit par G. SENIZERGUES- Avril 2007 */ /*--------------------------------------------------*/ #include #include #include #include #include "triang.h" /* ------------------VARIABLES GLOBALES -----------------------*/ int NP=0; /* nombre de points */ Point *POLYG[NPMAX]; /* tableau des sommets du polygone */ Point *DIAG[NDMAX]; /* tableau des diagonales */ dliste_points PTS=NULL; /* d-liste des Point */ int xmin,xmax,ymin,ymax; /* coordonnees extremes */ Point *MIN; /* nouvelle origine */ /* ---------------------FONCTIONS -----------------------------*/ /* ALLOCATION MEMOIRE */ Point *Palloc(void) { return((Point *)malloc(sizeof(Point)));} cell *caloc(void) { return((cell *)malloc(sizeof(cell)));} int *ialloc(void) { return((int *)malloc(sizeof(int)));} /* d-LISTES */ void ajouter(dliste_points *L, cell *p, Point *P) { cell *q=caloc(); q->val=P; if(*L==NULL) /* creation d'une liste de longueur 1 */ {q->prec=q; q->suiv=q; *L=q;} else /* insertion d'une nouvelle cellule */ /* p est suppose non nul */ {q->prec=p; q->suiv=p->suiv; q->prec->suiv=q; q->suiv->prec=q;}} void supprimer(dliste_points *L, cell *p) {if (p->prec== p) {*L=NULL;} else {p->prec->suiv=p->suiv; p->suiv->prec=p->prec; if (p==*L) *L=(*L)->suiv; }} /* ENTREES-SORTIES */ void lire_points( void ) { int n = 0; cell *ccour=caloc(); Point *Pcour; int *xtemp=ialloc(); int *ytemp=ialloc(); printf("%%");printf("donnez-moi des points, au plus %3d \n",NPMAX); while (( n < NPMAX) && (scanf("%d %d",xtemp,ytemp) != EOF)) { Pcour=Palloc(); Pcour->x= *xtemp; Pcour->y= *ytemp; POLYG[n]=Pcour; ajouter(&PTS,ccour,Pcour); ++n; ccour=PTS->prec;} {if (n < NPMAX) {NP=n; printf("%%");printf("%3d points lus\n",n); } else {printf("%%");printf("%3d points lus; nombre max est atteint;\n les autres points ne seront pas lus \n",n);}}} void ecrire_points(void) {int n=0;cell *ccour=PTS; printf("%%");printf("Liste des points \n"); while ( n < NP) {printf("%%");printf("(%d,%d)\n",ccour->val->x,ccour->val->y); printf("%%");printf("%d\n",ccour->ore); ccour=ccour->suiv; n++;}} void ecrire_points_inverse(void) {int n=0;cell *ccour=PTS->prec; printf("%%");printf("Liste des points \n"); while ( n < NP) {printf("%%");printf("(%d,%d)\n",ccour->val->x,ccour->val->y); ccour=ccour->prec; n++;}} extern void ecrire_ps(void) {printf("%%");printf("%%");printf("!PS\n"); printf("%%");printf("%%");printf("Creator: ges/LMI/lmi06/ALGOGEOM/TD/TPtriang/MYTRIANG/triang.c\n"); printf("\n"); printf("%%");printf("%%");printf("nouvelles coordonnees\n"); /* nouvelles unites de longueur, en 1/72 d'inch */ printf("/xscale");printf("{");printf("576 \t %d \t %d \t sub \t div \t mul",xmax+4,xmin); printf(" }"); printf("def \n"); printf("/yscale");printf("{");printf("576 \t %d \t %d \t sub \t div \t mul",ymax+4,ymin); printf(" }"); printf("def \n"); printf("1 setlinewidth \n"); printf("0 setgray \n"); printf("%%");printf("%%");printf("les points \n"); int i; /* on dessine les points */ for(i=0;ix,POLYG[i]->y); printf("closepath stroke \n");} /* on dessine le polygone en noir */ printf("%%");printf("%%");printf("le polygone\n"); printf("newpath \n"); printf("%d xscale \t %d yscale \t moveto \n",POLYG[0]->x,POLYG[0]->y); for(i=1;ix,POLYG[i]->y); printf("closepath stroke \n"); /* on dessine les diagonales en bleu */ printf("%%");printf("%%");printf("les diagonales\n"); printf("0.0 0.0 1.0 setrgbcolor \n"); printf("newpath \n"); for(i=0;ix,DIAG[2*i]->y); printf("%d xscale \t %d yscale \t lineto \n",DIAG[2*i+1]->x,DIAG[2*i+1]->y); } printf("stroke \n"); } /* GEOMETRIE */ int det(Point *p1, Point *p2) /* determinant */ {return((p1->x * p2->y)-(p1->y * p2->x));} int direct(Point *p1, Point *p2, Point *p3) {Point *u= Palloc();Point *v=Palloc(); u->x= p2->x - p1->x; u->y= p2->y - p1->y; v->x= p3->x - p2->x; v->y= p3->y - p2->y; if (det(u,v) > 0) {free(u);free(v);return(1);} else {free(u);free(v);return(0);} } void changer_coord(Point *OR) /* transforme les coordonnes en prenant l'origine OR */ {int i=0; for(i=0;ix= (POLYG[i]->x)-(OR->x); POLYG[i]->y= (POLYG[i]->y)-(OR->y);} } int oreille(cell *p) /* renvoie 1 (resp 0) si *p est une oreille */ {Point *q=p->prec->val; Point *r=p->suiv->val; cell *ccour=p->suiv->suiv; cell *cder=p->prec; if (!direct(q,p->val,r)) return(0); else while(ccour != cder) { if(direct(q,p->val,ccour->val) && direct(p->val,r,ccour->val) && direct(r,q,ccour->val)) return(0); else ccour=ccour->suiv;} return(1);} void trianguler(void) {int n=0; cell *ccour=PTS; cell *cpred; /* calculer les oreilles */ while (n < NP) {ccour->ore=oreille(ccour); ccour=ccour->suiv;n++;} /* boucle de suppression des oreilles */ n=0; ccour=PTS; while (n< NP-3) {if (ccour->ore) {DIAG[2*n]=ccour->prec->val; DIAG[2*n+1]=ccour->suiv->val; cpred=ccour->prec; n++;supprimer(&PTS,ccour); cpred->ore=oreille(cpred); cpred->suiv->ore=oreille(cpred->suiv); ccour=cpred; } else {ccour=ccour->suiv;} } } /* ---------------------ALGO ---------------------*/ /* Lire les points */ /* trianguler: */ /* calculer les oreilles */ /* boucle de suppression des oreilles */ /* Abscisses et ordonnees extremes */ /* Changer d'origine */ /* Generer le postscript */ /* -----------------------------------------------*/ int main() { int n=0; /* Lire les points */ lire_points(); /* trianguler: */ trianguler(); ecrire_points(); /* Abscisses et ordonnees extremes */ xmin=POLYG[0]->x;xmax=POLYG[0]->x;ymin=POLYG[0]->y;ymax=POLYG[0]->y; n=1; while (n < NP) {if (POLYG[n]->x < xmin) xmin=POLYG[n]->x; if (POLYG[n]->x > xmax) xmax=POLYG[n]->x; if (POLYG[n]->y < ymin) ymin=POLYG[n]->y; if (POLYG[n]->y > ymax) ymax=POLYG[n]->y; n++; } printf("%%");printf("%d, %d, %d, %d)\n",xmin,xmax,ymin, ymax); /* Changer d'origine */ MIN=Palloc(); MIN->x=xmin-2; MIN->y=ymin-2; changer_coord(MIN); /* Generer le postscript */ ecrire_ps(); return(EXIT_SUCCESS); }