[postgis-users] Re: C question, PG_RETURN_POINTER: GPC
integration
Cedric BERNIER
cedric.bernier@thales-is.com
Tue Apr 30 16:13:58 2002
Il s'agit d'un message multivolet au format MIME.
---------------------- multipart/mixed attachment
Bonjour Nicolas,
J'ai perdu le fil de la conversation, pourrais tu me rappeler ce que font=
tes 2 fonctions C ?
qu'est ce que le gpc ?
Merci
Cedric
Nicolas Ribot a =E9crit :
> Mr Ono,
> (and maybe other people interested)
>
> Here are the files (scot_gpc.c and scot_gpc.h).
> I tested the functions with very simple geometries.
> I join to the c files a sql file containing the dump of the postgis tab=
le
> (testgpc).
>
> > Thank you very much, Mr. Ribot. I'd like to try some geometries usin=
g your
> > functions.
> >
> > Regards.
> >
> > _______________________________________________
> > postgis-users mailing list
> > postgis-users@postgis.refractions.net
> > http://postgis.refractions.net/mailman/listinfo/postgis-users
>
> ---------------------------------------------------------------------=
---
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
>
> Project: Generic Polygon Clipper
>
> A new algorithm for calculating the difference, intersection=
,
> exclusive-or or union of arbitrary polygon sets.
>
> File: gpc.h
> Author: Alan Murta (email: gpc@cs.man.ac.uk)
> Version: 2.31
> Date: 4th June 1999
>
> Copyright: (C) 1997-1999, Advanced Interfaces Group,
> University of Manchester.
>
> This software is free for non-commercial use. It may be copi=
ed,
> modified, and redistributed provided that this copyright not=
ice
> is preserved on all copies. The intellectual property rights=
of
> the algorithms used reside with the University of Manchester
> Advanced Interfaces Group.
>
> You may not use this software, in whole or in part, in suppo=
rt
> of any commercial product without the express consent of the
> author.
>
> There is no warranty or other guarantee of fitness of this
> software for any purpose. It is provided solely "as is".
>
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> #ifndef __gpc_h
> #define __gpc_h
>
> #include <stdio.h>
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Constants
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> /* Increase GPC_EPSILON to encourage merging of near coincident edges =
*/
>
> #define GPC_EPSILON (DBL_EPSILON)
>
> #define GPC_VERSION "2.31"
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Public Data Types
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> typedef enum /* Set operation type =
*/
> {
> GPC_DIFF, /* Difference =
*/
> GPC_INT, /* Intersection =
*/
> GPC_XOR, /* Exclusive or =
*/
> GPC_UNION /* Union =
*/
> } gpc_op;
>
> typedef struct /* Polygon vertex structure =
*/
> {
> double x; /* Vertex x component =
*/
> double y; /* vertex y component =
*/
> } gpc_vertex;
>
> typedef struct /* Vertex list structure =
*/
> {
> int num_vertices; /* Number of vertices in list =
*/
> gpc_vertex *vertex; /* Vertex array pointer =
*/
> } gpc_vertex_list;
>
> typedef struct /* Polygon set structure =
*/
> {
> int num_contours; /* Number of contours in polygon =
*/
> int *hole; /* Hole / external contour flags =
*/
> gpc_vertex_list *contour; /* Contour array pointer =
*/
> } gpc_polygon;
>
> typedef struct /* Tristrip set structure =
*/
> {
> int num_strips; /* Number of tristrips =
*/
> gpc_vertex_list *strip; /* Tristrip array pointer =
*/
> } gpc_tristrip;
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Public Function Prototypes
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> void gpc_read_polygon (FILE *infile_ptr,
> int read_hole_flags,
> gpc_polygon *polygon);
>
> void gpc_write_polygon (FILE *outfile_ptr,
> int write_hole_flags,
> gpc_polygon *polygon);
>
> void gpc_add_contour (gpc_polygon *polygon,
> gpc_vertex_list *contour,
> int hole);
>
> void gpc_polygon_clip (gpc_op set_operation,
> gpc_polygon *subject_polygon,
> gpc_polygon *clip_polygon,
> gpc_polygon *result_polygon);
>
> void gpc_tristrip_clip (gpc_op set_operation,
> gpc_polygon *subject_polygon,
> gpc_polygon *clip_polygon,
> gpc_tristrip *result_tristrip);
>
> void gpc_polygon_to_tristrip (gpc_polygon *polygon,
> gpc_tristrip *tristrip);
>
> void gpc_free_polygon (gpc_polygon *polygon);
>
> void gpc_free_tristrip (gpc_tristrip *tristrip);
>
> #endif
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> End of file: gpc.h
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> ---------------------------------------------------------------------=
---
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
>
> Project: Generic Polygon Clipper
>
> A new algorithm for calculating the difference, intersection=
,
> exclusive-or or union of arbitrary polygon sets.
>
> File: gpc.c
> Author: Alan Murta (email: gpc@cs.man.ac.uk)
> Version: 2.31
> Date: 4th June 1999
>
> Copyright: (C) 1997-1999, Advanced Interfaces Group,
> University of Manchester.
>
> This software is free for non-commercial use. It may be copi=
ed,
> modified, and redistributed provided that this copyright not=
ice
> is preserved on all copies. The intellectual property rights=
of
> the algorithms used reside with the University of Manchester
> Advanced Interfaces Group.
>
> You may not use this software, in whole or in part, in suppo=
rt
> of any commercial product without the express consent of the
> author.
>
> There is no warranty or other guarantee of fitness of this
> software for any purpose. It is provided solely "as is".
>
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Includes
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> #include "gpc.h"
> #include <stdlib.h>
> #include <float.h>
> #include <math.h>
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Constants
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> #ifndef TRUE
> #define FALSE 0
> #define TRUE 1
> #endif
>
> #define LEFT 0
> #define RIGHT 1
>
> #define ABOVE 0
> #define BELOW 1
>
> #define CLIP 0
> #define SUBJ 1
>
> #define INVERT_TRISTRIPS FALSE
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Macros
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> #define EQ(a, b) (fabs((a) - (b)) <=3D GPC_EPSILON)
>
> #define PREV_INDEX(i, n) ((i - 1 + n) % n)
> #define NEXT_INDEX(i, n) ((i + 1 ) % n)
>
> #define OPTIMAL(v, i, n) ((v[PREV_INDEX(i, n)].y !=3D v[i].y) || \
> (v[NEXT_INDEX(i, n)].y !=3D v[i].y))
>
> #define FWD_MIN(v, i, n) ((v[PREV_INDEX(i, n)].vertex.y >=3D v[i].ver=
tex.y) \
> && (v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex=
.y))
>
> #define NOT_FMAX(v, i, n) (v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex=
.y)
>
> #define REV_MIN(v, i, n) ((v[PREV_INDEX(i, n)].vertex.y > v[i].vertex=
.y) \
> && (v[NEXT_INDEX(i, n)].vertex.y >=3D v[i].ver=
tex.y))
>
> #define NOT_RMAX(v, i, n) (v[PREV_INDEX(i, n)].vertex.y > v[i].vertex=
.y)
>
> #define VERTEX(e,p,s,x,y) {add_vertex(&((e)->outp[(p)]->v[(s)]), x, y)=
; \
> (e)->outp[(p)]->active++;}
>
> #define P_EDGE(d,e,p,i,j) {(d)=3D (e); \
> do {(d)=3D (d)->prev;} while (!(d)->outp[(p=
)]); \
> (i)=3D (d)->bot.x + (d)->dx * ((j)-(d)->bot=
.y);}
>
> #define N_EDGE(d,e,p,i,j) {(d)=3D (e); \
> do {(d)=3D (d)->next;} while (!(d)->outp[(p=
)]); \
> (i)=3D (d)->bot.x + (d)->dx * ((j)-(d)->bot=
.y);}
>
> #define MALLOC(p, b, s) {if ((b) > 0) { \
> p=3D malloc(b); if (!(p)) { \
> fprintf(stderr, "gpc malloc failure: %s\n",=
s); \
> exit(0);}} else p=3D NULL;}
>
> #define FREE(p) {if (p) {free(p); (p)=3D NULL;}}
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Private Data Types
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> typedef enum /* Edge intersection classes =
*/
> {
> NUL, /* Empty non-intersection =
*/
> EMX, /* External maximum =
*/
> ELI, /* External left intermediate =
*/
> TED, /* Top edge =
*/
> ERI, /* External right intermediate =
*/
> RED, /* Right edge =
*/
> IMM, /* Internal maximum and minimum =
*/
> IMN, /* Internal minimum =
*/
> EMN, /* External minimum =
*/
> EMM, /* External maximum and minimum =
*/
> LED, /* Left edge =
*/
> ILI, /* Internal left intermediate =
*/
> BED, /* Bottom edge =
*/
> IRI, /* Internal right intermediate =
*/
> IMX, /* Internal maximum =
*/
> FUL /* Full non-intersection =
*/
> } vertex_type;
>
> typedef enum /* Horizontal edge states =
*/
> {
> NH, /* No horizontal edge =
*/
> BH, /* Bottom horizontal edge =
*/
> TH /* Top horizontal edge =
*/
> } h_state;
>
> typedef enum /* Edge bundle state =
*/
> {
> UNBUNDLED, /* Isolated edge not within a bundl=
e */
> BUNDLE_HEAD, /* Bundle head node =
*/
> BUNDLE_TAIL /* Passive bundle tail node =
*/
> } bundle_state;
>
> typedef struct v_shape /* Internal vertex list datatype =
*/
> {
> double x; /* X coordinate component =
*/
> double y; /* Y coordinate component =
*/
> struct v_shape *next; /* Pointer to next vertex in list =
*/
> } vertex_node;
>
> typedef struct p_shape /* Internal contour / tristrip type=
*/
> {
> int active; /* Active flag / vertex count =
*/
> int hole; /* Hole / external contour flag =
*/
> vertex_node *v[2]; /* Left and right vertex list ptrs =
*/
> struct p_shape *next; /* Pointer to next polygon contour =
*/
> struct p_shape *proxy; /* Pointer to actual structure used=
*/
> } polygon_node;
>
> typedef struct edge_shape
> {
> gpc_vertex vertex; /* Piggy-backed contour vertex data=
*/
> gpc_vertex bot; /* Edge lower (x, y) coordinate =
*/
> gpc_vertex top; /* Edge upper (x, y) coordinate =
*/
> double xb; /* Scanbeam bottom x coordinate =
*/
> double xt; /* Scanbeam top x coordinate =
*/
> double dx; /* Change in x for a unit y increas=
e */
> int type; /* Clip / subject edge flag =
*/
> int bundle[2][2]; /* Bundle edge flags =
*/
> int bside[2]; /* Bundle left / right indicators =
*/
> bundle_state bstate[2]; /* Edge bundle state =
*/
> polygon_node *outp[2]; /* Output polygon / tristrip pointe=
r */
> struct edge_shape *prev; /* Previous edge in the AET =
*/
> struct edge_shape *next; /* Next edge in the AET =
*/
> struct edge_shape *pred; /* Edge connected at the lower end =
*/
> struct edge_shape *succ; /* Edge connected at the upper end =
*/
> struct edge_shape *next_bound; /* Pointer to next bound in LMT =
*/
> } edge_node;
>
> typedef struct lmt_shape /* Local minima table =
*/
> {
> double y; /* Y coordinate at local minimum =
*/
> edge_node *first_bound; /* Pointer to bound list =
*/
> struct lmt_shape *next; /* Pointer to next local minimum =
*/
> } lmt_node;
>
> typedef struct sbt_t_shape /* Scanbeam tree =
*/
> {
> double y; /* Scanbeam node y value =
*/
> struct sbt_t_shape *less; /* Pointer to nodes with lower y =
*/
> struct sbt_t_shape *more; /* Pointer to nodes with higher y =
*/
> } sb_tree;
>
> typedef struct it_shape /* Intersection table =
*/
> {
> edge_node *ie[2]; /* Intersecting edge (bundle) pair =
*/
> gpc_vertex point; /* Point of intersection =
*/
> struct it_shape *next; /* The next intersection table node=
*/
> } it_node;
>
> typedef struct st_shape /* Sorted edge table =
*/
> {
> edge_node *edge; /* Pointer to AET edge =
*/
> double xb; /* Scanbeam bottom x coordinate =
*/
> double xt; /* Scanbeam top x coordinate =
*/
> double dx; /* Change in x for a unit y increas=
e */
> struct st_shape *prev; /* Previous edge in sorted list =
*/
> } st_node;
>
> typedef struct bbox_shape /* Contour axis-aligned bounding bo=
x */
> {
> double xmin; /* Minimum x coordinate =
*/
> double ymin; /* Minimum y coordinate =
*/
> double xmax; /* Maximum x coordinate =
*/
> double ymax; /* Maximum y coordinate =
*/
> } bbox;
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Global Data
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> /* Horizontal edge state transitions within scanbeam boundary */
> const h_state next_h_state[3][6]=3D
> {
> /* ABOVE BELOW CROSS */
> /* L R L R L R */
> /* NH */ {BH, TH, TH, BH, NH, NH},
> /* BH */ {NH, NH, NH, NH, TH, TH},
> /* TH */ {NH, NH, NH, NH, BH, BH}
> };
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Private Functions
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> static void reset_it(it_node **it)
> {
> it_node *itn;
>
> while (*it)
> {
> itn=3D (*it)->next;
> FREE(*it);
> *it=3D itn;
> }
> }
>
> static void reset_lmt(lmt_node **lmt)
> {
> lmt_node *lmtn;
>
> while (*lmt)
> {
> lmtn=3D (*lmt)->next;
> FREE(*lmt);
> *lmt=3D lmtn;
> }
> }
>
> static void insert_bound(edge_node **b, edge_node *e)
> {
> edge_node *existing_bound;
>
> if (!*b)
> {
> /* Link node e to the tail of the list */
> *b=3D e;
> }
> else
> {
> /* Do primary sort on the x field */
> if (e[0].bot.x < (*b)[0].bot.x)
> {
> /* Insert a new node mid-list */
> existing_bound=3D *b;
> *b=3D e;
> (*b)->next_bound=3D existing_bound;
> }
> else
> {
> if (e[0].bot.x =3D=3D (*b)[0].bot.x)
> {
> /* Do secondary sort on the dx field */
> if (e[0].dx < (*b)[0].dx)
> {
> /* Insert a new node mid-list */
> existing_bound=3D *b;
> *b=3D e;
> (*b)->next_bound=3D existing_bound;
> }
> else
> {
> /* Head further down the list */
> insert_bound(&((*b)->next_bound), e);
> }
> }
> else
> {
> /* Head further down the list */
> insert_bound(&((*b)->next_bound), e);
> }
> }
> }
> }
>
> static edge_node **bound_list(lmt_node **lmt, double y)
> {
> lmt_node *existing_node;
>
> if (!*lmt)
> {
> /* Add node onto the tail end of the LMT */
> MALLOC(*lmt, sizeof(lmt_node), "LMT insertion");
> (*lmt)->y=3D y;
> (*lmt)->first_bound=3D NULL;
> (*lmt)->next=3D NULL;
> return &((*lmt)->first_bound);
> }
> else
> if (y < (*lmt)->y)
> {
> /* Insert a new LMT node before the current node */
> existing_node=3D *lmt;
> MALLOC(*lmt, sizeof(lmt_node), "LMT insertion");
> (*lmt)->y=3D y;
> (*lmt)->first_bound=3D NULL;
> (*lmt)->next=3D existing_node;
> return &((*lmt)->first_bound);
> }
> else
> if (y > (*lmt)->y)
> /* Head further up the LMT */
> return bound_list(&((*lmt)->next), y);
> else
> /* Use this existing LMT node */
> return &((*lmt)->first_bound);
> }
>
> static void add_to_sbtree(int *entries, sb_tree **sbtree, double y)
> {
> if (!*sbtree)
> {
> /* Add a new tree node here */
> MALLOC(*sbtree, sizeof(sb_tree), "scanbeam tree insertion");
> (*sbtree)->y=3D y;
> (*sbtree)->less=3D NULL;
> (*sbtree)->more=3D NULL;
> (*entries)++;
> }
> else
> {
> if ((*sbtree)->y > y)
> {
> /* Head into the 'less' sub-tree */
> add_to_sbtree(entries, &((*sbtree)->less), y);
> }
> else
> {
> if ((*sbtree)->y < y)
> {
> /* Head into the 'more' sub-tree */
> add_to_sbtree(entries, &((*sbtree)->more), y);
> }
> }
> }
> }
>
> static void build_sbt(int *entries, double *sbt, sb_tree *sbtree)
> {
> if (sbtree->less)
> build_sbt(entries, sbt, sbtree->less);
> sbt[*entries]=3D sbtree->y;
> (*entries)++;
> if (sbtree->more)
> build_sbt(entries, sbt, sbtree->more);
> }
>
> static void free_sbtree(sb_tree **sbtree)
> {
> if (*sbtree)
> {
> free_sbtree(&((*sbtree)->less));
> free_sbtree(&((*sbtree)->more));
> FREE(*sbtree);
> }
> }
>
> static int count_optimal_vertices(gpc_vertex_list c)
> {
> int result=3D 0, i;
>
> /* Ignore non-contributing contours */
> if (c.num_vertices > 0)
> {
> for (i=3D 0; i < c.num_vertices; i++)
> /* Ignore superfluous vertices embedded in horizontal edges */
> if (OPTIMAL(c.vertex, i, c.num_vertices))
> result++;
> }
> return result;
> }
>
> static edge_node *build_lmt(lmt_node **lmt, sb_tree **sbtree,
> int *sbt_entries, gpc_polygon *p, int type,
> gpc_op op)
> {
> int c, i, min, max, num_edges, v, num_vertices;
> int total_vertices=3D 0, e_index=3D0;
> edge_node *e, *edge_table;
>
> for (c=3D 0; c < p->num_contours; c++)
> total_vertices+=3D count_optimal_vertices(p->contour[c]);
>
> /* Create the entire input polygon edge table in one go */
> MALLOC(edge_table, total_vertices * sizeof(edge_node),
> "edge table creation");
>
> for (c=3D 0; c < p->num_contours; c++)
> {
> if (p->contour[c].num_vertices < 0)
> {
> /* Ignore the non-contributing contour and repair the vertex coun=
t */
> p->contour[c].num_vertices=3D -p->contour[c].num_vertices;
> }
> else
> {
> /* Perform contour optimisation */
> num_vertices=3D 0;
> for (i=3D 0; i < p->contour[c].num_vertices; i++)
> if (OPTIMAL(p->contour[c].vertex, i, p->contour[c].num_vertices=
))
> {
> edge_table[num_vertices].vertex.x=3D p->contour[c].vertex[i].=
x;
> edge_table[num_vertices].vertex.y=3D p->contour[c].vertex[i].=
y;
>
> /* Record vertex in the scanbeam table */
> add_to_sbtree(sbt_entries, sbtree,
> edge_table[num_vertices].vertex.y);
>
> num_vertices++;
> }
>
> /* Do the contour forward pass */
> for (min=3D 0; min < num_vertices; min++)
> {
> /* If a forward local minimum... */
> if (FWD_MIN(edge_table, min, num_vertices))
> {
> /* Search for the next local maximum... */
> num_edges=3D 1;
> max=3D NEXT_INDEX(min, num_vertices);
> while (NOT_FMAX(edge_table, max, num_vertices))
> {
> num_edges++;
> max=3D NEXT_INDEX(max, num_vertices);
> }
>
> /* Build the next edge list */
> e=3D &edge_table[e_index];
> e_index+=3D num_edges;
> v=3D min;
> e[0].bstate[BELOW]=3D UNBUNDLED;
> e[0].bundle[BELOW][CLIP]=3D FALSE;
> e[0].bundle[BELOW][SUBJ]=3D FALSE;
> for (i=3D 0; i < num_edges; i++)
> {
> e[i].xb=3D edge_table[v].vertex.x;
> e[i].bot.x=3D edge_table[v].vertex.x;
> e[i].bot.y=3D edge_table[v].vertex.y;
>
> v=3D NEXT_INDEX(v, num_vertices);
>
> e[i].top.x=3D edge_table[v].vertex.x;
> e[i].top.y=3D edge_table[v].vertex.y;
> e[i].dx=3D (edge_table[v].vertex.x - e[i].bot.x) /
> (e[i].top.y - e[i].bot.y);
> e[i].type=3D type;
> e[i].outp[ABOVE]=3D NULL;
> e[i].outp[BELOW]=3D NULL;
> e[i].next=3D NULL;
> e[i].prev=3D NULL;
> e[i].succ=3D ((num_edges > 1) && (i < (num_edges - 1))) ?
> &(e[i + 1]) : NULL;
> e[i].pred=3D ((num_edges > 1) && (i > 0)) ? &(e[i - 1]) : N=
ULL;
> e[i].next_bound=3D NULL;
> e[i].bside[CLIP]=3D (op =3D=3D GPC_DIFF) ? RIGHT : LEFT;
> e[i].bside[SUBJ]=3D LEFT;
> }
> insert_bound(bound_list(lmt, edge_table[min].vertex.y), e);
> }
> }
>
> /* Do the contour reverse pass */
> for (min=3D 0; min < num_vertices; min++)
> {
> /* If a reverse local minimum... */
> if (REV_MIN(edge_table, min, num_vertices))
> {
> /* Search for the previous local maximum... */
> num_edges=3D 1;
> max=3D PREV_INDEX(min, num_vertices);
> while (NOT_RMAX(edge_table, max, num_vertices))
> {
> num_edges++;
> max=3D PREV_INDEX(max, num_vertices);
> }
>
> /* Build the previous edge list */
> e=3D &edge_table[e_index];
> e_index+=3D num_edges;
> v=3D min;
> e[0].bstate[BELOW]=3D UNBUNDLED;
> e[0].bundle[BELOW][CLIP]=3D FALSE;
> e[0].bundle[BELOW][SUBJ]=3D FALSE;
> for (i=3D 0; i < num_edges; i++)
> {
> e[i].xb=3D edge_table[v].vertex.x;
> e[i].bot.x=3D edge_table[v].vertex.x;
> e[i].bot.y=3D edge_table[v].vertex.y;
>
> v=3D PREV_INDEX(v, num_vertices);
>
> e[i].top.x=3D edge_table[v].vertex.x;
> e[i].top.y=3D edge_table[v].vertex.y;
> e[i].dx=3D (edge_table[v].vertex.x - e[i].bot.x) /
> (e[i].top.y - e[i].bot.y);
> e[i].type=3D type;
> e[i].outp[ABOVE]=3D NULL;
> e[i].outp[BELOW]=3D NULL;
> e[i].next=3D NULL;
> e[i].prev=3D NULL;
> e[i].succ=3D ((num_edges > 1) && (i < (num_edges - 1))) ?
> &(e[i + 1]) : NULL;
> e[i].pred=3D ((num_edges > 1) && (i > 0)) ? &(e[i - 1]) : N=
ULL;
> e[i].next_bound=3D NULL;
> e[i].bside[CLIP]=3D (op =3D=3D GPC_DIFF) ? RIGHT : LEFT;
> e[i].bside[SUBJ]=3D LEFT;
> }
> insert_bound(bound_list(lmt, edge_table[min].vertex.y), e);
> }
> }
> }
> }
> return edge_table;
> }
>
> static void add_edge_to_aet(edge_node **aet, edge_node *edge, edge_node=
*prev)
> {
> if (!*aet)
> {
> /* Append edge onto the tail end of the AET */
> *aet=3D edge;
> edge->prev=3D prev;
> edge->next=3D NULL;
> }
> else
> {
> /* Do primary sort on the xb field */
> if (edge->xb < (*aet)->xb)
> {
> /* Insert edge here (before the AET edge) */
> edge->prev=3D prev;
> edge->next=3D *aet;
> (*aet)->prev=3D edge;
> *aet=3D edge;
> }
> else
> {
> if (edge->xb =3D=3D (*aet)->xb)
> {
> /* Do secondary sort on the dx field */
> if (edge->dx < (*aet)->dx)
> {
> /* Insert edge here (before the AET edge) */
> edge->prev=3D prev;
> edge->next=3D *aet;
> (*aet)->prev=3D edge;
> *aet=3D edge;
> }
> else
> {
> /* Head further into the AET */
> add_edge_to_aet(&((*aet)->next), edge, *aet);
> }
> }
> else
> {
> /* Head further into the AET */
> add_edge_to_aet(&((*aet)->next), edge, *aet);
> }
> }
> }
> }
>
> static void add_intersection(it_node **it, edge_node *edge0, edge_node =
*edge1,
> double x, double y)
> {
> it_node *existing_node;
>
> if (!*it)
> {
> /* Append a new node to the tail of the list */
> MALLOC(*it, sizeof(it_node), "IT insertion");
> (*it)->ie[0]=3D edge0;
> (*it)->ie[1]=3D edge1;
> (*it)->point.x=3D x;
> (*it)->point.y=3D y;
> (*it)->next=3D NULL;
> }
> else
> {
> if ((*it)->point.y > y)
> {
> /* Insert a new node mid-list */
> existing_node=3D *it;
> MALLOC(*it, sizeof(it_node), "IT insertion");
> (*it)->ie[0]=3D edge0;
> (*it)->ie[1]=3D edge1;
> (*it)->point.x=3D x;
> (*it)->point.y=3D y;
> (*it)->next=3D existing_node;
> }
> else
> /* Head further down the list */
> add_intersection(&((*it)->next), edge0, edge1, x, y);
> }
> }
>
> static void add_st_edge(st_node **st, it_node **it, edge_node *edge,
> double dy)
> {
> st_node *existing_node;
> double den, r, x, y;
>
> if (!*st)
> {
> /* Append edge onto the tail end of the ST */
> MALLOC(*st, sizeof(st_node), "ST insertion");
> (*st)->edge=3D edge;
> (*st)->xb=3D edge->xb;
> (*st)->xt=3D edge->xt;
> (*st)->dx=3D edge->dx;
> (*st)->prev=3D NULL;
> }
> else
> {
> den=3D ((*st)->xt - (*st)->xb) - (edge->xt - edge->xb);
>
> /* If new edge and ST edge don't cross */
> if ((edge->xt >=3D (*st)->xt) || (edge->dx =3D=3D (*st)->dx) ||
> (fabs(den) <=3D DBL_EPSILON))
> {
> /* No intersection - insert edge here (before the ST edge) */
> existing_node=3D *st;
> MALLOC(*st, sizeof(st_node), "ST insertion");
> (*st)->edge=3D edge;
> (*st)->xb=3D edge->xb;
> (*st)->xt=3D edge->xt;
> (*st)->dx=3D edge->dx;
> (*st)->prev=3D existing_node;
> }
> else
> {
> /* Compute intersection between new edge and ST edge */
> r=3D (edge->xb - (*st)->xb) / den;
> x=3D (*st)->xb + r * ((*st)->xt - (*st)->xb);
> y=3D r * dy;
>
> /* Insert the edge pointers and the intersection point in the IT =
*/
> add_intersection(it, (*st)->edge, edge, x, y);
>
> /* Head further into the ST */
> add_st_edge(&((*st)->prev), it, edge, dy);
> }
> }
> }
>
> static void build_intersection_table(it_node **it, edge_node *aet, doub=
le dy)
> {
> st_node *st, *stp;
> edge_node *edge;
>
> /* Build intersection table for the current scanbeam */
> reset_it(it);
> st=3D NULL;
>
> /* Process each AET edge */
> for (edge=3D aet; edge; edge=3D edge->next)
> {
> if ((edge->bstate[ABOVE] =3D=3D BUNDLE_HEAD) ||
> edge->bundle[ABOVE][CLIP] || edge->bundle[ABOVE][SUBJ])
> add_st_edge(&st, it, edge, dy);
> }
>
> /* Free the sorted edge table */
> while (st)
> {
> stp=3D st->prev;
> FREE(st);
> st=3D stp;
> }
> }
>
> static int count_contours(polygon_node *polygon)
> {
> int nc, nv;
> vertex_node *v, *nextv;
>
> for (nc=3D 0; polygon; polygon=3D polygon->next)
> if (polygon->active)
> {
> /* Count the vertices in the current contour */
> nv=3D 0;
> for (v=3D polygon->proxy->v[LEFT]; v; v=3D v->next)
> nv++;
>
> /* Record valid vertex counts in the active field */
> if (nv > 2)
> {
> polygon->active=3D nv;
> nc++;
> }
> else
> {
> /* Invalid contour: just free the heap */
> for (v=3D polygon->proxy->v[LEFT]; v; v=3D nextv)
> {
> nextv=3D v->next;
> FREE(v);
> }
> polygon->active=3D 0;
> }
> }
> return nc;
> }
>
> static void add_left(polygon_node *p, double x, double y)
> {
> vertex_node *nv;
>
> /* Create a new vertex node and set its fields */
> MALLOC(nv, sizeof(vertex_node), "vertex node creation");
> nv->x=3D x;
> nv->y=3D y;
>
> /* Add vertex nv to the left end of the polygon's vertex list */
> nv->next=3D p->proxy->v[LEFT];
>
> /* Update proxy->[LEFT] to point to nv */
> p->proxy->v[LEFT]=3D nv;
> }
>
> static void merge_left(polygon_node *p, polygon_node *q, polygon_node *=
list)
> {
> polygon_node *target;
>
> /* Label contour as a hole */
> q->proxy->hole=3D TRUE;
>
> if (p->proxy !=3D q->proxy)
> {
> /* Assign p's vertex list to the left end of q's list */
> p->proxy->v[RIGHT]->next=3D q->proxy->v[LEFT];
> q->proxy->v[LEFT]=3D p->proxy->v[LEFT];
>
> /* Redirect any p->proxy references to q->proxy */
>
> for (target=3D p->proxy; list; list=3D list->next)
> {
> if (list->proxy =3D=3D target)
> {
> list->active=3D FALSE;
> list->proxy=3D q->proxy;
> }
> }
> }
> }
>
> static void add_right(polygon_node *p, double x, double y)
> {
> vertex_node *nv;
>
> /* Create a new vertex node and set its fields */
> MALLOC(nv, sizeof(vertex_node), "vertex node creation");
> nv->x=3D x;
> nv->y=3D y;
> nv->next=3D NULL;
>
> /* Add vertex nv to the right end of the polygon's vertex list */
> p->proxy->v[RIGHT]->next=3D nv;
>
> /* Update proxy->v[RIGHT] to point to nv */
> p->proxy->v[RIGHT]=3D nv;
> }
>
> static void merge_right(polygon_node *p, polygon_node *q, polygon_node =
*list)
> {
> polygon_node *target;
>
> /* Label contour as external */
> q->proxy->hole=3D FALSE;
>
> if (p->proxy !=3D q->proxy)
> {
> /* Assign p's vertex list to the right end of q's list */
> q->proxy->v[RIGHT]->next=3D p->proxy->v[LEFT];
> q->proxy->v[RIGHT]=3D p->proxy->v[RIGHT];
>
> /* Redirect any p->proxy references to q->proxy */
> for (target=3D p->proxy; list; list=3D list->next)
> {
> if (list->proxy =3D=3D target)
> {
> list->active=3D FALSE;
> list->proxy=3D q->proxy;
> }
> }
> }
> }
>
> static void add_local_min(polygon_node **p, edge_node *edge,
> double x, double y)
> {
> polygon_node *existing_min;
> vertex_node *nv;
>
> existing_min=3D *p;
>
> MALLOC(*p, sizeof(polygon_node), "polygon node creation");
>
> /* Create a new vertex node and set its fields */
> MALLOC(nv, sizeof(vertex_node), "vertex node creation");
> nv->x=3D x;
> nv->y=3D y;
> nv->next=3D NULL;
>
> /* Initialise proxy to point to p itself */
> (*p)->proxy=3D (*p);
> (*p)->active=3D TRUE;
> (*p)->next=3D existing_min;
>
> /* Make v[LEFT] and v[RIGHT] point to new vertex nv */
> (*p)->v[LEFT]=3D nv;
> (*p)->v[RIGHT]=3D nv;
>
> /* Assign polygon p to the edge */
> edge->outp[ABOVE]=3D *p;
> }
>
> static int count_tristrips(polygon_node *tn)
> {
> int total;
>
> for (total=3D 0; tn; tn=3D tn->next)
> if (tn->active > 2)
> total++;
> return total;
> }
>
> static void add_vertex(vertex_node **t, double x, double y)
> {
> if (!(*t))
> {
> MALLOC(*t, sizeof(vertex_node), "tristrip vertex creation");
> (*t)->x=3D x;
> (*t)->y=3D y;
> (*t)->next=3D NULL;
> }
> else
> /* Head further down the list */
> add_vertex(&((*t)->next), x, y);
> }
>
> static void new_tristrip(polygon_node **tn, edge_node *edge,
> double x, double y)
> {
> if (!(*tn))
> {
> MALLOC(*tn, sizeof(polygon_node), "tristrip node creation");
> (*tn)->next=3D NULL;
> (*tn)->v[LEFT]=3D NULL;
> (*tn)->v[RIGHT]=3D NULL;
> (*tn)->active=3D 1;
> add_vertex(&((*tn)->v[LEFT]), x, y);
> edge->outp[ABOVE]=3D *tn;
> }
> else
> /* Head further down the list */
> new_tristrip(&((*tn)->next), edge, x, y);
> }
>
> static bbox *create_contour_bboxes(gpc_polygon *p)
> {
> bbox *box;
> int c, v;
>
> MALLOC(box, p->num_contours * sizeof(bbox), "Bounding box creation");
>
> /* Construct contour bounding boxes */
> for (c=3D 0; c < p->num_contours; c++)
> {
> /* Initialise bounding box extent */
> box[c].xmin=3D DBL_MAX;
> box[c].ymin=3D DBL_MAX;
> box[c].xmax=3D -DBL_MAX;
> box[c].ymax=3D -DBL_MAX;
>
> for (v=3D 0; v < p->contour[c].num_vertices; v++)
> {
> /* Adjust bounding box */
> if (p->contour[c].vertex[v].x < box[c].xmin)
> box[c].xmin=3D p->contour[c].vertex[v].x;
> if (p->contour[c].vertex[v].y < box[c].ymin)
> box[c].ymin=3D p->contour[c].vertex[v].y;
> if (p->contour[c].vertex[v].x > box[c].xmax)
> box[c].xmax=3D p->contour[c].vertex[v].x;
> if (p->contour[c].vertex[v].y > box[c].ymax)
> box[c].ymax=3D p->contour[c].vertex[v].y;
> }
> }
> return box;
> }
>
> static void minimax_test(gpc_polygon *subj, gpc_polygon *clip, gpc_op o=
p)
> {
> bbox *s_bbox, *c_bbox;
> int s, c, *o_table, overlap;
>
> s_bbox=3D create_contour_bboxes(subj);
> c_bbox=3D create_contour_bboxes(clip);
>
> MALLOC(o_table, subj->num_contours * clip->num_contours * sizeof(int)=
,
> "overlap table creation");
>
> /* Check all subject contour bounding boxes against clip boxes */
> for (s=3D 0; s < subj->num_contours; s++)
> for (c=3D 0; c < clip->num_contours; c++)
> o_table[c * subj->num_contours + s]=3D
> (!((s_bbox[s].xmax < c_bbox[c].xmin) ||
> (s_bbox[s].xmin > c_bbox[c].xmax))) &&
> (!((s_bbox[s].ymax < c_bbox[c].ymin) ||
> (s_bbox[s].ymin > c_bbox[c].ymax)));
>
> /* For each clip contour, search for any subject contour overlaps */
> for (c=3D 0; c < clip->num_contours; c++)
> {
> overlap=3D 0;
> for (s=3D 0; (!overlap) && (s < subj->num_contours); s++)
> overlap=3D o_table[c * subj->num_contours + s];
>
> if (!overlap)
> /* Flag non contributing status by negating vertex count */
> clip->contour[c].num_vertices =3D -clip->contour[c].num_vertices;
> }
>
> if (op =3D=3D GPC_INT)
> {
> /* For each subject contour, search for any clip contour overlaps *=
/
> for (s=3D 0; s < subj->num_contours; s++)
> {
> overlap=3D 0;
> for (c=3D 0; (!overlap) && (c < clip->num_contours); c++)
> overlap=3D o_table[c * subj->num_contours + s];
>
> if (!overlap)
> /* Flag non contributing status by negating vertex count */
> subj->contour[s].num_vertices =3D -subj->contour[s].num_vertice=
s;
> }
> }
>
> FREE(s_bbox);
> FREE(c_bbox);
> FREE(o_table);
> }
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> Public Functions
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> void gpc_free_polygon(gpc_polygon *p)
> {
> int c;
>
> for (c=3D 0; c < p->num_contours; c++)
> FREE(p->contour[c].vertex);
> FREE(p->hole);
> FREE(p->contour);
> p->num_contours=3D 0;
> }
>
> void gpc_read_polygon(FILE *fp, int read_hole_flags, gpc_polygon *p)
> {
> int c, v;
>
> fscanf(fp, "%d", &(p->num_contours));
> MALLOC(p->hole, p->num_contours * sizeof(int),
> "hole flag array creation");
> MALLOC(p->contour, p->num_contours
> * sizeof(gpc_vertex_list), "contour creation");
> for (c=3D 0; c < p->num_contours; c++)
> {
> fscanf(fp, "%d", &(p->contour[c].num_vertices));
>
> if (read_hole_flags)
> fscanf(fp, "%d", &(p->hole[c]));
> else
> p->hole[c]=3D FALSE; /* Assume all contours to be external */
>
> MALLOC(p->contour[c].vertex, p->contour[c].num_vertices
> * sizeof(gpc_vertex), "vertex creation");
> for (v=3D 0; v < p->contour[c].num_vertices; v++)
> fscanf(fp, "%lf %lf", &(p->contour[c].vertex[v].x),
> &(p->contour[c].vertex[v].y));
> }
> }
>
> void gpc_write_polygon(FILE *fp, int write_hole_flags, gpc_polygon *p)
> {
> int c, v;
>
> fprintf(fp, "%d\n", p->num_contours);
> for (c=3D 0; c < p->num_contours; c++)
> {
> fprintf(fp, "%d\n", p->contour[c].num_vertices);
>
> if (write_hole_flags)
> fprintf(fp, "%d\n", p->hole[c]);
>
> for (v=3D 0; v < p->contour[c].num_vertices; v++)
> fprintf(fp, "% .*lf % .*lf\n",
> DBL_DIG, p->contour[c].vertex[v].x,
> DBL_DIG, p->contour[c].vertex[v].y);
> }
> }
>
> void gpc_add_contour(gpc_polygon *p, gpc_vertex_list *new_contour, int =
hole)
> {
> int *extended_hole, c, v;
> gpc_vertex_list *extended_contour;
>
> /* Create an extended hole array */
> MALLOC(extended_hole, (p->num_contours + 1)
> * sizeof(int), "contour hole addition");
>
> /* Create an extended contour array */
> MALLOC(extended_contour, (p->num_contours + 1)
> * sizeof(gpc_vertex_list), "contour addition");
>
> /* Copy the old contour and hole data into the extended arrays */
> for (c=3D 0; c < p->num_contours; c++)
> {
> extended_hole[c]=3D p->hole[c];
> extended_contour[c]=3D p->contour[c];
> }
>
> /* Copy the new contour and hole onto the end of the extended arrays =
*/
> c=3D p->num_contours;
> extended_hole[c]=3D hole;
> extended_contour[c].num_vertices=3D new_contour->num_vertices;
> MALLOC(extended_contour[c].vertex, new_contour->num_vertices
> * sizeof(gpc_vertex), "contour addition");
> for (v=3D 0; v < new_contour->num_vertices; v++)
> extended_contour[c].vertex[v]=3D new_contour->vertex[v];
>
> /* Dispose of the old contour */
> FREE(p->contour);
> FREE(p->hole);
>
> /* Update the polygon information */
> p->num_contours++;
> p->hole=3D extended_hole;
> p->contour=3D extended_contour;
> }
>
> void gpc_polygon_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip,
> gpc_polygon *result)
> {
> sb_tree *sbtree=3D NULL;
> it_node *it=3D NULL, *intersect;
> edge_node *edge, *prev_edge, *next_edge, *succ_edge, *e0, *e1;
> edge_node *aet=3D NULL, *c_heap=3D NULL, *s_heap=3D NULL;
> lmt_node *lmt=3D NULL, *local_min;
> polygon_node *out_poly=3D NULL, *p, *q, *poly, *npoly, *cf=3D NULL;
> vertex_node *vtx, *nv;
> h_state horiz[2];
> int in[2], exists[2], parity[2]=3D {LEFT, LEFT};
> int c, v, contributing, search, scanbeam=3D 0, sbt_entries=
=3D 0;
> int vclass, bl, br, tl, tr;
> double *sbt=3D NULL, xb, px, yb, yt, dy, ix, iy;
>
> /* Test for trivial NULL result cases */
> if (((subj->num_contours =3D=3D 0) && (clip->num_contours =3D=3D 0))
> || ((subj->num_contours =3D=3D 0) && ((op =3D=3D GPC_INT) || (op =3D=
=3D GPC_DIFF)))
> || ((clip->num_contours =3D=3D 0) && (op =3D=3D GPC_INT)))
> {
> result->num_contours=3D 0;
> result->hole=3D NULL;
> result->contour=3D NULL;
> return;
> }
>
> /* Identify potentialy contributing contours */
> if (((op =3D=3D GPC_INT) || (op =3D=3D GPC_DIFF))
> && (subj->num_contours > 0) && (clip->num_contours > 0))
> minimax_test(subj, clip, op);
>
> /* Build LMT */
> if (subj->num_contours > 0)
> s_heap=3D build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op);
> if (clip->num_contours > 0)
> c_heap=3D build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op);
>
> /* Return a NULL result if no contours contribute */
> if (lmt =3D=3D NULL)
> {
> result->num_contours=3D 0;
> result->hole=3D NULL;
> result->contour=3D NULL;
> reset_lmt(&lmt);
> FREE(s_heap);
> FREE(c_heap);
> return;
> }
>
> /* Build scanbeam table from scanbeam tree */
> MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation");
> build_sbt(&scanbeam, sbt, sbtree);
> scanbeam=3D 0;
> free_sbtree(&sbtree);
>
> /* Allow pointer re-use without causing memory leak */
> if (subj =3D=3D result)
> gpc_free_polygon(subj);
> if (clip =3D=3D result)
> gpc_free_polygon(clip);
>
> /* Invert clip polygon for difference operation */
> if (op =3D=3D GPC_DIFF)
> parity[CLIP]=3D RIGHT;
>
> local_min=3D lmt;
>
> /* Process each scanbeam */
> while (scanbeam < sbt_entries)
> {
> /* Set yb and yt to the bottom and top of the scanbeam */
> yb=3D sbt[scanbeam++];
> if (scanbeam < sbt_entries)
> {
> yt=3D sbt[scanbeam];
> dy=3D yt - yb;
> }
>
> /* =3D=3D=3D SCANBEAM BOUNDARY PROCESSING =3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D */
>
> /* If LMT node corresponding to yb exists */
> if (local_min)
> {
> if (local_min->y =3D=3D yb)
> {
> /* Add edges starting at this local minimum to the AET */
> for (edge=3D local_min->first_bound; edge; edge=3D edge->next_b=
ound)
> add_edge_to_aet(&aet, edge, NULL);
>
> local_min=3D local_min->next;
> }
> }
>
> /* Set dummy previous x value */
> px=3D -DBL_MAX;
>
> /* Create bundles within AET */
> e0=3D aet;
> e1=3D aet;
>
> /* Set up bundle fields of first edge */
> aet->bundle[ABOVE][ aet->type]=3D (aet->top.y !=3D yb);
> aet->bundle[ABOVE][!aet->type]=3D FALSE;
> aet->bstate[ABOVE]=3D UNBUNDLED;
>
> for (next_edge=3D aet->next; next_edge; next_edge=3D next_edge->nex=
t)
> {
> /* Set up bundle fields of next edge */
> next_edge->bundle[ABOVE][ next_edge->type]=3D (next_edge->top.y !=
=3D yb);
> next_edge->bundle[ABOVE][!next_edge->type]=3D FALSE;
> next_edge->bstate[ABOVE]=3D UNBUNDLED;
>
> /* Bundle edges above the scanbeam boundary if they coincide */
> if (next_edge->bundle[ABOVE][next_edge->type])
> {
> if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx)
> && (e0->top.y !=3D yb))
> {
> next_edge->bundle[ABOVE][ next_edge->type]^=3D
> e0->bundle[ABOVE][ next_edge->type];
> next_edge->bundle[ABOVE][!next_edge->type]=3D
> e0->bundle[ABOVE][!next_edge->type];
> next_edge->bstate[ABOVE]=3D BUNDLE_HEAD;
> e0->bundle[ABOVE][CLIP]=3D FALSE;
> e0->bundle[ABOVE][SUBJ]=3D FALSE;
> e0->bstate[ABOVE]=3D BUNDLE_TAIL;
> }
> e0=3D next_edge;
> }
> }
>
> horiz[CLIP]=3D NH;
> horiz[SUBJ]=3D NH;
>
> /* Process each edge at this scanbeam boundary */
> for (edge=3D aet; edge; edge=3D edge->next)
> {
> exists[CLIP]=3D edge->bundle[ABOVE][CLIP] +
> (edge->bundle[BELOW][CLIP] << 1);
> exists[SUBJ]=3D edge->bundle[ABOVE][SUBJ] +
> (edge->bundle[BELOW][SUBJ] << 1);
>
> if (exists[CLIP] || exists[SUBJ])
> {
> /* Set bundle side */
> edge->bside[CLIP]=3D parity[CLIP];
> edge->bside[SUBJ]=3D parity[SUBJ];
>
> /* Determine contributing status and quadrant occupancies */
> switch (op)
> {
> case GPC_DIFF:
> case GPC_INT:
> contributing=3D (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ]=
))
> || (exists[SUBJ] && (parity[CLIP] || horiz[CLIP]))
> || (exists[CLIP] && exists[SUBJ]
> && (parity[CLIP] =3D=3D parity[SUBJ]));
> br=3D (parity[CLIP])
> && (parity[SUBJ]);
> bl=3D (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
> && (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
> tr=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH))
> && (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH));
> tl=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH) ^ edge->bundle[BELO=
W][CLIP])
> && (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH) ^ edge->bundle[BELOW]=
[SUBJ]);
> break;
> case GPC_XOR:
> contributing=3D exists[CLIP] || exists[SUBJ];
> br=3D (parity[CLIP])
> ^ (parity[SUBJ]);
> bl=3D (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
> ^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
> tr=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH))
> ^ (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH));
> tl=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH) ^ edge->bundle[BELO=
W][CLIP])
> ^ (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH) ^ edge->bundle[BELOW]=
[SUBJ]);
> break;
> case GPC_UNION:
> contributing=3D (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ=
]))
> || (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP])=
)
> || (exists[CLIP] && exists[SUBJ]
> && (parity[CLIP] =3D=3D parity[SUBJ]));
> br=3D (parity[CLIP])
> || (parity[SUBJ]);
> bl=3D (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
> || (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
> tr=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH))
> || (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH));
> tl=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH) ^ edge->bundle[BELO=
W][CLIP])
> || (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH) ^ edge->bundle[BELOW]=
[SUBJ]);
> break;
> }
>
> /* Update parity */
> parity[CLIP]^=3D edge->bundle[ABOVE][CLIP];
> parity[SUBJ]^=3D edge->bundle[ABOVE][SUBJ];
>
> /* Update horizontal state */
> if (exists[CLIP])
> horiz[CLIP]=3D
> next_h_state[horiz[CLIP]]
> [((exists[CLIP] - 1) << 1) + parity[CLIP]];
> if (exists[SUBJ])
> horiz[SUBJ]=3D
> next_h_state[horiz[SUBJ]]
> [((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
>
> vclass=3D tr + (tl << 1) + (br << 2) + (bl << 3);
>
> if (contributing)
> {
> xb=3D edge->xb;
>
> switch (vclass)
> {
> case EMN:
> case IMN:
> add_local_min(&out_poly, edge, xb, yb);
> px=3D xb;
> cf=3D edge->outp[ABOVE];
> break;
> case ERI:
> if (xb !=3D px)
> {
> add_right(cf, xb, yb);
> px=3D xb;
> }
> edge->outp[ABOVE]=3D cf;
> cf=3D NULL;
> break;
> case ELI:
> add_left(edge->outp[BELOW], xb, yb);
> px=3D xb;
> cf=3D edge->outp[BELOW];
> break;
> case EMX:
> if (xb !=3D px)
> {
> add_left(cf, xb, yb);
> px=3D xb;
> }
> merge_right(cf, edge->outp[BELOW], out_poly);
> cf=3D NULL;
> break;
> case ILI:
> if (xb !=3D px)
> {
> add_left(cf, xb, yb);
> px=3D xb;
> }
> edge->outp[ABOVE]=3D cf;
> cf=3D NULL;
> break;
> case IRI:
> add_right(edge->outp[BELOW], xb, yb);
> px=3D xb;
> cf=3D edge->outp[BELOW];
> edge->outp[BELOW]=3D NULL;
> break;
> case IMX:
> if (xb !=3D px)
> {
> add_right(cf, xb, yb);
> px=3D xb;
> }
> merge_left(cf, edge->outp[BELOW], out_poly);
> cf=3D NULL;
> edge->outp[BELOW]=3D NULL;
> break;
> case IMM:
> if (xb !=3D px)
> {
> add_right(cf, xb, yb);
> px=3D xb;
> }
> merge_left(cf, edge->outp[BELOW], out_poly);
> edge->outp[BELOW]=3D NULL;
> add_local_min(&out_poly, edge, xb, yb);
> cf=3D edge->outp[ABOVE];
> break;
> case EMM:
> if (xb !=3D px)
> {
> add_left(cf, xb, yb);
> px=3D xb;
> }
> merge_right(cf, edge->outp[BELOW], out_poly);
> edge->outp[BELOW]=3D NULL;
> add_local_min(&out_poly, edge, xb, yb);
> cf=3D edge->outp[ABOVE];
> break;
> case LED:
> if (edge->bot.y =3D=3D yb)
> add_left(edge->outp[BELOW], xb, yb);
> edge->outp[ABOVE]=3D edge->outp[BELOW];
> px=3D xb;
> break;
> case RED:
> if (edge->bot.y =3D=3D yb)
> add_right(edge->outp[BELOW], xb, yb);
> edge->outp[ABOVE]=3D edge->outp[BELOW];
> px=3D xb;
> break;
> default:
> break;
> } /* End of switch */
> } /* End of contributing conditional */
> } /* End of edge exists conditional */
> } /* End of AET loop */
>
> /* Delete terminating edges from the AET, otherwise compute xt */
> for (edge=3D aet; edge; edge=3D edge->next)
> {
> if (edge->top.y =3D=3D yb)
> {
> prev_edge=3D edge->prev;
> next_edge=3D edge->next;
> if (prev_edge)
> prev_edge->next=3D next_edge;
> else
> aet=3D next_edge;
> if (next_edge)
> next_edge->prev=3D prev_edge;
>
> /* Copy bundle head state to the adjacent tail edge if required=
*/
> if ((edge->bstate[BELOW] =3D=3D BUNDLE_HEAD) && prev_edge)
> {
> if (prev_edge->bstate[BELOW] =3D=3D BUNDLE_TAIL)
> {
> prev_edge->outp[BELOW]=3D edge->outp[BELOW];
> prev_edge->bstate[BELOW]=3D UNBUNDLED;
> if (prev_edge->prev)
> if (prev_edge->prev->bstate[BELOW] =3D=3D BUNDLE_TAIL)
> prev_edge->bstate[BELOW]=3D BUNDLE_HEAD;
> }
> }
> }
> else
> {
> if (edge->top.y =3D=3D yt)
> edge->xt=3D edge->top.x;
> else
> edge->xt=3D edge->bot.x + edge->dx * (yt - edge->bot.y);
> }
> }
>
> if (scanbeam < sbt_entries)
> {
> /* =3D=3D=3D SCANBEAM INTERIOR PROCESSING =3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D */
>
> build_intersection_table(&it, aet, dy);
>
> /* Process each node in the intersection table */
> for (intersect=3D it; intersect; intersect=3D intersect->next)
> {
> e0=3D intersect->ie[0];
> e1=3D intersect->ie[1];
>
> /* Only generate output for contributing intersections */
> if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ])
> && (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ]))
> {
> p=3D e0->outp[ABOVE];
> q=3D e1->outp[ABOVE];
> ix=3D intersect->point.x;
> iy=3D intersect->point.y + yb;
>
> in[CLIP]=3D ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP])
> || ( e1->bundle[ABOVE][CLIP] && e1->bside[CLIP])
> || (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLI=
P]
> && e0->bside[CLIP] && e1->bside[CLIP]);
> in[SUBJ]=3D ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ])
> || ( e1->bundle[ABOVE][SUBJ] && e1->bside[SUBJ])
> || (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUB=
J]
> && e0->bside[SUBJ] && e1->bside[SUBJ]);
>
> /* Determine quadrant occupancies */
> switch (op)
> {
> case GPC_DIFF:
> case GPC_INT:
> tr=3D (in[CLIP])
> && (in[SUBJ]);
> tl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
> && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
> br=3D (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
> && (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
> bl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOV=
E][CLIP])
> && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE]=
[SUBJ]);
> break;
> case GPC_XOR:
> tr=3D (in[CLIP])
> ^ (in[SUBJ]);
> tl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
> ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
> br=3D (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
> ^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
> bl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOV=
E][CLIP])
> ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE]=
[SUBJ]);
> break;
> case GPC_UNION:
> tr=3D (in[CLIP])
> || (in[SUBJ]);
> tl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
> || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
> br=3D (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
> || (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
> bl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOV=
E][CLIP])
> || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE]=
[SUBJ]);
> break;
> }
>
> vclass=3D tr + (tl << 1) + (br << 2) + (bl << 3);
>
> switch (vclass)
> {
> case EMN:
> add_local_min(&out_poly, e0, ix, iy);
> e1->outp[ABOVE]=3D e0->outp[ABOVE];
> break;
> case ERI:
> if (p)
> {
> add_right(p, ix, iy);
> e1->outp[ABOVE]=3D p;
> e0->outp[ABOVE]=3D NULL;
> }
> break;
> case ELI:
> if (q)
> {
> add_left(q, ix, iy);
> e0->outp[ABOVE]=3D q;
> e1->outp[ABOVE]=3D NULL;
> }
> break;
> case EMX:
> if (p && q)
> {
> add_left(p, ix, iy);
> merge_right(p, q, out_poly);
> e0->outp[ABOVE]=3D NULL;
> e1->outp[ABOVE]=3D NULL;
> }
> break;
> case IMN:
> add_local_min(&out_poly, e0, ix, iy);
> e1->outp[ABOVE]=3D e0->outp[ABOVE];
> break;
> case ILI:
> if (p)
> {
> add_left(p, ix, iy);
> e1->outp[ABOVE]=3D p;
> e0->outp[ABOVE]=3D NULL;
> }
> break;
> case IRI:
> if (q)
> {
> add_right(q, ix, iy);
> e0->outp[ABOVE]=3D q;
> e1->outp[ABOVE]=3D NULL;
> }
> break;
> case IMX:
> if (p && q)
> {
> add_right(p, ix, iy);
> merge_left(p, q, out_poly);
> e0->outp[ABOVE]=3D NULL;
> e1->outp[ABOVE]=3D NULL;
> }
> break;
> case IMM:
> if (p && q)
> {
> add_right(p, ix, iy);
> merge_left(p, q, out_poly);
> add_local_min(&out_poly, e0, ix, iy);
> e1->outp[ABOVE]=3D e0->outp[ABOVE];
> }
> break;
> case EMM:
> if (p && q)
> {
> add_left(p, ix, iy);
> merge_right(p, q, out_poly);
> add_local_min(&out_poly, e0, ix, iy);
> e1->outp[ABOVE]=3D e0->outp[ABOVE];
> }
> break;
> default:
> break;
> } /* End of switch */
> } /* End of contributing intersection conditional */
>
> /* Swap bundle sides in response to edge crossing */
> if (e0->bundle[ABOVE][CLIP])
> e1->bside[CLIP]=3D !e1->bside[CLIP];
> if (e1->bundle[ABOVE][CLIP])
> e0->bside[CLIP]=3D !e0->bside[CLIP];
> if (e0->bundle[ABOVE][SUBJ])
> e1->bside[SUBJ]=3D !e1->bside[SUBJ];
> if (e1->bundle[ABOVE][SUBJ])
> e0->bside[SUBJ]=3D !e0->bside[SUBJ];
>
> /* Swap e0 and e1 bundles in the AET */
> prev_edge=3D e0->prev;
> next_edge=3D e1->next;
> if (next_edge)
> next_edge->prev=3D e0;
>
> if (e0->bstate[ABOVE] =3D=3D BUNDLE_HEAD)
> {
> search=3D TRUE;
> while (search)
> {
> prev_edge=3D prev_edge->prev;
> if (prev_edge)
> {
> if (prev_edge->bstate[ABOVE] !=3D BUNDLE_TAIL)
> search=3D FALSE;
> }
> else
> search=3D FALSE;
> }
> }
> if (!prev_edge)
> {
> aet->prev=3D e1;
> e1->next=3D aet;
> aet=3D e0->next;
> }
> else
> {
> prev_edge->next->prev=3D e1;
> e1->next=3D prev_edge->next;
> prev_edge->next=3D e0->next;
> }
> e0->next->prev=3D prev_edge;
> e1->next->prev=3D e1;
> e0->next=3D next_edge;
> } /* End of IT loop*/
>
> /* Prepare for next scanbeam */
> for (edge=3D aet; edge; edge=3D next_edge)
> {
> next_edge=3D edge->next;
> succ_edge=3D edge->succ;
>
> if ((edge->top.y =3D=3D yt) && succ_edge)
> {
> /* Replace AET edge by its successor */
> succ_edge->outp[BELOW]=3D edge->outp[ABOVE];
> succ_edge->bstate[BELOW]=3D edge->bstate[ABOVE];
> succ_edge->bundle[BELOW][CLIP]=3D edge->bundle[ABOVE][CLIP];
> succ_edge->bundle[BELOW][SUBJ]=3D edge->bundle[ABOVE][SUBJ];
> prev_edge=3D edge->prev;
> if (prev_edge)
> prev_edge->next=3D succ_edge;
> else
> aet=3D succ_edge;
> if (next_edge)
> next_edge->prev=3D succ_edge;
> succ_edge->prev=3D prev_edge;
> succ_edge->next=3D next_edge;
> }
> else
> {
> /* Update this edge */
> edge->outp[BELOW]=3D edge->outp[ABOVE];
> edge->bstate[BELOW]=3D edge->bstate[ABOVE];
> edge->bundle[BELOW][CLIP]=3D edge->bundle[ABOVE][CLIP];
> edge->bundle[BELOW][SUBJ]=3D edge->bundle[ABOVE][SUBJ];
> edge->xb=3D edge->xt;
> }
> edge->outp[ABOVE]=3D NULL;
> }
> }
> } /* =3D=3D=3D END OF SCANBEAM PROCESSING =3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
*/
>
> /* Generate result polygon from out_poly */
> result->contour=3D NULL;
> result->hole=3D NULL;
> result->num_contours=3D count_contours(out_poly);
> if (result->num_contours > 0)
> {
> MALLOC(result->hole, result->num_contours
> * sizeof(int), "hole flag table creation");
> MALLOC(result->contour, result->num_contours
> * sizeof(gpc_vertex_list), "contour creation");
>
> c=3D 0;
> for (poly=3D out_poly; poly; poly=3D npoly)
> {
> npoly=3D poly->next;
> if (poly->active)
> {
> result->hole[c]=3D poly->proxy->hole;
> result->contour[c].num_vertices=3D poly->active;
> MALLOC(result->contour[c].vertex,
> result->contour[c].num_vertices * sizeof(gpc_vertex),
> "vertex creation");
>
> v=3D result->contour[c].num_vertices - 1;
> for (vtx=3D poly->proxy->v[LEFT]; vtx; vtx=3D nv)
> {
> nv=3D vtx->next;
> result->contour[c].vertex[v].x=3D vtx->x;
> result->contour[c].vertex[v].y=3D vtx->y;
> FREE(vtx);
> v--;
> }
> c++;
> }
> FREE(poly);
> }
> }
>
> /* Tidy up */
> reset_it(&it);
> reset_lmt(&lmt);
> FREE(c_heap);
> FREE(s_heap);
> FREE(sbt);
> }
>
> void gpc_free_tristrip(gpc_tristrip *t)
> {
> int s;
>
> for (s=3D 0; s < t->num_strips; s++)
> FREE(t->strip[s].vertex);
> FREE(t->strip);
> t->num_strips=3D 0;
> }
>
> void gpc_polygon_to_tristrip(gpc_polygon *s, gpc_tristrip *t)
> {
> gpc_polygon c;
>
> c.num_contours=3D 0;
> c.hole=3D NULL;
> c.contour=3D NULL;
> gpc_tristrip_clip(GPC_DIFF, s, &c, t);
> }
>
> void gpc_tristrip_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip,
> gpc_tristrip *result)
> {
> sb_tree *sbtree=3D NULL;
> it_node *it=3D NULL, *intersect;
> edge_node *edge, *prev_edge, *next_edge, *succ_edge, *e0, *e1;
> edge_node *aet=3D NULL, *c_heap=3D NULL, *s_heap=3D NULL, *cf;
> lmt_node *lmt=3D NULL, *local_min;
> polygon_node *tlist=3D NULL, *tn, *tnn, *p, *q;
> vertex_node *lt, *ltn, *rt, *rtn;
> h_state horiz[2];
> vertex_type cft;
> int in[2], exists[2], parity[2]=3D {LEFT, LEFT};
> int s, v, contributing, search, scanbeam=3D 0, sbt_entries=
=3D 0;
> int vclass, bl, br, tl, tr;
> double *sbt=3D NULL, xb, px, nx, yb, yt, dy, ix, iy;
>
> /* Test for trivial NULL result cases */
> if (((subj->num_contours =3D=3D 0) && (clip->num_contours =3D=3D 0))
> || ((subj->num_contours =3D=3D 0) && ((op =3D=3D GPC_INT) || (op =3D=
=3D GPC_DIFF)))
> || ((clip->num_contours =3D=3D 0) && (op =3D=3D GPC_INT)))
> {
> result->num_strips=3D 0;
> result->strip=3D NULL;
> return;
> }
>
> /* Identify potentialy contributing contours */
> if (((op =3D=3D GPC_INT) || (op =3D=3D GPC_DIFF))
> && (subj->num_contours > 0) && (clip->num_contours > 0))
> minimax_test(subj, clip, op);
>
> /* Build LMT */
> if (subj->num_contours > 0)
> s_heap=3D build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op);
> if (clip->num_contours > 0)
> c_heap=3D build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op);
>
> /* Return a NULL result if no contours contribute */
> if (lmt =3D=3D NULL)
> {
> result->num_strips=3D 0;
> result->strip=3D NULL;
> reset_lmt(&lmt);
> FREE(s_heap);
> FREE(c_heap);
> return;
> }
>
> /* Build scanbeam table from scanbeam tree */
> MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation");
> build_sbt(&scanbeam, sbt, sbtree);
> scanbeam=3D 0;
> free_sbtree(&sbtree);
>
> /* Invert clip polygon for difference operation */
> if (op =3D=3D GPC_DIFF)
> parity[CLIP]=3D RIGHT;
>
> local_min=3D lmt;
>
> /* Process each scanbeam */
> while (scanbeam < sbt_entries)
> {
> /* Set yb and yt to the bottom and top of the scanbeam */
> yb=3D sbt[scanbeam++];
> if (scanbeam < sbt_entries)
> {
> yt=3D sbt[scanbeam];
> dy=3D yt - yb;
> }
>
> /* =3D=3D=3D SCANBEAM BOUNDARY PROCESSING =3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D */
>
> /* If LMT node corresponding to yb exists */
> if (local_min)
> {
> if (local_min->y =3D=3D yb)
> {
> /* Add edges starting at this local minimum to the AET */
> for (edge=3D local_min->first_bound; edge; edge=3D edge->next_b=
ound)
> add_edge_to_aet(&aet, edge, NULL);
>
> local_min=3D local_min->next;
> }
> }
>
> /* Set dummy previous x value */
> px=3D -DBL_MAX;
>
> /* Create bundles within AET */
> e0=3D aet;
> e1=3D aet;
>
> /* Set up bundle fields of first edge */
> aet->bundle[ABOVE][ aet->type]=3D (aet->top.y !=3D yb);
> aet->bundle[ABOVE][!aet->type]=3D FALSE;
> aet->bstate[ABOVE]=3D UNBUNDLED;
>
> for (next_edge=3D aet->next; next_edge; next_edge=3D next_edge->nex=
t)
> {
> /* Set up bundle fields of next edge */
> next_edge->bundle[ABOVE][ next_edge->type]=3D (next_edge->top.y !=
=3D yb);
> next_edge->bundle[ABOVE][!next_edge->type]=3D FALSE;
> next_edge->bstate[ABOVE]=3D UNBUNDLED;
>
> /* Bundle edges above the scanbeam boundary if they coincide */
> if (next_edge->bundle[ABOVE][next_edge->type])
> {
> if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx)
> && (e0->top.y !=3D yb))
> {
> next_edge->bundle[ABOVE][ next_edge->type]^=3D
> e0->bundle[ABOVE][ next_edge->type];
> next_edge->bundle[ABOVE][!next_edge->type]=3D
> e0->bundle[ABOVE][!next_edge->type];
> next_edge->bstate[ABOVE]=3D BUNDLE_HEAD;
> e0->bundle[ABOVE][CLIP]=3D FALSE;
> e0->bundle[ABOVE][SUBJ]=3D FALSE;
> e0->bstate[ABOVE]=3D BUNDLE_TAIL;
> }
> e0=3D next_edge;
> }
> }
>
> horiz[CLIP]=3D NH;
> horiz[SUBJ]=3D NH;
>
> /* Process each edge at this scanbeam boundary */
> for (edge=3D aet; edge; edge=3D edge->next)
> {
> exists[CLIP]=3D edge->bundle[ABOVE][CLIP] +
> (edge->bundle[BELOW][CLIP] << 1);
> exists[SUBJ]=3D edge->bundle[ABOVE][SUBJ] +
> (edge->bundle[BELOW][SUBJ] << 1);
>
> if (exists[CLIP] || exists[SUBJ])
> {
> /* Set bundle side */
> edge->bside[CLIP]=3D parity[CLIP];
> edge->bside[SUBJ]=3D parity[SUBJ];
>
> /* Determine contributing status and quadrant occupancies */
> switch (op)
> {
> case GPC_DIFF:
> case GPC_INT:
> contributing=3D (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ]=
))
> || (exists[SUBJ] && (parity[CLIP] || horiz[CLIP]))
> || (exists[CLIP] && exists[SUBJ]
> && (parity[CLIP] =3D=3D parity[SUBJ]));
> br=3D (parity[CLIP])
> && (parity[SUBJ]);
> bl=3D (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
> && (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
> tr=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH))
> && (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH));
> tl=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH) ^ edge->bundle[BELO=
W][CLIP])
> && (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH) ^ edge->bundle[BELOW]=
[SUBJ]);
> break;
> case GPC_XOR:
> contributing=3D exists[CLIP] || exists[SUBJ];
> br=3D (parity[CLIP])
> ^ (parity[SUBJ]);
> bl=3D (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
> ^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
> tr=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH))
> ^ (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH));
> tl=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH) ^ edge->bundle[BELO=
W][CLIP])
> ^ (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH) ^ edge->bundle[BELOW]=
[SUBJ]);
> break;
> case GPC_UNION:
> contributing=3D (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ=
]))
> || (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP])=
)
> || (exists[CLIP] && exists[SUBJ]
> && (parity[CLIP] =3D=3D parity[SUBJ]));
> br=3D (parity[CLIP])
> || (parity[SUBJ]);
> bl=3D (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
> || (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
> tr=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH))
> || (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH));
> tl=3D (parity[CLIP] ^ (horiz[CLIP]!=3DNH) ^ edge->bundle[BELO=
W][CLIP])
> || (parity[SUBJ] ^ (horiz[SUBJ]!=3DNH) ^ edge->bundle[BELOW]=
[SUBJ]);
> break;
> }
>
> /* Update parity */
> parity[CLIP]^=3D edge->bundle[ABOVE][CLIP];
> parity[SUBJ]^=3D edge->bundle[ABOVE][SUBJ];
>
> /* Update horizontal state */
> if (exists[CLIP])
> horiz[CLIP]=3D
> next_h_state[horiz[CLIP]]
> [((exists[CLIP] - 1) << 1) + parity[CLIP]];
> if (exists[SUBJ])
> horiz[SUBJ]=3D
> next_h_state[horiz[SUBJ]]
> [((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
>
> vclass=3D tr + (tl << 1) + (br << 2) + (bl << 3);
>
> if (contributing)
> {
> xb=3D edge->xb;
>
> switch (vclass)
> {
> case EMN:
> new_tristrip(&tlist, edge, xb, yb);
> cf=3D edge;
> break;
> case ERI:
> edge->outp[ABOVE]=3D cf->outp[ABOVE];
> if (xb !=3D cf->xb)
> VERTEX(edge, ABOVE, RIGHT, xb, yb);
> cf=3D NULL;
> break;
> case ELI:
> VERTEX(edge, BELOW, LEFT, xb, yb);
> edge->outp[ABOVE]=3D NULL;
> cf=3D edge;
> break;
> case EMX:
> if (xb !=3D cf->xb)
> VERTEX(edge, BELOW, RIGHT, xb, yb);
> edge->outp[ABOVE]=3D NULL;
> cf=3D NULL;
> break;
> case IMN:
> if (cft =3D=3D LED)
> {
> if (cf->bot.y !=3D yb)
> VERTEX(cf, BELOW, LEFT, cf->xb, yb);
> new_tristrip(&tlist, cf, cf->xb, yb);
> }
> edge->outp[ABOVE]=3D cf->outp[ABOVE];
> VERTEX(edge, ABOVE, RIGHT, xb, yb);
> break;
> case ILI:
> new_tristrip(&tlist, edge, xb, yb);
> cf=3D edge;
> cft=3D ILI;
> break;
> case IRI:
> if (cft =3D=3D LED)
> {
> if (cf->bot.y !=3D yb)
> VERTEX(cf, BELOW, LEFT, cf->xb, yb);
> new_tristrip(&tlist, cf, cf->xb, yb);
> }
> VERTEX(edge, BELOW, RIGHT, xb, yb);
> edge->outp[ABOVE]=3D NULL;
> break;
> case IMX:
> VERTEX(edge, BELOW, LEFT, xb, yb);
> edge->outp[ABOVE]=3D NULL;
> cft=3D IMX;
> break;
> case IMM:
> VERTEX(edge, BELOW, LEFT, xb, yb);
> edge->outp[ABOVE]=3D cf->outp[ABOVE];
> if (xb !=3D cf->xb)
> VERTEX(cf, ABOVE, RIGHT, xb, yb);
> cf=3D edge;
> break;
> case EMM:
> VERTEX(edge, BELOW, RIGHT, xb, yb);
> edge->outp[ABOVE]=3D NULL;
> new_tristrip(&tlist, edge, xb, yb);
> cf=3D edge;
> break;
> case LED:
> if (edge->bot.y =3D=3D yb)
> VERTEX(edge, BELOW, LEFT, xb, yb);
> edge->outp[ABOVE]=3D edge->outp[BELOW];
> cf=3D edge;
> cft=3D LED;
> break;
> case RED:
> edge->outp[ABOVE]=3D cf->outp[ABOVE];
> if (cft =3D=3D LED)
> {
> if (cf->bot.y =3D=3D yb)
> {
> VERTEX(edge, BELOW, RIGHT, xb, yb);
> }
> else
> {
> if (edge->bot.y =3D=3D yb)
> {
> VERTEX(cf, BELOW, LEFT, cf->xb, yb);
> VERTEX(edge, BELOW, RIGHT, xb, yb);
> }
> }
> }
> else
> {
> VERTEX(edge, BELOW, RIGHT, xb, yb);
> VERTEX(edge, ABOVE, RIGHT, xb, yb);
> }
> cf=3D NULL;
> break;
> default:
> break;
> } /* End of switch */
> } /* End of contributing conditional */
> } /* End of edge exists conditional */
> } /* End of AET loop */
>
> /* Delete terminating edges from the AET, otherwise compute xt */
> for (edge=3D aet; edge; edge=3D edge->next)
> {
> if (edge->top.y =3D=3D yb)
> {
> prev_edge=3D edge->prev;
> next_edge=3D edge->next;
> if (prev_edge)
> prev_edge->next=3D next_edge;
> else
> aet=3D next_edge;
> if (next_edge)
> next_edge->prev=3D prev_edge;
>
> /* Copy bundle head state to the adjacent tail edge if required=
*/
> if ((edge->bstate[BELOW] =3D=3D BUNDLE_HEAD) && prev_edge)
> {
> if (prev_edge->bstate[BELOW] =3D=3D BUNDLE_TAIL)
> {
> prev_edge->outp[BELOW]=3D edge->outp[BELOW];
> prev_edge->bstate[BELOW]=3D UNBUNDLED;
> if (prev_edge->prev)
> if (prev_edge->prev->bstate[BELOW] =3D=3D BUNDLE_TAIL)
> prev_edge->bstate[BELOW]=3D BUNDLE_HEAD;
> }
> }
> }
> else
> {
> if (edge->top.y =3D=3D yt)
> edge->xt=3D edge->top.x;
> else
> edge->xt=3D edge->bot.x + edge->dx * (yt - edge->bot.y);
> }
> }
>
> if (scanbeam < sbt_entries)
> {
> /* =3D=3D=3D SCANBEAM INTERIOR PROCESSING =3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D */
>
> build_intersection_table(&it, aet, dy);
>
> /* Process each node in the intersection table */
> for (intersect=3D it; intersect; intersect=3D intersect->next)
> {
> e0=3D intersect->ie[0];
> e1=3D intersect->ie[1];
>
> /* Only generate output for contributing intersections */
> if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ])
> && (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ]))
> {
> p=3D e0->outp[ABOVE];
> q=3D e1->outp[ABOVE];
> ix=3D intersect->point.x;
> iy=3D intersect->point.y + yb;
>
> in[CLIP]=3D ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP])
> || ( e1->bundle[ABOVE][CLIP] && e1->bside[CLIP])
> || (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLI=
P]
> && e0->bside[CLIP] && e1->bside[CLIP]);
> in[SUBJ]=3D ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ])
> || ( e1->bundle[ABOVE][SUBJ] && e1->bside[SUBJ])
> || (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUB=
J]
> && e0->bside[SUBJ] && e1->bside[SUBJ]);
>
> /* Determine quadrant occupancies */
> switch (op)
> {
> case GPC_DIFF:
> case GPC_INT:
> tr=3D (in[CLIP])
> && (in[SUBJ]);
> tl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
> && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
> br=3D (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
> && (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
> bl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOV=
E][CLIP])
> && (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE]=
[SUBJ]);
> break;
> case GPC_XOR:
> tr=3D (in[CLIP])
> ^ (in[SUBJ]);
> tl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
> ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
> br=3D (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
> ^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
> bl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOV=
E][CLIP])
> ^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE]=
[SUBJ]);
> break;
> case GPC_UNION:
> tr=3D (in[CLIP])
> || (in[SUBJ]);
> tl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
> || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
> br=3D (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
> || (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
> bl=3D (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOV=
E][CLIP])
> || (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE]=
[SUBJ]);
> break;
> }
>
> vclass=3D tr + (tl << 1) + (br << 2) + (bl << 3);
>
> switch (vclass)
> {
> case EMN:
> new_tristrip(&tlist, e1, ix, iy);
> e0->outp[ABOVE]=3D e1->outp[ABOVE];
> break;
> case ERI:
> if (p)
> {
> P_EDGE(prev_edge, e0, ABOVE, px, iy);
> VERTEX(prev_edge, ABOVE, LEFT, px, iy);
> VERTEX(e0, ABOVE, RIGHT, ix, iy);
> e1->outp[ABOVE]=3D e0->outp[ABOVE];
> e0->outp[ABOVE]=3D NULL;
> }
> break;
> case ELI:
> if (q)
> {
> N_EDGE(next_edge, e1, ABOVE, nx, iy);
> VERTEX(e1, ABOVE, LEFT, ix, iy);
> VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
> e0->outp[ABOVE]=3D e1->outp[ABOVE];
> e1->outp[ABOVE]=3D NULL;
> }
> break;
> case EMX:
> if (p && q)
> {
> VERTEX(e0, ABOVE, LEFT, ix, iy);
> e0->outp[ABOVE]=3D NULL;
> e1->outp[ABOVE]=3D NULL;
> }
> break;
> case IMN:
> P_EDGE(prev_edge, e0, ABOVE, px, iy);
> VERTEX(prev_edge, ABOVE, LEFT, px, iy);
> N_EDGE(next_edge, e1, ABOVE, nx, iy);
> VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
> new_tristrip(&tlist, prev_edge, px, iy);
> e1->outp[ABOVE]=3D prev_edge->outp[ABOVE];
> VERTEX(e1, ABOVE, RIGHT, ix, iy);
> new_tristrip(&tlist, e0, ix, iy);
> next_edge->outp[ABOVE]=3D e0->outp[ABOVE];
> VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
> break;
> case ILI:
> if (p)
> {
> VERTEX(e0, ABOVE, LEFT, ix, iy);
> N_EDGE(next_edge, e1, ABOVE, nx, iy);
> VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
> e1->outp[ABOVE]=3D e0->outp[ABOVE];
> e0->outp[ABOVE]=3D NULL;
> }
> break;
> case IRI:
> if (q)
> {
> VERTEX(e1, ABOVE, RIGHT, ix, iy);
> P_EDGE(prev_edge, e0, ABOVE, px, iy);
> VERTEX(prev_edge, ABOVE, LEFT, px, iy);
> e0->outp[ABOVE]=3D e1->outp[ABOVE];
> e1->outp[ABOVE]=3D NULL;
> }
> break;
> case IMX:
> if (p && q)
> {
> VERTEX(e0, ABOVE, RIGHT, ix, iy);
> VERTEX(e1, ABOVE, LEFT, ix, iy);
> e0->outp[ABOVE]=3D NULL;
> e1->outp[ABOVE]=3D NULL;
> P_EDGE(prev_edge, e0, ABOVE, px, iy);
> VERTEX(prev_edge, ABOVE, LEFT, px, iy);
> new_tristrip(&tlist, prev_edge, px, iy);
> N_EDGE(next_edge, e1, ABOVE, nx, iy);
> VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
> next_edge->outp[ABOVE]=3D prev_edge->outp[ABOVE];
> VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
> }
> break;
> case IMM:
> if (p && q)
> {
> VERTEX(e0, ABOVE, RIGHT, ix, iy);
> VERTEX(e1, ABOVE, LEFT, ix, iy);
> P_EDGE(prev_edge, e0, ABOVE, px, iy);
> VERTEX(prev_edge, ABOVE, LEFT, px, iy);
> new_tristrip(&tlist, prev_edge, px, iy);
> N_EDGE(next_edge, e1, ABOVE, nx, iy);
> VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
> e1->outp[ABOVE]=3D prev_edge->outp[ABOVE];
> VERTEX(e1, ABOVE, RIGHT, ix, iy);
> new_tristrip(&tlist, e0, ix, iy);
> next_edge->outp[ABOVE]=3D e0->outp[ABOVE];
> VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
> }
> break;
> case EMM:
> if (p && q)
> {
> VERTEX(e0, ABOVE, LEFT, ix, iy);
> new_tristrip(&tlist, e1, ix, iy);
> e0->outp[ABOVE]=3D e1->outp[ABOVE];
> }
> break;
> default:
> break;
> } /* End of switch */
> } /* End of contributing intersection conditional */
>
> /* Swap bundle sides in response to edge crossing */
> if (e0->bundle[ABOVE][CLIP])
> e1->bside[CLIP]=3D !e1->bside[CLIP];
> if (e1->bundle[ABOVE][CLIP])
> e0->bside[CLIP]=3D !e0->bside[CLIP];
> if (e0->bundle[ABOVE][SUBJ])
> e1->bside[SUBJ]=3D !e1->bside[SUBJ];
> if (e1->bundle[ABOVE][SUBJ])
> e0->bside[SUBJ]=3D !e0->bside[SUBJ];
>
> /* Swap e0 and e1 bundles in the AET */
> prev_edge=3D e0->prev;
> next_edge=3D e1->next;
> if (e1->next)
> e1->next->prev=3D e0;
>
> if (e0->bstate[ABOVE] =3D=3D BUNDLE_HEAD)
> {
> search=3D TRUE;
> while (search)
> {
> prev_edge=3D prev_edge->prev;
> if (prev_edge)
> {
> if (prev_edge->bundle[ABOVE][CLIP]
> || prev_edge->bundle[ABOVE][SUBJ]
> || (prev_edge->bstate[ABOVE] =3D=3D BUNDLE_HEAD))
> search=3D FALSE;
> }
> else
> search=3D FALSE;
> }
> }
> if (!prev_edge)
> {
> e1->next=3D aet;
> aet=3D e0->next;
> }
> else
> {
> e1->next=3D prev_edge->next;
> prev_edge->next=3D e0->next;
> }
> e0->next->prev=3D prev_edge;
> e1->next->prev=3D e1;
> e0->next=3D next_edge;
> } /* End of IT loop*/
>
> /* Prepare for next scanbeam */
> for (edge=3D aet; edge; edge=3D next_edge)
> {
> next_edge=3D edge->next;
> succ_edge=3D edge->succ;
>
> if ((edge->top.y =3D=3D yt) && succ_edge)
> {
> /* Replace AET edge by its successor */
> succ_edge->outp[BELOW]=3D edge->outp[ABOVE];
> succ_edge->bstate[BELOW]=3D edge->bstate[ABOVE];
> succ_edge->bundle[BELOW][CLIP]=3D edge->bundle[ABOVE][CLIP];
> succ_edge->bundle[BELOW][SUBJ]=3D edge->bundle[ABOVE][SUBJ];
> prev_edge=3D edge->prev;
> if (prev_edge)
> prev_edge->next=3D succ_edge;
> else
> aet=3D succ_edge;
> if (next_edge)
> next_edge->prev=3D succ_edge;
> succ_edge->prev=3D prev_edge;
> succ_edge->next=3D next_edge;
> }
> else
> {
> /* Update this edge */
> edge->outp[BELOW]=3D edge->outp[ABOVE];
> edge->bstate[BELOW]=3D edge->bstate[ABOVE];
> edge->bundle[BELOW][CLIP]=3D edge->bundle[ABOVE][CLIP];
> edge->bundle[BELOW][SUBJ]=3D edge->bundle[ABOVE][SUBJ];
> edge->xb=3D edge->xt;
> }
> edge->outp[ABOVE]=3D NULL;
> }
> }
> } /* =3D=3D=3D END OF SCANBEAM PROCESSING =3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
*/
>
> /* Generate result tristrip from tlist */
> result->strip=3D NULL;
> result->num_strips=3D count_tristrips(tlist);
> if (result->num_strips > 0)
> {
> MALLOC(result->strip, result->num_strips * sizeof(gpc_vertex_list),
> "tristrip list creation");
>
> s=3D 0;
> for (tn=3D tlist; tn; tn=3D tnn)
> {
> tnn=3D tn->next;
>
> if (tn->active > 2)
> {
> /* Valid tristrip: copy the vertices and free the heap */
> result->strip[s].num_vertices=3D tn->active;
> MALLOC(result->strip[s].vertex, tn->active * sizeof(gpc_vertex)=
,
> "tristrip creation");
> v=3D 0;
> if (INVERT_TRISTRIPS)
> {
> lt=3D tn->v[RIGHT];
> rt=3D tn->v[LEFT];
> }
> else
> {
> lt=3D tn->v[LEFT];
> rt=3D tn->v[RIGHT];
> }
> while (lt || rt)
> {
> if (lt)
> {
> ltn=3D lt->next;
> result->strip[s].vertex[v].x=3D lt->x;
> result->strip[s].vertex[v].y=3D lt->y;
> v++;
> FREE(lt);
> lt=3D ltn;
> }
> if (rt)
> {
> rtn=3D rt->next;
> result->strip[s].vertex[v].x=3D rt->x;
> result->strip[s].vertex[v].y=3D rt->y;
> v++;
> FREE(rt);
> rt=3D rtn;
> }
> }
> s++;
> }
> else
> {
> /* Invalid tristrip: just free the heap */
> for (lt=3D tn->v[LEFT]; lt; lt=3D ltn)
> {
> ltn=3D lt->next;
> FREE(lt);
> }
> for (rt=3D tn->v[RIGHT]; rt; rt=3Drtn)
> {
> rtn=3D rt->next;
> FREE(rt);
> }
> }
> FREE(tn);
> }
> }
>
> /* Tidy up */
> reset_it(&it);
> reset_lmt(&lmt);
> FREE(c_heap);
> FREE(s_heap);
> FREE(sbt);
> }
>
> /*
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> End of file: gpc.c
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> */
>
> ---------------------------------------------------------------------=
---
> --
> -- Selected TOC Entries:
> --
> \connect - postgres
> --
> -- TOC Entry ID 2 (OID 922575)
> --
> -- Name: testgpc Type: TABLE Owner: postgres
> --
>
> CREATE TABLE "testgpc" (
> "id" integer,
> "geom" geometry
> );
>
> --
> -- Data for TOC Entry ID 3 (OID 922575)
> --
> -- Name: testgpc Type: TABLE DATA Owner: postgres
> --
>
> COPY "testgpc" FROM stdin;
> 1 SRID=3D-1;POLYGON((1 1,3 1,3 3,1 1))
> 2 SRID=3D-1;POLYGON((2 1,2 3,1 3,2 1))
> 3 SRID=3D-1;POLYGON((3 2,10 2,10 6,8 6,8 3,5 3,5 6,3 6,3 2),(4.5 =
4.5,4.5 5,3.5 5,3.5 4.5,4.5 4.5),(9.5 4.5,9.5 5,8.5 5,8.5 4.5,9.5 4.5))
> 4 SRID=3D-1;POLYGON((12 4,12 8,1 8,1 4,12 4))
> 5 SRID=3D-1;POLYGON((9 5,9 7.5,6.5 7.5,6.5 5,9 5),(8.5 5,8.5 7,7 =
7,8.5 5))
> \.
---------------------- multipart/mixed attachment
A non-text attachment was scrubbed...
Name: cedric.bernier.vcf
Type: text/x-vcard
Size: 377 bytes
Desc: Carte pour Cedric BERNIER
Url : http://lists.refractions.net/pipermail/postgis-users/attachments/20020430/ca161ab1/cedric.bernier.vcf
---------------------- multipart/mixed attachment--