#include <stdexcept>
#include "gpc.h"
#include <stdlib.h>
#include <float.h>
#include <math.h>

Include dependency graph for gpc.cpp:

Classes
struct	bbox_shape

class	edge_node

struct	it_shape

class	lmt_node

class	polygon_node

struct	sbt_t_shape

struct	st_shape

struct	v_shape

Macros
#define	ABOVE 0

#define	BELOW 1

#define	CLIP 0

#define	EQ(a, b) (fabs((a) - (b)) <= GPC_EPSILON)

#define	FALSE 0

#define	FREE(p) {if (p) {free(p); (p)= NULL;}}

#define	FWD_MIN(v, i, n)

#define	INVERT_TRISTRIPS FALSE

#define	LEFT 0

#define	MALLOC(p, b, s, t)

#define	N_EDGE(d, e, p, i, j)

#define	NEXT_INDEX(i, n) ((i + 1 ) % n)

#define	NOT_FMAX(v, i, n) (v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex.y)

#define	NOT_RMAX(v, i, n) (v[PREV_INDEX(i, n)].vertex.y > v[i].vertex.y)

#define	OPTIMAL(v, i, n)

#define	P_EDGE(d, e, p, i, j)

#define	PREV_INDEX(i, n) ((i - 1 + n) % n)

#define	REV_MIN(v, i, n)

#define	RIGHT 1

#define	SUBJ 1

#define	TRUE 1

#define	VERTEX(e, p, s, x, y)

Typedefs
typedef struct bbox_shape	bbox

typedef struct it_shape	it_node

typedef struct sbt_t_shape	sb_tree

typedef struct st_shape	st_node

typedef struct v_shape	vertex_node

Enumerations
enum	bundle_state { UNBUNDLED, BUNDLE_HEAD, BUNDLE_TAIL }

enum	h_state { NH, BH, TH }

enum	vertex_type { NUL, EMX, ELI, TED, ERI, RED, IMM, IMN, EMN, EMM, LED, ILI, BED, IRI, IMX, FUL }

Functions
static void	add_edge_to_aet (edge_node *aet, edge_node edge, edge_node *prev)

static void	add_intersection (it_node *it, edge_node edge0, edge_node *edge1, double x, double y)

static void	add_left (polygon_node *p, double x, double y)

static void	add_local_min (polygon_node *p, edge_node edge, double x, double y)

static void	add_right (polygon_node *p, double x, double y)

static void	add_st_edge (st_node st, it_node it, edge_node *edge, double dy)

static void	add_to_sbtree (int entries, sb_tree *sbtree, double y)

static void	add_vertex (vertex_node **t, double x, double y)

static edge_node **	bound_list (lmt_node **lmt, double y)

static void	build_intersection_table (it_node *it, edge_node aet, double dy)

static edge_node *	build_lmt (lmt_node lmt, sb_tree sbtree, int sbt_entries, gpc_polygon p, int type, gpc_op op)

static void	build_sbt (int entries, double sbt, sb_tree *sbtree)

static int	count_contours (polygon_node *polygon)

static int	count_optimal_vertices (gpc_vertex_list c)

static int	count_tristrips (polygon_node *tn)

static bbox *	create_contour_bboxes (gpc_polygon *p)

static void	free_sbtree (sb_tree **sbtree)

void	gpc_add_contour (gpc_polygon p, gpc_vertex_list new_contour, int hole)

void	gpc_free_polygon (gpc_polygon *p)

void	gpc_free_tristrip (gpc_tristrip *t)

void	gpc_polygon_clip (gpc_op op, gpc_polygon subj, gpc_polygon clip, gpc_polygon *result)

void	gpc_polygon_to_tristrip (gpc_polygon s, gpc_tristrip t)

void	gpc_tristrip_clip (gpc_op op, gpc_polygon subj, gpc_polygon clip, gpc_tristrip *result)

void	gpc_write_polygon (FILE fp, int write_hole_flags, gpc_polygon p)

static void	insert_bound (edge_node *b, edge_node e)

static void	merge_left (polygon_node p, polygon_node q, polygon_node *list)

static void	merge_right (polygon_node p, polygon_node q, polygon_node *list)

static void	minimax_test (gpc_polygon subj, gpc_polygon clip, gpc_op op)

static void	new_tristrip (polygon_node *tn, edge_node edge, double x, double y)

static void	reset_it (it_node **it)

static void	reset_lmt (lmt_node **lmt)

Variables
const h_state	next_h_state [3][6]

Macro Definition Documentation

