src/gpc.c

   1 /*
   2 ===========================================================================
   3
   4 Project:   Generic Polygon Clipper
   5
   6            A new algorithm for calculating the difference, intersection,
   7            exclusive-or or union of arbitrary polygon sets.
   8
   9 File:      gpc.c
  10 Author:    Alan Murta (email: gpc@cs.man.ac.uk)
  11 Version:   2.32
  12 Date:      17th December 2004
  13
  14 Copyright: (C) 1997-2004, Advanced Interfaces Group,
  15            University of Manchester.
  16
  17            This software is free for non-commercial use. It may be copied,
  18            modified, and redistributed provided that this copyright notice
  19            is preserved on all copies. The intellectual property rights of
  20            the algorithms used reside with the University of Manchester
  21            Advanced Interfaces Group.
  22
  23            You may not use this software, in whole or in part, in support
  24            of any commercial product without the express consent of the
  25            author.
  26
  27            There is no warranty or other guarantee of fitness of this
  28            software for any purpose. It is provided solely "as is".
  29
  30 ===========================================================================
  31 */
  32
  33
  34 /*
  35 ===========================================================================
  36                                 Includes
  37 ===========================================================================
  38 */
  39
  40 #include "gpc.h"
  41 #include <stdlib.h>
  42 #include <float.h>
  43 #include <math.h>
  44
  45
  46 /*
  47 ===========================================================================
  48                                 Constants
  49 ===========================================================================
  50 */
  51
  52 #ifndef TRUE
  53 #define FALSE              0
  54 #define TRUE               1
  55 #endif
  56
  57 #define LEFT               0
  58 #define RIGHT              1
  59
  60 #define ABOVE              0
  61 #define BELOW              1
  62
  63 #define CLIP               0
  64 #define SUBJ               1
  65
  66 #define INVERT_TRISTRIPS   FALSE
  67
  68
  69 /*
  70 ===========================================================================
  71                                  Macros
  72 ===========================================================================
  73 */
  74
  75 #define EQ(a, b)           (fabs((a) - (b)) <= GPC_EPSILON)
  76
  77 #define PREV_INDEX(i, n)   ((i - 1 + n) % n)
  78 #define NEXT_INDEX(i, n)   ((i + 1    ) % n)
  79
  80 #define OPTIMAL(v, i, n)   ((v[PREV_INDEX(i, n)].y != v[i].y) || \
  81                             (v[NEXT_INDEX(i, n)].y != v[i].y))
  82
  83 #define FWD_MIN(v, i, n)   ((v[PREV_INDEX(i, n)].vertex.y >= v[i].vertex.y) \
  84                          && (v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex.y))
  85
  86 #define NOT_FMAX(v, i, n)   (v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex.y)
  87
  88 #define REV_MIN(v, i, n)   ((v[PREV_INDEX(i, n)].vertex.y > v[i].vertex.y) \
  89                          && (v[NEXT_INDEX(i, n)].vertex.y >= v[i].vertex.y))
  90
  91 #define NOT_RMAX(v, i, n)   (v[PREV_INDEX(i, n)].vertex.y > v[i].vertex.y)
  92
  93 #define VERTEX(e,p,s,x,y)  {add_vertex(&((e)->outp[(p)]->v[(s)]), x, y); \
  94                             (e)->outp[(p)]->active++;}
  95
  96 #define P_EDGE(d,e,p,i,j)  {(d)= (e); \
  97                             do {(d)= (d)->prev;} while (!(d)->outp[(p)]); \
  98                             (i)= (d)->bot.x + (d)->dx * ((j)-(d)->bot.y);}
  99
 100 #define N_EDGE(d,e,p,i,j)  {(d)= (e); \
 101                             do {(d)= (d)->next;} while (!(d)->outp[(p)]); \
 102                             (i)= (d)->bot.x + (d)->dx * ((j)-(d)->bot.y);}
 103
 104 #define MALLOC(p, b, s, t) {if ((b) > 0) { \
 105                             p= (t*)malloc(b); if (!(p)) { \
 106                             fprintf(stderr, "gpc malloc failure: %s\n", s); \
 107                             exit(0);}} else p= NULL;}
 108
 109 #define FREE(p)            {if (p) {free(p); (p)= NULL;}}
 110
 111
 112 /*
 113 ===========================================================================
 114                             Private Data Types
 115 ===========================================================================
 116 */
 117
 118 typedef enum                        /* Edge intersection classes         */
 119 {
 120   NUL,                              /* Empty non-intersection            */
 121   EMX,                              /* External maximum                  */
 122   ELI,                              /* External left intermediate        */
 123   TED,                              /* Top edge                          */
 124   ERI,                              /* External right intermediate       */
 125   RED,                              /* Right edge                        */
 126   IMM,                              /* Internal maximum and minimum      */
 127   IMN,                              /* Internal minimum                  */
 128   EMN,                              /* External minimum                  */
 129   EMM,                              /* External maximum and minimum      */
 130   LED,                              /* Left edge                         */
 131   ILI,                              /* Internal left intermediate        */
 132   BED,                              /* Bottom edge                       */
 133   IRI,                              /* Internal right intermediate       */
 134   IMX,                              /* Internal maximum                  */
 135   FUL                               /* Full non-intersection             */
 136 } vertex_type;
 137
 138 typedef enum                        /* Horizontal edge states            */
 139 {
 140   NH,                               /* No horizontal edge                */
 141   BH,                               /* Bottom horizontal edge            */
 142   TH                                /* Top horizontal edge               */
 143 } h_state;
 144
 145 typedef enum                        /* Edge bundle state                 */
 146 {
 147   UNBUNDLED,                        /* Isolated edge not within a bundle */
 148   BUNDLE_HEAD,                      /* Bundle head node                  */
 149   BUNDLE_TAIL                       /* Passive bundle tail node          */
 150 } bundle_state;
 151
 152 typedef struct v_shape              /* Internal vertex list datatype     */
 153 {
 154   double              x;            /* X coordinate component            */
 155   double              y;            /* Y coordinate component            */
 156   struct v_shape     *next;         /* Pointer to next vertex in list    */
 157 } vertex_node;
 158
 159 typedef struct p_shape              /* Internal contour / tristrip type  */
 160 {
 161   int                 active;       /* Active flag / vertex count        */
 162   int                 hole;         /* Hole / external contour flag      */
 163   vertex_node        *v[2];         /* Left and right vertex list ptrs   */
 164   struct p_shape     *next;         /* Pointer to next polygon contour   */
 165   struct p_shape     *proxy;        /* Pointer to actual structure used  */
 166 } polygon_node;
 167
 168 typedef struct edge_shape
 169 {
 170   gpc_vertex          vertex;       /* Piggy-backed contour vertex data  */
 171   gpc_vertex          bot;          /* Edge lower (x, y) coordinate      */
 172   gpc_vertex          top;          /* Edge upper (x, y) coordinate      */
 173   double              xb;           /* Scanbeam bottom x coordinate      */
 174   double              xt;           /* Scanbeam top x coordinate         */
 175   double              dx;           /* Change in x for a unit y increase */
 176   int                 type;         /* Clip / subject edge flag          */
 177   int                 bundle[2][2]; /* Bundle edge flags                 */
 178   int                 bside[2];     /* Bundle left / right indicators    */
 179   bundle_state        bstate[2];    /* Edge bundle state                 */
 180   polygon_node       *outp[2];      /* Output polygon / tristrip pointer */
 181   struct edge_shape  *prev;         /* Previous edge in the AET          */
 182   struct edge_shape  *next;         /* Next edge in the AET              */
 183   struct edge_shape  *pred;         /* Edge connected at the lower end   */
 184   struct edge_shape  *succ;         /* Edge connected at the upper end   */
 185   struct edge_shape  *next_bound;   /* Pointer to next bound in LMT      */
 186 } edge_node;
 187
 188 typedef struct lmt_shape            /* Local minima table                */
 189 {
 190   double              y;            /* Y coordinate at local minimum     */
 191   edge_node          *first_bound;  /* Pointer to bound list             */
 192   struct lmt_shape   *next;         /* Pointer to next local minimum     */
 193 } lmt_node;
 194
 195 typedef struct sbt_t_shape          /* Scanbeam tree                     */
 196 {
 197   double              y;            /* Scanbeam node y value             */
 198   struct sbt_t_shape *less;         /* Pointer to nodes with lower y     */
 199   struct sbt_t_shape *more;         /* Pointer to nodes with higher y    */
 200 } sb_tree;
 201
 202 typedef struct it_shape             /* Intersection table                */
 203 {
 204   edge_node          *ie[2];        /* Intersecting edge (bundle) pair   */
 205   gpc_vertex          point;        /* Point of intersection             */
 206   struct it_shape    *next;         /* The next intersection table node  */
 207 } it_node;
 208
 209 typedef struct st_shape             /* Sorted edge table                 */
 210 {
 211   edge_node          *edge;         /* Pointer to AET edge               */
 212   double              xb;           /* Scanbeam bottom x coordinate      */
 213   double              xt;           /* Scanbeam top x coordinate         */
 214   double              dx;           /* Change in x for a unit y increase */
 215   struct st_shape    *prev;         /* Previous edge in sorted list      */
 216 } st_node;
 217
 218 typedef struct bbox_shape           /* Contour axis-aligned bounding box */
 219 {
 220   double             xmin;          /* Minimum x coordinate              */
 221   double             ymin;          /* Minimum y coordinate              */
 222   double             xmax;          /* Maximum x coordinate              */
 223   double             ymax;          /* Maximum y coordinate              */
 224 } bbox;
 225
 226
 227 /*
 228 ===========================================================================
 229                                Global Data
 230 ===========================================================================
 231 */
 232
 233 /* Horizontal edge state transitions within scanbeam boundary */
 234 const h_state next_h_state[3][6]=
 235 {
 236   /*        ABOVE     BELOW     CROSS */
 237   /*        L   R     L   R     L   R */
 238   /* NH */ {BH, TH,   TH, BH,   NH, NH},
 239   /* BH */ {NH, NH,   NH, NH,   TH, TH},
 240   /* TH */ {NH, NH,   NH, NH,   BH, BH}
 241 };
 242
 243
 244 /*
 245 ===========================================================================
 246                              Private Functions
 247 ===========================================================================
 248 */
 249
 250 static void reset_it(it_node **it)
 251 {
 252   it_node *itn;
 253
 254   while (*it)
 255   {
 256     itn= (*it)->next;
 257     FREE(*it);
 258     *it= itn;
 259   }
 260 }
 261
 262
 263 static void reset_lmt(lmt_node **lmt)
 264 {
 265   lmt_node *lmtn;
 266
 267   while (*lmt)
 268   {
 269     lmtn= (*lmt)->next;
 270     FREE(*lmt);
 271     *lmt= lmtn;
 272   }
 273 }
 274
 275
 276 static void insert_bound(edge_node **b, edge_node *e)
 277 {
 278   edge_node *existing_bound;
 279
 280   if (!*b)
 281   {
 282     /* Link node e to the tail of the list */
 283     *b= e;
 284   }
 285   else
 286   {
 287     /* Do primary sort on the x field */
 288     if (e[0].bot.x < (*b)[0].bot.x)
 289     {
 290       /* Insert a new node mid-list */
 291       existing_bound= *b;
 292       *b= e;
 293       (*b)->next_bound= existing_bound;
 294     }
 295     else
 296     {
 297       if (e[0].bot.x == (*b)[0].bot.x)
 298       {
 299         /* Do secondary sort on the dx field */
 300         if (e[0].dx < (*b)[0].dx)
 301         {
 302           /* Insert a new node mid-list */
 303           existing_bound= *b;
 304           *b= e;
 305           (*b)->next_bound= existing_bound;
 306         }
 307         else
 308         {
 309           /* Head further down the list */
 310           insert_bound(&((*b)->next_bound), e);
 311         }
 312       }
 313       else
 314       {
 315         /* Head further down the list */
 316         insert_bound(&((*b)->next_bound), e);
 317       }
 318     }
 319   }
 320 }
 321
 322
 323 static edge_node **bound_list(lmt_node **lmt, double y)
 324 {
 325   lmt_node *existing_node;
 326
 327   if (!*lmt)
 328   {
 329     /* Add node onto the tail end of the LMT */
 330     MALLOC(*lmt, sizeof(lmt_node), "LMT insertion", lmt_node);
 331     (*lmt)->y= y;
 332     (*lmt)->first_bound= NULL;
 333     (*lmt)->next= NULL;
 334     return &((*lmt)->first_bound);
 335   }
 336   else
 337     if (y < (*lmt)->y)
 338     {
 339       /* Insert a new LMT node before the current node */
 340       existing_node= *lmt;
 341       MALLOC(*lmt, sizeof(lmt_node), "LMT insertion", lmt_node);
 342       (*lmt)->y= y;
 343       (*lmt)->first_bound= NULL;
 344       (*lmt)->next= existing_node;
 345       return &((*lmt)->first_bound);
 346     }
 347     else
 348       if (y > (*lmt)->y)
 349         /* Head further up the LMT */
 350         return bound_list(&((*lmt)->next), y);
 351       else
 352         /* Use this existing LMT node */
 353         return &((*lmt)->first_bound);
 354 }
 355
 356
 357 static void add_to_sbtree(int *entries, sb_tree **sbtree, double y)
 358 {
 359   if (!*sbtree)
 360   {
 361     /* Add a new tree node here */
 362     MALLOC(*sbtree, sizeof(sb_tree), "scanbeam tree insertion", sb_tree);
 363     (*sbtree)->y= y;
 364     (*sbtree)->less= NULL;
 365     (*sbtree)->more= NULL;
 366     (*entries)++;
 367   }
 368   else
 369   {
 370     if ((*sbtree)->y > y)
 371     {
 372     /* Head into the 'less' sub-tree */
 373       add_to_sbtree(entries, &((*sbtree)->less), y);
 374     }
 375     else
 376     {
 377       if ((*sbtree)->y < y)
 378       {
 379         /* Head into the 'more' sub-tree */
 380         add_to_sbtree(entries, &((*sbtree)->more), y);
 381       }
 382     }
 383   }
 384 }
 385
 386
 387 static void build_sbt(int *entries, double *sbt, sb_tree *sbtree)
 388 {
 389   if (sbtree->less)
 390     build_sbt(entries, sbt, sbtree->less);
 391   sbt[*entries]= sbtree->y;
 392   (*entries)++;
 393   if (sbtree->more)
 394     build_sbt(entries, sbt, sbtree->more);
 395 }
 396
 397
 398 static void free_sbtree(sb_tree **sbtree)
 399 {
 400   if (*sbtree)
 401   {
 402     free_sbtree(&((*sbtree)->less));
 403     free_sbtree(&((*sbtree)->more));
 404     FREE(*sbtree);
 405   }
 406 }
 407
 408
 409 static int count_optimal_vertices(gpc_vertex_list c)
 410 {
 411   int result= 0, i;
 412
 413   /* Ignore non-contributing contours */
 414   if (c.num_vertices > 0)
 415   {
 416     for (i= 0; i < c.num_vertices; i++)
 417       /* Ignore superfluous vertices embedded in horizontal edges */
 418       if (OPTIMAL(c.vertex, i, c.num_vertices))
 419         result++;
 420   }
 421   return result;
 422 }
 423
 424
 425 static edge_node *build_lmt(lmt_node **lmt, sb_tree **sbtree,
 426                             int *sbt_entries, gpc_polygon *p, int type,
 427                             gpc_op op)
 428 {
 429   int          c, i, min, max, num_edges, v, num_vertices;
 430   int          total_vertices= 0, e_index=0;
 431   edge_node   *e, *edge_table;
 432
 433   for (c= 0; c < p->num_contours; c++)
 434     total_vertices+= count_optimal_vertices(p->contour[c]);
 435
 436   /* Create the entire input polygon edge table in one go */
 437   MALLOC(edge_table, total_vertices * sizeof(edge_node),
 438          "edge table creation", edge_node);
 439
 440   for (c= 0; c < p->num_contours; c++)
 441   {
 442     if (p->contour[c].num_vertices < 0)
 443     {
 444       /* Ignore the non-contributing contour and repair the vertex count */
 445       p->contour[c].num_vertices= -p->contour[c].num_vertices;
 446     }
 447     else
 448     {
 449       /* Perform contour optimisation */
 450       num_vertices= 0;
 451       for (i= 0; i < p->contour[c].num_vertices; i++)
 452         if (OPTIMAL(p->contour[c].vertex, i, p->contour[c].num_vertices))
 453         {
 454           edge_table[num_vertices].vertex.x= p->contour[c].vertex[i].x;
 455           edge_table[num_vertices].vertex.y= p->contour[c].vertex[i].y;
 456
 457           /* Record vertex in the scanbeam table */
 458           add_to_sbtree(sbt_entries, sbtree,
 459                         edge_table[num_vertices].vertex.y);
 460
 461           num_vertices++;
 462         }
 463
 464       /* Do the contour forward pass */
 465       for (min= 0; min < num_vertices; min++)
 466       {
 467         /* If a forward local minimum... */
 468         if (FWD_MIN(edge_table, min, num_vertices))
 469         {
 470           /* Search for the next local maximum... */
 471           num_edges= 1;
 472           max= NEXT_INDEX(min, num_vertices);
 473           while (NOT_FMAX(edge_table, max, num_vertices))
 474           {
 475             num_edges++;
 476             max= NEXT_INDEX(max, num_vertices);
 477           }
 478
 479           /* Build the next edge list */
 480           e= &edge_table[e_index];
 481           e_index+= num_edges;
 482           v= min;
 483           e[0].bstate[BELOW]= UNBUNDLED;
 484           e[0].bundle[BELOW][CLIP]= FALSE;
 485           e[0].bundle[BELOW][SUBJ]= FALSE;
 486           for (i= 0; i < num_edges; i++)
 487           {
 488             e[i].xb= edge_table[v].vertex.x;
 489             e[i].bot.x= edge_table[v].vertex.x;
 490             e[i].bot.y= edge_table[v].vertex.y;
 491
 492             v= NEXT_INDEX(v, num_vertices);
 493
 494             e[i].top.x= edge_table[v].vertex.x;
 495             e[i].top.y= edge_table[v].vertex.y;
 496             e[i].dx= (edge_table[v].vertex.x - e[i].bot.x) /
 497                        (e[i].top.y - e[i].bot.y);
 498             e[i].type= type;
 499             e[i].outp[ABOVE]= NULL;
 500             e[i].outp[BELOW]= NULL;
 501             e[i].next= NULL;
 502             e[i].prev= NULL;
 503             e[i].succ= ((num_edges > 1) && (i < (num_edges - 1))) ?
 504                        &(e[i + 1]) : NULL;
 505             e[i].pred= ((num_edges > 1) && (i > 0)) ? &(e[i - 1]) : NULL;
 506             e[i].next_bound= NULL;
 507             e[i].bside[CLIP]= (op == GPC_DIFF) ? RIGHT : LEFT;
 508             e[i].bside[SUBJ]= LEFT;
 509           }
 510           insert_bound(bound_list(lmt, edge_table[min].vertex.y), e);
 511         }
 512       }
 513
 514       /* Do the contour reverse pass */
 515       for (min= 0; min < num_vertices; min++)
 516       {
 517       /* If a reverse local minimum... */
 518         if (REV_MIN(edge_table, min, num_vertices))
 519         {
 520           /* Search for the previous local maximum... */
 521           num_edges= 1;
 522           max= PREV_INDEX(min, num_vertices);
 523           while (NOT_RMAX(edge_table, max, num_vertices))
 524           {
 525             num_edges++;
 526             max= PREV_INDEX(max, num_vertices);
 527           }
 528
 529           /* Build the previous edge list */
 530           e= &edge_table[e_index];
 531           e_index+= num_edges;
 532           v= min;
 533           e[0].bstate[BELOW]= UNBUNDLED;
 534           e[0].bundle[BELOW][CLIP]= FALSE;
 535           e[0].bundle[BELOW][SUBJ]= FALSE;
 536           for (i= 0; i < num_edges; i++)
 537           {
 538             e[i].xb= edge_table[v].vertex.x;
 539             e[i].bot.x= edge_table[v].vertex.x;
 540             e[i].bot.y= edge_table[v].vertex.y;
 541
 542             v= PREV_INDEX(v, num_vertices);
 543
 544             e[i].top.x= edge_table[v].vertex.x;
 545             e[i].top.y= edge_table[v].vertex.y;
 546             e[i].dx= (edge_table[v].vertex.x - e[i].bot.x) /
 547                        (e[i].top.y - e[i].bot.y);
 548             e[i].type= type;
 549             e[i].outp[ABOVE]= NULL;
 550             e[i].outp[BELOW]= NULL;
 551             e[i].next= NULL;
 552             e[i].prev= NULL;
 553             e[i].succ= ((num_edges > 1) && (i < (num_edges - 1))) ?
 554                        &(e[i + 1]) : NULL;
 555             e[i].pred= ((num_edges > 1) && (i > 0)) ? &(e[i - 1]) : NULL;
 556             e[i].next_bound= NULL;
 557             e[i].bside[CLIP]= (op == GPC_DIFF) ? RIGHT : LEFT;
 558             e[i].bside[SUBJ]= LEFT;
 559           }
 560           insert_bound(bound_list(lmt, edge_table[min].vertex.y), e);
 561         }
 562       }
 563     }
 564   }
 565   return edge_table;
 566 }
 567
 568
 569 static void add_edge_to_aet(edge_node **aet, edge_node *edge, edge_node *prev)
 570 {
 571   if (!*aet)
 572   {
 573     /* Append edge onto the tail end of the AET */
 574     *aet= edge;
 575     edge->prev= prev;
 576     edge->next= NULL;
 577   }
 578   else
 579   {
 580     /* Do primary sort on the xb field */
 581     if (edge->xb < (*aet)->xb)
 582     {
 583       /* Insert edge here (before the AET edge) */
 584       edge->prev= prev;
 585       edge->next= *aet;
 586       (*aet)->prev= edge;
 587       *aet= edge;
 588     }
 589     else
 590     {
 591       if (edge->xb == (*aet)->xb)
 592       {
 593         /* Do secondary sort on the dx field */
 594         if (edge->dx < (*aet)->dx)
 595         {
 596           /* Insert edge here (before the AET edge) */
 597           edge->prev= prev;
 598           edge->next= *aet;
 599           (*aet)->prev= edge;
 600           *aet= edge;
 601         }
 602         else
 603         {
 604           /* Head further into the AET */
 605           add_edge_to_aet(&((*aet)->next), edge, *aet);
 606         }
 607       }
 608       else
 609       {
 610         /* Head further into the AET */
 611         add_edge_to_aet(&((*aet)->next), edge, *aet);
 612       }
 613     }
 614   }
 615 }
 616
 617
 618 static void add_intersection(it_node **it, edge_node *edge0, edge_node *edge1,
 619                              double x, double y)
 620 {
 621   it_node *existing_node;
 622
 623   if (!*it)
 624   {
 625     /* Append a new node to the tail of the list */
 626     MALLOC(*it, sizeof(it_node), "IT insertion", it_node);
 627     (*it)->ie[0]= edge0;
 628     (*it)->ie[1]= edge1;
 629     (*it)->point.x= x;
 630     (*it)->point.y= y;
 631     (*it)->next= NULL;
 632   }
 633   else
 634   {
 635     if ((*it)->point.y > y)
 636     {
 637       /* Insert a new node mid-list */
 638       existing_node= *it;
 639       MALLOC(*it, sizeof(it_node), "IT insertion", it_node);
 640       (*it)->ie[0]= edge0;
 641       (*it)->ie[1]= edge1;
 642       (*it)->point.x= x;
 643       (*it)->point.y= y;
 644       (*it)->next= existing_node;
 645     }
 646     else
 647       /* Head further down the list */
 648       add_intersection(&((*it)->next), edge0, edge1, x, y);
 649   }
 650 }
 651
 652
 653 static void add_st_edge(st_node **st, it_node **it, edge_node *edge,
 654                         double dy)
 655 {
 656   st_node *existing_node;
 657   double   den, r, x, y;
 658
 659   if (!*st)
 660   {
 661     /* Append edge onto the tail end of the ST */
 662     MALLOC(*st, sizeof(st_node), "ST insertion", st_node);
 663     (*st)->edge= edge;
 664     (*st)->xb= edge->xb;
 665     (*st)->xt= edge->xt;
 666     (*st)->dx= edge->dx;
 667     (*st)->prev= NULL;
 668   }
 669   else
 670   {
 671     den= ((*st)->xt - (*st)->xb) - (edge->xt - edge->xb);
 672
 673     /* If new edge and ST edge don't cross */
 674     if ((edge->xt >= (*st)->xt) || (edge->dx == (*st)->dx) ||
 675         (fabs(den) <= DBL_EPSILON))
 676     {
 677       /* No intersection - insert edge here (before the ST edge) */
 678       existing_node= *st;
 679       MALLOC(*st, sizeof(st_node), "ST insertion", st_node);
 680       (*st)->edge= edge;
 681       (*st)->xb= edge->xb;
 682       (*st)->xt= edge->xt;
 683       (*st)->dx= edge->dx;
 684       (*st)->prev= existing_node;
 685     }
 686     else
 687     {
 688       /* Compute intersection between new edge and ST edge */
 689       r= (edge->xb - (*st)->xb) / den;
 690       x= (*st)->xb + r * ((*st)->xt - (*st)->xb);
 691       y= r * dy;
 692
 693       /* Insert the edge pointers and the intersection point in the IT */
 694       add_intersection(it, (*st)->edge, edge, x, y);
 695
 696       /* Head further into the ST */
 697       add_st_edge(&((*st)->prev), it, edge, dy);
 698     }
 699   }
 700 }
 701
 702
 703 static void build_intersection_table(it_node **it, edge_node *aet, double dy)
 704 {
 705   st_node   *st, *stp;
 706   edge_node *edge;
 707
 708   /* Build intersection table for the current scanbeam */
 709   reset_it(it);
 710   st= NULL;
 711
 712   /* Process each AET edge */
 713   for (edge= aet; edge; edge= edge->next)
 714   {
 715     if ((edge->bstate[ABOVE] == BUNDLE_HEAD) ||
 716          edge->bundle[ABOVE][CLIP] || edge->bundle[ABOVE][SUBJ])
 717       add_st_edge(&st, it, edge, dy);
 718   }
 719
 720   /* Free the sorted edge table */
 721   while (st)
 722   {
 723     stp= st->prev;
 724     FREE(st);
 725     st= stp;
 726   }
 727 }
 728
 729 static int count_contours(polygon_node *polygon)
 730 {
 731   int          nc, nv;
 732   vertex_node *v, *nextv;
 733
 734   for (nc= 0; polygon; polygon= polygon->next)
 735     if (polygon->active)
 736     {
 737       /* Count the vertices in the current contour */
 738       nv= 0;
 739       for (v= polygon->proxy->v[LEFT]; v; v= v->next)
 740         nv++;
 741
 742       /* Record valid vertex counts in the active field */
 743       if (nv > 2)
 744       {
 745         polygon->active= nv;
 746         nc++;
 747       }
 748       else
 749       {
 750         /* Invalid contour: just free the heap */
 751         for (v= polygon->proxy->v[LEFT]; v; v= nextv)
 752         {
 753           nextv= v->next;
 754           FREE(v);
 755         }
 756         polygon->active= 0;
 757       }
 758     }
 759   return nc;
 760 }
 761
 762
 763 static void add_left(polygon_node *p, double x, double y)
 764 {
 765   vertex_node *nv;
 766
 767   /* Create a new vertex node and set its fields */
 768   MALLOC(nv, sizeof(vertex_node), "vertex node creation", vertex_node);
 769   nv->x= x;
 770   nv->y= y;
 771
 772   /* Add vertex nv to the left end of the polygon's vertex list */
 773   nv->next= p->proxy->v[LEFT];
 774
 775   /* Update proxy->[LEFT] to point to nv */
 776   p->proxy->v[LEFT]= nv;
 777 }
 778
 779
 780 static void merge_left(polygon_node *p, polygon_node *q, polygon_node *list)
 781 {
 782   polygon_node *target;
 783
 784   /* Label contour as a hole */
 785   q->proxy->hole= TRUE;
 786
 787   if (p->proxy != q->proxy)
 788   {
 789     /* Assign p's vertex list to the left end of q's list */
 790     p->proxy->v[RIGHT]->next= q->proxy->v[LEFT];
 791     q->proxy->v[LEFT]= p->proxy->v[LEFT];
 792
 793     /* Redirect any p->proxy references to q->proxy */
 794
 795     for (target= p->proxy; list; list= list->next)
 796     {
 797       if (list->proxy == target)
 798       {
 799         list->active= FALSE;
 800         list->proxy= q->proxy;
 801       }
 802     }
 803   }
 804 }
 805
 806
 807 static void add_right(polygon_node *p, double x, double y)
 808 {
 809   vertex_node *nv;
 810
 811   /* Create a new vertex node and set its fields */
 812   MALLOC(nv, sizeof(vertex_node), "vertex node creation", vertex_node);
 813   nv->x= x;
 814   nv->y= y;
 815   nv->next= NULL;
 816
 817   /* Add vertex nv to the right end of the polygon's vertex list */
 818   p->proxy->v[RIGHT]->next= nv;
 819
 820   /* Update proxy->v[RIGHT] to point to nv */
 821   p->proxy->v[RIGHT]= nv;
 822 }
 823
 824
 825 static void merge_right(polygon_node *p, polygon_node *q, polygon_node *list)
 826 {
 827   polygon_node *target;
 828
 829   /* Label contour as external */
 830   q->proxy->hole= FALSE;
 831
 832   if (p->proxy != q->proxy)
 833   {
 834     /* Assign p's vertex list to the right end of q's list */
 835     q->proxy->v[RIGHT]->next= p->proxy->v[LEFT];
 836     q->proxy->v[RIGHT]= p->proxy->v[RIGHT];
 837
 838     /* Redirect any p->proxy references to q->proxy */
 839     for (target= p->proxy; list; list= list->next)
 840     {
 841       if (list->proxy == target)
 842       {
 843         list->active= FALSE;
 844         list->proxy= q->proxy;
 845       }
 846     }
 847   }
 848 }
 849
 850
 851 static void add_local_min(polygon_node **p, edge_node *edge,
 852                           double x, double y)
 853 {
 854   polygon_node *existing_min;
 855   vertex_node  *nv;
 856
 857   existing_min= *p;
 858
 859   MALLOC(*p, sizeof(polygon_node), "polygon node creation", polygon_node);
 860
 861   /* Create a new vertex node and set its fields */
 862   MALLOC(nv, sizeof(vertex_node), "vertex node creation", vertex_node);
 863   nv->x= x;
 864   nv->y= y;
 865   nv->next= NULL;
 866
 867   /* Initialise proxy to point to p itself */
 868   (*p)->proxy= (*p);
 869   (*p)->active= TRUE;
 870   (*p)->next= existing_min;
 871
 872   /* Make v[LEFT] and v[RIGHT] point to new vertex nv */
 873   (*p)->v[LEFT]= nv;
 874   (*p)->v[RIGHT]= nv;
 875
 876   /* Assign polygon p to the edge */
 877   edge->outp[ABOVE]= *p;
 878 }
 879
 880
 881 static int count_tristrips(polygon_node *tn)
 882 {
 883   int total;
 884
 885   for (total= 0; tn; tn= tn->next)
 886     if (tn->active > 2)
 887       total++;
 888   return total;
 889 }
 890
 891
 892 static void add_vertex(vertex_node **t, double x, double y)
 893 {
 894   if (!(*t))
 895   {
 896     MALLOC(*t, sizeof(vertex_node), "tristrip vertex creation", vertex_node);
 897     (*t)->x= x;
 898     (*t)->y= y;
 899     (*t)->next= NULL;
 900   }
 901   else
 902     /* Head further down the list */
 903     add_vertex(&((*t)->next), x, y);
 904 }
 905
 906
 907 static void new_tristrip(polygon_node **tn, edge_node *edge,
 908                          double x, double y)
 909 {
 910   if (!(*tn))
 911   {
 912     MALLOC(*tn, sizeof(polygon_node), "tristrip node creation", polygon_node);
 913     (*tn)->next= NULL;
 914     (*tn)->v[LEFT]= NULL;
 915     (*tn)->v[RIGHT]= NULL;
 916     (*tn)->active= 1;
 917     add_vertex(&((*tn)->v[LEFT]), x, y);
 918     edge->outp[ABOVE]= *tn;
 919   }
 920   else
 921     /* Head further down the list */
 922     new_tristrip(&((*tn)->next), edge, x, y);
 923 }
 924
 925
 926 static bbox *create_contour_bboxes(gpc_polygon *p)
 927 {
 928   bbox *box;
 929   int   c, v;
 930
 931   MALLOC(box, p->num_contours * sizeof(bbox), "Bounding box creation", bbox);
 932
 933   /* Construct contour bounding boxes */
 934   for (c= 0; c < p->num_contours; c++)
 935   {
 936     /* Initialise bounding box extent */
 937     box[c].xmin= DBL_MAX;
 938     box[c].ymin= DBL_MAX;
 939     box[c].xmax= -DBL_MAX;
 940     box[c].ymax= -DBL_MAX;
 941
 942     for (v= 0; v < p->contour[c].num_vertices; v++)
 943     {
 944       /* Adjust bounding box */
 945       if (p->contour[c].vertex[v].x < box[c].xmin)
 946         box[c].xmin= p->contour[c].vertex[v].x;
 947       if (p->contour[c].vertex[v].y < box[c].ymin)
 948         box[c].ymin= p->contour[c].vertex[v].y;
 949       if (p->contour[c].vertex[v].x > box[c].xmax)
 950         box[c].xmax= p->contour[c].vertex[v].x;
 951       if (p->contour[c].vertex[v].y > box[c].ymax)
 952           box[c].ymax= p->contour[c].vertex[v].y;
 953     }
 954   }
 955   return box;
 956 }
 957
 958
 959 static void minimax_test(gpc_polygon *subj, gpc_polygon *clip, gpc_op op)
 960 {
 961   bbox *s_bbox, *c_bbox;
 962   int   s, c, *o_table, overlap;
 963
 964   s_bbox= create_contour_bboxes(subj);
 965   c_bbox= create_contour_bboxes(clip);
 966
 967   MALLOC(o_table, subj->num_contours * clip->num_contours * sizeof(int),
 968          "overlap table creation", int);
 969
 970   /* Check all subject contour bounding boxes against clip boxes */
 971   for (s= 0; s < subj->num_contours; s++)
 972     for (c= 0; c < clip->num_contours; c++)
 973       o_table[c * subj->num_contours + s]=
 974              (!((s_bbox[s].xmax < c_bbox[c].xmin) ||
 975                 (s_bbox[s].xmin > c_bbox[c].xmax))) &&
 976              (!((s_bbox[s].ymax < c_bbox[c].ymin) ||
 977                 (s_bbox[s].ymin > c_bbox[c].ymax)));
 978
 979   /* For each clip contour, search for any subject contour overlaps */
 980   for (c= 0; c < clip->num_contours; c++)
 981   {
 982     overlap= 0;
 983     for (s= 0; (!overlap) && (s < subj->num_contours); s++)
 984       overlap= o_table[c * subj->num_contours + s];
 985
 986     if (!overlap)
 987       /* Flag non contributing status by negating vertex count */
 988       clip->contour[c].num_vertices = -clip->contour[c].num_vertices;
 989   }
 990
 991   if (op == GPC_INT)
 992   {
 993     /* For each subject contour, search for any clip contour overlaps */
 994     for (s= 0; s < subj->num_contours; s++)
 995     {
 996       overlap= 0;
 997       for (c= 0; (!overlap) && (c < clip->num_contours); c++)
 998         overlap= o_table[c * subj->num_contours + s];
 999
1000       if (!overlap)
1001         /* Flag non contributing status by negating vertex count */
1002         subj->contour[s].num_vertices = -subj->contour[s].num_vertices;
1003     }
1004   }
1005
1006   FREE(s_bbox);
1007   FREE(c_bbox);
1008   FREE(o_table);
1009 }
1010
1011
1012 /*
1013 ===========================================================================
1014                              Public Functions
1015 ===========================================================================
1016 */
1017
1018 void gpc_free_polygon(gpc_polygon *p)
1019 {
1020   int c;
1021
1022   for (c= 0; c < p->num_contours; c++)
1023     FREE(p->contour[c].vertex);
1024   FREE(p->hole);
1025   FREE(p->contour);
1026   p->num_contours= 0;
1027 }
1028
1029
1030 void gpc_read_polygon(FILE *fp, int read_hole_flags, gpc_polygon *p)
1031 {
1032   int c, v;
1033
1034   fscanf(fp, "%d", &(p->num_contours));
1035   MALLOC(p->hole, p->num_contours * sizeof(int),
1036          "hole flag array creation", int);
1037   MALLOC(p->contour, p->num_contours
1038          * sizeof(gpc_vertex_list), "contour creation", gpc_vertex_list);
1039   for (c= 0; c < p->num_contours; c++)
1040   {
1041     fscanf(fp, "%d", &(p->contour[c].num_vertices));
1042
1043     if (read_hole_flags)
1044       fscanf(fp, "%d", &(p->hole[c]));
1045     else
1046       p->hole[c]= FALSE; /* Assume all contours to be external */
1047
1048     MALLOC(p->contour[c].vertex, p->contour[c].num_vertices
1049            * sizeof(gpc_vertex), "vertex creation", gpc_vertex);
1050     for (v= 0; v < p->contour[c].num_vertices; v++)
1051       fscanf(fp, "%lf %lf", &(p->contour[c].vertex[v].x),
1052                             &(p->contour[c].vertex[v].y));
1053   }
1054 }
1055
1056
1057 void gpc_write_polygon(FILE *fp, int write_hole_flags, gpc_polygon *p)
1058 {
1059   int c, v;
1060
1061   fprintf(fp, "%d\n", p->num_contours);
1062   for (c= 0; c < p->num_contours; c++)
1063   {
1064     fprintf(fp, "%d\n", p->contour[c].num_vertices);
1065
1066     if (write_hole_flags)
1067       fprintf(fp, "%d\n", p->hole[c]);
1068
1069     for (v= 0; v < p->contour[c].num_vertices; v++)
1070       fprintf(fp, "% .*f % .*f\n",
1071               DBL_DIG, p->contour[c].vertex[v].x,
1072               DBL_DIG, p->contour[c].vertex[v].y);
1073   }
1074 }
1075
1076
1077 void gpc_add_contour(gpc_polygon *p, gpc_vertex_list *new_contour, int hole)
1078 {
1079   int             *extended_hole, c, v;
1080   gpc_vertex_list *extended_contour;
1081
1082   /* Create an extended hole array */
1083   MALLOC(extended_hole, (p->num_contours + 1)
1084          * sizeof(int), "contour hole addition", int);
1085
1086   /* Create an extended contour array */
1087   MALLOC(extended_contour, (p->num_contours + 1)
1088          * sizeof(gpc_vertex_list), "contour addition", gpc_vertex_list);
1089
1090   /* Copy the old contour and hole data into the extended arrays */
1091   for (c= 0; c < p->num_contours; c++)
1092   {
1093     extended_hole[c]= p->hole[c];
1094     extended_contour[c]= p->contour[c];
1095   }
1096
1097   /* Copy the new contour and hole onto the end of the extended arrays */
1098   c= p->num_contours;
1099   extended_hole[c]= hole;
1100   extended_contour[c].num_vertices= new_contour->num_vertices;
1101   MALLOC(extended_contour[c].vertex, new_contour->num_vertices
1102          * sizeof(gpc_vertex), "contour addition", gpc_vertex);
1103   for (v= 0; v < new_contour->num_vertices; v++)
1104     extended_contour[c].vertex[v]= new_contour->vertex[v];
1105
1106   /* Dispose of the old contour */
1107   FREE(p->contour);
1108   FREE(p->hole);
1109
1110   /* Update the polygon information */
1111   p->num_contours++;
1112   p->hole= extended_hole;
1113   p->contour= extended_contour;
1114 }
1115
1116
1117 void gpc_polygon_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip,
1118                       gpc_polygon *result)
1119 {
1120   sb_tree       *sbtree= NULL;
1121   it_node       *it= NULL, *intersect;
1122   edge_node     *edge, *prev_edge, *next_edge, *succ_edge, *e0, *e1;
1123   edge_node     *aet= NULL, *c_heap= NULL, *s_heap= NULL;
1124   lmt_node      *lmt= NULL, *local_min;
1125   polygon_node  *out_poly= NULL, *p, *q, *poly, *npoly, *cf= NULL;
1126   vertex_node   *vtx, *nv;
1127   h_state        horiz[2];
1128   int            in[2], exists[2], parity[2]= {LEFT, LEFT};
1129   int            c, v, contributing=0, search, scanbeam= 0, sbt_entries= 0;
1130   int            vclass, bl=0, br=0, tl=0, tr=0;
1131   double        *sbt= NULL, xb, px, yb, yt=0.0, dy=0.0, ix, iy;
1132
1133   /* Test for trivial NULL result cases */
1134   if (((subj->num_contours == 0) && (clip->num_contours == 0))
1135    || ((subj->num_contours == 0) && ((op == GPC_INT) || (op == GPC_DIFF)))
1136    || ((clip->num_contours == 0) &&  (op == GPC_INT)))
1137   {
1138     result->num_contours= 0;
1139     result->hole= NULL;
1140     result->contour= NULL;
1141     return;
1142   }
1143
1144   /* Identify potentialy contributing contours */
1145   if (((op == GPC_INT) || (op == GPC_DIFF))
1146    && (subj->num_contours > 0) && (clip->num_contours > 0))
1147     minimax_test(subj, clip, op);
1148
1149   /* Build LMT */
1150   if (subj->num_contours > 0)
1151     s_heap= build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op);
1152   if (clip->num_contours > 0)
1153     c_heap= build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op);
1154
1155   /* Return a NULL result if no contours contribute */
1156   if (lmt == NULL)
1157   {
1158     result->num_contours= 0;
1159     result->hole= NULL;
1160     result->contour= NULL;
1161     reset_lmt(&lmt);
1162     FREE(s_heap);
1163     FREE(c_heap);
1164     return;
1165   }
1166
1167   /* Build scanbeam table from scanbeam tree */
1168   MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation", double);
1169   build_sbt(&scanbeam, sbt, sbtree);
1170   scanbeam= 0;
1171   free_sbtree(&sbtree);
1172
1173   /* Allow pointer re-use without causing memory leak */
1174   if (subj == result)
1175     gpc_free_polygon(subj);
1176   if (clip == result)
1177     gpc_free_polygon(clip);
1178
1179   /* Invert clip polygon for difference operation */
1180   if (op == GPC_DIFF)
1181     parity[CLIP]= RIGHT;
1182
1183   local_min= lmt;
1184
1185   /* Process each scanbeam */
1186   while (scanbeam < sbt_entries)
1187   {
1188     /* Set yb and yt to the bottom and top of the scanbeam */
1189     yb= sbt[scanbeam++];
1190     if (scanbeam < sbt_entries)
1191     {
1192       yt= sbt[scanbeam];
1193       dy= yt - yb;
1194     }
1195
1196     /* === SCANBEAM BOUNDARY PROCESSING ================================ */
1197
1198     /* If LMT node corresponding to yb exists */
1199     if (local_min)
1200     {
1201       if (local_min->y == yb)
1202       {
1203         /* Add edges starting at this local minimum to the AET */
1204         for (edge= local_min->first_bound; edge; edge= edge->next_bound)
1205           add_edge_to_aet(&aet, edge, NULL);
1206
1207         local_min= local_min->next;
1208       }
1209     }
1210
1211     /* Set dummy previous x value */
1212     px= -DBL_MAX;
1213
1214     /* Create bundles within AET */
1215     e0= aet;
1216     e1= aet;
1217
1218     /* Set up bundle fields of first edge */
1219     aet->bundle[ABOVE][ aet->type]= (aet->top.y != yb);
1220     aet->bundle[ABOVE][!aet->type]= FALSE;
1221     aet->bstate[ABOVE]= UNBUNDLED;
1222
1223     for (next_edge= aet->next; next_edge; next_edge= next_edge->next)
1224     {
1225       /* Set up bundle fields of next edge */
1226       next_edge->bundle[ABOVE][ next_edge->type]= (next_edge->top.y != yb);
1227       next_edge->bundle[ABOVE][!next_edge->type]= FALSE;
1228       next_edge->bstate[ABOVE]= UNBUNDLED;
1229
1230       /* Bundle edges above the scanbeam boundary if they coincide */
1231       if (next_edge->bundle[ABOVE][next_edge->type])
1232       {
1233         if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx)
1234          && (e0->top.y != yb))
1235         {
1236           next_edge->bundle[ABOVE][ next_edge->type]^=
1237             e0->bundle[ABOVE][ next_edge->type];
1238           next_edge->bundle[ABOVE][!next_edge->type]=
1239             e0->bundle[ABOVE][!next_edge->type];
1240           next_edge->bstate[ABOVE]= BUNDLE_HEAD;
1241           e0->bundle[ABOVE][CLIP]= FALSE;
1242           e0->bundle[ABOVE][SUBJ]= FALSE;
1243           e0->bstate[ABOVE]= BUNDLE_TAIL;
1244         }
1245         e0= next_edge;
1246       }
1247     }
1248
1249     horiz[CLIP]= NH;
1250     horiz[SUBJ]= NH;
1251
1252     /* Process each edge at this scanbeam boundary */
1253     for (edge= aet; edge; edge= edge->next)
1254     {
1255       exists[CLIP]= edge->bundle[ABOVE][CLIP] +
1256                    (edge->bundle[BELOW][CLIP] << 1);
1257       exists[SUBJ]= edge->bundle[ABOVE][SUBJ] +
1258                    (edge->bundle[BELOW][SUBJ] << 1);
1259
1260       if (exists[CLIP] || exists[SUBJ])
1261       {
1262         /* Set bundle side */
1263         edge->bside[CLIP]= parity[CLIP];
1264         edge->bside[SUBJ]= parity[SUBJ];
1265
1266         /* Determine contributing status and quadrant occupancies */
1267         switch (op)
1268         {
1269         case GPC_DIFF:
1270         case GPC_INT:
1271           contributing= (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ]))
1272                      || (exists[SUBJ] && (parity[CLIP] || horiz[CLIP]))
1273                      || (exists[CLIP] && exists[SUBJ]
1274                      && (parity[CLIP] == parity[SUBJ]));
1275           br= (parity[CLIP])
1276            && (parity[SUBJ]);
1277           bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1278            && (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1279           tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1280            && (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1281           tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1282            && (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1283           break;
1284         case GPC_XOR:
1285           contributing= exists[CLIP] || exists[SUBJ];
1286           br= (parity[CLIP])
1287             ^ (parity[SUBJ]);
1288           bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1289             ^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1290           tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1291             ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1292           tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1293             ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1294           break;
1295         case GPC_UNION:
1296           contributing= (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ]))
1297                      || (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP]))
1298                      || (exists[CLIP] && exists[SUBJ]
1299                      && (parity[CLIP] == parity[SUBJ]));
1300           br= (parity[CLIP])
1301            || (parity[SUBJ]);
1302           bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1303            || (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1304           tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1305            || (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1306           tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1307            || (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1308           break;
1309         }
1310
1311         /* Update parity */
1312         parity[CLIP]^= edge->bundle[ABOVE][CLIP];
1313         parity[SUBJ]^= edge->bundle[ABOVE][SUBJ];
1314
1315         /* Update horizontal state */
1316         if (exists[CLIP])
1317           horiz[CLIP]=
1318             next_h_state[horiz[CLIP]]
1319                         [((exists[CLIP] - 1) << 1) + parity[CLIP]];
1320         if (exists[SUBJ])
1321           horiz[SUBJ]=
1322             next_h_state[horiz[SUBJ]]
1323                         [((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
1324
1325         vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
1326
1327         if (contributing)
1328         {
1329           xb= edge->xb;
1330
1331           switch (vclass)
1332           {
1333           case EMN:
1334           case IMN:
1335             add_local_min(&out_poly, edge, xb, yb);
1336             px= xb;
1337             cf= edge->outp[ABOVE];
1338             break;
1339           case ERI:
1340             if (xb != px)
1341             {
1342               add_right(cf, xb, yb);
1343               px= xb;
1344             }
1345             edge->outp[ABOVE]= cf;
1346             cf= NULL;
1347             break;
1348           case ELI:
1349             add_left(edge->outp[BELOW], xb, yb);
1350             px= xb;
1351             cf= edge->outp[BELOW];
1352             break;
1353           case EMX:
1354             if (xb != px)
1355             {
1356               add_left(cf, xb, yb);
1357               px= xb;
1358             }
1359             merge_right(cf, edge->outp[BELOW], out_poly);
1360             cf= NULL;
1361             break;
1362           case ILI:
1363             if (xb != px)
1364             {
1365               add_left(cf, xb, yb);
1366               px= xb;
1367             }
1368             edge->outp[ABOVE]= cf;
1369             cf= NULL;
1370             break;
1371           case IRI:
1372             add_right(edge->outp[BELOW], xb, yb);
1373             px= xb;
1374             cf= edge->outp[BELOW];
1375             edge->outp[BELOW]= NULL;
1376             break;
1377           case IMX:
1378             if (xb != px)
1379             {
1380               add_right(cf, xb, yb);
1381               px= xb;
1382             }
1383             merge_left(cf, edge->outp[BELOW], out_poly);
1384             cf= NULL;
1385             edge->outp[BELOW]= NULL;
1386             break;
1387           case IMM:
1388             if (xb != px)
1389             {
1390               add_right(cf, xb, yb);
1391               px= xb;
1392             }
1393             merge_left(cf, edge->outp[BELOW], out_poly);
1394             edge->outp[BELOW]= NULL;
1395             add_local_min(&out_poly, edge, xb, yb);
1396             cf= edge->outp[ABOVE];
1397             break;
1398           case EMM:
1399             if (xb != px)
1400             {
1401               add_left(cf, xb, yb);
1402               px= xb;
1403             }
1404             merge_right(cf, edge->outp[BELOW], out_poly);
1405             edge->outp[BELOW]= NULL;
1406             add_local_min(&out_poly, edge, xb, yb);
1407             cf= edge->outp[ABOVE];
1408             break;
1409           case LED:
1410             if (edge->bot.y == yb)
1411               add_left(edge->outp[BELOW], xb, yb);
1412             edge->outp[ABOVE]= edge->outp[BELOW];
1413             px= xb;
1414             break;
1415           case RED:
1416             if (edge->bot.y == yb)
1417               add_right(edge->outp[BELOW], xb, yb);
1418             edge->outp[ABOVE]= edge->outp[BELOW];
1419             px= xb;
1420             break;
1421           default:
1422             break;
1423           } /* End of switch */
1424         } /* End of contributing conditional */
1425       } /* End of edge exists conditional */
1426     } /* End of AET loop */
1427
1428     /* Delete terminating edges from the AET, otherwise compute xt */
1429     for (edge= aet; edge; edge= edge->next)
1430     {
1431       if (edge->top.y == yb)
1432       {
1433         prev_edge= edge->prev;
1434         next_edge= edge->next;
1435         if (prev_edge)
1436           prev_edge->next= next_edge;
1437         else
1438           aet= next_edge;
1439         if (next_edge)
1440           next_edge->prev= prev_edge;
1441
1442         /* Copy bundle head state to the adjacent tail edge if required */
1443         if ((edge->bstate[BELOW] == BUNDLE_HEAD) && prev_edge)
1444         {
1445           if (prev_edge->bstate[BELOW] == BUNDLE_TAIL)
1446           {
1447             prev_edge->outp[BELOW]= edge->outp[BELOW];
1448             prev_edge->bstate[BELOW]= UNBUNDLED;
1449             if (prev_edge->prev)
1450               if (prev_edge->prev->bstate[BELOW] == BUNDLE_TAIL)
1451                 prev_edge->bstate[BELOW]= BUNDLE_HEAD;
1452           }
1453         }
1454       }
1455       else
1456       {
1457         if (edge->top.y == yt)
1458           edge->xt= edge->top.x;
1459         else
1460           edge->xt= edge->bot.x + edge->dx * (yt - edge->bot.y);
1461       }
1462     }
1463
1464     if (scanbeam < sbt_entries)
1465     {
1466       /* === SCANBEAM INTERIOR PROCESSING ============================== */
1467
1468       build_intersection_table(&it, aet, dy);
1469
1470       /* Process each node in the intersection table */
1471       for (intersect= it; intersect; intersect= intersect->next)
1472       {
1473         e0= intersect->ie[0];
1474         e1= intersect->ie[1];
1475
1476         /* Only generate output for contributing intersections */
1477         if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ])
1478          && (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ]))
1479         {
1480           p= e0->outp[ABOVE];
1481           q= e1->outp[ABOVE];
1482           ix= intersect->point.x;
1483           iy= intersect->point.y + yb;
1484
1485           in[CLIP]= ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP])
1486                  || ( e1->bundle[ABOVE][CLIP] &&  e1->bside[CLIP])
1487                  || (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLIP]
1488                      && e0->bside[CLIP] && e1->bside[CLIP]);
1489           in[SUBJ]= ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ])
1490                  || ( e1->bundle[ABOVE][SUBJ] &&  e1->bside[SUBJ])
1491                  || (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUBJ]
1492                      && e0->bside[SUBJ] && e1->bside[SUBJ]);
1493
1494           /* Determine quadrant occupancies */
1495           switch (op)
1496           {
1497           case GPC_DIFF:
1498           case GPC_INT:
1499             tr= (in[CLIP])
1500              && (in[SUBJ]);
1501             tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
1502              && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
1503             br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
1504              && (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1505             bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
1506              && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1507             break;
1508           case GPC_XOR:
1509             tr= (in[CLIP])
1510               ^ (in[SUBJ]);
1511             tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
1512               ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
1513             br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
1514               ^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1515             bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
1516               ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1517             break;
1518           case GPC_UNION:
1519             tr= (in[CLIP])
1520              || (in[SUBJ]);
1521             tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
1522              || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
1523             br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
1524              || (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1525             bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
1526              || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1527             break;
1528           }
1529
1530           vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
1531
1532           switch (vclass)
1533           {
1534           case EMN:
1535             add_local_min(&out_poly, e0, ix, iy);
1536             e1->outp[ABOVE]= e0->outp[ABOVE];
1537             break;
1538           case ERI:
1539             if (p)
1540             {
1541               add_right(p, ix, iy);
1542               e1->outp[ABOVE]= p;
1543               e0->outp[ABOVE]= NULL;
1544             }
1545             break;
1546           case ELI:
1547             if (q)
1548             {
1549               add_left(q, ix, iy);
1550               e0->outp[ABOVE]= q;
1551               e1->outp[ABOVE]= NULL;
1552             }
1553             break;
1554           case EMX:
1555             if (p && q)
1556             {
1557               add_left(p, ix, iy);
1558               merge_right(p, q, out_poly);
1559               e0->outp[ABOVE]= NULL;
1560               e1->outp[ABOVE]= NULL;
1561             }
1562             break;
1563           case IMN:
1564             add_local_min(&out_poly, e0, ix, iy);
1565             e1->outp[ABOVE]= e0->outp[ABOVE];
1566             break;
1567           case ILI:
1568             if (p)
1569             {
1570               add_left(p, ix, iy);
1571               e1->outp[ABOVE]= p;
1572               e0->outp[ABOVE]= NULL;
1573             }
1574             break;
1575           case IRI:
1576             if (q)
1577             {
1578               add_right(q, ix, iy);
1579               e0->outp[ABOVE]= q;
1580               e1->outp[ABOVE]= NULL;
1581             }
1582             break;
1583           case IMX:
1584             if (p && q)
1585             {
1586               add_right(p, ix, iy);
1587               merge_left(p, q, out_poly);
1588               e0->outp[ABOVE]= NULL;
1589               e1->outp[ABOVE]= NULL;
1590             }
1591             break;
1592           case IMM:
1593             if (p && q)
1594             {
1595               add_right(p, ix, iy);
1596               merge_left(p, q, out_poly);
1597               add_local_min(&out_poly, e0, ix, iy);
1598               e1->outp[ABOVE]= e0->outp[ABOVE];
1599             }
1600             break;
1601           case EMM:
1602             if (p && q)
1603             {
1604               add_left(p, ix, iy);
1605               merge_right(p, q, out_poly);
1606               add_local_min(&out_poly, e0, ix, iy);
1607               e1->outp[ABOVE]= e0->outp[ABOVE];
1608             }
1609             break;
1610           default:
1611             break;
1612           } /* End of switch */
1613         } /* End of contributing intersection conditional */
1614
1615         /* Swap bundle sides in response to edge crossing */
1616         if (e0->bundle[ABOVE][CLIP])
1617           e1->bside[CLIP]= !e1->bside[CLIP];
1618         if (e1->bundle[ABOVE][CLIP])
1619           e0->bside[CLIP]= !e0->bside[CLIP];
1620         if (e0->bundle[ABOVE][SUBJ])
1621           e1->bside[SUBJ]= !e1->bside[SUBJ];
1622         if (e1->bundle[ABOVE][SUBJ])
1623           e0->bside[SUBJ]= !e0->bside[SUBJ];
1624
1625         /* Swap e0 and e1 bundles in the AET */
1626         prev_edge= e0->prev;
1627         next_edge= e1->next;
1628         if (next_edge)
1629           next_edge->prev= e0;
1630
1631         if (e0->bstate[ABOVE] == BUNDLE_HEAD)
1632         {
1633           search= TRUE;
1634           while (search)
1635           {
1636             prev_edge= prev_edge->prev;
1637             if (prev_edge)
1638             {
1639               if (prev_edge->bstate[ABOVE] != BUNDLE_TAIL)
1640                 search= FALSE;
1641             }
1642             else
1643               search= FALSE;
1644           }
1645         }
1646         if (!prev_edge)
1647         {
1648           aet->prev= e1;
1649           e1->next= aet;
1650           aet= e0->next;
1651         }
1652         else
1653         {
1654           prev_edge->next->prev= e1;
1655           e1->next= prev_edge->next;
1656           prev_edge->next= e0->next;
1657         }
1658         e0->next->prev= prev_edge;
1659         e1->next->prev= e1;
1660         e0->next= next_edge;
1661       } /* End of IT loop*/
1662
1663       /* Prepare for next scanbeam */
1664       for (edge= aet; edge; edge= next_edge)
1665       {
1666         next_edge= edge->next;
1667         succ_edge= edge->succ;
1668
1669         if ((edge->top.y == yt) && succ_edge)
1670         {
1671           /* Replace AET edge by its successor */
1672           succ_edge->outp[BELOW]= edge->outp[ABOVE];
1673           succ_edge->bstate[BELOW]= edge->bstate[ABOVE];
1674           succ_edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
1675           succ_edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
1676           prev_edge= edge->prev;
1677           if (prev_edge)
1678             prev_edge->next= succ_edge;
1679           else
1680             aet= succ_edge;
1681           if (next_edge)
1682             next_edge->prev= succ_edge;
1683           succ_edge->prev= prev_edge;
1684           succ_edge->next= next_edge;
1685         }
1686         else
1687         {
1688           /* Update this edge */
1689           edge->outp[BELOW]= edge->outp[ABOVE];
1690           edge->bstate[BELOW]= edge->bstate[ABOVE];
1691           edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
1692           edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
1693           edge->xb= edge->xt;
1694               }
1695         edge->outp[ABOVE]= NULL;
1696       }
1697     }
1698   } /* === END OF SCANBEAM PROCESSING ================================== */
1699
1700   /* Generate result polygon from out_poly */
1701   result->contour= NULL;
1702   result->hole= NULL;
1703   result->num_contours= count_contours(out_poly);
1704   if (result->num_contours > 0)
1705   {
1706     MALLOC(result->hole, result->num_contours
1707            * sizeof(int), "hole flag table creation", int);
1708     MALLOC(result->contour, result->num_contours
1709            * sizeof(gpc_vertex_list), "contour creation", gpc_vertex_list);
1710
1711     c= 0;
1712     for (poly= out_poly; poly; poly= npoly)
1713     {
1714       npoly= poly->next;
1715       if (poly->active)
1716       {
1717         result->hole[c]= poly->proxy->hole;
1718         result->contour[c].num_vertices= poly->active;
1719         MALLOC(result->contour[c].vertex,
1720           result->contour[c].num_vertices * sizeof(gpc_vertex),
1721           "vertex creation", gpc_vertex);
1722
1723         v= result->contour[c].num_vertices - 1;
1724         for (vtx= poly->proxy->v[LEFT]; vtx; vtx= nv)
1725         {
1726           nv= vtx->next;
1727           result->contour[c].vertex[v].x= vtx->x;
1728           result->contour[c].vertex[v].y= vtx->y;
1729           FREE(vtx);
1730           v--;
1731         }
1732         c++;
1733       }
1734       FREE(poly);
1735     }
1736   }
1737   else
1738   {
1739     for (poly= out_poly; poly; poly= npoly)
1740     {
1741       npoly= poly->next;
1742       FREE(poly);
1743     }
1744   }
1745
1746   /* Tidy up */
1747   reset_it(&it);
1748   reset_lmt(&lmt);
1749   FREE(c_heap);
1750   FREE(s_heap);
1751   FREE(sbt);
1752 }
1753
1754
1755 void gpc_free_tristrip(gpc_tristrip *t)
1756 {
1757   int s;
1758
1759   for (s= 0; s < t->num_strips; s++)
1760     FREE(t->strip[s].vertex);
1761   FREE(t->strip);
1762   t->num_strips= 0;
1763 }
1764
1765
1766 void gpc_polygon_to_tristrip(gpc_polygon *s, gpc_tristrip *t)
1767 {
1768   gpc_polygon c;
1769
1770   c.num_contours= 0;
1771   c.hole= NULL;
1772   c.contour= NULL;
1773   gpc_tristrip_clip(GPC_DIFF, s, &c, t);
1774 }
1775
1776
1777 void gpc_tristrip_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip,
1778                        gpc_tristrip *result)
1779 {
1780   sb_tree       *sbtree= NULL;
1781   it_node       *it= NULL, *intersect;
1782   edge_node     *edge, *prev_edge, *next_edge, *succ_edge, *e0, *e1;
1783   edge_node     *aet= NULL, *c_heap= NULL, *s_heap= NULL, *cf=NULL;
1784   lmt_node      *lmt= NULL, *local_min;
1785   polygon_node  *tlist= NULL, *tn, *tnn, *p, *q;
1786   vertex_node   *lt, *ltn, *rt, *rtn;
1787   h_state        horiz[2];
1788   vertex_type    cft=NUL;
1789   int            in[2], exists[2], parity[2]= {LEFT, LEFT};
1790   int            s, v, contributing=0, search, scanbeam= 0, sbt_entries= 0;
1791   int            vclass, bl=0, br=0, tl=0, tr=0;
1792   double        *sbt= NULL, xb, px, nx, yb, yt=0.0, dy=0.0, ix, iy;
1793
1794   /* Test for trivial NULL result cases */
1795   if (((subj->num_contours == 0) && (clip->num_contours == 0))
1796    || ((subj->num_contours == 0) && ((op == GPC_INT) || (op == GPC_DIFF)))
1797    || ((clip->num_contours == 0) &&  (op == GPC_INT)))
1798   {
1799     result->num_strips= 0;
1800     result->strip= NULL;
1801     return;
1802   }
1803
1804   /* Identify potentialy contributing contours */
1805   if (((op == GPC_INT) || (op == GPC_DIFF))
1806    && (subj->num_contours > 0) && (clip->num_contours > 0))
1807     minimax_test(subj, clip, op);
1808
1809   /* Build LMT */
1810   if (subj->num_contours > 0)
1811     s_heap= build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op);
1812   if (clip->num_contours > 0)
1813     c_heap= build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op);
1814
1815   /* Return a NULL result if no contours contribute */
1816   if (lmt == NULL)
1817   {
1818     result->num_strips= 0;
1819     result->strip= NULL;
1820     reset_lmt(&lmt);
1821     FREE(s_heap);
1822     FREE(c_heap);
1823     return;
1824   }
1825
1826   /* Build scanbeam table from scanbeam tree */
1827   MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation", double);
1828   build_sbt(&scanbeam, sbt, sbtree);
1829   scanbeam= 0;
1830   free_sbtree(&sbtree);
1831
1832   /* Invert clip polygon for difference operation */
1833   if (op == GPC_DIFF)
1834     parity[CLIP]= RIGHT;
1835
1836   local_min= lmt;
1837
1838   /* Process each scanbeam */
1839   while (scanbeam < sbt_entries)
1840   {
1841     /* Set yb and yt to the bottom and top of the scanbeam */
1842     yb= sbt[scanbeam++];
1843     if (scanbeam < sbt_entries)
1844     {
1845       yt= sbt[scanbeam];
1846       dy= yt - yb;
1847     }
1848
1849     /* === SCANBEAM BOUNDARY PROCESSING ================================ */
1850
1851     /* If LMT node corresponding to yb exists */
1852     if (local_min)
1853     {
1854       if (local_min->y == yb)
1855       {
1856         /* Add edges starting at this local minimum to the AET */
1857         for (edge= local_min->first_bound; edge; edge= edge->next_bound)
1858           add_edge_to_aet(&aet, edge, NULL);
1859
1860         local_min= local_min->next;
1861       }
1862     }
1863
1864     /* Set dummy previous x value */
1865     px= -DBL_MAX;
1866
1867     /* Create bundles within AET */
1868     e0= aet;
1869     e1= aet;
1870
1871     /* Set up bundle fields of first edge */
1872     aet->bundle[ABOVE][ aet->type]= (aet->top.y != yb);
1873     aet->bundle[ABOVE][!aet->type]= FALSE;
1874     aet->bstate[ABOVE]= UNBUNDLED;
1875
1876     for (next_edge= aet->next; next_edge; next_edge= next_edge->next)
1877     {
1878       /* Set up bundle fields of next edge */
1879       next_edge->bundle[ABOVE][ next_edge->type]= (next_edge->top.y != yb);
1880       next_edge->bundle[ABOVE][!next_edge->type]= FALSE;
1881       next_edge->bstate[ABOVE]= UNBUNDLED;
1882
1883       /* Bundle edges above the scanbeam boundary if they coincide */
1884       if (next_edge->bundle[ABOVE][next_edge->type])
1885       {
1886         if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx)
1887          && (e0->top.y != yb))
1888         {
1889           next_edge->bundle[ABOVE][ next_edge->type]^=
1890             e0->bundle[ABOVE][ next_edge->type];
1891           next_edge->bundle[ABOVE][!next_edge->type]=
1892             e0->bundle[ABOVE][!next_edge->type];
1893           next_edge->bstate[ABOVE]= BUNDLE_HEAD;
1894           e0->bundle[ABOVE][CLIP]= FALSE;
1895           e0->bundle[ABOVE][SUBJ]= FALSE;
1896           e0->bstate[ABOVE]= BUNDLE_TAIL;
1897         }
1898         e0= next_edge;
1899       }
1900     }
1901
1902     horiz[CLIP]= NH;
1903     horiz[SUBJ]= NH;
1904
1905     /* Process each edge at this scanbeam boundary */
1906     for (edge= aet; edge; edge= edge->next)
1907     {
1908       exists[CLIP]= edge->bundle[ABOVE][CLIP] +
1909                    (edge->bundle[BELOW][CLIP] << 1);
1910       exists[SUBJ]= edge->bundle[ABOVE][SUBJ] +
1911                    (edge->bundle[BELOW][SUBJ] << 1);
1912
1913       if (exists[CLIP] || exists[SUBJ])
1914       {
1915         /* Set bundle side */
1916         edge->bside[CLIP]= parity[CLIP];
1917         edge->bside[SUBJ]= parity[SUBJ];
1918
1919         /* Determine contributing status and quadrant occupancies */
1920         switch (op)
1921         {
1922         case GPC_DIFF:
1923         case GPC_INT:
1924           contributing= (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ]))
1925                      || (exists[SUBJ] && (parity[CLIP] || horiz[CLIP]))
1926                      || (exists[CLIP] && exists[SUBJ]
1927                      && (parity[CLIP] == parity[SUBJ]));
1928           br= (parity[CLIP])
1929            && (parity[SUBJ]);
1930           bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1931            && (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1932           tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1933            && (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1934           tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1935            && (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1936           break;
1937         case GPC_XOR:
1938           contributing= exists[CLIP] || exists[SUBJ];
1939           br= (parity[CLIP])
1940             ^ (parity[SUBJ]);
1941           bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1942             ^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1943           tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1944             ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1945           tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1946             ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1947           break;
1948         case GPC_UNION:
1949           contributing= (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ]))
1950                      || (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP]))
1951                      || (exists[CLIP] && exists[SUBJ]
1952                      && (parity[CLIP] == parity[SUBJ]));
1953           br= (parity[CLIP])
1954            || (parity[SUBJ]);
1955           bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1956            || (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1957           tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1958            || (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1959           tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1960            || (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1961           break;
1962         }
1963
1964         /* Update parity */
1965         parity[CLIP]^= edge->bundle[ABOVE][CLIP];
1966         parity[SUBJ]^= edge->bundle[ABOVE][SUBJ];
1967
1968         /* Update horizontal state */
1969         if (exists[CLIP])
1970           horiz[CLIP]=
1971             next_h_state[horiz[CLIP]]
1972                         [((exists[CLIP] - 1) << 1) + parity[CLIP]];
1973         if (exists[SUBJ])
1974           horiz[SUBJ]=
1975             next_h_state[horiz[SUBJ]]
1976                         [((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
1977
1978         vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
1979
1980         if (contributing)
1981         {
1982           xb= edge->xb;
1983
1984           switch (vclass)
1985           {
1986           case EMN:
1987             new_tristrip(&tlist, edge, xb, yb);
1988             cf= edge;
1989             break;
1990           case ERI:
1991             edge->outp[ABOVE]= cf->outp[ABOVE];
1992             if (xb != cf->xb)
1993               VERTEX(edge, ABOVE, RIGHT, xb, yb);
1994             cf= NULL;
1995             break;
1996           case ELI:
1997             VERTEX(edge, BELOW, LEFT, xb, yb);
1998             edge->outp[ABOVE]= NULL;
1999             cf= edge;
2000             break;
2001           case EMX:
2002             if (xb != cf->xb)
2003               VERTEX(edge, BELOW, RIGHT, xb, yb);
2004             edge->outp[ABOVE]= NULL;
2005             cf= NULL;
2006             break;
2007           case IMN:
2008             if (cft == LED)
2009             {
2010               if (cf->bot.y != yb)
2011                 VERTEX(cf, BELOW, LEFT, cf->xb, yb);
2012               new_tristrip(&tlist, cf, cf->xb, yb);
2013             }
2014             edge->outp[ABOVE]= cf->outp[ABOVE];
2015             VERTEX(edge, ABOVE, RIGHT, xb, yb);
2016             break;
2017           case ILI:
2018             new_tristrip(&tlist, edge, xb, yb);
2019             cf= edge;
2020             cft= ILI;
2021             break;
2022           case IRI:
2023             if (cft == LED)
2024             {
2025               if (cf->bot.y != yb)
2026                 VERTEX(cf, BELOW, LEFT, cf->xb, yb);
2027               new_tristrip(&tlist, cf, cf->xb, yb);
2028             }
2029             VERTEX(edge, BELOW, RIGHT, xb, yb);
2030             edge->outp[ABOVE]= NULL;
2031             break;
2032           case IMX:
2033             VERTEX(edge, BELOW, LEFT, xb, yb);
2034             edge->outp[ABOVE]= NULL;
2035             cft= IMX;
2036             break;
2037           case IMM:
2038             VERTEX(edge, BELOW, LEFT, xb, yb);
2039             edge->outp[ABOVE]= cf->outp[ABOVE];
2040             if (xb != cf->xb)
2041               VERTEX(cf, ABOVE, RIGHT, xb, yb);
2042             cf= edge;
2043             break;
2044           case EMM:
2045             VERTEX(edge, BELOW, RIGHT, xb, yb);
2046             edge->outp[ABOVE]= NULL;
2047             new_tristrip(&tlist, edge, xb, yb);
2048             cf= edge;
2049             break;
2050           case LED:
2051             if (edge->bot.y == yb)
2052               VERTEX(edge, BELOW, LEFT, xb, yb);
2053             edge->outp[ABOVE]= edge->outp[BELOW];
2054             cf= edge;
2055             cft= LED;
2056             break;
2057           case RED:
2058             edge->outp[ABOVE]= cf->outp[ABOVE];
2059             if (cft == LED)
2060             {
2061               if (cf->bot.y == yb)
2062               {
2063                 VERTEX(edge, BELOW, RIGHT, xb, yb);
2064               }
2065               else
2066               {
2067                 if (edge->bot.y == yb)
2068                 {
2069                   VERTEX(cf, BELOW, LEFT, cf->xb, yb);
2070                   VERTEX(edge, BELOW, RIGHT, xb, yb);
2071                 }
2072               }
2073             }
2074             else
2075             {
2076               VERTEX(edge, BELOW, RIGHT, xb, yb);
2077               VERTEX(edge, ABOVE, RIGHT, xb, yb);
2078             }
2079             cf= NULL;
2080             break;
2081           default:
2082             break;
2083           } /* End of switch */
2084         } /* End of contributing conditional */
2085       } /* End of edge exists conditional */
2086     } /* End of AET loop */
2087
2088     /* Delete terminating edges from the AET, otherwise compute xt */
2089     for (edge= aet; edge; edge= edge->next)
2090     {
2091       if (edge->top.y == yb)
2092       {
2093         prev_edge= edge->prev;
2094         next_edge= edge->next;
2095         if (prev_edge)
2096           prev_edge->next= next_edge;
2097         else
2098           aet= next_edge;
2099         if (next_edge)
2100           next_edge->prev= prev_edge;
2101
2102         /* Copy bundle head state to the adjacent tail edge if required */
2103         if ((edge->bstate[BELOW] == BUNDLE_HEAD) && prev_edge)
2104         {
2105           if (prev_edge->bstate[BELOW] == BUNDLE_TAIL)
2106           {
2107             prev_edge->outp[BELOW]= edge->outp[BELOW];
2108             prev_edge->bstate[BELOW]= UNBUNDLED;
2109             if (prev_edge->prev)
2110               if (prev_edge->prev->bstate[BELOW] == BUNDLE_TAIL)
2111                 prev_edge->bstate[BELOW]= BUNDLE_HEAD;
2112           }
2113         }
2114       }
2115       else
2116       {
2117         if (edge->top.y == yt)
2118           edge->xt= edge->top.x;
2119         else
2120           edge->xt= edge->bot.x + edge->dx * (yt - edge->bot.y);
2121       }
2122     }
2123
2124     if (scanbeam < sbt_entries)
2125     {
2126       /* === SCANBEAM INTERIOR PROCESSING ============================== */
2127
2128       build_intersection_table(&it, aet, dy);
2129
2130       /* Process each node in the intersection table */
2131       for (intersect= it; intersect; intersect= intersect->next)
2132       {
2133         e0= intersect->ie[0];
2134         e1= intersect->ie[1];
2135
2136         /* Only generate output for contributing intersections */
2137         if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ])
2138          && (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ]))
2139         {
2140           p= e0->outp[ABOVE];
2141           q= e1->outp[ABOVE];
2142           ix= intersect->point.x;
2143           iy= intersect->point.y + yb;
2144
2145           in[CLIP]= ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP])
2146                  || ( e1->bundle[ABOVE][CLIP] &&  e1->bside[CLIP])
2147                  || (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLIP]
2148                      && e0->bside[CLIP] && e1->bside[CLIP]);
2149           in[SUBJ]= ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ])
2150                  || ( e1->bundle[ABOVE][SUBJ] &&  e1->bside[SUBJ])
2151                  || (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUBJ]
2152                      && e0->bside[SUBJ] && e1->bside[SUBJ]);
2153
2154           /* Determine quadrant occupancies */
2155           switch (op)
2156           {
2157           case GPC_DIFF:
2158           case GPC_INT:
2159             tr= (in[CLIP])
2160              && (in[SUBJ]);
2161             tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
2162              && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
2163             br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
2164              && (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2165             bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
2166              && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2167             break;
2168           case GPC_XOR:
2169             tr= (in[CLIP])
2170               ^ (in[SUBJ]);
2171             tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
2172               ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
2173             br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
2174               ^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2175             bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
2176               ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2177             break;
2178           case GPC_UNION:
2179             tr= (in[CLIP])
2180              || (in[SUBJ]);
2181             tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
2182              || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
2183             br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
2184              || (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2185             bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
2186              || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2187             break;
2188           }
2189
2190           vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
2191
2192           switch (vclass)
2193           {
2194           case EMN:
2195             new_tristrip(&tlist, e1, ix, iy);
2196             e0->outp[ABOVE]= e1->outp[ABOVE];
2197             break;
2198           case ERI:
2199             if (p)
2200             {
2201               P_EDGE(prev_edge, e0, ABOVE, px, iy);
2202               VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2203               VERTEX(e0, ABOVE, RIGHT, ix, iy);
2204               e1->outp[ABOVE]= e0->outp[ABOVE];
2205               e0->outp[ABOVE]= NULL;
2206             }
2207             break;
2208           case ELI:
2209             if (q)
2210             {
2211               N_EDGE(next_edge, e1, ABOVE, nx, iy);
2212               VERTEX(e1, ABOVE, LEFT, ix, iy);
2213               VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2214               e0->outp[ABOVE]= e1->outp[ABOVE];
2215               e1->outp[ABOVE]= NULL;
2216             }
2217             break;
2218           case EMX:
2219             if (p && q)
2220             {
2221               VERTEX(e0, ABOVE, LEFT, ix, iy);
2222               e0->outp[ABOVE]= NULL;
2223               e1->outp[ABOVE]= NULL;
2224             }
2225             break;
2226           case IMN:
2227             P_EDGE(prev_edge, e0, ABOVE, px, iy);
2228             VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2229             N_EDGE(next_edge, e1, ABOVE, nx, iy);
2230             VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2231             new_tristrip(&tlist, prev_edge, px, iy);
2232             e1->outp[ABOVE]= prev_edge->outp[ABOVE];
2233             VERTEX(e1, ABOVE, RIGHT, ix, iy);
2234             new_tristrip(&tlist, e0, ix, iy);
2235             next_edge->outp[ABOVE]= e0->outp[ABOVE];
2236             VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2237             break;
2238           case ILI:
2239             if (p)
2240             {
2241               VERTEX(e0, ABOVE, LEFT, ix, iy);
2242               N_EDGE(next_edge, e1, ABOVE, nx, iy);
2243               VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2244               e1->outp[ABOVE]= e0->outp[ABOVE];
2245               e0->outp[ABOVE]= NULL;
2246             }
2247             break;
2248           case IRI:
2249             if (q)
2250             {
2251               VERTEX(e1, ABOVE, RIGHT, ix, iy);
2252               P_EDGE(prev_edge, e0, ABOVE, px, iy);
2253               VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2254               e0->outp[ABOVE]= e1->outp[ABOVE];
2255               e1->outp[ABOVE]= NULL;
2256             }
2257             break;
2258           case IMX:
2259             if (p && q)
2260             {
2261               VERTEX(e0, ABOVE, RIGHT, ix, iy);
2262               VERTEX(e1, ABOVE, LEFT, ix, iy);
2263               e0->outp[ABOVE]= NULL;
2264               e1->outp[ABOVE]= NULL;
2265               P_EDGE(prev_edge, e0, ABOVE, px, iy);
2266               VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2267               new_tristrip(&tlist, prev_edge, px, iy);
2268               N_EDGE(next_edge, e1, ABOVE, nx, iy);
2269               VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2270               next_edge->outp[ABOVE]= prev_edge->outp[ABOVE];
2271               VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2272             }
2273             break;
2274           case IMM:
2275             if (p && q)
2276             {
2277               VERTEX(e0, ABOVE, RIGHT, ix, iy);
2278               VERTEX(e1, ABOVE, LEFT, ix, iy);
2279               P_EDGE(prev_edge, e0, ABOVE, px, iy);
2280               VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2281               new_tristrip(&tlist, prev_edge, px, iy);
2282               N_EDGE(next_edge, e1, ABOVE, nx, iy);
2283               VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2284               e1->outp[ABOVE]= prev_edge->outp[ABOVE];
2285               VERTEX(e1, ABOVE, RIGHT, ix, iy);
2286               new_tristrip(&tlist, e0, ix, iy);
2287               next_edge->outp[ABOVE]= e0->outp[ABOVE];
2288               VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2289             }
2290             break;
2291           case EMM:
2292             if (p && q)
2293             {
2294               VERTEX(e0, ABOVE, LEFT, ix, iy);
2295               new_tristrip(&tlist, e1, ix, iy);
2296               e0->outp[ABOVE]= e1->outp[ABOVE];
2297             }
2298             break;
2299           default:
2300             break;
2301           } /* End of switch */
2302         } /* End of contributing intersection conditional */
2303
2304         /* Swap bundle sides in response to edge crossing */
2305         if (e0->bundle[ABOVE][CLIP])
2306           e1->bside[CLIP]= !e1->bside[CLIP];
2307         if (e1->bundle[ABOVE][CLIP])
2308           e0->bside[CLIP]= !e0->bside[CLIP];
2309         if (e0->bundle[ABOVE][SUBJ])
2310           e1->bside[SUBJ]= !e1->bside[SUBJ];
2311         if (e1->bundle[ABOVE][SUBJ])
2312           e0->bside[SUBJ]= !e0->bside[SUBJ];
2313
2314         /* Swap e0 and e1 bundles in the AET */
2315         prev_edge= e0->prev;
2316         next_edge= e1->next;
2317         if (e1->next)
2318           e1->next->prev= e0;
2319
2320         if (e0->bstate[ABOVE] == BUNDLE_HEAD)
2321         {
2322           search= TRUE;
2323           while (search)
2324           {
2325             prev_edge= prev_edge->prev;
2326             if (prev_edge)
2327             {
2328               if (prev_edge->bundle[ABOVE][CLIP]
2329                || prev_edge->bundle[ABOVE][SUBJ]
2330                || (prev_edge->bstate[ABOVE] == BUNDLE_HEAD))
2331                 search= FALSE;
2332             }
2333             else
2334               search= FALSE;
2335           }
2336         }
2337         if (!prev_edge)
2338         {
2339            e1->next= aet;
2340            aet= e0->next;
2341         }
2342         else
2343         {
2344           e1->next= prev_edge->next;
2345           prev_edge->next= e0->next;
2346         }
2347         e0->next->prev= prev_edge;
2348         e1->next->prev= e1;
2349         e0->next= next_edge;
2350       } /* End of IT loop*/
2351
2352       /* Prepare for next scanbeam */
2353       for (edge= aet; edge; edge= next_edge)
2354       {
2355         next_edge= edge->next;
2356         succ_edge= edge->succ;
2357
2358         if ((edge->top.y == yt) && succ_edge)
2359         {
2360           /* Replace AET edge by its successor */
2361           succ_edge->outp[BELOW]= edge->outp[ABOVE];
2362           succ_edge->bstate[BELOW]= edge->bstate[ABOVE];
2363           succ_edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
2364           succ_edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
2365           prev_edge= edge->prev;
2366           if (prev_edge)
2367             prev_edge->next= succ_edge;
2368           else
2369             aet= succ_edge;
2370           if (next_edge)
2371             next_edge->prev= succ_edge;
2372           succ_edge->prev= prev_edge;
2373           succ_edge->next= next_edge;
2374         }
2375         else
2376         {
2377           /* Update this edge */
2378           edge->outp[BELOW]= edge->outp[ABOVE];
2379           edge->bstate[BELOW]= edge->bstate[ABOVE];
2380           edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
2381           edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
2382           edge->xb= edge->xt;
2383         }
2384         edge->outp[ABOVE]= NULL;
2385       }
2386     }
2387   } /* === END OF SCANBEAM PROCESSING ================================== */
2388
2389   /* Generate result tristrip from tlist */
2390   result->strip= NULL;
2391   result->num_strips= count_tristrips(tlist);
2392   if (result->num_strips > 0)
2393   {
2394     MALLOC(result->strip, result->num_strips * sizeof(gpc_vertex_list),
2395            "tristrip list creation", gpc_vertex_list);
2396
2397     s= 0;
2398     for (tn= tlist; tn; tn= tnn)
2399     {
2400       tnn= tn->next;
2401
2402       if (tn->active > 2)
2403       {
2404         /* Valid tristrip: copy the vertices and free the heap */
2405         result->strip[s].num_vertices= tn->active;
2406         MALLOC(result->strip[s].vertex, tn->active * sizeof(gpc_vertex),
2407                "tristrip creation", gpc_vertex);
2408         v= 0;
2409         if (INVERT_TRISTRIPS)
2410         {
2411           lt= tn->v[RIGHT];
2412           rt= tn->v[LEFT];
2413         }
2414         else
2415         {
2416           lt= tn->v[LEFT];
2417           rt= tn->v[RIGHT];
2418         }
2419         while (lt || rt)
2420         {
2421           if (lt)
2422           {
2423             ltn= lt->next;
2424             result->strip[s].vertex[v].x= lt->x;
2425             result->strip[s].vertex[v].y= lt->y;
2426             v++;
2427             FREE(lt);
2428             lt= ltn;
2429           }
2430           if (rt)
2431           {
2432             rtn= rt->next;
2433             result->strip[s].vertex[v].x= rt->x;
2434             result->strip[s].vertex[v].y= rt->y;
2435             v++;
2436             FREE(rt);
2437             rt= rtn;
2438           }
2439         }
2440         s++;
2441       }
2442       else
2443       {
2444         /* Invalid tristrip: just free the heap */
2445         for (lt= tn->v[LEFT]; lt; lt= ltn)
2446         {
2447           ltn= lt->next;
2448           FREE(lt);
2449         }
2450         for (rt= tn->v[RIGHT]; rt; rt=rtn)
2451         {
2452           rtn= rt->next;
2453           FREE(rt);
2454         }
2455       }
2456       FREE(tn);
2457     }
2458   }
2459
2460   /* Tidy up */
2461   reset_it(&it);
2462   reset_lmt(&lmt);
2463   FREE(c_heap);
2464   FREE(s_heap);
2465   FREE(sbt);
2466 }
2467
2468 /*
2469 ===========================================================================
2470                            End of file: gpc.c
2471 ===========================================================================
2472 */