1/*
2===========================================================================
3
4Project:   Generic Polygon Clipper
5
6           A new algorithm for calculating the difference, intersection,
7           exclusive-or or union of arbitrary polygon sets.
8
9File:      gpc.c
10Author:    Alan Murta (email: gpc@cs.man.ac.uk)
11Version:   2.32
12Date:      17th December 2004
13
14Copyright: (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
118typedef 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
138typedef enum                        /* Horizontal edge states            */
139{
140  NH,                               /* No horizontal edge                */
141  BH,                               /* Bottom horizontal edge            */
142  TH                                /* Top horizontal edge               */
143} h_state;
144
145typedef 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
152typedef 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
159typedef 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
168typedef 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
188typedef 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
195typedef 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
202typedef 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
209typedef 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
218typedef 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 */
234const 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
250static 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
263static 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
276static 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
323static 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
357static 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
387static 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
398static 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
409static 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
425static 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
569static 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
618static 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
653static 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
703static 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
729static 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
763static 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
780static 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
807static 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
825static 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
851static 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
881static 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
892static 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
907static 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
926static 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
959static 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
1018void 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
1030void 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
1057void 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, "% .*lf % .*lf\n",
1071              DBL_DIG, p->contour[c].vertex[v].x,
1072              DBL_DIG, p->contour[c].vertex[v].y);
1073  }
1074}
1075
1076
1077void 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
1117void 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, search, scanbeam= 0, sbt_entries= 0;
1130  int            vclass, bl, br, tl, tr;
1131  double        *sbt= NULL, xb, px, yb, yt, dy, 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
1755void 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
1766void 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
1777void 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;
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;
1789  int            in[2], exists[2], parity[2]= {LEFT, LEFT};
1790  int            s, v, contributing, search, scanbeam= 0, sbt_entries= 0;
1791  int            vclass, bl, br, tl, tr;
1792  double        *sbt= NULL, xb, px, nx, yb, yt, dy, 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*/
2473