◆ ABOVE

#define ABOVE 0

Definition at line 106 of file gpc.cpp.

◆ BELOW

#define BELOW 1

Definition at line 107 of file gpc.cpp.

◆ CLIP

#define CLIP 0

Definition at line 109 of file gpc.cpp.

◆ EQ

#define EQ	(	a,
		b
	)	(fabs((a) - (b)) <= GPC_EPSILON)

Definition at line 121 of file gpc.cpp.

◆ FALSE

#define FALSE 0

Definition at line 99 of file gpc.cpp.

◆ FREE

#define FREE ( p ) {if (p) {free(p); (p)= NULL;}}

Definition at line 155 of file gpc.cpp.

◆ FWD_MIN

#define FWD_MIN	(	v,
		i,
		n
	)

Value:

((v[PREV_INDEX(i, n)].vertex.y >= v[i].vertex.y) \

&& (v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex.y))

NEXT_INDEX

#define NEXT_INDEX(i, n)

Definition: gpc.cpp:124

PREV_INDEX

#define PREV_INDEX(i, n)

Definition: gpc.cpp:123

Definition at line 129 of file gpc.cpp.

◆ INVERT_TRISTRIPS

#define INVERT_TRISTRIPS FALSE

Definition at line 112 of file gpc.cpp.

◆ LEFT

#define LEFT 0

Definition at line 103 of file gpc.cpp.

◆ MALLOC

#define MALLOC	(	p,
		b,
		s,
		t
	)

Value:

{if ((b) > 0) { \
                                                        p= (t*)malloc(b); if (!(p)) { \
                                                        fprintf(stderr, "gpc malloc failure: %s\n", s); \
                                                        exit(0);}} else p= NULL;}

Definition at line 150 of file gpc.cpp.

◆ N_EDGE

#define N_EDGE	(	d,
		e,
		p,
		i,
		j
	)

Value:

{(d)= (e); \
                                                        do {(d)= (d)->next;} while (!(d)->outp[(p)]); \
                                                        (i)= (d)->bot.x + (d)->dx * ((j)-(d)->bot.y);}

Definition at line 146 of file gpc.cpp.

◆ NEXT_INDEX

#define NEXT_INDEX	(	i,
		n
	)	((i + 1 ) % n)

Definition at line 124 of file gpc.cpp.

◆ NOT_FMAX

#define NOT_FMAX	(	v,
		i,
		n
	)	(v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex.y)

Definition at line 132 of file gpc.cpp.

◆ NOT_RMAX

#define NOT_RMAX	(	v,
		i,
		n
	)	(v[PREV_INDEX(i, n)].vertex.y > v[i].vertex.y)

Definition at line 137 of file gpc.cpp.

◆ OPTIMAL

#define OPTIMAL	(	v,
		i,
		n
	)

Value:

((v[PREV_INDEX(i, n)].y != v[i].y) || \

(v[NEXT_INDEX(i, n)].y != v[i].y))

NEXT_INDEX

#define NEXT_INDEX(i, n)

Definition: gpc.cpp:124

PREV_INDEX

#define PREV_INDEX(i, n)

Definition: gpc.cpp:123

Definition at line 126 of file gpc.cpp.

◆ P_EDGE

#define P_EDGE	(	d,
		e,
		p,
		i,
		j
	)

Value:

{(d)= (e); \
                                                        do {(d)= (d)->prev;} while (!(d)->outp[(p)]); \
                                                        (i)= (d)->bot.x + (d)->dx * ((j)-(d)->bot.y);}

Definition at line 142 of file gpc.cpp.

◆ PREV_INDEX

#define PREV_INDEX	(	i,
		n
	)	((i - 1 + n) % n)

Definition at line 123 of file gpc.cpp.

◆ REV_MIN

#define REV_MIN	(	v,
		i,
		n
	)

Value:

((v[PREV_INDEX(i, n)].vertex.y > v[i].vertex.y) \

&& (v[NEXT_INDEX(i, n)].vertex.y >= v[i].vertex.y))

NEXT_INDEX

#define NEXT_INDEX(i, n)

Definition: gpc.cpp:124

PREV_INDEX

#define PREV_INDEX(i, n)

Definition: gpc.cpp:123

Definition at line 134 of file gpc.cpp.

◆ RIGHT

#define RIGHT 1

Definition at line 104 of file gpc.cpp.

◆ SUBJ

#define SUBJ 1

Definition at line 110 of file gpc.cpp.

◆ TRUE

#define TRUE 1

Definition at line 100 of file gpc.cpp.

