home *** CD-ROM | disk | FTP | other *** search
/ ftp.disi.unige.it / 2015-02-11.ftp.disi.unige.it.tar / ftp.disi.unige.it / pub / .person / MagilloP / GEOMOD99 / build.c next >
C/C++ Source or Header  |  1999-05-04  |  10KB  |  374 lines
  1. /***********************************************************************/
  2. /* FILE: build.c                                                       */
  3. /***********************************************************************/
  4.  
  5. /*
  6. Costruzione di quadtree per triangolazione.
  7. Per metterci al riparo da casi particolari assumiamo che i vertici 
  8. della triangolazione abbiano coordinate intere o terminanti per 0.5,
  9. ed utilizziamo nel quadtree coordinate terminanti per 0.3
  10. */
  11.  
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14. #include <math.h>
  15.  
  16. #include "point.h"
  17.  
  18. #include "stack.h"
  19. #include "tree.h"
  20.  
  21. /***********************************************************************/
  22.  
  23. /* triangolazione letta da file */
  24. COMPLETARE: dichiarazione variabile globale per la triangulazione tau;
  25.  
  26. /* radice dell'albero da costruire */
  27. QTree root;
  28.  
  29. /* massima profondita' ammessa per il quadtree (determina la minima 
  30.    dimensione per un nodo) */
  31. #define MAXDEPTH 6
  32.  
  33. void ReadTriangulation(void)
  34. {
  35.   int i;
  36.   int vrtNum, trgNum; /* per leggere numero di vertici e triangoli */
  37.   float x, y;         /* per leggere coordinate di un vertice */
  38.   int v1, v2, v3;     /* per leggere vertici di un triangolo */
  39.   int ad1, ad2, ad3;  /* per leggere adiacenti di un triangolo */
  40.   int t;              /* per leggere triangolo associato a un vertice */
  41.   
  42. COMPLETARE con allocazione dello spazio per la struttura dati per
  43. la triangolazione e copia nella struttura dati delle informazioni
  44. lette.
  45.  
  46.   /* legge il numero di vertici */
  47.   scanf("%d",&vrtNum);
  48.   
  49.   /* legge i vertici */
  50.   for (i=0; i<vrtNum; i++)
  51.   {
  52.     scanf("%f %f", &x, &y);
  53.   }
  54.   
  55.   /* legge il numero di triangoli */
  56.   scanf("%d",&trgNum);
  57.  
  58.   /* legge la relazione TV */
  59.   for (i=0; i<trgNum; i++)
  60.   {
  61.     scanf("%d %d %d", &v1, &v2, &v3);
  62.   }
  63.   
  64.   /* legge la relazione VT parziale */
  65.   for (i=0; i<vrtNum; i++)
  66.   {
  67.     scanf("%d", &t);
  68.   }
  69.   
  70.   /* legge la relazione TT */
  71.   for (i=0; i<trgNum; i++)
  72.   {
  73.     scanf("%d %d %d", &ad1, &ad2, &ad3);
  74.   }
  75. }
  76.  
  77. /***********************************************************************/
  78.  
  79. double log2(double x)
  80. {
  81.   return (log(x)/log(2.0));
  82. }  
  83.  
  84. /* controlla se il punto p si trova strettamente all'interno del
  85.    rettangolo con angolo in basso a sinistra (x0,y0), larghezza 
  86.    dx ed altezza dy */
  87. int pointInBox(Point p, float x0, float y0, float dx, float dy)
  88. {
  89.   if (p[X]<=x0) return 0;
  90.   if (p[X]>=x0+dx) return 0;
  91.   if (p[Y]<=y0) return 0;
  92.   if (p[Y]>=y0+dy) return 0;
  93.   return 1;
  94. }
  95.  
  96. /* controlla se il lato di estremi p1 e p2 interseca propriamente
  97.    il rettangolo con angolo in basso a sinistra (x0,y0), larghezza 
  98.    dx ed altezza dy */
  99. int edgeInBox(Point p1, Point p2, 
  100.               float x0, float y0, float dx, float dy)
  101. {
  102.   int is_left, is_right;
  103.   Point aux;
  104.   int i, j;
  105.   /* almeno uno dei due estremi deve essere a destra della retta x=x0 */
  106.   if ( (p1[X]<=x0) && (p2[X]<=x0) ) return 0;
  107.   /* almeno uno dei due estremi deve essere a sinistra di x=x0+dx */
  108.   if ( (p1[X]>=x0+dx) && (p2[X]>=x0+dx) ) return 0;
  109.   /* almeno uno dei due estremi deve essere sopra la retta y=y0 */
  110.   if ( (p1[Y]<=y0) && (p2[Y]<=y0) ) return 0;
  111.   /* almeno uno dei due estremi deve essere sotto la retta y=y0+dy */
  112.   if ( (p1[Y]>=y0+dy) && (p2[Y]>=y0+dy) ) return 0;
  113.   /* almeno due vertici del box devono giacere da parti opposte
  114.      rispetto al segmento p1 p2 */
  115.   is_left = is_right = 0;
  116.   for (i=0; i<2; i++)
  117.     for (j=0; j<2; j++)
  118.     {
  119.       aux[X] = x0; aux[Y] = y0;
  120.       if (i) aux[X] += dx; 
  121.       if (j) aux[Y] += dy;
  122.       is_left = is_left || Left(aux, p1, p2);
  123.       is_right = is_right || (!LeftOn(aux, p1, p2));
  124.     }
  125.   if (is_left && is_right) return 1;
  126.   return 0;
  127. }
  128.  
  129. /* controlla se il triangolo t interseca propriamente il rettangolo 
  130.    con angolo in basso a sinistra (x0,y0), larghezza dx ed altezza dy */
  131. int triangleInBox(int t, /* indice del triangolo */
  132.                   float x0, float y0, float dx, float dy)
  133. {
  134.   Point *p1, *p2, *p3, aux;
  135. COMPLETARE: 
  136.   p1 = primo vertice del triangolo di indice t
  137.   p2 = secondo vertice
  138.   p3 = terzo vertice
  139.   
  140.   /* se almeno un vertice e' propriamente dentro --> t interseca */
  141.   if (pointInBox(*p1,x0,y0,dx,dy)) return 1;
  142.   if (pointInBox(*p2,x0,y0,dx,dy)) return 1;
  143.   if (pointInBox(*p3,x0,y0,dx,dy)) return 1;
  144.   
  145.   /* se almeno un lato interseca propriamente --> t interseca */
  146.   if (edgeInBox(*p1,*p2,x0,y0,dx,dy)) return 1;
  147.   if (edgeInBox(*p2,*p3,x0,y0,dx,dy)) return 1; 
  148.   if (edgeInBox(*p3,*p1,x0,y0,dx,dy)) return 1; 
  149.   
  150.   /* controllo se t ricopre interamente il box (uso contenimento
  151.      del baricentro in t */
  152.   aux[X] = x0 + 0.5*dx;
  153.   aux[Y] = y0 + 0.5*dy;
  154.   if (InTriangle(aux, *p1, *p2, *p3)) return 1;
  155.   return 0;
  156. }
  157.  
  158. void clipElements(QTree n,   /* nodo corrente */
  159.             int vNum, Stack vl, /* numero e vertici da collocare */
  160.             int tNum, Stack tl, /* numero e triangoli da collocare */
  161.             int *vNum1, Stack *vl1, 
  162.             int *tNum1, Stack *tl1)
  163. {
  164.   int i;
  165.   float x0, y0, dx, dy;
  166.   Point p;
  167.   
  168.   NodeBox(n, &x0, &y0, &dx, &dy);
  169.   (*tNum1) = (*vNum1) = 0;
  170.   EmptyStack(vl1);
  171.   EmptyStack(tl1);
  172.   for (i=0; i<vNum; i++)
  173.   {
  174. COMPLETARE: ricavare dalla struttura dati il punto p
  175. corrispondente al vertice di indice vl->content
  176.  
  177.     if (pointInBox(p, x0,y0,dx,dy))
  178.     {  PushStack(vl->content, vl1);
  179.        (*vNum1)++;
  180.     }
  181.     vl = StackPop(vl);
  182.   }
  183.   for (i=0; i<tNum; i++)
  184.   {
  185.     if (triangleInBox(tl->content, x0,y0,dx,dy))
  186.     {  PushStack(tl->content, tl1);
  187.        (*tNum1)++;
  188.     }
  189.     tl = StackPop(tl);
  190.   }
  191. }
  192.  
  193. void Build (QTree root,   /* nodo corrente */
  194.             int depth,    /* profondita' del nodo corrente */
  195.             int vNum, Stack vl, /* numero e vertici da collocare */
  196.             int tNum, Stack tl) /* numero e triangoli da collocare */
  197. {
  198.   Stack aux;
  199.   
  200.   if ( (vNum==0) && (tNum==0) ) /* quadrante vuoto */
  201.   {
  202.     SetEmptyLeaf(root);
  203.     return;
  204.   }
  205.   if ( tNum==1 ) /* un solo triangolo */
  206.   {
  207.     SetOneTriangLeaf(root, StackTop(tl));
  208.     return;
  209.   }
  210.   if ( tNum==2 ) /* due soli triangoli */
  211.   {
  212.     SetTwoTriangLeaf(root, StackTop(tl), StackTop(StackPop(tl)));
  213.     return;
  214.   }
  215.   if (vNum==1) /* un solo vertice */
  216.   {
  217.     /* controllo che tutti i triangoli presenti siano incidenti in
  218.        quel vertice */
  219.     for (aux = tl; aux; aux = StackPop(aux))
  220.     {
  221. COMPLETARE: 
  222. ricavare dalla struttura dati gli indici tv1, tv2, tv3 del primo, 
  223. secondo e terzo vertice del triangolo di indice StackTop(aux)
  224.  
  225.       if ( (tv1 != StackTop(vl)) &&
  226.            (tv2 != StackTop(vl)) &&
  227.            (tv3 != StackTop(vl)) ) break;
  228.     }
  229.     /* qui aux==NULL solo se tutti i triangoli erano incidenti, 
  230.        altrimenti il ciclo si e' interrotto prima */
  231.     if (!aux)
  232.     {  
  233.        SetVertexLeaf(root, StackTop(vl));
  234.        return;
  235.     }
  236.     /* altrimenti andro' al caso generale */
  237.   }
  238.   /* caso generale, il nodo va suddiviso,
  239.      prima pero' controllo che non sia troppo piccolo */
  240.   if (depth == MAXDEPTH)
  241.   {
  242.     int i;
  243.     Stack aux;
  244.     SetStopLeaf(root, tNum);
  245.     aux = tl;
  246.     for (i=0; i<tNum; i++)
  247.     {
  248.       AddTriToStopLeaf(root, i, StackTop(aux));
  249.       aux = StackPop(aux);
  250.     }
  251.   }       
  252.   else /* suddivido il nodo */     
  253.   {
  254.     int i;
  255.     Stack vli, tli;
  256.     int vni, tni;    
  257.     MakeChildren(root);
  258.     for (i=NE;i<=SW;i++)
  259.     {
  260.        /* per ogni sotto-quadrante, calcolo vertici e triangoli
  261.           rilevanti, e costruisco ricorsivamente */
  262.        clipElements(NodeChild(root,i), vNum,vl, tNum,tl, 
  263.                     &vni,&vli, &tni,&tli);
  264.        Build(NodeChild(root,i), depth+1, vni,vli,tni,tli);   
  265.        deleteStack(&vli);
  266.        deleteStack(&tli);
  267.     }
  268.   }
  269. }
  270.  
  271. /* 
  272. Costruisce quadtree sulla triangolazione tau.
  273. */
  274. void BuildQuadtree (void)
  275. {
  276.   int i;
  277.   /* insieme dei vertici e dei triangoli da collocare */
  278.   Stack vStack;
  279.   Stack tStack;
  280.   /* numero di vertici e di triangoli da collocare */
  281.   int vNum;
  282.   int tNum;
  283.   /* coordinate estreme della scena */
  284.   float x1, y1, x2, y2;
  285.   /* angolo in basso a sinistra, larghezza e altezza del 
  286.      rettangolo iniziale */
  287.   float x0, y0, dx, dy;
  288.    
  289.   /* inizializza le informazioni ausiliarie */
  290.   EmptyStack(&vStack);
  291.   EmptyStack(&tStack);
  292.   vNum = tNum = 0;
  293.  
  294. COMPLETARE: 
  295. vrtNum = numero di vertici della triangolazione tau
  296. trgNum = numero di triangoli della triangolazione tau
  297.  
  298.   for (i=0; i<vrtNum; i++)
  299.   {
  300.     PushStack(i,&vStack); vNum++;
  301.   }
  302.   for (i=0; i<trgNum; i++)
  303.   {
  304.     PushStack(i,&tStack); tNum++;
  305.   }
  306.  
  307.   /* calcola le coordinate estreme della triangolazione,
  308.      che servono per determinare il rettangolo iniziale */
  309.  
  310. COMPLETARE ritrovando dalla struttura dati le info
  311. corrispondenti alle parti scritte in italiano
  312.  
  313.   x1 = x2 = ascissa del primo vertice di tau
  314.   y1 = y2 = ordinata del primo vertice di tau
  315.   for (i=1; i<vrtNum; i++)
  316.   {
  317.     x = ascissa dell'i-esimo vertice di tau
  318.     y = ordinata dell'i-esimo vertice di tau
  319.      
  320.     if (x < x1) x1 = xi;
  321.     else if (x > x2) x2 = x;
  322.     if (y < y1) y1 = y;
  323.     else if (y > y2) y2 = y;
  324.   }
  325.   
  326.   /* calcola il rettangolo iniziale. L'ampiezza di tale 
  327.      rettangolo e' la piu' piccola potenza di due tale da
  328.      contenere tutta la triangolazione */
  329.   x0 = floor(x1)-0.3;
  330.   dx = pow(2.0, ceil(log2(x2-x0)));
  331.   y0 = floor(y1)-0.3;
  332.   dy = pow(2.0, ceil(log2(y2-y0)));
  333.   
  334.   /* inizializza e riempie l'albero */
  335.   MakeRoot(&root, x0,y0,dx,dy);
  336.   Build(root,0, vNum,vStack,tNum,tStack);
  337.  
  338.   deleteStack(&vStack);
  339.   deleteStack(&tStack);
  340. }
  341.   
  342. /***********************************************************************/
  343.  
  344. void PrintQuadtree(QTree n)
  345. {
  346.   int i;
  347.   writeNode(n);
  348.   switch (NodeType(n))
  349.   {
  350.     case  UNKNOWN:
  351.       printf("ERRORE"); break;
  352.     case INTERNAL:
  353.       for (i=NE;i<=SW;i++)
  354.       {
  355.         PrintQuadtree( NodeChild(n,i));
  356.       }
  357.       break;
  358.     case VERTEX:
  359.     case TWOTRI:
  360.     case ONETRI:
  361.     case EMPTY:
  362.     case STOP:
  363.       writeNode(n);
  364.       break;
  365.   }
  366. }
  367.  
  368. void main(void)
  369. {  
  370.   ReadTriangulation();
  371.   BuildQuadtree();
  372.   PrintQuadtree(root);
  373. }
  374.