/* programme ecrit par Axel GUERRA et Bastien RENAUD*/ /* Avril 2007 */ /*---------------------------------------------------*/ #include #include #include #include #include "triang.h" /* ------------------VARIABLES GLOBALES -----------------------*/ int NP=0; /* nombre de points */ int NPOLY=0; /* nombre de points */ int ND=0; /* nombre de points diagonaux */ 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 */ /* ---------------------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; NP--; 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("%%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=NPOLY=n; printf("%%%3d points lus\n",n); } else {printf("%%%3d points lus; nombre max est atteint;\n les autres points ne seront pas lus \n",n);} } } void lire_points_fichier(char* inputFileName) { int n = 0; cell *ccour=caloc(); Point *Pcour; int *xtemp=ialloc(); int *ytemp=ialloc(); FILE* file = fopen(inputFileName, "r"); while (( n < NPMAX) && (fscanf(file, "%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=NPOLY=n; printf("%%%3d points lus\n",n); } else {printf("%%%3d points lus; nombre max est atteint;\n les autres points ne seront pas lus \n",n);} } void ecrire_points(void) { int n; cell *ccour=PTS; printf("%%Liste des points \n"); for (n = 0 ; n < NP ; n++) { printf("%%(%d,%d)\n",ccour->val->x,ccour->val->y); ccour=ccour->suiv; } } void ecrire_points_inverse(void) { int n; cell *ccour=PTS->prec; printf("%%Liste des points \n"); for (n = 0 ; n < NP ; n++) { printf("%%(%d,%d)\n",ccour->val->x,ccour->val->y); ccour=ccour->prec; } } void ecrire_diags(void) { int n; printf("%%Liste des diagonales \n"); for (n = 0 ; n < ND ; n += 2){ printf("(%d, %d) - (%d, %d)\n", DIAG[n]->x, DIAG[n]->y, DIAG[n + 1]->x, DIAG[n + 1]->y); } } /** * Fonction qui génére un fichier de type PostScript en prenant compte de la marge à gauche, droite, en haut et en * bas. Le polygone est aussi redimensionné afin de remplir au maximum la page sans jamais dépasser. Ce polygone est * rendu en noir et les diagonales calculées en rouge. *************************************************************************************************************************/ void ecrire_ps(char* psFileName, float leftMargin, float rightMargin, float topMargin, float bottomMargin) { const float A4_WIDTH = 21.0f; const float A4_HEIGHT = 29.7f; FILE* file = fopen(psFileName, "w"); int i; float xPP, yPP, xMin, yMin, xMax, yMax; /* variables qualifiant le rectangle englobant. */ float width, height, delta; xMin = yMin = 999; xMax = yMax = -999; delta = 1; width = A4_WIDTH - (leftMargin + rightMargin); /* calcul la largeur de la page en tenant compte des marges. */ height = A4_HEIGHT - (topMargin + bottomMargin); /* calcul la hauteur de la page en tenant compte des marges. */ for (i = 0 ; i < NPOLY ; i++){ /* calcul du rectangle englobant. */ if(POLYG[i]->x < xMin){xMin = POLYG[i]->x;} else if(xMax < POLYG[i]->x){xMax = POLYG[i]->x;} if(POLYG[i]->y < yMin){yMin = POLYG[i]->y;} else if(yMax < POLYG[i]->y){yMax = POLYG[i]->y;} } if((xMax - xMin) / width < (yMax - yMin) / height){ /* Calcul le rapport d'agrandissemnt en fonction du rectangle */ delta = height / (yMax - yMin); /* afin que l'objet prenne toujours toute la page. */ } else { delta = width / (xMax - xMin); } xMin *= delta; /* Mise à l'échelle du rectangle englobant (donc de l'objet). */ yMin *= delta; xMax *= delta; yMax *= delta; xPP = (width - xMax + xMin) / 2 - xMin + leftMargin; /* Calcul de la position en x et y du Premier Point en prenant */ yPP = (height - yMax + yMin) / 2 - yMin + topMargin; /* soin de centrer le rectangle englobant. */ fprintf(file, "%%!postscriptfile: result.ps\n\n"); /* Ecriture du fichier PostScript en y décrivant d'abord les */ fprintf(file, "/cm {7200 254 div mul} def\n"); /* diagonales en rouge (pour que ca soit joli) puis le polygone */ /* en noir. */ fprintf(file, "1.0 0.0 0.0 setrgbcolor\n"); for (i = 0 ; i < ND ; i+=2){ fprintf(file, "newpath\n"); fprintf(file, "%g cm %g cm moveto\n", DIAG[i]->x * delta + xPP, DIAG[i]->y * delta + yPP); fprintf(file, "%g cm %g cm rlineto\n", (DIAG[i+1]->x - DIAG[i]->x) * delta, (DIAG[i+1]->y - DIAG[i]->y) * delta); fprintf(file, "closepath\n"); fprintf(file, "stroke\n"); } fprintf(file, "0.0 0.0 0.0 setrgbcolor\n"); fprintf(file, "newpath\n"); fprintf(file, "%g cm %g cm moveto\n", xPP, yPP); for (i = 1 ; i < NPOLY ; i++){ fprintf(file, "%g cm %g cm rlineto\n", (POLYG[i]->x - POLYG[i-1]->x) * delta, (POLYG[i]->y - POLYG[i-1]->y) * delta); } fprintf(file, "closepath\n"); fprintf(file, "stroke\n"); fprintf(file, "showpage\n"); fclose(file); } /*************************************************************/ /*************************** GEOMETRIE ***********************/ /*************************************************************/ int det(Vecteur *u, Vecteur *v) /* determinant */ { return((u->x * v->y) - (u->y * v->x)); } int direct(Point *p1, Point *p2, Point *p3) { Vecteur *u = Palloc(); Vecteur *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) return(1); else return(0); free(u); free(v); } void changer_coord(Point *OR) { int n; int x = OR->x; int y = OR->y; cell *ccour=PTS; for (n = 0 ; n < NP ; n++) { ccour->val->x -= x; ccour->val->y -= y; ccour=ccour->suiv; } } int estDansTriangle(Point *p1, Point *p2, Point *p3, Point *p) { #define ComputeVecteur(u, a, b) {(u)->x = (b)->x - (a)->x; (u)->y = (b)->y - (a)->y;} Vecteur *u = Palloc(); Vecteur *v = Palloc(); ComputeVecteur(u, p1, p2); ComputeVecteur(v, p1, p); if (det(u, v) >= 0){ ComputeVecteur(u, p2, p3); ComputeVecteur(v, p2, p); if (det(u, v) >= 0){ ComputeVecteur(u, p3, p1); ComputeVecteur(v, p3, p); if (det(u, v) >= 0){ free(u); free(v); return 1; } } } free(u); free(v); return 0; } int oreille(cell *c) { int n = NP; int estdans = 0; Point *cour = c->val; Point *prec = c->prec->val; Point *suiv = c->suiv->val; cell* ccour = c->suiv->suiv; if (direct(prec, cour, suiv)){ for (n = 2 ; n < NP - 1 && estdans == 0 ; n++){ estdans = estDansTriangle(prec, cour, suiv, ccour->val); ccour = ccour->suiv; } if (estdans == 0){ //printf("direct & oreille = 1\n"); return 1; } //else printf("direct & oreille = 0\n"); } //else printf("indirect & oreille = 0\n"); return 0; } void trianguler(void) { cell *c = PTS, *cnext = NULL; while (NP > 3){ if (oreille(c)){ //printf("suppression\n"); DIAG[ND++] = c->prec->val; DIAG[ND++] = c->suiv->val; cnext = c->suiv; supprimer(&PTS, c); c = cnext; } else{ c = c->suiv; } } } /* ---------------------ALGO ---------------------*/ /* Lire les points */ /* trianguler: */ /* calculer les oreilles */ /* boucle de suppression des oreilles */ /* Abscisses et ordonnees extremes */ /* Generer le postscript */ /* -----------------------------------------------*/ int main(int argc, char** argv) { if(argc < 3){ printf("Usage : %s \n",argv[0]); return(EXIT_FAILURE); } if(argc > 3){ printf("Attention : seul les deux premiers arguments sont pris en compte.\n"); } lire_points_fichier(argv[1]); changer_coord(PTS->val); ecrire_points(); trianguler(); ecrire_ps(argv[2],1.0f,1.0f,1.0f,1.0f); return(EXIT_SUCCESS); }