◆ VERTEX

#define VERTEX	(	e,
		p,
		s,
		x,
		y
	)

Value:

{add_vertex(&((e)->outp[(p)]->v[(s)]), x, y); \

(e)->outp[(p)]->active++;}

add_vertex

static void add_vertex(vertex_node **t, double x, double y)

Definition: gpc.cpp:965

Definition at line 139 of file gpc.cpp.

Typedef Documentation

◆ bbox

typedef struct bbox_shape bbox

◆ it_node

typedef struct it_shape it_node

◆ sb_tree

typedef struct sbt_t_shape sb_tree

◆ st_node

typedef struct st_shape st_node

◆ vertex_node

typedef struct v_shape vertex_node

Enumeration Type Documentation

◆ bundle_state

enum bundle_state

Enumerator
UNBUNDLED
BUNDLE_HEAD
BUNDLE_TAIL

Definition at line 191 of file gpc.cpp.

◆ h_state

enum h_state

Enumerator
NH
BH
TH

Definition at line 184 of file gpc.cpp.

◆ vertex_type

enum vertex_type

Enumerator
NUL
EMX
ELI
TED
ERI
RED
IMM
IMN
EMN
EMM
LED
ILI
BED
IRI
IMX
FUL

Definition at line 164 of file gpc.cpp.

Function Documentation

◆ add_edge_to_aet()

static void add_edge_to_aet	(	edge_node **	aet,
		edge_node *	edge,
		edge_node *	prev
	)

static

Definition at line 628 of file gpc.cpp.

◆ add_intersection()

static void add_intersection	(	it_node **	it,
		edge_node *	edge0,
		edge_node *	edge1,
		double	x,
		double	y
	)

static

Definition at line 677 of file gpc.cpp.

◆ add_left()

static void add_left	(	polygon_node *	p,
		double	x,
		double	y
	)

static

Definition at line 822 of file gpc.cpp.

◆ add_local_min()

static void add_local_min	(	polygon_node **	p,
		edge_node *	edge,
		double	x,
		double	y
	)

static

Definition at line 921 of file gpc.cpp.

◆ add_right()

static void add_right	(	polygon_node *	p,
		double	x,
		double	y
	)

static

Definition at line 871 of file gpc.cpp.

◆ add_st_edge()

static void add_st_edge	(	st_node **	st,
		it_node **	it,
		edge_node *	edge,
		double	dy
	)

static

Definition at line 712 of file gpc.cpp.

◆ add_to_sbtree()

static void add_to_sbtree	(	int *	entries,
		sb_tree **	sbtree,
		double	y
	)

static

Definition at line 415 of file gpc.cpp.

◆ add_vertex()

static void add_vertex	(	vertex_node **	t,
		double	x,
		double	y
	)

static

Definition at line 965 of file gpc.cpp.

◆ bound_list()

static edge_node** bound_list	(	lmt_node **	lmt,
		double	y
	)

static

Definition at line 381 of file gpc.cpp.

◆ build_intersection_table()

static void build_intersection_table	(	it_node **	it,
		edge_node *	aet,
		double	dy
	)

static

Definition at line 762 of file gpc.cpp.

◆ build_lmt()

static edge_node* build_lmt	(	lmt_node **	lmt,
		sb_tree **	sbtree,
		int *	sbt_entries,
		gpc_polygon *	p,
		int	type,
		gpc_op	op
	)

static

Definition at line 483 of file gpc.cpp.

◆ build_sbt()

static void build_sbt	(	int *	entries,
		double *	sbt,
		sb_tree *	sbtree
	)

static

Definition at line 445 of file gpc.cpp.

◆ count_contours()

static int count_contours ( polygon_node * polygon )

static

Definition at line 788 of file gpc.cpp.

◆ count_optimal_vertices()

static int count_optimal_vertices ( gpc_vertex_list c )

static

Definition at line 467 of file gpc.cpp.

◆ count_tristrips()

static int count_tristrips ( polygon_node * tn )

static

Definition at line 954 of file gpc.cpp.

◆ create_contour_bboxes()

static bbox* create_contour_bboxes ( gpc_polygon * p )

static

Definition at line 1001 of file gpc.cpp.

◆ free_sbtree()

static void free_sbtree ( sb_tree ** sbtree )

static

Definition at line 456 of file gpc.cpp.

◆ gpc_add_contour()

void gpc_add_contour	(	gpc_polygon *	p,
		gpc_vertex_list *	new_contour,
		int	hole
	)

