home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch7_5 / monotone.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-04  |  17.4 KB  |  689 lines
  1. #include "basic.h"
  2. #include <math.h>
  3.  
  4. #define CROSS_SINE(v0, v1) ((v0).x * (v1).y - (v1).x * (v0).y)
  5. #define LENGTH(v0) (sqrt((v0).x * (v0).x + (v0).y * (v0).y))
  6.  
  7. static monchain_t mchain[TRSIZE]; /* Table to hold all the monotone */
  8.                   /* polygons . Each monotone polygon */
  9.                   /* is a circularly linked list */
  10.  
  11. static vertexchain_t vert[SEGSIZE]; /* chain init. information. This */
  12.                     /* is used to decide which */
  13.                     /* monotone polygon to split if */
  14.                     /* there are several other */
  15.                     /* polygons touching at the same */
  16.                     /* vertex  */
  17.  
  18. static int mon[SEGSIZE];    /* contains position of any vertex in */
  19.                 /* the monotone chain for the polygon */
  20. static int visited[TRSIZE];
  21. static int chain_idx, op_idx, mon_idx;
  22.  
  23. /* Function returns TRUE if the trapezoid lies inside the polygon */
  24. static int inside_polygon(t)
  25.      trap_t *t;
  26. {
  27.   int rseg = t->rseg;
  28.  
  29.   if (t->state == ST_INVALID)
  30.     return 0;
  31.  
  32.   if ((t->lseg <= 0) || (t->rseg <= 0))
  33.     return 0;
  34.   
  35.   if (((t->u0 <= 0) && (t->u1 <= 0)) || 
  36.       ((t->d0 <= 0) && (t->d1 <= 0))) /* triangle */
  37.     return (_greater_than(&seg[rseg].v1, &seg[rseg].v0));
  38.   
  39.   return 0;
  40. }
  41.  
  42.  
  43. /* return a new mon structure from the table */
  44. static int newmon()
  45. {
  46.   return ++mon_idx;
  47. }
  48.  
  49.  
  50. /* return a new chain element from the table */
  51. static int new_chain_element()
  52. {
  53.   return ++chain_idx;
  54. }
  55.  
  56.  
  57. static double get_angle(vp0, vpnext, vp1)
  58.      point_t *vp0;
  59.      point_t *vpnext;
  60.      point_t *vp1;
  61. {
  62.   point_t v0, v1;
  63.   
  64.   v0.x = vpnext->x - vp0->x;
  65.   v0.y = vpnext->y - vp0->y;
  66.  
  67.   v1.x = vp1->x - vp0->x;
  68.   v1.y = vp1->y - vp0->y;
  69.  
  70.   if (CROSS_SINE(v0, v1) >= 0)    /* sine is positive */
  71.     return DOT(v0, v1)/LENGTH(v0)/LENGTH(v1);
  72.   else
  73.     return (-1.0 * DOT(v0, v1)/LENGTH(v0)/LENGTH(v1) - 2);
  74. }
  75.  
  76.  
  77. /* (v0, v1) is the new diagonal to be added to the polygon. Find which */
  78. /* chain to use and return the positions of v0 and v1 in p and q */ 
  79. static int get_vertex_positions(v0, v1, ip, iq)
  80.      int v0;
  81.      int v1;
  82.      int *ip;
  83.      int *iq;
  84. {
  85.   vertexchain_t *vp0, *vp1;
  86.   register int i;
  87.   double angle, temp;
  88.   int tp, tq;
  89.  
  90.   vp0 = &vert[v0];
  91.   vp1 = &vert[v1];
  92.   
  93.   /* p is identified as follows. Scan from (v0, v1) rightwards till */
  94.   /* you hit the first segment starting from v0. That chain is the */
  95.   /* chain of our interest */
  96.   
  97.   angle = -4.0;
  98.   for (i = 0; i < 4; i++)
  99.     {
  100.       if (vp0->vnext[i] <= 0)
  101.     continue;
  102.       if ((temp = get_angle(&vp0->pt, &(vert[vp0->vnext[i]].pt), 
  103.                 &vp1->pt)) > angle)
  104.     {
  105.       angle = temp;
  106.       tp = i;
  107.     }
  108.     }
  109.  
  110.   *ip = tp;
  111.  
  112.   /* Do similar actions for q */
  113.  
  114.   angle = -4.0;
  115.   for (i = 0; i < 4; i++)
  116.     {
  117.       if (vp1->vnext[i] <= 0)
  118.     continue;      
  119.       if ((temp = get_angle(&vp1->pt, &(vert[vp1->vnext[i]].pt), 
  120.                 &vp0->pt)) > angle)
  121.     {
  122.       angle = temp;
  123.       tq = i;
  124.     }
  125.     }
  126.  
  127.   *iq = tq;
  128.  
  129.   return 0;
  130. }
  131.  
  132.   
  133. /* v0 and v1 are specified in anti-clockwise order with respect to 
  134.  * the current monotone polygon mcur. Split the current polygon into 
  135.  * two polygons using the diagonal (v0, v1) 
  136.  */
  137. static int make_new_monotone_poly(mcur, v0, v1)
  138.      int mcur;
  139.      int v0;
  140.      int v1;
  141. {
  142.   int p, q, ip, iq;
  143.   int mnew = newmon();
  144.   int i, j, nf0, nf1;
  145.   vertexchain_t *vp0, *vp1;
  146.   
  147.   vp0 = &vert[v0];
  148.   vp1 = &vert[v1];
  149.  
  150.   get_vertex_positions(v0, v1, &ip, &iq);
  151.  
  152.   p = vp0->vpos[ip];
  153.   q = vp1->vpos[iq];
  154.  
  155.   /* At this stage, we have got the positions of v0 and v1 in the */
  156.   /* desired chain. Now modify the linked lists */
  157.  
  158.   i = new_chain_element();    /* for the new list */
  159.   j = new_chain_element();
  160.  
  161.   mchain[i].vnum = v0;
  162.   mchain[j].vnum = v1;
  163.  
  164.   mchain[i].next = mchain[p].next;
  165.   mchain[mchain[p].next].prev = i;
  166.   mchain[i].prev = j;
  167.   mchain[j].next = i;
  168.   mchain[j].prev = mchain[q].prev;
  169.   mchain[mchain[q].prev].next = j;
  170.  
  171.   mchain[p].next = q;
  172.   mchain[q].prev = p;
  173.  
  174.   nf0 = vp0->nextfree;
  175.   nf1 = vp1->nextfree;
  176.  
  177.   vp0->vnext[ip] = v1;
  178.  
  179.   vp0->vpos[nf0] = i;
  180.   vp0->vnext[nf0] = mchain[mchain[i].next].vnum;
  181.   vp1->vpos[nf1] = j;
  182.   vp1->vnext[nf1] = v0;
  183.  
  184.   vp0->nextfree++;
  185.   vp1->nextfree++;
  186.  
  187. #ifdef DEBUG
  188.   fprintf(stderr, "make_poly: mcur = %d, (v0, v1) = (%d, %d)\n", 
  189.       mcur, v0, v1);
  190.   fprintf(stderr, "next posns = (p, q) = (%d, %d)\n", p, q);
  191. #endif
  192.  
  193.   mon[mcur] = p;
  194.   mon[mnew] = i;
  195.   return mnew;
  196. }
  197.  
  198. /* Main routine to get monotone polygons from the trapezoidation of 
  199.  * the polygon.
  200.  */
  201.  
  202. int monotonate_trapezoids(n)
  203.      int n;
  204. {
  205.   register int i;
  206.   int tr_start;
  207.  
  208.   memset((void *)vert, 0, sizeof(vert));
  209.   memset((void *)visited, 0, sizeof(visited));
  210.   memset((void *)mchain, 0, sizeof(mchain));
  211.   memset((void *)mon, 0, sizeof(mon));
  212.   
  213.   /* First locate a trapezoid which lies inside the polygon */
  214.   /* and which is triangular */
  215.   for (i = 0; i < TRSIZE; i++)
  216.     if (inside_polygon(&tr[i]))
  217.       break;
  218.   tr_start = i;
  219.   
  220.   /* Initialise the mon data-structure and start spanning all the */
  221.   /* trapezoids within the polygon */
  222.  
  223.   for (i = 1; i <= n; i++)
  224.     {
  225.       mchain[i].prev = i - 1;
  226.       mchain[i].next = i + 1;
  227.       mchain[i].vnum = i;
  228.       vert[i].pt = seg[i].v0;
  229.       vert[i].vnext[0] = i + 1;    /* next vertex */
  230.       vert[i].vpos[0] = i;    /* locn. of next vertex */
  231.       vert[i].nextfree = 1;
  232.     }
  233.   mchain[1].prev = n;
  234.   mchain[n].next = 1;
  235.   vert[n].vnext[0] = 1;
  236.   vert[n].vpos[0] = n;
  237.   chain_idx = n;
  238.   mon_idx = 0;
  239.   mon[0] = 1;            /* position of any vertex in the first */
  240.                 /* chain  */
  241.   
  242.   /* traverse the polygon */
  243.   if (tr[tr_start].u0 > 0)
  244.     traverse_polygon(0, tr_start, tr[tr_start].u0, TR_FROM_UP);
  245.   else if (tr[tr_start].d0 > 0)
  246.     traverse_polygon(0, tr_start, tr[tr_start].d0, TR_FROM_DN);
  247.   
  248.   /* return the number of polygons created */
  249.   return newmon();
  250. }
  251.  
  252.  
  253. /* recursively visit all the trapezoids */
  254. int traverse_polygon(mcur, trnum, from, dir)
  255.      int mcur;
  256.      int trnum;
  257.      int from;
  258.      int dir;
  259. {
  260.   trap_t *t = &tr[trnum];
  261.   int mnew;
  262.   int v0, v1;
  263.   int retval;
  264.   int do_switch = FALSE;
  265.  
  266.   if ((trnum <= 0) || visited[trnum])
  267.     return 0;
  268.  
  269.   visited[trnum] = TRUE;
  270.   
  271.   /* We have much more information available here. */
  272.   /* rseg: goes upwards   */
  273.   /* lseg: goes downwards */
  274.  
  275.   /* Initially assume that dir = TR_FROM_DN (from the left) */
  276.   /* Switch v0 and v1 if necessary afterwards */
  277.  
  278.  
  279.   /* special cases for triangles with cusps at the opposite ends. */
  280.   /* take care of this first */
  281.   if ((t->u0 <= 0) && (t->u1 <= 0))
  282.     {
  283.       if ((t->d0 > 0) && (t->d1 > 0)) /* downward opening triangle */
  284.     {
  285.       v0 = tr[t->d1].lseg;
  286.       v1 = t->lseg;
  287.       if (from == t->d1)
  288.         {
  289.           do_switch = TRUE;
  290.           mnew = make_new_monotone_poly(mcur, v1, v0);
  291.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  292.           traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);        
  293.         }
  294.       else
  295.         {
  296.           mnew = make_new_monotone_poly(mcur, v0, v1);
  297.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  298.           traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
  299.         }
  300.     }
  301.       else
  302.     {
  303.       retval = SP_NOSPLIT;    /* Just traverse all neighbours */
  304.       traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  305.       traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  306.       traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  307.       traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  308.       }
  309.     }
  310.   
  311.   else if ((t->d0 <= 0) && (t->d1 <= 0))
  312.     {
  313.       if ((t->u0 > 0) && (t->u1 > 0)) /* upward opening triangle */
  314.     {
  315.       v0 = t->rseg;
  316.       v1 = tr[t->u0].rseg;
  317.       if (from == t->u1)
  318.         {
  319.           do_switch = TRUE;
  320.           mnew = make_new_monotone_poly(mcur, v1, v0);
  321.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  322.           traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);        
  323.         }
  324.       else
  325.         {
  326.           mnew = make_new_monotone_poly(mcur, v0, v1);
  327.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  328.           traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
  329.         }
  330.     }
  331.       else
  332.     {
  333.       retval = SP_NOSPLIT;    /* Just traverse all neighbours */
  334.       traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  335.       traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  336.       traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  337.       traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  338.     }
  339.     }
  340.   
  341.   else if ((t->u0 > 0) && (t->u1 > 0)) 
  342.     {
  343.       if ((t->d0 > 0) && (t->d1 > 0)) /* downward + upward cusps */
  344.     {
  345.       v0 = tr[t->d1].lseg;
  346.       v1 = tr[t->u0].rseg;
  347.       retval = SP_2UP_2DN;
  348.       if (((dir == TR_FROM_DN) && (t->d1 == from)) ||
  349.           ((dir == TR_FROM_UP) && (t->u1 == from)))
  350.         {
  351.           do_switch = TRUE;
  352.           mnew = make_new_monotone_poly(mcur, v1, v0);
  353.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  354.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  355.           traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
  356.           traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
  357.         }
  358.       else
  359.         {
  360.           mnew = make_new_monotone_poly(mcur, v0, v1);
  361.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  362.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  363.           traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
  364.           traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);          
  365.         }
  366.     }
  367.       else            /* only downward cusp */
  368.     {
  369.       if (_equal_to(&t->lo, &seg[t->lseg].v1))
  370.         {
  371.           v0 = tr[t->u0].rseg;
  372.           v1 = MODULO_NEXT(t->lseg + 1, global.nseg);
  373.           retval = SP_2UP_LEFT;
  374.           if ((dir == TR_FROM_UP) && (t->u0 == from))
  375.         {
  376.           do_switch = TRUE;
  377.           mnew = make_new_monotone_poly(mcur, v1, v0);
  378.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  379.           traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
  380.           traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
  381.           traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
  382.         }
  383.           else
  384.         {
  385.           mnew = make_new_monotone_poly(mcur, v0, v1);
  386.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  387.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  388.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  389.           traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
  390.         }
  391.         }
  392.       else
  393.         {
  394.           v0 = t->rseg;
  395.           v1 = tr[t->u0].rseg;    
  396.           retval = SP_2UP_RIGHT;
  397.           if ((dir == TR_FROM_UP) && (t->u1 == from))
  398.         {
  399.           do_switch = TRUE;
  400.           mnew = make_new_monotone_poly(mcur, v1, v0);
  401.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  402.           traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
  403.           traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
  404.           traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
  405.         }
  406.           else
  407.         {
  408.           mnew = make_new_monotone_poly(mcur, v0, v1);
  409.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  410.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  411.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  412.           traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
  413.         }
  414.         }
  415.     }
  416.     }
  417.   else if ((t->u0 > 0) || (t->u1 > 0)) /* no downward cusp */
  418.     {
  419.       if ((t->d0 > 0) && (t->d1 > 0)) /* only upward cusp */
  420.     {
  421.       if (_equal_to(&t->hi, &seg[t->lseg].v0))
  422.         {
  423.           v0 = tr[t->d1].lseg;
  424.           v1 = t->lseg;
  425.           retval = SP_2DN_LEFT;
  426.           if (!((dir == TR_FROM_DN) && (t->d0 == from)))
  427.         {
  428.           do_switch = TRUE;
  429.           mnew = make_new_monotone_poly(mcur, v1, v0);
  430.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  431.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  432.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  433.           traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
  434.         }
  435.           else
  436.         {
  437.           mnew = make_new_monotone_poly(mcur, v0, v1);
  438.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  439.           traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
  440.           traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
  441.           traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);          
  442.         }
  443.         }
  444.       else
  445.         {
  446.           v0 = tr[t->d1].lseg;
  447.           v1 = MODULO_NEXT(t->rseg + 1, global.nseg);
  448.           retval = SP_2DN_RIGHT;        
  449.           if ((dir == TR_FROM_DN) && (t->d1 == from))
  450.         {
  451.           do_switch = TRUE;
  452.           mnew = make_new_monotone_poly(mcur, v1, v0);
  453.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  454.           traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
  455.           traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
  456.           traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
  457.         }
  458.           else
  459.         {
  460.           mnew = make_new_monotone_poly(mcur, v0, v1);
  461.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  462.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  463.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  464.           traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
  465.         }
  466.         }
  467.     }
  468.       else            /* no cusp */
  469.     {
  470.       if (_equal_to(&t->hi, &seg[t->lseg].v0) &&
  471.           _equal_to(&t->lo, &seg[t->rseg].v0))
  472.         {
  473.           v0 = t->rseg;
  474.           v1 = t->lseg;
  475.           retval = SP_SIMPLE_LRDN;
  476.           if (dir == TR_FROM_UP)
  477.         {
  478.           do_switch = TRUE;
  479.           mnew = make_new_monotone_poly(mcur, v1, v0);
  480.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  481.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  482.           traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
  483.           traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
  484.         }
  485.           else
  486.         {
  487.           mnew = make_new_monotone_poly(mcur, v0, v1);
  488.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  489.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  490.           traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
  491.           traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
  492.         }
  493.         }
  494.       else if (_equal_to(&t->hi, &seg[t->rseg].v1) &&
  495.            _equal_to(&t->lo, &seg[t->lseg].v1))
  496.         {
  497.           v0 = MODULO_NEXT(t->rseg + 1, global.nseg);
  498.           v1 = MODULO_NEXT(t->lseg + 1, global.nseg);
  499.           retval = SP_SIMPLE_LRUP;
  500.           if (dir == TR_FROM_UP)
  501.         {
  502.           do_switch = TRUE;
  503.           mnew = make_new_monotone_poly(mcur, v1, v0);
  504.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  505.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  506.           traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
  507.           traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
  508.         }
  509.           else
  510.         {
  511.           mnew = make_new_monotone_poly(mcur, v0, v1);
  512.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
  513.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  514.           traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
  515.           traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
  516.         }
  517.         }
  518.       else            /* no split possible */
  519.         {
  520.           retval = SP_NOSPLIT;
  521.           traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
  522.           traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
  523.           traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
  524.           traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);                    
  525.         }
  526.     }
  527.     }
  528.  
  529.   return retval;
  530. }
  531.  
  532.  
  533. int triangulate_monotone_polygons(nmonpoly, op)
  534.      int nmonpoly;
  535.      int op[][3];
  536. {
  537.   register int i;
  538.   point_t ymax, ymin;
  539.   int p, vfirst, posmax, posmin, v;
  540.   int vcount;
  541.  
  542. #ifdef DEBUG
  543.   for (i = 0; i < nmonpoly; i++)
  544.     {
  545.       fprintf(stderr, "\n\nPolygon %d: ", i);
  546.       vfirst = mchain[mon[i]].vnum;
  547.       p = mchain[mon[i]].next;
  548.       fprintf (stderr, "%d ", mchain[mon[i]].vnum);
  549.       while (mchain[p].vnum != vfirst)
  550.     {
  551.       fprintf(stderr, "%d ", mchain[p].vnum);
  552.       p = mchain[p].next;
  553.     }
  554.     }
  555.   fprintf(stderr, "\n");
  556. #endif
  557.  
  558.   op_idx = 0;
  559.   for (i = 0; i < nmonpoly; i++)
  560.     {
  561.       vcount = 1;
  562.       vfirst = mchain[mon[i]].vnum;
  563.       ymax = ymin = vert[vfirst].pt;
  564.       posmax = posmin = mon[i];
  565.       p = mchain[mon[i]].next;
  566.       while ((v = mchain[p].vnum) != vfirst)
  567.     {
  568.       if (_greater_than(&vert[v].pt, &ymax))
  569.         {
  570.           ymax = vert[v].pt;
  571.           posmax = p;
  572.         }
  573.       if (_less_than(&vert[v].pt, &ymin))
  574.         {
  575.           ymin = vert[v].pt;
  576.           posmin = p;
  577.         }
  578.       p = mchain[p].next;
  579.       vcount++;
  580.     }
  581.       
  582.       if (vcount == 3)        /* already a triangle */
  583.     {
  584.       op[op_idx][0] = mchain[p].vnum;
  585.       op[op_idx][1] = mchain[mchain[p].next].vnum;
  586.       op[op_idx][2] = mchain[mchain[p].prev].vnum;
  587.       op_idx++;
  588.     }
  589.       else            /* triangulate the polygon */
  590.     {
  591.       v = mchain[mchain[posmax].next].vnum;
  592.       if (_equal_to(&vert[v].pt, &ymin))
  593.         {            /* LHS is a single line */
  594.           triangulate_single_polygon(posmax, TRI_LHS, op);
  595.         }
  596.       else
  597.         triangulate_single_polygon(posmax, TRI_RHS, op);
  598.     }
  599.     }
  600.   
  601. #ifdef DEBUG
  602.   for (i = 0; i < (global.nseg - 2); i++)
  603.     fprintf(stderr, "tri #%d: (%d, %d, %d)\n", i, op[i][0], op[i][1],
  604.        op[i][2]);
  605. #endif
  606. }
  607.  
  608.  
  609. /* A greedy corner-cutting algorithm to triangulate a y-monotone 
  610.  * polygon in O(n) time.
  611.  * Joseph O-Rourke, Computational Geometry in C.
  612.  */
  613. int triangulate_single_polygon(posmax, side, op)
  614.      int posmax;
  615.      int side;
  616.      int op[][3];
  617. {
  618.   register int v;
  619.   int rc[SEGSIZE], ri = 0;    /* reflex chain */
  620.   int endv, tmp, vpos;
  621.   
  622.   if (side == TRI_RHS)        /* RHS segment is a single segment */
  623.     {
  624.       rc[0] = mchain[posmax].vnum;
  625.       tmp = mchain[posmax].next;
  626.       rc[1] = mchain[tmp].vnum;
  627.       ri = 1;
  628.       
  629.       vpos = mchain[tmp].next;
  630.       v = mchain[vpos].vnum;
  631.       
  632.       if ((endv = mchain[mchain[posmax].prev].vnum) == 0)
  633.     endv = global.nseg;
  634.     }
  635.   else                /* LHS is a single segment */
  636.     {
  637.       tmp = mchain[posmax].next;
  638.       rc[0] = mchain[tmp].vnum;
  639.       tmp = mchain[tmp].next;
  640.       rc[1] = mchain[tmp].vnum;
  641.       ri = 1;
  642.  
  643.       vpos = mchain[tmp].next;
  644.       v = mchain[vpos].vnum;
  645.  
  646.       endv = mchain[posmax].vnum;
  647.     }
  648.   
  649.   while ((v != endv) || (ri > 1))
  650.     {
  651.       if (ri > 0)        /* reflex chain is non-empty */
  652.     {
  653.       if (CROSS(vert[v].pt, vert[rc[ri - 1]].pt, 
  654.             vert[rc[ri]].pt) > 0)
  655.         {            /* convex corner: cut if off */
  656.           op[op_idx][0] = rc[ri - 1];
  657.           op[op_idx][1] = rc[ri];
  658.           op[op_idx][2] = v;
  659.           op_idx++;         
  660.           ri--;
  661.         }
  662.       else        /* non-convex */
  663.         {        /* add v to the chain */
  664.           ri++;
  665.           rc[ri] = v;
  666.           vpos = mchain[vpos].next;
  667.           v = mchain[vpos].vnum;
  668.         }
  669.     }
  670.       else            /* reflex-chain empty: add v to the */
  671.     {            /* reflex chain and advance it  */
  672.       rc[++ri] = v;
  673.       vpos = mchain[vpos].next;
  674.       v = mchain[vpos].vnum;
  675.     }
  676.     } /* end-while */
  677.   
  678.   /* reached the bottom vertex. Add in the triangle formed */
  679.   op[op_idx][0] = rc[ri - 1];
  680.   op[op_idx][1] = rc[ri];
  681.   op[op_idx][2] = v;
  682.   op_idx++;         
  683.   ri--;
  684.   
  685.   return 0;
  686. }
  687.  
  688.  
  689.