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