Definition at line 1148 of file gpc.cpp.

◆ gpc_free_polygon()

void gpc_free_polygon ( gpc_polygon * p )

Definition at line 1093 of file gpc.cpp.

◆ gpc_free_tristrip()

void gpc_free_tristrip ( gpc_tristrip * t )

Definition at line 1829 of file gpc.cpp.

◆ gpc_polygon_clip()

void gpc_polygon_clip	(	gpc_op	op,
		gpc_polygon *	subj,
		gpc_polygon *	clip,
		gpc_polygon *	result
	)

Definition at line 1189 of file gpc.cpp.

◆ gpc_polygon_to_tristrip()

void gpc_polygon_to_tristrip	(	gpc_polygon *	s,
		gpc_tristrip *	t
	)

Definition at line 1838 of file gpc.cpp.

◆ gpc_tristrip_clip()

void gpc_tristrip_clip	(	gpc_op	op,
		gpc_polygon *	subj,
		gpc_polygon *	clip,
		gpc_tristrip *	result
	)

Definition at line 1849 of file gpc.cpp.

◆ gpc_write_polygon()

void gpc_write_polygon	(	FILE *	fp,
		int	write_hole_flags,
		gpc_polygon *	p
	)

Definition at line 1130 of file gpc.cpp.

◆ insert_bound()

static void insert_bound	(	edge_node **	b,
		edge_node *	e
	)

static

Definition at line 334 of file gpc.cpp.

◆ merge_left()

static void merge_left	(	polygon_node *	p,
		polygon_node *	q,
		polygon_node *	list
	)

static

Definition at line 841 of file gpc.cpp.

◆ merge_right()

static void merge_right	(	polygon_node *	p,
		polygon_node *	q,
		polygon_node *	list
	)

static

Definition at line 891 of file gpc.cpp.

◆ minimax_test()

static void minimax_test	(	gpc_polygon *	subj,
		gpc_polygon *	clip,
		gpc_op	op
	)

static

Definition at line 1034 of file gpc.cpp.

◆ new_tristrip()

static void new_tristrip	(	polygon_node **	tn,
		edge_node *	edge,
		double	x,
		double	y
	)

static

Definition at line 980 of file gpc.cpp.

◆ reset_it()

static void reset_it ( it_node ** it )

static

Definition at line 308 of file gpc.cpp.

◆ reset_lmt()

static void reset_lmt ( lmt_node ** lmt )

static

Definition at line 321 of file gpc.cpp.

Variable Documentation

◆ next_h_state

const h_state next_h_state[3][6]

Initial value:

=
{
  
  
   {BH, TH,   TH, BH,   NH, NH},
   {NH, NH,   NH, NH,   TH, TH},
   {NH, NH,   NH, NH,   BH, BH}
}

Definition at line 292 of file gpc.cpp.

Classes

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

◆ ABOVE

◆ BELOW

◆ CLIP

◆ EQ

◆ FALSE

◆ FREE

◆ FWD_MIN

◆ INVERT_TRISTRIPS

◆ LEFT

◆ MALLOC

◆ N_EDGE

◆ NEXT_INDEX

◆ NOT_FMAX

◆ NOT_RMAX

◆ OPTIMAL

◆ P_EDGE

◆ PREV_INDEX

◆ REV_MIN

◆ RIGHT

◆ SUBJ

◆ TRUE

◆ VERTEX

Typedef Documentation

◆ bbox

◆ it_node

◆ sb_tree

◆ st_node

◆ vertex_node

Enumeration Type Documentation

◆ bundle_state

◆ h_state

◆ vertex_type

Function Documentation

◆ add_edge_to_aet()

◆ add_intersection()

◆ add_left()

◆ add_local_min()

◆ add_right()

◆ add_st_edge()

◆ add_to_sbtree()

◆ add_vertex()

◆ bound_list()

◆ build_intersection_table()

◆ build_lmt()

◆ build_sbt()

◆ count_contours()

◆ count_optimal_vertices()

◆ count_tristrips()

◆ create_contour_bboxes()

◆ free_sbtree()

◆ gpc_add_contour()

◆ gpc_free_polygon()

◆ gpc_free_tristrip()

◆ gpc_polygon_clip()

◆ gpc_polygon_to_tristrip()

◆ gpc_tristrip_clip()

◆ gpc_write_polygon()

◆ insert_bound()

◆ merge_left()

◆ merge_right()

◆ minimax_test()

◆ new_tristrip()

◆ reset_it()

◆ reset_lmt()

Variable Documentation

◆ next_h_state