WorldSim - 1.4.5

Utilities Configuration GA
NNFW WorldSim Total 99% Experiments
gpc.cpp
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-2013 Gilles Debunne. All rights reserved.
26 
27  This file is part of the QGLViewer library version 2.5.2.
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, i;
470 
471  /* Ignore non-contributing contours */
472  if (c.num_vertices > 0)
473  {
474  for (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 c, 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 (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 (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 c, v;
1005 
1006  MALLOC(box, p->num_contours * sizeof(bbox), "Bounding box creation", bbox);
1007 
1008  /* Construct contour bounding boxes */
1009  for (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 s, c, *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 (s= 0; s < subj->num_contours; s++)
1047  for (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 (c= 0; c < clip->num_contours; c++)
1056  {
1057  overlap= 0;
1058  for (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 (s= 0; s < subj->num_contours; s++)
1070  {
1071  overlap= 0;
1072  for (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  int c;
1096 
1097  for (c= 0; c < p->num_contours; c++)
1098  FREE(p->contour[c].vertex);
1099  FREE(p->hole);
1100  FREE(p->contour);
1101  p->num_contours= 0;
1102 }
1103 
1104 /* Unused and fscanf creates compilation warnings
1105 void gpc_read_polygon(FILE *fp, int read_hole_flags, gpc_polygon *p)
1106 {
1107  int c, v;
1108 
1109  fscanf(fp, "%d", &(p->num_contours));
1110  MALLOC(p->hole, p->num_contours * sizeof(int),
1111  "hole flag array creation", int);
1112  MALLOC(p->contour, p->num_contours
1113  * sizeof(gpc_vertex_list), "contour creation", gpc_vertex_list);
1114  for (c= 0; c < p->num_contours; c++)
1115  {
1116  fscanf(fp, "%d", &(p->contour[c].num_vertices));
1117 
1118  if (read_hole_flags)
1119  fscanf(fp, "%d", &(p->hole[c]));
1120  else
1121  p->hole[c]= FALSE; // Assume all contours to be external
1122 
1123  MALLOC(p->contour[c].vertex, p->contour[c].num_vertices
1124  * sizeof(gpc_vertex), "vertex creation", gpc_vertex);
1125  for (v= 0; v < p->contour[c].num_vertices; v++)
1126  fscanf(fp, "%lf %lf", &(p->contour[c].vertex[v].x),
1127  &(p->contour[c].vertex[v].y));
1128  }
1129 }
1130 */
1131 
1132 void gpc_write_polygon(FILE *fp, int write_hole_flags, gpc_polygon *p)
1133 {
1134  int c, v;
1135 
1136  fprintf(fp, "%d\n", p->num_contours);
1137  for (c= 0; c < p->num_contours; c++)
1138  {
1139  fprintf(fp, "%d\n", p->contour[c].num_vertices);
1140 
1141  if (write_hole_flags)
1142  fprintf(fp, "%d\n", p->hole[c]);
1143 
1144  for (v= 0; v < p->contour[c].num_vertices; v++)
1145  fprintf(fp, "% .*lf % .*lf\n",
1146  DBL_DIG, p->contour[c].vertex[v].x,
1147  DBL_DIG, p->contour[c].vertex[v].y);
1148  }
1149 }
1150 
1151 
1152 void gpc_add_contour(gpc_polygon *p, gpc_vertex_list *new_contour, int hole)
1153 {
1154  int *extended_hole, c, v;
1155  gpc_vertex_list *extended_contour;
1156 
1157  /* Create an extended hole array */
1158  MALLOC(extended_hole, (p->num_contours + 1)
1159  * sizeof(int), "contour hole addition", int);
1160 
1161  /* Create an extended contour array */
1162  MALLOC(extended_contour, (p->num_contours + 1)
1163  * sizeof(gpc_vertex_list), "contour addition", gpc_vertex_list);
1164 
1165  /* Copy the old contour and hole data into the extended arrays */
1166  for (c= 0; c < p->num_contours; c++)
1167  {
1168  extended_hole[c]= p->hole[c];
1169  extended_contour[c]= p->contour[c];
1170  }
1171 
1172  /* Copy the new contour and hole onto the end of the extended arrays */
1173  c= p->num_contours;
1174  extended_hole[c]= hole;
1175  extended_contour[c].num_vertices= new_contour->num_vertices;
1176  MALLOC(extended_contour[c].vertex, new_contour->num_vertices
1177  * sizeof(gpc_vertex), "contour addition", gpc_vertex);
1178  for (v= 0; v < new_contour->num_vertices; v++)
1179  extended_contour[c].vertex[v]= new_contour->vertex[v];
1180 
1181  /* Dispose of the old contour */
1182  FREE(p->contour);
1183  FREE(p->hole);
1184 
1185  /* Update the polygon information */
1186  p->num_contours++;
1187  p->hole= extended_hole;
1188  p->contour= extended_contour;
1189 }
1190 
1191 
1192 void gpc_polygon_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip,
1193  gpc_polygon *result)
1194 {
1195  sb_tree *sbtree= NULL;
1196  it_node *it= NULL, *intersect=0;
1197  edge_node *edge=0, *prev_edge=0, *next_edge=0, *succ_edge=0, *e0=0, *e1=0;
1198  edge_node *aet= NULL, *c_heap= NULL, *s_heap= NULL;
1199  lmt_node *lmt= NULL, *local_min=0;
1200  polygon_node *out_poly= NULL, *p=0, *q=0, *poly=0, *npoly=0, *cf= NULL;
1201  vertex_node *vtx=0, *nv=0;
1202  h_state horiz[2];
1203  int in[2], exists[2], parity[2]= {LEFT, LEFT};
1204  int c, v, contributing=0, search, scanbeam= 0, sbt_entries= 0;
1205  int vclass=0, bl=0, br=0, tl=0, tr=0;
1206  double *sbt= NULL, xb, px, yb, yt=0.0, dy=0.0, ix, iy;
1207 
1208  /* Test for trivial NULL result cases */
1209  if (((subj->num_contours == 0) && (clip->num_contours == 0))
1210  || ((subj->num_contours == 0) && ((op == GPC_INT) || (op == GPC_DIFF)))
1211  || ((clip->num_contours == 0) && (op == GPC_INT)))
1212  {
1213  result->num_contours= 0;
1214  result->hole= NULL;
1215  result->contour= NULL;
1216  return;
1217  }
1218 
1219  /* Identify potentialy contributing contours */
1220  if (((op == GPC_INT) || (op == GPC_DIFF))
1221  && (subj->num_contours > 0) && (clip->num_contours > 0))
1222  minimax_test(subj, clip, op);
1223 
1224  /* Build LMT */
1225  if (subj->num_contours > 0)
1226  s_heap= build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op);
1227  if (clip->num_contours > 0)
1228  c_heap= build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op);
1229 
1230  /* Return a NULL result if no contours contribute */
1231  if (lmt == NULL)
1232  {
1233  result->num_contours= 0;
1234  result->hole= NULL;
1235  result->contour= NULL;
1236  reset_lmt(&lmt);
1237  FREE(s_heap);
1238  FREE(c_heap);
1239  return;
1240  }
1241 
1242  /* Build scanbeam table from scanbeam tree */
1243  MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation", double);
1244  build_sbt(&scanbeam, sbt, sbtree);
1245  scanbeam= 0;
1246  free_sbtree(&sbtree);
1247 
1248  /* Allow pointer re-use without causing memory leak */
1249  if (subj == result)
1250  gpc_free_polygon(subj);
1251  if (clip == result)
1252  gpc_free_polygon(clip);
1253 
1254  /* Invert clip polygon for difference operation */
1255  if (op == GPC_DIFF)
1256  parity[CLIP]= RIGHT;
1257 
1258  local_min= lmt;
1259 
1260  /* Process each scanbeam */
1261  while (scanbeam < sbt_entries)
1262  {
1263  /* Set yb and yt to the bottom and top of the scanbeam */
1264  yb= sbt[scanbeam++];
1265  if (scanbeam < sbt_entries)
1266  {
1267  yt= sbt[scanbeam];
1268  dy= yt - yb;
1269  }
1270 
1271  /* === SCANBEAM BOUNDARY PROCESSING ================================ */
1272 
1273  /* If LMT node corresponding to yb exists */
1274  if (local_min)
1275  {
1276  if (local_min->y == yb)
1277  {
1278  /* Add edges starting at this local minimum to the AET */
1279  for (edge= local_min->first_bound; edge; edge= edge->next_bound)
1280  add_edge_to_aet(&aet, edge, NULL);
1281 
1282  local_min= local_min->next;
1283  }
1284  }
1285 
1286  /* Set dummy previous x value */
1287  px= -DBL_MAX;
1288 
1289  /* Create bundles within AET */
1290  e0= aet;
1291  e1= aet;
1292 
1293  /* Set up bundle fields of first edge */
1294  aet->bundle[ABOVE][ aet->type]= (aet->top.y != yb);
1295  aet->bundle[ABOVE][!aet->type]= FALSE;
1296  aet->bstate[ABOVE]= UNBUNDLED;
1297 
1298  for (next_edge= aet->next; next_edge; next_edge= next_edge->next)
1299  {
1300  /* Set up bundle fields of next edge */
1301  next_edge->bundle[ABOVE][ next_edge->type]= (next_edge->top.y != yb);
1302  next_edge->bundle[ABOVE][!next_edge->type]= FALSE;
1303  next_edge->bstate[ABOVE]= UNBUNDLED;
1304 
1305  /* Bundle edges above the scanbeam boundary if they coincide */
1306  if (next_edge->bundle[ABOVE][next_edge->type])
1307  {
1308  if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx)
1309  && (e0->top.y != yb))
1310  {
1311  next_edge->bundle[ABOVE][ next_edge->type]^=
1312  e0->bundle[ABOVE][ next_edge->type];
1313  next_edge->bundle[ABOVE][!next_edge->type]=
1314  e0->bundle[ABOVE][!next_edge->type];
1315  next_edge->bstate[ABOVE]= BUNDLE_HEAD;
1316  e0->bundle[ABOVE][CLIP]= FALSE;
1317  e0->bundle[ABOVE][SUBJ]= FALSE;
1318  e0->bstate[ABOVE]= BUNDLE_TAIL;
1319  }
1320  e0= next_edge;
1321  }
1322  }
1323 
1324  horiz[CLIP]= NH;
1325  horiz[SUBJ]= NH;
1326 
1327  /* Process each edge at this scanbeam boundary */
1328  for (edge= aet; edge; edge= edge->next)
1329  {
1330  exists[CLIP]= edge->bundle[ABOVE][CLIP] +
1331  (edge->bundle[BELOW][CLIP] << 1);
1332  exists[SUBJ]= edge->bundle[ABOVE][SUBJ] +
1333  (edge->bundle[BELOW][SUBJ] << 1);
1334 
1335  if (exists[CLIP] || exists[SUBJ])
1336  {
1337  /* Set bundle side */
1338  edge->bside[CLIP]= parity[CLIP];
1339  edge->bside[SUBJ]= parity[SUBJ];
1340 
1341  /* Determine contributing status and quadrant occupancies */
1342  switch (op)
1343  {
1344  case GPC_DIFF:
1345  case GPC_INT:
1346  contributing= (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ]))
1347  || (exists[SUBJ] && (parity[CLIP] || horiz[CLIP]))
1348  || (exists[CLIP] && exists[SUBJ]
1349  && (parity[CLIP] == parity[SUBJ]));
1350  br= (parity[CLIP])
1351  && (parity[SUBJ]);
1352  bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1353  && (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1354  tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1355  && (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1356  tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1357  && (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1358  break;
1359  case GPC_XOR:
1360  contributing= exists[CLIP] || exists[SUBJ];
1361  br= (parity[CLIP])
1362  ^ (parity[SUBJ]);
1363  bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1364  ^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1365  tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1366  ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1367  tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1368  ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1369  break;
1370  case GPC_UNION:
1371  contributing= (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ]))
1372  || (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP]))
1373  || (exists[CLIP] && exists[SUBJ]
1374  && (parity[CLIP] == parity[SUBJ]));
1375  br= (parity[CLIP])
1376  || (parity[SUBJ]);
1377  bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
1378  || (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
1379  tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
1380  || (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
1381  tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
1382  || (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
1383  break;
1384  }
1385 
1386  /* Update parity */
1387  parity[CLIP]^= edge->bundle[ABOVE][CLIP];
1388  parity[SUBJ]^= edge->bundle[ABOVE][SUBJ];
1389 
1390  /* Update horizontal state */
1391  if (exists[CLIP])
1392  horiz[CLIP]=
1393  next_h_state[horiz[CLIP]]
1394  [((exists[CLIP] - 1) << 1) + parity[CLIP]];
1395  if (exists[SUBJ])
1396  horiz[SUBJ]=
1397  next_h_state[horiz[SUBJ]]
1398  [((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
1399 
1400  vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
1401 
1402  if (contributing)
1403  {
1404  xb= edge->xb;
1405 
1406  switch (vclass)
1407  {
1408  case EMN:
1409  case IMN:
1410  add_local_min(&out_poly, edge, xb, yb);
1411  px= xb;
1412  cf= edge->outp[ABOVE];
1413  break;
1414  case ERI:
1415  if (xb != px)
1416  {
1417  add_right(cf, xb, yb);
1418  px= xb;
1419  }
1420  edge->outp[ABOVE]= cf;
1421  cf= NULL;
1422  break;
1423  case ELI:
1424  add_left(edge->outp[BELOW], xb, yb);
1425  px= xb;
1426  cf= edge->outp[BELOW];
1427  break;
1428  case EMX:
1429  if (xb != px)
1430  {
1431  add_left(cf, xb, yb);
1432  px= xb;
1433  }
1434  merge_right(cf, edge->outp[BELOW], out_poly);
1435  cf= NULL;
1436  break;
1437  case ILI:
1438  if (xb != px)
1439  {
1440  add_left(cf, xb, yb);
1441  px= xb;
1442  }
1443  edge->outp[ABOVE]= cf;
1444  cf= NULL;
1445  break;
1446  case IRI:
1447  add_right(edge->outp[BELOW], xb, yb);
1448  px= xb;
1449  cf= edge->outp[BELOW];
1450  edge->outp[BELOW]= NULL;
1451  break;
1452  case IMX:
1453  if (xb != px)
1454  {
1455  add_right(cf, xb, yb);
1456  px= xb;
1457  }
1458  merge_left(cf, edge->outp[BELOW], out_poly);
1459  cf= NULL;
1460  edge->outp[BELOW]= NULL;
1461  break;
1462  case IMM:
1463  if (xb != px)
1464  {
1465  add_right(cf, xb, yb);
1466  px= xb;
1467  }
1468  merge_left(cf, edge->outp[BELOW], out_poly);
1469  edge->outp[BELOW]= NULL;
1470  add_local_min(&out_poly, edge, xb, yb);
1471  cf= edge->outp[ABOVE];
1472  break;
1473  case EMM:
1474  if (xb != px)
1475  {
1476  add_left(cf, xb, yb);
1477  px= xb;
1478  }
1479  merge_right(cf, edge->outp[BELOW], out_poly);
1480  edge->outp[BELOW]= NULL;
1481  add_local_min(&out_poly, edge, xb, yb);
1482  cf= edge->outp[ABOVE];
1483  break;
1484  case LED:
1485  if (edge->bot.y == yb)
1486  add_left(edge->outp[BELOW], xb, yb);
1487  edge->outp[ABOVE]= edge->outp[BELOW];
1488  px= xb;
1489  break;
1490  case RED:
1491  if (edge->bot.y == yb)
1492  add_right(edge->outp[BELOW], xb, yb);
1493  edge->outp[ABOVE]= edge->outp[BELOW];
1494  px= xb;
1495  break;
1496  default:
1497  break;
1498  } /* End of switch */
1499  } /* End of contributing conditional */
1500  } /* End of edge exists conditional */
1501  } /* End of AET loop */
1502 
1503  /* Delete terminating edges from the AET, otherwise compute xt */
1504  for (edge= aet; edge; edge= edge->next)
1505  {
1506  if (edge->top.y == yb)
1507  {
1508  prev_edge= edge->prev;
1509  next_edge= edge->next;
1510  if (prev_edge)
1511  prev_edge->next= next_edge;
1512  else
1513  aet= next_edge;
1514  if (next_edge)
1515  next_edge->prev= prev_edge;
1516 
1517  /* Copy bundle head state to the adjacent tail edge if required */
1518  if ((edge->bstate[BELOW] == BUNDLE_HEAD) && prev_edge)
1519  {
1520  if (prev_edge->bstate[BELOW] == BUNDLE_TAIL)
1521  {
1522  prev_edge->outp[BELOW]= edge->outp[BELOW];
1523  prev_edge->bstate[BELOW]= UNBUNDLED;
1524  if (prev_edge->prev)
1525  if (prev_edge->prev->bstate[BELOW] == BUNDLE_TAIL)
1526  prev_edge->bstate[BELOW]= BUNDLE_HEAD;
1527  }
1528  }
1529  }
1530  else
1531  {
1532  if (edge->top.y == yt)
1533  edge->xt= edge->top.x;
1534  else
1535  edge->xt= edge->bot.x + edge->dx * (yt - edge->bot.y);
1536  }
1537  }
1538 
1539  if (scanbeam < sbt_entries)
1540  {
1541  /* === SCANBEAM INTERIOR PROCESSING ============================== */
1542 
1543  build_intersection_table(&it, aet, dy);
1544 
1545  /* Process each node in the intersection table */
1546  for (intersect= it; intersect; intersect= intersect->next)
1547  {
1548  e0= intersect->ie[0];
1549  e1= intersect->ie[1];
1550 
1551  /* Only generate output for contributing intersections */
1552  if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ])
1553  && (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ]))
1554  {
1555  p= e0->outp[ABOVE];
1556  q= e1->outp[ABOVE];
1557  ix= intersect->point.x;
1558  iy= intersect->point.y + yb;
1559 
1560  in[CLIP]= ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP])
1561  || ( e1->bundle[ABOVE][CLIP] && e1->bside[CLIP])
1562  || (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLIP]
1563  && e0->bside[CLIP] && e1->bside[CLIP]);
1564  in[SUBJ]= ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ])
1565  || ( e1->bundle[ABOVE][SUBJ] && e1->bside[SUBJ])
1566  || (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUBJ]
1567  && e0->bside[SUBJ] && e1->bside[SUBJ]);
1568 
1569  /* Determine quadrant occupancies */
1570  switch (op)
1571  {
1572  case GPC_DIFF:
1573  case GPC_INT:
1574  tr= (in[CLIP])
1575  && (in[SUBJ]);
1576  tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
1577  && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
1578  br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
1579  && (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1580  bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
1581  && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1582  break;
1583  case GPC_XOR:
1584  tr= (in[CLIP])
1585  ^ (in[SUBJ]);
1586  tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
1587  ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
1588  br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
1589  ^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1590  bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
1591  ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1592  break;
1593  case GPC_UNION:
1594  tr= (in[CLIP])
1595  || (in[SUBJ]);
1596  tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
1597  || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
1598  br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
1599  || (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1600  bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
1601  || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
1602  break;
1603  }
1604 
1605  vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
1606 
1607  switch (vclass)
1608  {
1609  case EMN:
1610  add_local_min(&out_poly, e0, ix, iy);
1611  e1->outp[ABOVE]= e0->outp[ABOVE];
1612  break;
1613  case ERI:
1614  if (p)
1615  {
1616  add_right(p, ix, iy);
1617  e1->outp[ABOVE]= p;
1618  e0->outp[ABOVE]= NULL;
1619  }
1620  break;
1621  case ELI:
1622  if (q)
1623  {
1624  add_left(q, ix, iy);
1625  e0->outp[ABOVE]= q;
1626  e1->outp[ABOVE]= NULL;
1627  }
1628  break;
1629  case EMX:
1630  if (p && q)
1631  {
1632  add_left(p, ix, iy);
1633  merge_right(p, q, out_poly);
1634  e0->outp[ABOVE]= NULL;
1635  e1->outp[ABOVE]= NULL;
1636  }
1637  break;
1638  case IMN:
1639  add_local_min(&out_poly, e0, ix, iy);
1640  e1->outp[ABOVE]= e0->outp[ABOVE];
1641  break;
1642  case ILI:
1643  if (p)
1644  {
1645  add_left(p, ix, iy);
1646  e1->outp[ABOVE]= p;
1647  e0->outp[ABOVE]= NULL;
1648  }
1649  break;
1650  case IRI:
1651  if (q)
1652  {
1653  add_right(q, ix, iy);
1654  e0->outp[ABOVE]= q;
1655  e1->outp[ABOVE]= NULL;
1656  }
1657  break;
1658  case IMX:
1659  if (p && q)
1660  {
1661  add_right(p, ix, iy);
1662  merge_left(p, q, out_poly);
1663  e0->outp[ABOVE]= NULL;
1664  e1->outp[ABOVE]= NULL;
1665  }
1666  break;
1667  case IMM:
1668  if (p && q)
1669  {
1670  add_right(p, ix, iy);
1671  merge_left(p, q, out_poly);
1672  add_local_min(&out_poly, e0, ix, iy);
1673  e1->outp[ABOVE]= e0->outp[ABOVE];
1674  }
1675  break;
1676  case EMM:
1677  if (p && q)
1678  {
1679  add_left(p, ix, iy);
1680  merge_right(p, q, out_poly);
1681  add_local_min(&out_poly, e0, ix, iy);
1682  e1->outp[ABOVE]= e0->outp[ABOVE];
1683  }
1684  break;
1685  default:
1686  break;
1687  } /* End of switch */
1688  } /* End of contributing intersection conditional */
1689 
1690  /* Swap bundle sides in response to edge crossing */
1691  if (e0->bundle[ABOVE][CLIP])
1692  e1->bside[CLIP]= !e1->bside[CLIP];
1693  if (e1->bundle[ABOVE][CLIP])
1694  e0->bside[CLIP]= !e0->bside[CLIP];
1695  if (e0->bundle[ABOVE][SUBJ])
1696  e1->bside[SUBJ]= !e1->bside[SUBJ];
1697  if (e1->bundle[ABOVE][SUBJ])
1698  e0->bside[SUBJ]= !e0->bside[SUBJ];
1699 
1700  /* Swap e0 and e1 bundles in the AET */
1701  prev_edge= e0->prev;
1702  next_edge= e1->next;
1703  if (next_edge)
1704  next_edge->prev= e0;
1705 
1706  if (e0->bstate[ABOVE] == BUNDLE_HEAD)
1707  {
1708  search= TRUE;
1709  while (search)
1710  {
1711  prev_edge= prev_edge->prev;
1712  if (prev_edge)
1713  {
1714  if (prev_edge->bstate[ABOVE] != BUNDLE_TAIL)
1715  search= FALSE;
1716  }
1717  else
1718  search= FALSE;
1719  }
1720  }
1721  if (!prev_edge)
1722  {
1723  aet->prev= e1;
1724  e1->next= aet;
1725  aet= e0->next;
1726  }
1727  else
1728  {
1729  prev_edge->next->prev= e1;
1730  e1->next= prev_edge->next;
1731  prev_edge->next= e0->next;
1732  }
1733  if(e0->next == NULL) throw runtime_error("GPC internal error.") ;
1734  if(e1->next == NULL) throw runtime_error("GPC internal error.") ;
1735  e0->next->prev= prev_edge;
1736  e1->next->prev= e1;
1737  e0->next= next_edge;
1738  } /* End of IT loop*/
1739 
1740  /* Prepare for next scanbeam */
1741  for (edge= aet; edge; edge= next_edge)
1742  {
1743  next_edge= edge->next;
1744  succ_edge= edge->succ;
1745 
1746  if ((edge->top.y == yt) && succ_edge)
1747  {
1748  /* Replace AET edge by its successor */
1749  succ_edge->outp[BELOW]= edge->outp[ABOVE];
1750  succ_edge->bstate[BELOW]= edge->bstate[ABOVE];
1751  succ_edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
1752  succ_edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
1753  prev_edge= edge->prev;
1754  if (prev_edge)
1755  prev_edge->next= succ_edge;
1756  else
1757  aet= succ_edge;
1758  if (next_edge)
1759  next_edge->prev= succ_edge;
1760  succ_edge->prev= prev_edge;
1761  succ_edge->next= next_edge;
1762  }
1763  else
1764  {
1765  /* Update this edge */
1766  edge->outp[BELOW]= edge->outp[ABOVE];
1767  edge->bstate[BELOW]= edge->bstate[ABOVE];
1768  edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
1769  edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
1770  edge->xb= edge->xt;
1771  }
1772  edge->outp[ABOVE]= NULL;
1773  }
1774  }
1775  } /* === END OF SCANBEAM PROCESSING ================================== */
1776 
1777  /* Generate result polygon from out_poly */
1778  result->contour= NULL;
1779  result->hole= NULL;
1780  result->num_contours= count_contours(out_poly);
1781  if (result->num_contours > 0)
1782  {
1783  MALLOC(result->hole, result->num_contours
1784  * sizeof(int), "hole flag table creation", int);
1785  MALLOC(result->contour, result->num_contours
1786  * sizeof(gpc_vertex_list), "contour creation", gpc_vertex_list);
1787 
1788  c= 0;
1789  for (poly= out_poly; poly; poly= npoly)
1790  {
1791  npoly= poly->next;
1792  if (poly->active)
1793  {
1794  result->hole[c]= poly->proxy->hole;
1795  result->contour[c].num_vertices= poly->active;
1796  MALLOC(result->contour[c].vertex,
1797  result->contour[c].num_vertices * sizeof(gpc_vertex),
1798  "vertex creation", gpc_vertex);
1799 
1800  v= result->contour[c].num_vertices - 1;
1801  for (vtx= poly->proxy->v[LEFT]; vtx; vtx= nv)
1802  {
1803  nv= vtx->next;
1804  result->contour[c].vertex[v].x= vtx->x;
1805  result->contour[c].vertex[v].y= vtx->y;
1806  FREE(vtx);
1807  v--;
1808  }
1809  c++;
1810  }
1811  FREE(poly);
1812  }
1813  }
1814  else
1815  {
1816  for (poly= out_poly; poly; poly= npoly)
1817  {
1818  npoly= poly->next;
1819  FREE(poly);
1820  }
1821  }
1822 
1823  /* Tidy up */
1824  reset_it(&it);
1825  reset_lmt(&lmt);
1826  FREE(c_heap);
1827  FREE(s_heap);
1828  FREE(sbt);
1829 }
1830 
1831 
1832 void gpc_free_tristrip(gpc_tristrip *t)
1833 {
1834  int s;
1835 
1836  for (s= 0; s < t->num_strips; s++)
1837  FREE(t->strip[s].vertex);
1838  FREE(t->strip);
1839  t->num_strips= 0;
1840 }
1841 
1842 
1843 void gpc_polygon_to_tristrip(gpc_polygon *s, gpc_tristrip *t)
1844 {
1845  gpc_polygon c;
1846 
1847  c.num_contours= 0;
1848  c.hole= NULL;
1849  c.contour= NULL;
1850  gpc_tristrip_clip(GPC_DIFF, s, &c, t);
1851 }
1852 
1853 
1854 void gpc_tristrip_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip,
1855  gpc_tristrip *result)
1856 {
1857  sb_tree *sbtree= NULL;
1858  it_node *it= NULL, *intersect;
1859  edge_node *edge=0, *prev_edge=0, *next_edge=0, *succ_edge=0, *e0=0, *e1=0;
1860  edge_node *aet= NULL, *c_heap= NULL, *s_heap= NULL, *cf=0;
1861  lmt_node *lmt= NULL, *local_min;
1862  polygon_node *tlist= NULL, *tn, *tnn, *p, *q;
1863  vertex_node *lt, *ltn, *rt, *rtn;
1864  h_state horiz[2];
1865  vertex_type cft = NUL;
1866  int in[2], exists[2], parity[2]= {LEFT, LEFT};
1867  int s, v, contributing=0, search, scanbeam= 0, sbt_entries= 0;
1868  int vclass=0, bl=0, br=0, tl=0, tr=0;
1869  double *sbt= NULL, xb, px, nx, yb, yt=0.0, dy=0.0, ix, iy;
1870 
1871  /* Test for trivial NULL result cases */
1872  if (((subj->num_contours == 0) && (clip->num_contours == 0))
1873  || ((subj->num_contours == 0) && ((op == GPC_INT) || (op == GPC_DIFF)))
1874  || ((clip->num_contours == 0) && (op == GPC_INT)))
1875  {
1876  result->num_strips= 0;
1877  result->strip= NULL;
1878  return;
1879  }
1880 
1881  /* Identify potentialy contributing contours */
1882  if (((op == GPC_INT) || (op == GPC_DIFF))
1883  && (subj->num_contours > 0) && (clip->num_contours > 0))
1884  minimax_test(subj, clip, op);
1885 
1886  /* Build LMT */
1887  if (subj->num_contours > 0)
1888  s_heap= build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op);
1889  if (clip->num_contours > 0)
1890  c_heap= build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op);
1891 
1892  /* Return a NULL result if no contours contribute */
1893  if (lmt == NULL)
1894  {
1895  result->num_strips= 0;
1896  result->strip= NULL;
1897  reset_lmt(&lmt);
1898  FREE(s_heap);
1899  FREE(c_heap);
1900  return;
1901  }
1902 
1903  /* Build scanbeam table from scanbeam tree */
1904  MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation", double);
1905  build_sbt(&scanbeam, sbt, sbtree);
1906  scanbeam= 0;
1907  free_sbtree(&sbtree);
1908 
1909  /* Invert clip polygon for difference operation */
1910  if (op == GPC_DIFF)
1911  parity[CLIP]= RIGHT;
1912 
1913  local_min= lmt;
1914 
1915  /* Process each scanbeam */
1916  while (scanbeam < sbt_entries)
1917  {
1918  /* Set yb and yt to the bottom and top of the scanbeam */
1919  yb= sbt[scanbeam++];
1920  if (scanbeam < sbt_entries)
1921  {
1922  yt= sbt[scanbeam];
1923  dy= yt - yb;
1924  }
1925 
1926  /* === SCANBEAM BOUNDARY PROCESSING ================================ */
1927 
1928  /* If LMT node corresponding to yb exists */
1929  if (local_min)
1930  {
1931  if (local_min->y == yb)
1932  {
1933  /* Add edges starting at this local minimum to the AET */
1934  for (edge= local_min->first_bound; edge; edge= edge->next_bound)
1935  add_edge_to_aet(&aet, edge, NULL);
1936 
1937  local_min= local_min->next;
1938  }
1939  }
1940 
1941  /* Set dummy previous x value */
1942  px= -DBL_MAX;
1943 
1944  /* Create bundles within AET */
1945  e0= aet;
1946  e1= aet;
1947 
1948  /* Set up bundle fields of first edge */
1949  aet->bundle[ABOVE][ aet->type]= (aet->top.y != yb);
1950  aet->bundle[ABOVE][!aet->type]= FALSE;
1951  aet->bstate[ABOVE]= UNBUNDLED;
1952 
1953  for (next_edge= aet->next; next_edge; next_edge= next_edge->next)
1954  {
1955  /* Set up bundle fields of next edge */
1956  next_edge->bundle[ABOVE][ next_edge->type]= (next_edge->top.y != yb);
1957  next_edge->bundle[ABOVE][!next_edge->type]= FALSE;
1958  next_edge->bstate[ABOVE]= UNBUNDLED;
1959 
1960  /* Bundle edges above the scanbeam boundary if they coincide */
1961  if (next_edge->bundle[ABOVE][next_edge->type])
1962  {
1963  if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx)
1964  && (e0->top.y != yb))
1965  {
1966  next_edge->bundle[ABOVE][ next_edge->type]^=
1967  e0->bundle[ABOVE][ next_edge->type];
1968  next_edge->bundle[ABOVE][!next_edge->type]=
1969  e0->bundle[ABOVE][!next_edge->type];
1970  next_edge->bstate[ABOVE]= BUNDLE_HEAD;
1971  e0->bundle[ABOVE][CLIP]= FALSE;
1972  e0->bundle[ABOVE][SUBJ]= FALSE;
1973  e0->bstate[ABOVE]= BUNDLE_TAIL;
1974  }
1975  e0= next_edge;
1976  }
1977  }
1978 
1979  horiz[CLIP]= NH;
1980  horiz[SUBJ]= NH;
1981 
1982  /* Process each edge at this scanbeam boundary */
1983  for (edge= aet; edge; edge= edge->next)
1984  {
1985  exists[CLIP]= edge->bundle[ABOVE][CLIP] +
1986  (edge->bundle[BELOW][CLIP] << 1);
1987  exists[SUBJ]= edge->bundle[ABOVE][SUBJ] +
1988  (edge->bundle[BELOW][SUBJ] << 1);
1989 
1990  if (exists[CLIP] || exists[SUBJ])
1991  {
1992  /* Set bundle side */
1993  edge->bside[CLIP]= parity[CLIP];
1994  edge->bside[SUBJ]= parity[SUBJ];
1995 
1996  /* Determine contributing status and quadrant occupancies */
1997  switch (op)
1998  {
1999  case GPC_DIFF:
2000  case GPC_INT:
2001  contributing= (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ]))
2002  || (exists[SUBJ] && (parity[CLIP] || horiz[CLIP]))
2003  || (exists[CLIP] && exists[SUBJ]
2004  && (parity[CLIP] == parity[SUBJ]));
2005  br= (parity[CLIP])
2006  && (parity[SUBJ]);
2007  bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
2008  && (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
2009  tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
2010  && (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
2011  tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
2012  && (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
2013  break;
2014  case GPC_XOR:
2015  contributing= exists[CLIP] || exists[SUBJ];
2016  br= (parity[CLIP])
2017  ^ (parity[SUBJ]);
2018  bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
2019  ^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
2020  tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
2021  ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
2022  tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
2023  ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
2024  break;
2025  case GPC_UNION:
2026  contributing= (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ]))
2027  || (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP]))
2028  || (exists[CLIP] && exists[SUBJ]
2029  && (parity[CLIP] == parity[SUBJ]));
2030  br= (parity[CLIP])
2031  || (parity[SUBJ]);
2032  bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
2033  || (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
2034  tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
2035  || (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
2036  tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
2037  || (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
2038  break;
2039  }
2040 
2041  /* Update parity */
2042  parity[CLIP]^= edge->bundle[ABOVE][CLIP];
2043  parity[SUBJ]^= edge->bundle[ABOVE][SUBJ];
2044 
2045  /* Update horizontal state */
2046  if (exists[CLIP])
2047  horiz[CLIP]=
2048  next_h_state[horiz[CLIP]]
2049  [((exists[CLIP] - 1) << 1) + parity[CLIP]];
2050  if (exists[SUBJ])
2051  horiz[SUBJ]=
2052  next_h_state[horiz[SUBJ]]
2053  [((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
2054 
2055  vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
2056 
2057  if (contributing)
2058  {
2059  xb= edge->xb;
2060 
2061  switch (vclass)
2062  {
2063  case EMN:
2064  new_tristrip(&tlist, edge, xb, yb);
2065  cf= edge;
2066  break;
2067  case ERI:
2068  edge->outp[ABOVE]= cf->outp[ABOVE];
2069  if (xb != cf->xb)
2070  VERTEX(edge, ABOVE, RIGHT, xb, yb);
2071  cf= NULL;
2072  break;
2073  case ELI:
2074  VERTEX(edge, BELOW, LEFT, xb, yb);
2075  edge->outp[ABOVE]= NULL;
2076  cf= edge;
2077  break;
2078  case EMX:
2079  if (xb != cf->xb)
2080  VERTEX(edge, BELOW, RIGHT, xb, yb);
2081  edge->outp[ABOVE]= NULL;
2082  cf= NULL;
2083  break;
2084  case IMN:
2085  if (cft == LED)
2086  {
2087  if (cf->bot.y != yb)
2088  VERTEX(cf, BELOW, LEFT, cf->xb, yb);
2089  new_tristrip(&tlist, cf, cf->xb, yb);
2090  }
2091  edge->outp[ABOVE]= cf->outp[ABOVE];
2092  VERTEX(edge, ABOVE, RIGHT, xb, yb);
2093  break;
2094  case ILI:
2095  new_tristrip(&tlist, edge, xb, yb);
2096  cf= edge;
2097  cft= ILI;
2098  break;
2099  case IRI:
2100  if (cft == LED)
2101  {
2102  if (cf->bot.y != yb)
2103  VERTEX(cf, BELOW, LEFT, cf->xb, yb);
2104  new_tristrip(&tlist, cf, cf->xb, yb);
2105  }
2106  VERTEX(edge, BELOW, RIGHT, xb, yb);
2107  edge->outp[ABOVE]= NULL;
2108  break;
2109  case IMX:
2110  VERTEX(edge, BELOW, LEFT, xb, yb);
2111  edge->outp[ABOVE]= NULL;
2112  cft= IMX;
2113  break;
2114  case IMM:
2115  VERTEX(edge, BELOW, LEFT, xb, yb);
2116  edge->outp[ABOVE]= cf->outp[ABOVE];
2117  if (xb != cf->xb)
2118  VERTEX(cf, ABOVE, RIGHT, xb, yb);
2119  cf= edge;
2120  break;
2121  case EMM:
2122  VERTEX(edge, BELOW, RIGHT, xb, yb);
2123  edge->outp[ABOVE]= NULL;
2124  new_tristrip(&tlist, edge, xb, yb);
2125  cf= edge;
2126  break;
2127  case LED:
2128  if (edge->bot.y == yb)
2129  VERTEX(edge, BELOW, LEFT, xb, yb);
2130  edge->outp[ABOVE]= edge->outp[BELOW];
2131  cf= edge;
2132  cft= LED;
2133  break;
2134  case RED:
2135  edge->outp[ABOVE]= cf->outp[ABOVE];
2136  if (cft == LED)
2137  {
2138  if (cf->bot.y == yb)
2139  {
2140  VERTEX(edge, BELOW, RIGHT, xb, yb);
2141  }
2142  else
2143  {
2144  if (edge->bot.y == yb)
2145  {
2146  VERTEX(cf, BELOW, LEFT, cf->xb, yb);
2147  VERTEX(edge, BELOW, RIGHT, xb, yb);
2148  }
2149  }
2150  }
2151  else
2152  {
2153  VERTEX(edge, BELOW, RIGHT, xb, yb);
2154  VERTEX(edge, ABOVE, RIGHT, xb, yb);
2155  }
2156  cf= NULL;
2157  break;
2158  default:
2159  break;
2160  } /* End of switch */
2161  } /* End of contributing conditional */
2162  } /* End of edge exists conditional */
2163  } /* End of AET loop */
2164 
2165  /* Delete terminating edges from the AET, otherwise compute xt */
2166  for (edge= aet; edge; edge= edge->next)
2167  {
2168  if (edge->top.y == yb)
2169  {
2170  prev_edge= edge->prev;
2171  next_edge= edge->next;
2172  if (prev_edge)
2173  prev_edge->next= next_edge;
2174  else
2175  aet= next_edge;
2176  if (next_edge)
2177  next_edge->prev= prev_edge;
2178 
2179  /* Copy bundle head state to the adjacent tail edge if required */
2180  if ((edge->bstate[BELOW] == BUNDLE_HEAD) && prev_edge)
2181  {
2182  if (prev_edge->bstate[BELOW] == BUNDLE_TAIL)
2183  {
2184  prev_edge->outp[BELOW]= edge->outp[BELOW];
2185  prev_edge->bstate[BELOW]= UNBUNDLED;
2186  if (prev_edge->prev)
2187  if (prev_edge->prev->bstate[BELOW] == BUNDLE_TAIL)
2188  prev_edge->bstate[BELOW]= BUNDLE_HEAD;
2189  }
2190  }
2191  }
2192  else
2193  {
2194  if (edge->top.y == yt)
2195  edge->xt= edge->top.x;
2196  else
2197  edge->xt= edge->bot.x + edge->dx * (yt - edge->bot.y);
2198  }
2199  }
2200 
2201  if (scanbeam < sbt_entries)
2202  {
2203  /* === SCANBEAM INTERIOR PROCESSING ============================== */
2204 
2205  build_intersection_table(&it, aet, dy);
2206 
2207  /* Process each node in the intersection table */
2208  for (intersect= it; intersect; intersect= intersect->next)
2209  {
2210  e0= intersect->ie[0];
2211  e1= intersect->ie[1];
2212 
2213  /* Only generate output for contributing intersections */
2214  if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ])
2215  && (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ]))
2216  {
2217  p= e0->outp[ABOVE];
2218  q= e1->outp[ABOVE];
2219  ix= intersect->point.x;
2220  iy= intersect->point.y + yb;
2221 
2222  in[CLIP]= ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP])
2223  || ( e1->bundle[ABOVE][CLIP] && e1->bside[CLIP])
2224  || (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLIP]
2225  && e0->bside[CLIP] && e1->bside[CLIP]);
2226  in[SUBJ]= ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ])
2227  || ( e1->bundle[ABOVE][SUBJ] && e1->bside[SUBJ])
2228  || (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUBJ]
2229  && e0->bside[SUBJ] && e1->bside[SUBJ]);
2230 
2231  /* Determine quadrant occupancies */
2232  switch (op)
2233  {
2234  case GPC_DIFF:
2235  case GPC_INT:
2236  tr= (in[CLIP])
2237  && (in[SUBJ]);
2238  tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
2239  && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
2240  br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
2241  && (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2242  bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
2243  && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2244  break;
2245  case GPC_XOR:
2246  tr= (in[CLIP])
2247  ^ (in[SUBJ]);
2248  tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
2249  ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
2250  br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
2251  ^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2252  bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
2253  ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2254  break;
2255  case GPC_UNION:
2256  tr= (in[CLIP])
2257  || (in[SUBJ]);
2258  tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
2259  || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
2260  br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
2261  || (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2262  bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
2263  || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
2264  break;
2265  }
2266 
2267  vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
2268 
2269  switch (vclass)
2270  {
2271  case EMN:
2272  new_tristrip(&tlist, e1, ix, iy);
2273  e0->outp[ABOVE]= e1->outp[ABOVE];
2274  break;
2275  case ERI:
2276  if (p)
2277  {
2278  P_EDGE(prev_edge, e0, ABOVE, px, iy);
2279  VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2280  VERTEX(e0, ABOVE, RIGHT, ix, iy);
2281  e1->outp[ABOVE]= e0->outp[ABOVE];
2282  e0->outp[ABOVE]= NULL;
2283  }
2284  break;
2285  case ELI:
2286  if (q)
2287  {
2288  N_EDGE(next_edge, e1, ABOVE, nx, iy);
2289  VERTEX(e1, ABOVE, LEFT, ix, iy);
2290  VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2291  e0->outp[ABOVE]= e1->outp[ABOVE];
2292  e1->outp[ABOVE]= NULL;
2293  }
2294  break;
2295  case EMX:
2296  if (p && q)
2297  {
2298  VERTEX(e0, ABOVE, LEFT, ix, iy);
2299  e0->outp[ABOVE]= NULL;
2300  e1->outp[ABOVE]= NULL;
2301  }
2302  break;
2303  case IMN:
2304  P_EDGE(prev_edge, e0, ABOVE, px, iy);
2305  VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2306  N_EDGE(next_edge, e1, ABOVE, nx, iy);
2307  VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2308  new_tristrip(&tlist, prev_edge, px, iy);
2309  e1->outp[ABOVE]= prev_edge->outp[ABOVE];
2310  VERTEX(e1, ABOVE, RIGHT, ix, iy);
2311  new_tristrip(&tlist, e0, ix, iy);
2312  next_edge->outp[ABOVE]= e0->outp[ABOVE];
2313  VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2314  break;
2315  case ILI:
2316  if (p)
2317  {
2318  VERTEX(e0, ABOVE, LEFT, ix, iy);
2319  N_EDGE(next_edge, e1, ABOVE, nx, iy);
2320  VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2321  e1->outp[ABOVE]= e0->outp[ABOVE];
2322  e0->outp[ABOVE]= NULL;
2323  }
2324  break;
2325  case IRI:
2326  if (q)
2327  {
2328  VERTEX(e1, ABOVE, RIGHT, ix, iy);
2329  P_EDGE(prev_edge, e0, ABOVE, px, iy);
2330  VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2331  e0->outp[ABOVE]= e1->outp[ABOVE];
2332  e1->outp[ABOVE]= NULL;
2333  }
2334  break;
2335  case IMX:
2336  if (p && q)
2337  {
2338  VERTEX(e0, ABOVE, RIGHT, ix, iy);
2339  VERTEX(e1, ABOVE, LEFT, ix, iy);
2340  e0->outp[ABOVE]= NULL;
2341  e1->outp[ABOVE]= NULL;
2342  P_EDGE(prev_edge, e0, ABOVE, px, iy);
2343  VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2344  new_tristrip(&tlist, prev_edge, px, iy);
2345  N_EDGE(next_edge, e1, ABOVE, nx, iy);
2346  VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2347  next_edge->outp[ABOVE]= prev_edge->outp[ABOVE];
2348  VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2349  }
2350  break;
2351  case IMM:
2352  if (p && q)
2353  {
2354  VERTEX(e0, ABOVE, RIGHT, ix, iy);
2355  VERTEX(e1, ABOVE, LEFT, ix, iy);
2356  P_EDGE(prev_edge, e0, ABOVE, px, iy);
2357  VERTEX(prev_edge, ABOVE, LEFT, px, iy);
2358  new_tristrip(&tlist, prev_edge, px, iy);
2359  N_EDGE(next_edge, e1, ABOVE, nx, iy);
2360  VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2361  e1->outp[ABOVE]= prev_edge->outp[ABOVE];
2362  VERTEX(e1, ABOVE, RIGHT, ix, iy);
2363  new_tristrip(&tlist, e0, ix, iy);
2364  next_edge->outp[ABOVE]= e0->outp[ABOVE];
2365  VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
2366  }
2367  break;
2368  case EMM:
2369  if (p && q)
2370  {
2371  VERTEX(e0, ABOVE, LEFT, ix, iy);
2372  new_tristrip(&tlist, e1, ix, iy);
2373  e0->outp[ABOVE]= e1->outp[ABOVE];
2374  }
2375  break;
2376  default:
2377  break;
2378  } /* End of switch */
2379  } /* End of contributing intersection conditional */
2380 
2381  /* Swap bundle sides in response to edge crossing */
2382  if (e0->bundle[ABOVE][CLIP])
2383  e1->bside[CLIP]= !e1->bside[CLIP];
2384  if (e1->bundle[ABOVE][CLIP])
2385  e0->bside[CLIP]= !e0->bside[CLIP];
2386  if (e0->bundle[ABOVE][SUBJ])
2387  e1->bside[SUBJ]= !e1->bside[SUBJ];
2388  if (e1->bundle[ABOVE][SUBJ])
2389  e0->bside[SUBJ]= !e0->bside[SUBJ];
2390 
2391  /* Swap e0 and e1 bundles in the AET */
2392  prev_edge= e0->prev;
2393  next_edge= e1->next;
2394  if (e1->next)
2395  e1->next->prev= e0;
2396 
2397  if (e0->bstate[ABOVE] == BUNDLE_HEAD)
2398  {
2399  search= TRUE;
2400  while (search)
2401  {
2402  prev_edge= prev_edge->prev;
2403  if (prev_edge)
2404  {
2405  if (prev_edge->bundle[ABOVE][CLIP]
2406  || prev_edge->bundle[ABOVE][SUBJ]
2407  || (prev_edge->bstate[ABOVE] == BUNDLE_HEAD))
2408  search= FALSE;
2409  }
2410  else
2411  search= FALSE;
2412  }
2413  }
2414  if (!prev_edge)
2415  {
2416  e1->next= aet;
2417  aet= e0->next;
2418  }
2419  else
2420  {
2421  e1->next= prev_edge->next;
2422  prev_edge->next= e0->next;
2423  }
2424  e0->next->prev= prev_edge;
2425  e1->next->prev= e1;
2426  e0->next= next_edge;
2427  } /* End of IT loop*/
2428 
2429  /* Prepare for next scanbeam */
2430  for (edge= aet; edge; edge= next_edge)
2431  {
2432  next_edge= edge->next;
2433  succ_edge= edge->succ;
2434 
2435  if ((edge->top.y == yt) && succ_edge)
2436  {
2437  /* Replace AET edge by its successor */
2438  succ_edge->outp[BELOW]= edge->outp[ABOVE];
2439  succ_edge->bstate[BELOW]= edge->bstate[ABOVE];
2440  succ_edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
2441  succ_edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
2442  prev_edge= edge->prev;
2443  if (prev_edge)
2444  prev_edge->next= succ_edge;
2445  else
2446  aet= succ_edge;
2447  if (next_edge)
2448  next_edge->prev= succ_edge;
2449  succ_edge->prev= prev_edge;
2450  succ_edge->next= next_edge;
2451  }
2452  else
2453  {
2454  /* Update this edge */
2455  edge->outp[BELOW]= edge->outp[ABOVE];
2456  edge->bstate[BELOW]= edge->bstate[ABOVE];
2457  edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
2458  edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
2459  edge->xb= edge->xt;
2460  }
2461  edge->outp[ABOVE]= NULL;
2462  }
2463  }
2464  } /* === END OF SCANBEAM PROCESSING ================================== */
2465 
2466  /* Generate result tristrip from tlist */
2467  result->strip= NULL;
2468  result->num_strips= count_tristrips(tlist);
2469  if (result->num_strips > 0)
2470  {
2471  MALLOC(result->strip, result->num_strips * sizeof(gpc_vertex_list),
2472  "tristrip list creation", gpc_vertex_list);
2473 
2474  s= 0;
2475  for (tn= tlist; tn; tn= tnn)
2476  {
2477  tnn= tn->next;
2478 
2479  if (tn->active > 2)
2480  {
2481  /* Valid tristrip: copy the vertices and free the heap */
2482  result->strip[s].num_vertices= tn->active;
2483  MALLOC(result->strip[s].vertex, tn->active * sizeof(gpc_vertex),
2484  "tristrip creation", gpc_vertex);
2485  v= 0;
2486  if (INVERT_TRISTRIPS)
2487  {
2488  lt= tn->v[RIGHT];
2489  rt= tn->v[LEFT];
2490  }
2491  else
2492  {
2493  lt= tn->v[LEFT];
2494  rt= tn->v[RIGHT];
2495  }
2496  while (lt || rt)
2497  {
2498  if (lt)
2499  {
2500  ltn= lt->next;
2501  result->strip[s].vertex[v].x= lt->x;
2502  result->strip[s].vertex[v].y= lt->y;
2503  v++;
2504  FREE(lt);
2505  lt= ltn;
2506  }
2507  if (rt)
2508  {
2509  rtn= rt->next;
2510  result->strip[s].vertex[v].x= rt->x;
2511  result->strip[s].vertex[v].y= rt->y;
2512  v++;
2513  FREE(rt);
2514  rt= rtn;
2515  }
2516  }
2517  s++;
2518  }
2519  else
2520  {
2521  /* Invalid tristrip: just free the heap */
2522  for (lt= tn->v[LEFT]; lt; lt= ltn)
2523  {
2524  ltn= lt->next;
2525  FREE(lt);
2526  }
2527  for (rt= tn->v[RIGHT]; rt; rt=rtn)
2528  {
2529  rtn= rt->next;
2530  FREE(rt);
2531  }
2532  }
2533  FREE(tn);
2534  }
2535  }
2536 
2537  /* Tidy up */
2538  reset_it(&it);
2539  reset_lmt(&lmt);
2540  FREE(c_heap);
2541  FREE(s_heap);
2542  FREE(sbt);
2543 }
2544 
2545 /*
2546 ===========================================================================
2547  End of file: gpc.c
2548 ===========================================================================
2549 */
lmt_node
Definition: gpc.cpp:244
polygon_node
Definition: gpc.cpp:205
gpc_vertex_list
Definition: gpc.h:117
st_shape
Definition: gpc.cpp:267
it_shape
Definition: gpc.cpp:260
gpc_tristrip
Definition: gpc.h:130
max
FARSA_UTIL_TEMPLATE const T max(const T &t1, const U &t2)
gpc_polygon
Definition: gpc.h:123
v_shape
Definition: gpc.cpp:198
gpc_vertex
Definition: gpc.h:111
bbox_shape
Definition: gpc.cpp:276
sbt_t_shape
Definition: gpc.cpp:253
min
FARSA_UTIL_TEMPLATE const T min(const T &t1, const U &t2)
edge_node
Definition: gpc.cpp:217