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

octovis
Author(s): Kai M. Wurm , Armin Hornung
autogenerated on Wed Jun 5 2019 19:26:39