Polygon clipping functions. More...

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <setjmp.h>
#include <math.h>
#include <string.h>
#include "global.h"
#include "pcb-printf.h"
#include "rtree.h"
#include "heap.h"

Include dependency graph for polygon1.c:

Go to the source code of this file.

Data Structures
struct	seg
struct	_insert_node_task
struct	info
struct	contour_info
struct	polyarea_info
struct	find_inside_info
struct	find_inside_m_pa_info
struct	pip
Defines
#define	ROUND(a) (long)((a) > 0 ? ((a) + 0.5) : ((a) - 0.5))
#define	EPSILON (1E-8)
#define	IsZero(a, b) (fabs((a) - (b)) < EPSILON)
#define	Vcopy(a, b) {(a)[0]=(b)[0];(a)[1]=(b)[1];}
#define	ISECTED 3
#define	UNKNWN 0
#define	INSIDE 1
#define	OUTSIDE 2
#define	SHARED 3
#define	SHARED2 4
#define	TOUCHES 99
#define	NODE_LABEL(n) ((n)->Flags.status)
#define	LABEL_NODE(n, l) ((n)->Flags.status = (l))
#define	error(code) longjmp(*(e), code)
#define	MemGet(ptr, type)
#define	DEBUGP(...)
#define	Vsub2(r, a, b) {(r)[0] = (a)[0] - (b)[0]; (r)[1] = (a)[1] - (b)[1];}
#define	Vadd2(r, a, b) {(r)[0] = (a)[0] + (b)[0]; (r)[1] = (a)[1] + (b)[1];}
#define	Vsca2(r, a, s) {(r)[0] = (a)[0] * (s); (r)[1] = (a)[1] * (s);}
#define	Vcpy2(r, a) {(r)[0] = (a)[0]; (r)[1] = (a)[1];}
#define	Vequ2(a, b) ((a)[0] == (b)[0] && (a)[1] == (b)[1])
#define	Vadds(r, a, b, s) {(r)[0] = ((a)[0] + (b)[0]) * (s); (r)[1] = ((a)[1] + (b)[1]) * (s);}
#define	Vswp2(a, b)
#define	ISECT_BAD_PARAM (-1)
#define	ISECT_NO_MEMORY (-2)
#define	Vzero(a) ((a)[0] == 0. && (a)[1] == 0.)
#define	Vsub(a, b, c) {(a)[0]=(b)[0]-(c)[0];(a)[1]=(b)[1]-(c)[1];}
Typedefs
typedef struct seg	seg
typedef struct _insert_node_task	insert_node_task
typedef struct info	info
typedef struct contour_info	contour_info
typedef int(*	S_Rule )(VNODE , DIRECTION )
	Start Rule.
typedef int(*	J_Rule )(char, VNODE , DIRECTION )
	Jump Rule.
typedef struct pip	pip
Enumerations
enum	DIRECTION { FORW, BACKW }
Functions
int	vect_equal (Vector v1, Vector v2)
void	vect_init (Vector v, double x, double y)
void	vect_sub (Vector res, Vector v2, Vector v3)
void	vect_min (Vector res, Vector v2, Vector v3)
void	vect_max (Vector res, Vector v2, Vector v3)
double	vect_dist2 (Vector v1, Vector v2)
double	vect_det2 (Vector v1, Vector v2)
	Value has sign of angle between vectors.
double	vect_len2 (Vector v1)
int	vect_inters2 (Vector p1, Vector p2, Vector q1, Vector q2, Vector S1, Vector S2)
	vect_inters2.
static VNODE *	node_add_single (VNODE *dest, Vector po)
	node_add.
static CVCList *	new_descriptor (VNODE *a, char poly, char side)
	new_descriptor.
static CVCList *	insert_descriptor (VNODE a, char poly, char side, CVCList start)
	insert_descriptor.
static VNODE *	node_add_single_point (VNODE *a, Vector p)
	node_add_point.
static unsigned int	node_label (VNODE *pn)
	node_label.
static CVCList *	add_descriptors (PLINE pl, char poly, CVCList list)
	add_descriptors.
static void	cntrbox_adjust (PLINE *c, Vector p)
static int	adjust_tree (rtree_t tree, struct seg s)
	adjust_tree().
static int	seg_in_region (const BoxType b, void cl)
	seg_in_region().
static insert_node_task *	prepend_insert_node_task (insert_node_task list, seg seg, VNODE *new_node)
	Prepend a deferred node-insersion task to a list.
static int	seg_in_seg (const BoxType b, void cl)
	seg_in_seg().
static void *	make_edge_tree (PLINE *pb)
static int	get_seg (const BoxType b, void cl)
static int	contour_bounds_touch (const BoxType b, void cl)
	intersect() (and helpers).
static int	intersect_impl (jmp_buf jb, POLYAREA b, POLYAREA *a, int add)
static int	intersect (jmp_buf jb, POLYAREA b, POLYAREA *a, int add)
static void	M_POLYAREA_intersect (jmp_buf e, POLYAREA afst, POLYAREA *bfst, int add)
static int	cntrbox_inside (PLINE c1, PLINE c2)
static int	count_contours_i_am_inside (const BoxType b, void cl)
static int	cntr_in_M_POLYAREA (PLINE poly, POLYAREA outfst, BOOLp test)
	cntr_in_M_POLYAREA.
static BOOLp	label_contour (PLINE *a)
	label_contour.
static BOOLp	cntr_label_POLYAREA (PLINE poly, POLYAREA ppl, BOOLp test)
static BOOLp	M_POLYAREA_label_separated (PLINE afst, POLYAREA b, BOOLp touch)
static BOOLp	M_POLYAREA_label (POLYAREA afst, POLYAREA b, BOOLp touch)
static void	InsCntr (jmp_buf e, PLINE c, POLYAREA **dst)
	Routines for temporary storing resulting contours.
static void	PutContour (jmp_buf e, PLINE cntr, POLYAREA contours, PLINE holes, POLYAREA owner, POLYAREA parent, PLINE *parent_contour)
static void	remove_contour (POLYAREA piece, PLINE prev_contour, PLINE *contour, int remove_rtree_entry)
static int	heap_it (const BoxType b, void cl)
static int	find_inside (const BoxType b, void cl)
static void	InsertHoles (jmp_buf e, POLYAREA dest, PLINE **src)
static int	UniteS_Rule (VNODE cur, DIRECTION initdir)
static int	IsectS_Rule (VNODE cur, DIRECTION initdir)
static int	SubS_Rule (VNODE cur, DIRECTION initdir)
static int	XorS_Rule (VNODE cur, DIRECTION initdir)
static int	IsectJ_Rule (char p, VNODE v, DIRECTION cdir)
static int	UniteJ_Rule (char p, VNODE v, DIRECTION cdir)
static int	XorJ_Rule (char p, VNODE v, DIRECTION cdir)
static int	SubJ_Rule (char p, VNODE v, DIRECTION cdir)
static int	jump (VNODE *cur, DIRECTION cdir, J_Rule rule)
	Return the edge that comes next.
static int	Gather (VNODE start, PLINE *result, J_Rule v_rule, DIRECTION initdir)
static void	Collect1 (jmp_buf e, VNODE cur, DIRECTION dir, POLYAREA contours, PLINE holes, J_Rule j_rule)
static void	Collect (jmp_buf e, PLINE a, POLYAREA contours, PLINE holes, S_Rule s_rule, J_Rule j_rule)
static int	cntr_Collect (jmp_buf e, PLINE A, POLYAREA contours, PLINE holes, int action, POLYAREA owner, POLYAREA parent, PLINE parent_contour)
static void	M_B_AREA_Collect (jmp_buf e, POLYAREA bfst, POLYAREA contours, PLINE holes, int action)
static int	contour_is_first (POLYAREA a, PLINE cur)
static int	contour_is_last (PLINE *cur)
static void	remove_polyarea (POLYAREA *list, POLYAREA piece)
static void	M_POLYAREA_separate_isected (jmp_buf e, POLYAREA pieces, PLINE holes, PLINE *isected)
static int	find_inside_m_pa (const BoxType b, void cl)
static void	M_POLYAREA_update_primary (jmp_buf e, POLYAREA pieces, PLINE holes, int action, POLYAREA bpa)
static void	M_POLYAREA_Collect_separated (jmp_buf e, PLINE afst, POLYAREA contours, PLINE holes, int action, BOOLp maybe)
static void	M_POLYAREA_Collect (jmp_buf e, POLYAREA afst, POLYAREA contours, PLINE holes, int action, BOOLp maybe)
BOOLp	Touching (POLYAREA a, POLYAREA b)
	Determine if two polygons touch or overlap.
int	poly_Boolean (const POLYAREA a_org, const POLYAREA b_org, POLYAREA **res, int action)
	The main clipping routines.
int	poly_Boolean_free (POLYAREA ai, POLYAREA bi, POLYAREA **res, int action)
	Just like poly_Boolean but frees the input polys.
static void	clear_marks (POLYAREA *p)
int	poly_AndSubtract_free (POLYAREA ai, POLYAREA bi, POLYAREA aandb, POLYAREA aminusb)
	Compute the intersection and subtraction (divides "a" into two pieces) and frees the input polys.
static int	cntrbox_pointin (PLINE *c, Vector p)
static int	node_neighbours (VNODE a, VNODE b)
VNODE *	poly_CreateNode (Vector v)
void	poly_IniContour (PLINE *c)
PLINE *	poly_NewContour (Vector v)
void	poly_ClrContour (PLINE *c)
void	poly_DelContour (PLINE **c)
void	poly_PreContour (PLINE *C, BOOLp optimize)
static int	flip_cb (const BoxType b, void cl)
void	poly_InvContour (PLINE *c)
void	poly_ExclVertex (VNODE *node)
void	poly_InclVertex (VNODE after, VNODE node)
BOOLp	poly_CopyContour (PLINE *dst, PLINE src)
BOOLp	poly_Copy0 (POLYAREA *dst, const POLYAREA src)
BOOLp	poly_Copy1 (POLYAREA dst, const POLYAREA src)
void	poly_M_Incl (POLYAREA *list, POLYAREA a)
BOOLp	poly_M_Copy0 (POLYAREA *dst, const POLYAREA srcfst)
BOOLp	poly_InclContour (POLYAREA p, PLINE c)
static int	crossing (const BoxType b, void cl)
int	poly_InsideContour (PLINE *c, Vector p)
	Checks whether point lies within contour independently of its orientation.
BOOLp	poly_CheckInside (POLYAREA *p, Vector v0)
BOOLp	poly_M_CheckInside (POLYAREA *p, Vector v0)
static double	dot (Vector A, Vector B)
static int	point_in_triangle (Vector A, Vector B, Vector C, Vector P)
	Compute whether point is inside a triangle formed by 3 other points.
static double	dot_orthogonal_to_direction (Vector A, Vector B, Vector C, Vector D)
	Returns the dot product of Vector A->B, and a vector orthogonal to Vector C->D.
static void	poly_ComputeInteriorPoint (PLINE *poly, Vector v)
	Algorithm from http://www.exaflop.org/docs/cgafaq/cga2.html.
int	poly_ContourInContour (PLINE poly, PLINE inner)

void	poly_Init (POLYAREA *p)
POLYAREA *	poly_Create (void)
void	poly_FreeContours (PLINE **pline)
void	poly_Free (POLYAREA **p)
static BOOLp	inside_sector (VNODE *pn, Vector p2)
BOOLp	poly_ChkContour (PLINE *a)

BOOLp	poly_Valid (POLYAREA *p)
static double	vect_m_dist (Vector v1, Vector v2)
Variables
Vector	vect_zero = { (long) 0, (long) 0 }

Detailed Description

Polygon clipping functions.

harry eaton implemented the algorithm described in "A Closed Set of Algorithms for Performing Set Operations on Polygonal Regions in the Plane" which the original code did not do.

I also modified it for integer coordinates and faster computation.

The license for this modified copy was switched to the GPL per term (3) of the original LGPL license.

Copyright.

based on:

poly_Boolean: a polygon clip library

(also the authors of the paper describing the actual algorithm)

leonov@propro.iis.nsk.su

in turn based on:

nclip: a polygon clip library

All cases where original (Klamer Schutte) code is present are marked.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

Note:: How about expanding polygons so that edges can be arcs rather than lines.
Consider using the third coordinate to store the radius of the arc.
The arc would pass through the vertex points.
Positive radius would indicate the arc bows left (center on right of P1-P2 path).
Negative radius would put the center on the other side.
0 radius would mean the edge is a line instead of arc.
The intersections of the two circles centered at the vertex points would determine the two possible arc centers.
If P2.x > P1.x then the center with smaller Y is selected for positive r.
If P2.y > P1.y then the center with greate X is selected for positive r.
The vec_inters2() routine would then need to handle line-line line-arc and arc-arc intersections.
Perhaps reverse tracing the arc would require look-ahead to check for arcs

Definition in file polygon1.c.

Define Documentation

#define DEBUGP ( ... )

Definition at line 139 of file polygon1.c.

Referenced by Collect1(), Gather(), jump(), label_contour(), new_descriptor(), poly_Valid(), and seg_in_seg().

#define EPSILON (1E-8)

Definition at line 89 of file polygon1.c.

Referenced by check_intersect_vertex(), cluster_find(), coord_wind(), edge_min_spacing(), epsilon_equals(), perpendicular_gradient(), point_wind(), poly_ChkContour(), poly_InclVertex(), routing_edge_insert(), space_edge(), and vertex_line_normal_intersection().

#define error ( code ) longjmp(*(e), code)

Definition at line 124 of file polygon1.c.

Referenced by bm_to_pathlist(), Collect1(), common_string_to_flags(), findpath(), InsertHoles(), M_POLYAREA_intersect(), parse_layer_list(), ParseGroupString(), ParseRouteString(), string_to_flags(), and string_to_pcbflags().

#define INSIDE 1

Definition at line 114 of file polygon1.c.

Referenced by cntr_Collect(), cntr_label_POLYAREA(), IsectJ_Rule(), IsectS_Rule(), label_contour(), M_B_AREA_Collect(), node_label(), SubJ_Rule(), XorJ_Rule(), and XorS_Rule().

#define ISECT_BAD_PARAM (-1)

Definition at line 227 of file polygon1.c.

#define ISECT_NO_MEMORY (-2)

Definition at line 228 of file polygon1.c.

#define ISECTED 3

Definition at line 112 of file polygon1.c.

Referenced by cntr_Collect(), cntr_label_POLYAREA(), find_inside_m_pa(), M_B_AREA_Collect(), M_POLYAREA_Collect(), M_POLYAREA_intersect(), M_POLYAREA_separate_isected(), M_POLYAREA_update_primary(), and seg_in_seg().

#define IsZero	(	a,
		b
	)	(fabs((a) - (b)) < EPSILON)

Definition at line 90 of file polygon1.c.

#define LABEL_NODE	(	n,
		l
	)	((n)->Flags.status = (l))

Definition at line 122 of file polygon1.c.

Referenced by label_contour(), and node_label().

#define MemGet	(	ptr,
		type
	)

Value:

if (UNLIKELY (((ptr) = (type *)malloc(sizeof(type))) == NULL))  \
    error(err_no_memory);

Definition at line 126 of file polygon1.c.

Referenced by InsCntr().

#define NODE_LABEL ( n ) ((n)->Flags.status)

Definition at line 121 of file polygon1.c.

Referenced by IsectS_Rule(), node_label(), SubS_Rule(), and UniteS_Rule().

#define OUTSIDE 2

Definition at line 115 of file polygon1.c.

Referenced by cntr_Collect(), cntr_label_POLYAREA(), label_contour(), M_B_AREA_Collect(), node_label(), SubJ_Rule(), SubS_Rule(), UniteJ_Rule(), UniteS_Rule(), XorJ_Rule(), and XorS_Rule().

#define ROUND ( a ) (long)((a) > 0 ? ((a) + 0.5) : ((a) - 0.5))

Definition at line 87 of file polygon1.c.

#define SHARED 3

Definition at line 116 of file polygon1.c.

Referenced by IsectJ_Rule(), IsectS_Rule(), node_label(), UniteJ_Rule(), and UniteS_Rule().

#define SHARED2 4

Definition at line 117 of file polygon1.c.

Referenced by node_label(), SubJ_Rule(), and SubS_Rule().

#define TOUCHES 99

Definition at line 119 of file polygon1.c.

Referenced by seg_in_seg(), and Touching().

#define UNKNWN 0

Definition at line 113 of file polygon1.c.

Referenced by label_contour(), M_B_AREA_Collect(), M_POLYAREA_separate_isected(), M_POLYAREA_update_primary(), node_add_single(), and node_label().

#define Vadd2	(	r,
		a,
		b
	)	{(r)[0] = (a)[0] + (b)[0]; (r)[1] = (a)[1] + (b)[1];}

Definition at line 145 of file polygon1.c.

#define Vadds	(	r,
		a,
		b,
		s
	)	{(r)[0] = ((a)[0] + (b)[0]) * (s); (r)[1] = ((a)[1] + (b)[1]) * (s);}

Definition at line 149 of file polygon1.c.

#define Vcopy	(	a,
		b
	)	{(a)[0]=(b)[0];(a)[1]=(b)[1];}

Definition at line 94 of file polygon1.c.

Referenced by poly_NewContour().

#define Vcpy2	(	r,
		a
	)	{(r)[0] = (a)[0]; (r)[1] = (a)[1];}

Definition at line 147 of file polygon1.c.

Referenced by vect_inters2().

#define Vequ2	(	a,
		b
	)	((a)[0] == (b)[0] && (a)[1] == (b)[1])

Definition at line 148 of file polygon1.c.

Referenced by vect_inters2().

#define Vsca2	(	r,
		a,
		s
	)	{(r)[0] = (a)[0] * (s); (r)[1] = (a)[1] * (s);}

Definition at line 146 of file polygon1.c.

#define Vsub	(	a,
		b,
		c
	)	{(a)[0]=(b)[0]-(c)[0];(a)[1]=(b)[1]-(c)[1];}

Definition at line 3414 of file polygon1.c.

Referenced by vect_sub().

#define Vsub2	(	r,
		a,
		b
	)	{(r)[0] = (a)[0] - (b)[0]; (r)[1] = (a)[1] - (b)[1];}

Definition at line 144 of file polygon1.c.

Referenced by crossing(), poly_PreContour(), and vect_inters2().

#define Vswp2	(	a,
		b
	)

Value:

{ long t; \
        t = (a)[0], (a)[0] = (b)[0], (b)[0] = t; \
        t = (a)[1], (a)[1] = (b)[1], (b)[1] = t; \
}

Definition at line 150 of file polygon1.c.

Referenced by vect_inters2().

#define Vzero ( a ) ((a)[0] == 0. && (a)[1] == 0.)

Definition at line 3412 of file polygon1.c.

Typedef Documentation

typedef struct contour_info contour_info

typedef struct info info

typedef struct _insert_node_task insert_node_task

Definition at line 535 of file polygon1.c.

typedef int(* J_Rule)(char, VNODE *, DIRECTION *)

Jump Rule.

Definition at line 1520 of file polygon1.c.

typedef struct pip pip

typedef int(* S_Rule)(VNODE *, DIRECTION *)

Start Rule.

Definition at line 1515 of file polygon1.c.

typedef struct seg seg

Enumeration Type Documentation

enum DIRECTION

Enumerator:

FORW
BACKW

Definition at line 1507 of file polygon1.c.

Function Documentation

static CVCList* add_descriptors	(	PLINE *	pl,
		char	poly,
		CVCList *	list
	)		`[static]`

add_descriptors.

Definition at line 494 of file polygon1.c.

References VNODE::cvc_next, VNODE::cvc_prev, PLINE::head, insert_descriptor(), VNODE::next, and node.

Referenced by M_POLYAREA_intersect().

Here is the call graph for this function:

static int adjust_tree	(	rtree_t *	tree,
		struct seg *	s
	)		`[static]`

adjust_tree().

This replaces the segment in the tree with the two new segments after a vertex has been added.

Definition at line 574 of file polygon1.c.

References seg::box, seg::intersected, malloc(), max, min, VNODE::next, seg::p, VNODE::point, r_delete_entry(), r_insert_entry(), seg::v, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by intersect_impl().

Here is the call graph for this function:

static void clear_marks ( POLYAREA * p ) [static]

Definition at line 2460 of file polygon1.c.

References c, POLYAREA::contours, POLYAREA::f, VNODE::Flags, PLINE::head, VNODE::mark, VNODE::next, and PLINE::next.

Referenced by poly_AndSubtract_free().

static int cntr_Collect	(	jmp_buf *	e,
		PLINE **	A,
		POLYAREA **	contours,
		PLINE **	holes,
		int	action,
		POLYAREA *	owner,
		POLYAREA *	parent,
		PLINE *	parent_contour
	)		`[static]`

Definition at line 1772 of file polygon1.c.

References Collect(), FALSE, INSIDE, ISECTED, IsectJ_Rule(), IsectS_Rule(), PLINE::next, OUTSIDE, PBO_ISECT, PBO_SUB, PBO_UNITE, PBO_XOR, poly_InvContour(), PutContour(), SubJ_Rule(), SubS_Rule(), TRUE, UniteJ_Rule(), UniteS_Rule(), XorJ_Rule(), and XorS_Rule().

Referenced by M_POLYAREA_Collect(), and M_POLYAREA_Collect_separated().

Here is the call graph for this function:

static int cntr_in_M_POLYAREA	(	PLINE *	poly,
		POLYAREA *	outfst,
		BOOLp	test
	)		`[static]`

cntr_in_M_POLYAREA.

Returns:: poly is inside outfst ? TRUE : FALSE.

Definition at line 1033 of file polygon1.c.

References PLINE::area, cntrbox_inside(), POLYAREA::contour_tree, POLYAREA::contours, count_contours_i_am_inside(), POLYAREA::f, FALSE, heap_create(), heap_destroy(), heap_insert(), heap_is_empty(), heap_remove_smallest(), r_search(), and TRUE.

Referenced by cntr_label_POLYAREA(), find_inside_m_pa(), and M_POLYAREA_update_primary().

Here is the call graph for this function:

static BOOLp cntr_label_POLYAREA	(	PLINE *	poly,
		POLYAREA *	ppl,
		BOOLp	test
	)		`[static]`

Definition at line 1165 of file polygon1.c.

References cntr_in_M_POLYAREA(), POLYAREA::contours, FALSE, PLINE::Flags, INSIDE, ISECTED, label_contour(), OUTSIDE, PLINE::status, and TRUE.

Referenced by M_POLYAREA_label(), and M_POLYAREA_label_separated().

Here is the call graph for this function:

static void cntrbox_adjust	(	PLINE *	c,
		Vector	p
	)		`[inline, static]`

Definition at line 517 of file polygon1.c.

References max, min, PLINE::xmax, PLINE::xmin, PLINE::ymax, and PLINE::ymin.

Referenced by intersect_impl(), poly_NewContour(), and poly_PreContour().

static int cntrbox_inside	(	PLINE *	c1,
		PLINE *	c2
	)		`[inline, static]`

Definition at line 1006 of file polygon1.c.

References PLINE::xmax, PLINE::xmin, PLINE::ymax, and PLINE::ymin.

Referenced by cntr_in_M_POLYAREA(), and poly_ContourInContour().

static int cntrbox_pointin	(	PLINE *	c,
		Vector	p
	)		`[inline, static]`

Definition at line 2551 of file polygon1.c.

References PLINE::xmax, PLINE::xmin, PLINE::ymax, and PLINE::ymin.

Referenced by poly_InsideContour().

static void Collect	(	jmp_buf *	e,
		PLINE *	a,
		POLYAREA **	contours,
		PLINE **	holes,
		S_Rule	s_rule,
		J_Rule	j_rule
	)		`[static]`

Definition at line 1750 of file polygon1.c.

References Collect1(), VNODE::cvc_prev, VNODE::Flags, FORW, PLINE::head, jump(), VNODE::mark, and VNODE::next.

Referenced by cntr_Collect().

Here is the call graph for this function:

static void Collect1	(	jmp_buf *	e,
		VNODE *	cur,
		DIRECTION	dir,
		POLYAREA **	contours,
		PLINE **	holes,
		J_Rule	j_rule
	)		`[static]`

Definition at line 1716 of file polygon1.c.

References PLINE::Count, DEBUGP, err_ok, error, PLINE::Flags, Gather(), PLINE::orient, poly_DelContour(), poly_PreContour(), PutContour(), and TRUE.

Referenced by Collect().

Here is the call graph for this function:

static int contour_bounds_touch	(	const BoxType *	b,
		void *	cl
	)		`[static]`

intersect() (and helpers).

This uses an rtree to find A-B intersections. Whenever a new vertex is added, the search for intersections is re-started because the rounding could alter the topology otherwise. This should use a faster algorithm for snap rounding intersection finding. The best algorthim is probably found in:

"Improved output-sensitive snap rounding," John Hershberger, Proceedings of the 22nd annual symposium on Computational geomerty, 2006, pp 357-366.

http://doi.acm.org/10.1145/1137856.1137909

Algorithms described by de Berg, or Goodrich or Halperin, or Hobby would probably work as well.

Definition at line 793 of file polygon1.c.

References info::b, seg::box, box, PLINE::Count, info::env, get_seg(), contour_info::getout, PLINE::head, seg::intersected, info::m, contour_info::need_restart, info::need_restart, VNODE::next, contour_info::node_insert_list, info::node_insert_list, contour_info::pa, VNODE::point, r_search(), info::s, seg_in_region(), seg_in_seg(), info::sego, info::touch, info::tree, PLINE::tree, UNLIKELY, and info::v.

Referenced by intersect_impl().

Here is the call graph for this function:

static int contour_is_first	(	POLYAREA *	a,
		PLINE *	cur
	)		`[inline, static]`

Definition at line 1898 of file polygon1.c.

References POLYAREA::contours.

Referenced by M_POLYAREA_separate_isected(), and M_POLYAREA_update_primary().

static int contour_is_last ( PLINE * cur ) [inline, static]

Definition at line 1905 of file polygon1.c.

References PLINE::next.

Referenced by M_POLYAREA_separate_isected(), and M_POLYAREA_update_primary().

static int count_contours_i_am_inside	(	const BoxType *	b,
		void *	cl
	)		`[static]`

Definition at line 1017 of file polygon1.c.

References check, and poly_ContourInContour().

Referenced by cntr_in_M_POLYAREA().

Here is the call graph for this function:

static int crossing	(	const BoxType *	b,
		void *	cl
	)		`[static]`

Definition at line 2921 of file polygon1.c.

References pip::env, pip::f, VNODE::next, pip::p, VNODE::point, seg::v, and Vsub2.

Referenced by poly_InsideContour().

static double dot	(	Vector	A,
		Vector	B
	)		`[static]`

Definition at line 3019 of file polygon1.c.

Referenced by ActionImport(), dot_orthogonal_to_direction(), and point_in_triangle().

static double dot_orthogonal_to_direction	(	Vector	A,
		Vector	B,
		Vector	C,
		Vector	D
	)		`[static]`

Returns the dot product of Vector A->B, and a vector orthogonal to Vector C->D.

The result is not normalisd, so will be weighted by the magnitude of the C->D vector.

Definition at line 3068 of file polygon1.c.

References dot().

Referenced by poly_ComputeInteriorPoint().

Here is the call graph for this function:

static int find_inside	(	const BoxType *	b,
		void *	cl
	)		`[static]`

Definition at line 1333 of file polygon1.c.

References check, PLINE::Flags, find_inside_info::jb, PLINE::orient, PLF_DIR, poly_ContourInContour(), find_inside_info::result, and find_inside_info::want_inside.

Referenced by InsertHoles().

Here is the call graph for this function:

static int find_inside_m_pa	(	const BoxType *	b,
		void *	cl
	)		`[static]`

Definition at line 2021 of file polygon1.c.

References check, cntr_in_M_POLYAREA(), FALSE, PLINE::Flags, ISECTED, find_inside_m_pa_info::jb, PLINE::orient, PLF_DIR, find_inside_m_pa_info::result, PLINE::status, and find_inside_m_pa_info::want_inside.

Referenced by M_POLYAREA_update_primary().

Here is the call graph for this function:

static int flip_cb	(	const BoxType *	b,
		void *	cl
	)		`[static]`

Definition at line 2716 of file polygon1.c.

References VNODE::prev, and seg::v.

Referenced by poly_InvContour().

static int Gather	(	VNODE *	start,
		PLINE **	result,
		J_Rule	v_rule,
		DIRECTION	initdir
	)		`[static]`

Definition at line 1672 of file polygon1.c.

References DEBUGP, err_no_memory, err_ok, FORW, jump(), VNODE::next, VNODE::point, poly_CreateNode(), poly_InclVertex(), poly_NewContour(), and VNODE::prev.

Referenced by Collect1().

Here is the call graph for this function:

static int get_seg	(	const BoxType *	b,
		void *	cl
	)		`[static]`

Definition at line 758 of file polygon1.c.

References s, info::s, info::sego, seg::v, and info::v.

Referenced by contour_bounds_touch().

static int heap_it	(	const BoxType *	b,
		void *	cl
	)		`[static]`

Definition at line 1314 of file polygon1.c.

References PLINE::area, POLYAREA::contours, PLINE::Count, heap_insert(), and polyarea_info::pa.

Referenced by InsertHoles().

Here is the call graph for this function:

static void InsCntr	(	jmp_buf *	e,
		PLINE *	c,
		POLYAREA **	dst
	)		`[static]`

Routines for temporary storing resulting contours.

Definition at line 1225 of file polygon1.c.

References POLYAREA::b, c, POLYAREA::contour_tree, POLYAREA::contours, POLYAREA::f, MemGet, r_create_tree(), and r_insert_entry().

Referenced by PutContour().

Here is the call graph for this function:

static CVCList* insert_descriptor	(	VNODE *	a,
		char	poly,
		char	side,
		CVCList *	start
	)		`[static]`

insert_descriptor.

Parameters:

a	is a cross-vertex node.
poly	is the polygon it comes from ('A' or 'B').
side	is the side this descriptor goes on ('P' for previous 'N' for next).
start	is the head of the list of cvclists.

Definition at line 307 of file polygon1.c.

References CVCList::angle, CVCList::head, new_descriptor(), CVCList::next, CVCList::parent, VNODE::point, and CVCList::prev.

Referenced by add_descriptors().

Here is the call graph for this function:

static void InsertHoles	(	jmp_buf *	e,
		POLYAREA *	dest,
		PLINE **	src
	)		`[static]`

Definition at line 1352 of file polygon1.c.

References polyarea_info::BoundingBox, POLYAREA::contour_tree, POLYAREA::contours, err_bad_parm, error, POLYAREA::f, find_inside(), heap_create(), heap_destroy(), heap_is_empty(), heap_it(), heap_remove_smallest(), find_inside_info::jb, malloc(), PLINE::next, polyarea_info::pa, poly_ContourInContour(), poly_DelContour(), r_create_tree(), r_destroy_tree(), r_insert_entry(), r_search(), remove_contour(), find_inside_info::result, TRUE, find_inside_info::want_inside, BoxType::X1, BoxType::X2, PLINE::xmax, PLINE::xmin, BoxType::Y1, BoxType::Y2, PLINE::ymax, and PLINE::ymin.

Referenced by poly_AndSubtract_free(), and poly_Boolean_free().

Here is the call graph for this function:

static BOOLp inside_sector	(	VNODE *	pn,
		Vector	p2
	)		`[static]`

Definition at line 3244 of file polygon1.c.

References FALSE, VNODE::next, VNODE::point, VNODE::prev, TRUE, vect_det2(), and vect_sub().

Referenced by poly_ChkContour().

Here is the call graph for this function:

static int intersect	(	jmp_buf *	jb,
		POLYAREA *	b,
		POLYAREA *	a,
		int	add
	)		`[static]`

Definition at line 952 of file polygon1.c.

References intersect_impl().

Referenced by find_pair_padline_callback(), and M_POLYAREA_intersect().

Here is the call graph for this function:

static int intersect_impl	(	jmp_buf *	jb,
		POLYAREA *	b,
		POLYAREA *	a,
		int	add
	)		`[static]`

Definition at line 874 of file polygon1.c.

References adjust_tree(), info::b, cntrbox_adjust(), contour_bounds_touch(), POLYAREA::contour_tree, POLYAREA::contours, PLINE::Count, contour_info::getout, contour_info::need_restart, info::need_restart, _insert_node_task::new_node, VNODE::next, _insert_node_task::next, PLINE::next, contour_info::node_insert_list, _insert_node_task::node_seg, seg::p, contour_info::pa, VNODE::point, VNODE::prev, r_search(), rtree::size, PLINE::tree, seg::v, BoxType::X1, BoxType::X2, PLINE::xmax, PLINE::xmin, BoxType::Y1, BoxType::Y2, PLINE::ymax, and PLINE::ymin.

Referenced by intersect().

Here is the call graph for this function:

static int IsectJ_Rule	(	char	p,
		VNODE *	v,
		DIRECTION *	cdir
	)		`[static]`

Definition at line 1560 of file polygon1.c.

References VNODE::Flags, FORW, INSIDE, SHARED, and VNODE::status.

Referenced by cntr_Collect().

static int IsectS_Rule	(	VNODE *	cur,
		DIRECTION *	initdir
	)		`[static]`

Definition at line 1530 of file polygon1.c.

References FORW, INSIDE, NODE_LABEL, and SHARED.

Referenced by cntr_Collect().

static int jump	(	VNODE **	cur,
		DIRECTION *	cdir,
		J_Rule	rule
	)		`[static]`

Return the edge that comes next.

If the direction is BACKW, then we return the next vertex so that prev vertex has the flags for the edge.

Returns:: true if an edge is found, false otherwise.

Definition at line 1622 of file polygon1.c.

References BACKW, DEBUGP, FALSE, VNODE::Flags, FORW, VNODE::mark, VNODE::next, CVCList::parent, VNODE::point, CVCList::poly, VNODE::prev, CVCList::prev, CVCList::side, and TRUE.

Referenced by Collect(), and Gather().

static BOOLp label_contour ( PLINE * a ) [static]

label_contour.

Definition at line 1133 of file polygon1.c.

References VNODE::cvc_next, DEBUGP, FALSE, PLINE::head, INSIDE, LABEL_NODE, VNODE::next, node_label(), OUTSIDE, and UNKNWN.

Referenced by cntr_label_POLYAREA().

Here is the call graph for this function:

static void M_B_AREA_Collect	(	jmp_buf *	e,
		POLYAREA *	bfst,
		POLYAREA **	contours,
		PLINE **	holes,
		int	action
	)		`[static]`

Definition at line 1842 of file polygon1.c.

References POLYAREA::contours, POLYAREA::f, PLINE::Flags, INSIDE, ISECTED, PLINE::next, OUTSIDE, PBO_ISECT, PBO_SUB, PBO_UNITE, PBO_XOR, poly_InvContour(), PutContour(), PLINE::status, and UNKNWN.

Referenced by poly_Boolean_free().

Here is the call graph for this function:

static void M_POLYAREA_Collect	(	jmp_buf *	e,
		POLYAREA *	afst,
		POLYAREA **	contours,
		PLINE **	holes,
		int	action,
		BOOLp	maybe
	)		`[static]`

Definition at line 2276 of file polygon1.c.

References POLYAREA::b, cntr_Collect(), POLYAREA::contours, POLYAREA::f, PLINE::Flags, ISECTED, and PLINE::status.

Referenced by poly_AndSubtract_free().

Here is the call graph for this function:

static void M_POLYAREA_Collect_separated	(	jmp_buf *	e,
		PLINE *	afst,
		POLYAREA **	contours,
		PLINE **	holes,
		int	action,
		BOOLp	maybe
	)		`[static]`

Definition at line 2261 of file polygon1.c.

References cntr_Collect().

Referenced by poly_Boolean_free().

Here is the call graph for this function:

static void M_POLYAREA_intersect	(	jmp_buf *	e,
		POLYAREA *	afst,
		POLYAREA *	bfst,
		int	add
	)		`[static]`

Definition at line 961 of file polygon1.c.

References add_descriptors(), info::b, POLYAREA::contours, err_bad_parm, err_no_memory, error, POLYAREA::f, PLINE::Flags, intersect(), ISECTED, PLINE::next, PLINE::status, UNLIKELY, PLINE::xmax, PLINE::xmin, PLINE::ymax, and PLINE::ymin.

Referenced by poly_AndSubtract_free(), poly_Boolean_free(), and Touching().

Here is the call graph for this function:

static BOOLp M_POLYAREA_label	(	POLYAREA *	afst,
		POLYAREA *	b,
		BOOLp	touch
	)		`[static]`

Definition at line 1201 of file polygon1.c.

References cntr_label_POLYAREA(), POLYAREA::contours, POLYAREA::f, FALSE, PLINE::next, and TRUE.

Referenced by poly_AndSubtract_free(), poly_Boolean_free(), and Touching().

Here is the call graph for this function:

static BOOLp M_POLYAREA_label_separated	(	PLINE *	afst,
		POLYAREA *	b,
		BOOLp	touch
	)		`[static]`

Definition at line 1188 of file polygon1.c.

References cntr_label_POLYAREA(), FALSE, PLINE::next, and TRUE.

Referenced by poly_Boolean_free().

Here is the call graph for this function:

static void M_POLYAREA_separate_isected	(	jmp_buf *	e,
		POLYAREA **	pieces,
		PLINE **	holes,
		PLINE **	isected
	)		`[static]`

Definition at line 1928 of file polygon1.c.

References contour_is_first(), contour_is_last(), POLYAREA::contours, POLYAREA::f, PLINE::Flags, ISECTED, PLINE::next, poly_Free(), remove_contour(), remove_polyarea(), PLINE::status, and UNKNWN.

Referenced by poly_Boolean_free().

Here is the call graph for this function:

static void M_POLYAREA_update_primary	(	jmp_buf *	e,
		POLYAREA **	pieces,
		PLINE **	holes,
		int	action,
		POLYAREA *	bpa
	)		`[static]`

Definition at line 2041 of file polygon1.c.

References box, cntr_in_M_POLYAREA(), contour_is_first(), contour_is_last(), POLYAREA::contour_tree, POLYAREA::contours, POLYAREA::f, FALSE, find_inside_m_pa(), PLINE::Flags, ISECTED, find_inside_m_pa_info::jb, MAKEMAX, MAKEMIN, PLINE::next, PBO_ISECT, PBO_SUB, PBO_UNITE, PBO_XOR, poly_DelContour(), poly_Free(), r_search(), remove_contour(), remove_polyarea(), find_inside_m_pa_info::result, PLINE::status, TRUE, UNKNWN, find_inside_m_pa_info::want_inside, BoxType::X1, BoxType::X2, PLINE::xmax, PLINE::xmin, BoxType::Y1, BoxType::Y2, PLINE::ymax, and PLINE::ymin.

Referenced by poly_Boolean_free().

Here is the call graph for this function:

static void* make_edge_tree ( PLINE * pb ) [static]

Definition at line 719 of file polygon1.c.

References seg::box, PLINE::head, seg::intersected, malloc(), VNODE::next, seg::p, VNODE::point, r_create_tree(), r_insert_entry(), s, seg::v, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by poly_CopyContour(), and poly_PreContour().

Here is the call graph for this function:

static CVCList* new_descriptor	(	VNODE *	a,
		char	poly,
		char	side
	)		`[static]`

new_descriptor.

Definition at line 237 of file polygon1.c.

References CVCList::angle, VNODE::cvc_next, VNODE::cvc_prev, DEBUGP, CVCList::head, malloc(), VNODE::next, CVCList::next, CVCList::parent, VNODE::point, poly, CVCList::poly, poly_ExclVertex(), VNODE::prev, CVCList::prev, CVCList::side, vect_equal(), vect_sub(), and vect_zero.

Referenced by insert_descriptor().

Here is the call graph for this function:

static VNODE* node_add_single	(	VNODE *	dest,
		Vector	po
	)		`[static]`

node_add.

Returns:: a bit field in new_point that indicates where the point was. 1 means a new node was created and inserted. 4 means the intersection was not on the dest point.

Definition at line 211 of file polygon1.c.

References VNODE::cvc_next, VNODE::cvc_prev, VNODE::Flags, VNODE::next, VNODE::point, poly_CreateNode(), VNODE::status, UNKNWN, and vect_equal().

Referenced by node_add_single_point().

Here is the call graph for this function:

static VNODE* node_add_single_point	(	VNODE *	a,
		Vector	p
	)		`[static]`

node_add_point.

Returns:: 1 if new node in b, 2 if new node in a and 3 if new node in both.

Definition at line 392 of file polygon1.c.

References VNODE::cvc_next, VNODE::cvc_prev, VNODE::next, and node_add_single().

Referenced by seg_in_seg().

Here is the call graph for this function:

static unsigned int node_label ( VNODE * pn ) [static]

node_label.

Definition at line 415 of file polygon1.c.

References CVCList::angle, VNODE::cvc_next, INSIDE, LABEL_NODE, VNODE::next, CVCList::next, NODE_LABEL, OUTSIDE, CVCList::parent, VNODE::point, CVCList::poly, VNODE::prev, CVCList::prev, region, SHARED, VNODE::shared, SHARED2, CVCList::side, and UNKNWN.

Referenced by label_contour().

static int node_neighbours	(	VNODE *	a,
		VNODE *	b
	)		`[inline, static]`

Definition at line 2559 of file polygon1.c.

References VNODE::next.

Referenced by poly_ChkContour().

static int point_in_triangle	(	Vector	A,
		Vector	B,
		Vector	C,
		Vector	P
	)		`[static]`

Compute whether point is inside a triangle formed by 3 other points.

Algorithm from http://www.blackpawn.com/texts/pointinpoly/default.html.

Definition at line 3031 of file polygon1.c.

References dot(), and u().

Referenced by poly_ComputeInteriorPoint().

Here is the call graph for this function:

int poly_AndSubtract_free	(	POLYAREA *	ai,
		POLYAREA *	bi,
		POLYAREA **	aandb,
		POLYAREA **	aminusb
	)

Compute the intersection and subtraction (divides "a" into two pieces) and frees the input polys.

This assumes that bi is a single simple polygon.

Definition at line 2488 of file polygon1.c.

References clear_marks(), FALSE, InsertHoles(), M_POLYAREA_Collect(), M_POLYAREA_intersect(), M_POLYAREA_label(), PLINE::next, PBO_ISECT, PBO_SUB, poly_DelContour(), poly_Free(), poly_Valid(), and TRUE.

Referenced by r_NoHolesPolygonDicer().

Here is the call graph for this function:

int poly_Boolean	(	const POLYAREA *	a_org,
		const POLYAREA *	b_org,
		POLYAREA **	res,
		int	action
	)

The main clipping routines.

Definition at line 2355 of file polygon1.c.

References err_no_memory, poly_Boolean_free(), and poly_M_Copy0().

Referenced by Subtract().

Here is the call graph for this function:

int poly_Boolean_free	(	POLYAREA *	ai,
		POLYAREA *	bi,
		POLYAREA **	res,
		int	action
	)

Just like poly_Boolean but frees the input polys.

Definition at line 2370 of file polygon1.c.

References err_ok, FALSE, InsertHoles(), M_B_AREA_Collect(), M_POLYAREA_Collect_separated(), M_POLYAREA_intersect(), M_POLYAREA_label(), M_POLYAREA_label_separated(), M_POLYAREA_separate_isected(), M_POLYAREA_update_primary(), PLINE::next, PBO_ISECT, PBO_SUB, PBO_UNITE, PBO_XOR, poly_DelContour(), poly_Free(), poly_Valid(), and TRUE.

Referenced by ArcPoly(), fill_clipped_contour(), line_sub_callback(), NoHolesPolygonDicer(), NotifyMode(), oct_therm(), pin_sub_callback(), poly_Boolean(), Subtract(), ThermPoly(), and Unsubtract().

Here is the call graph for this function:

BOOLp poly_CheckInside	(	POLYAREA *	p,
		Vector	v0
	)

Definition at line 2984 of file polygon1.c.

References POLYAREA::contours, FALSE, PLINE::next, poly_InsideContour(), and TRUE.

Referenced by IsPointInPolygon(), and poly_M_CheckInside().

Here is the call graph for this function:

BOOLp poly_ChkContour ( PLINE * a )

Returns:: TRUE if bad contour.

Definition at line 3270 of file polygon1.c.

References EPSILON, FALSE, PLINE::head, inside_sector(), VNODE::next, node_neighbours(), VNODE::point, VNODE::prev, TRUE, vect_dist2(), and vect_inters2().

Referenced by poly_Valid().

Here is the call graph for this function:

void poly_ClrContour ( PLINE * c )

Definition at line 2617 of file polygon1.c.

References PLINE::head, VNODE::next, poly_ExclVertex(), and poly_IniContour().

Here is the call graph for this function:

static void poly_ComputeInteriorPoint	(	PLINE *	poly,
		Vector	v
	)		`[static]`

Algorithm from http://www.exaflop.org/docs/cgafaq/cga2.html.

"Given a simple polygon, find some point inside it.

Here is a method based on the proof that there exists an internal diagonal, in [O'Rourke, 13-14].

The idea is that the midpoint of a diagonal is interior to the polygon.

Identify a convex vertex v; let its adjacent vertices be a and b.
For each other vertex q do:
1. If q is inside avb, compute distance to v (orthogonal to ab).
2. Save point q if distance is a new min.
If no point is inside, return midpoint of ab, or centroid of avb.
Else if some point inside, qv is internal: return its midpoint."

[O'Rourke]: Computational Geometry in C (2nd Ed.)

Joseph O'Rourke, Cambridge University Press 1998, ISBN 0-521-64010-5 Pbk, ISBN 0-521-64976-5 Hbk.

Definition at line 3108 of file polygon1.c.

References dist(), dot_orthogonal_to_direction(), PLINE::Flags, PLINE::head, VNODE::next, PLINE::orient, PLF_DIR, VNODE::point, and point_in_triangle().

Referenced by poly_ContourInContour().

Here is the call graph for this function:

int poly_ContourInContour	(	PLINE *	poly,
		PLINE *	inner
	)

Note:: This function assumes the caller _knows_ the contours do not intersect. If the contours intersect, the result is undefined. It will return the correct result if the two contours share common points beteween their contours. (Identical contours are treated as being inside each other).

Definition at line 3174 of file polygon1.c.

References cntrbox_inside(), PLINE::head, VNODE::point, poly_ComputeInteriorPoint(), and poly_InsideContour().

Referenced by count_contours_i_am_inside(), find_inside(), InsertHoles(), and poly_Valid().

Here is the call graph for this function:

BOOLp poly_Copy0	(	POLYAREA **	dst,
		const POLYAREA *	src
	)

Definition at line 2824 of file polygon1.c.

References FALSE, poly_Copy1(), and r_create_tree().

Here is the call graph for this function:

BOOLp poly_Copy1	(	POLYAREA *	dst,
		const POLYAREA *	src
	)

Definition at line 2837 of file polygon1.c.

References POLYAREA::b, POLYAREA::contour_tree, POLYAREA::contours, POLYAREA::f, FALSE, PLINE::next, poly_CopyContour(), r_insert_entry(), and TRUE.

Referenced by NoHolesPolygonDicer(), poly_Copy0(), and poly_M_Copy0().

Here is the call graph for this function:

BOOLp poly_CopyContour	(	PLINE **	dst,
		PLINE *	src
	)

Definition at line 2794 of file polygon1.c.

References PLINE::area, PLINE::Count, FALSE, PLINE::Flags, PLINE::head, make_edge_tree(), VNODE::next, PLINE::orient, VNODE::point, poly_CreateNode(), poly_InclVertex(), poly_NewContour(), TRUE, PLINE::xmax, PLINE::xmin, PLINE::ymax, and PLINE::ymin.

Referenced by fill_clipped_contour(), and poly_Copy1().

Here is the call graph for this function:

POLYAREA* poly_Create ( void )

Definition at line 3202 of file polygon1.c.

References malloc(), and poly_Init().

Referenced by ContourToPoly(), fill_clipped_contour(), NoHolesPolygonDicer(), original_poly(), and poly_M_Copy0().

Here is the call graph for this function:

VNODE* poly_CreateNode ( Vector v )

Definition at line 2565 of file polygon1.c.

References c, and VNODE::point.

Referenced by ArcPolyNoIntersect(), diag_line(), frac_circle(), Gather(), LinePoly(), node_add_single(), OctagonPoly(), original_poly(), poly_CopyContour(), RectPoly(), RoundRect(), square_therm(), and SquarePadPoly().

void poly_DelContour ( PLINE ** c )

Todo:: FIXME -- strict aliasing violation.

Definition at line 2631 of file polygon1.c.

References VNODE::cvc_next, VNODE::cvc_prev, VNODE::prev, and r_destroy_tree().

Referenced by biggest(), Collect1(), InsertHoles(), M_POLYAREA_update_primary(), MorphPolygon(), poly_AndSubtract_free(), poly_Boolean_free(), and poly_FreeContours().

Here is the call graph for this function:

void poly_ExclVertex ( VNODE * node )

Definition at line 2755 of file polygon1.c.

References VNODE::cvc_next, VNODE::cvc_prev, VNODE::next, and VNODE::prev.

Referenced by new_descriptor(), poly_ClrContour(), and poly_PreContour().

void poly_Free ( POLYAREA ** p )

Definition at line 3224 of file polygon1.c.

References POLYAREA::b, POLYAREA::contour_tree, POLYAREA::contours, POLYAREA::f, poly_FreeContours(), and r_destroy_tree().

Referenced by fill_clipped_contour(), FreePolygonMemory(), InitClip(), isects(), M_POLYAREA_separate_isected(), M_POLYAREA_update_primary(), poly_AndSubtract_free(), poly_Boolean_free(), r_NoHolesPolygonDicer(), Subtract(), and Unsubtract().

Here is the call graph for this function:

void poly_FreeContours ( PLINE ** pline )

Definition at line 3212 of file polygon1.c.

References PLINE::next, and poly_DelContour().

Referenced by ComputeNoHoles(), fill_contour_cb(), FreePolygonMemory(), InitClip(), and poly_Free().

Here is the call graph for this function:

BOOLp poly_InclContour	(	POLYAREA *	p,
		PLINE *	c
	)

Definition at line 2887 of file polygon1.c.

References c, POLYAREA::contour_tree, POLYAREA::contours, FALSE, PLINE::Flags, PLINE::next, PLINE::orient, PLF_DIR, r_insert_entry(), and TRUE.

Referenced by ContourToPoly(), fill_clipped_contour(), and original_poly().

Here is the call graph for this function:

void poly_InclVertex	(	VNODE *	after,
		VNODE *	node
	)

Definition at line 2768 of file polygon1.c.

References EPSILON, VNODE::next, node, VNODE::point, and VNODE::prev.

Referenced by ArcPolyNoIntersect(), diag_line(), frac_circle(), Gather(), LinePoly(), OctagonPoly(), original_poly(), poly_CopyContour(), RectPoly(), RoundRect(), square_therm(), and SquarePadPoly().

void poly_IniContour ( PLINE * c )

Definition at line 2582 of file polygon1.c.

References PLINE::cx, PLINE::cy, FALSE, PLINE::head, PLINE::is_round, VNODE::next, VNODE::prev, PLINE::radius, PLINE::xmax, PLINE::xmin, PLINE::ymax, and PLINE::ymin.

Referenced by poly_ClrContour(), and poly_NewContour().

void poly_Init ( POLYAREA * p )

Definition at line 3194 of file polygon1.c.

References POLYAREA::b, POLYAREA::contour_tree, POLYAREA::contours, POLYAREA::f, pip::p, and r_create_tree().

Referenced by poly_Create().

Here is the call graph for this function:

int poly_InsideContour	(	PLINE *	c,
		Vector	p
	)

Checks whether point lies within contour independently of its orientation.

Definition at line 2966 of file polygon1.c.

References cntrbox_pointin(), crossing(), pip::env, pip::f, FALSE, pip::p, r_search(), and PLINE::tree.

Referenced by IsPointInPolygonIgnoreHoles(), poly_CheckInside(), and poly_ContourInContour().

Here is the call graph for this function:

void poly_InvContour ( PLINE * c )

Definition at line 2724 of file polygon1.c.

References PLINE::Count, PLINE::Flags, flip_cb(), PLINE::head, VNODE::next, PLINE::orient, VNODE::prev, r_search(), and PLINE::tree.

Referenced by cntr_Collect(), M_B_AREA_Collect(), and original_poly().

Here is the call graph for this function:

BOOLp poly_M_CheckInside	(	POLYAREA *	p,
		Vector	v0
	)

Definition at line 3002 of file polygon1.c.

References POLYAREA::f, FALSE, pip::p, poly_CheckInside(), and TRUE.

Here is the call graph for this function:

BOOLp poly_M_Copy0	(	POLYAREA **	dst,
		const POLYAREA *	srcfst
	)

Definition at line 2868 of file polygon1.c.

References POLYAREA::f, FALSE, poly_Copy1(), poly_Create(), poly_M_Incl(), and TRUE.

Referenced by poly_Boolean().

Here is the call graph for this function:

void poly_M_Incl	(	POLYAREA **	list,
		POLYAREA *	a
	)

Definition at line 2855 of file polygon1.c.

References POLYAREA::b, and POLYAREA::f.

Referenced by poly_M_Copy0().

PLINE* poly_NewContour ( Vector v )

Definition at line 2597 of file polygon1.c.

References cntrbox_adjust(), PLINE::head, VNODE::point, poly_IniContour(), and Vcopy.

Referenced by ArcPolyNoIntersect(), CirclePoly(), diag_line(), Gather(), LinePoly(), OctagonPoly(), original_poly(), poly_CopyContour(), RectPoly(), RoundRect(), square_therm(), and SquarePadPoly().

Here is the call graph for this function:

void poly_PreContour	(	PLINE *	C,
		BOOLp	optimize
	)

Definition at line 2662 of file polygon1.c.

References PLINE::area, c, cntrbox_adjust(), PLINE::Count, PLINE::Flags, PLINE::head, make_edge_tree(), VNODE::next, PLINE::orient, PLF_DIR, PLF_INV, VNODE::point, poly_ExclVertex(), PLINE::tree, vect_det2(), Vsub2, PLINE::xmax, PLINE::xmin, PLINE::ymax, and PLINE::ymin.

Referenced by Collect1(), ContourToPoly(), and original_poly().

Here is the call graph for this function:

BOOLp poly_Valid ( POLYAREA * p )

Definition at line 3344 of file polygon1.c.

References c, POLYAREA::contours, DEBUGP, FALSE, PLINE::Flags, PLINE::head, n, PLINE::next, VNODE::next, PLINE::orient, pcb_fprintf(), PLF_DIR, PLF_INV, VNODE::point, poly_ChkContour(), poly_ContourInContour(), and TRUE.

Referenced by ContourToPoly(), InitClip(), original_poly(), poly_AndSubtract_free(), poly_Boolean_free(), Subtract(), Touching(), and Unsubtract().

Here is the call graph for this function:

static insert_node_task* prepend_insert_node_task	(	insert_node_task *	list,
		seg *	seg,
		VNODE *	new_node
	)		`[static]`

Prepend a deferred node-insersion task to a list.

Definition at line 632 of file polygon1.c.

References malloc(), _insert_node_task::new_node, _insert_node_task::next, and _insert_node_task::node_seg.

Referenced by seg_in_seg().

Here is the call graph for this function:

static void PutContour	(	jmp_buf *	e,
		PLINE *	cntr,
		POLYAREA **	contours,
		PLINE **	holes,
		POLYAREA *	owner,
		POLYAREA *	parent,
		PLINE *	parent_contour
	)		`[static]`

Definition at line 1249 of file polygon1.c.

References POLYAREA::contour_tree, PLINE::Count, PLINE::Flags, InsCntr(), PLINE::next, PLINE::orient, PLF_DIR, r_delete_entry(), and r_insert_entry().

Referenced by cntr_Collect(), Collect1(), and M_B_AREA_Collect().

Here is the call graph for this function:

static void remove_contour	(	POLYAREA *	piece,
		PLINE *	prev_contour,
		PLINE *	contour,
		int	remove_rtree_entry
	)		`[inline, static]`

Definition at line 1290 of file polygon1.c.

References POLYAREA::contour_tree, POLYAREA::contours, PLINE::next, and r_delete_entry().

Referenced by InsertHoles(), M_POLYAREA_separate_isected(), and M_POLYAREA_update_primary().

Here is the call graph for this function:

static void remove_polyarea	(	POLYAREA **	list,
		POLYAREA *	piece
	)		`[inline, static]`

Definition at line 1912 of file polygon1.c.

References POLYAREA::b, and POLYAREA::f.

Referenced by M_POLYAREA_separate_isected(), and M_POLYAREA_update_primary().

static int seg_in_region	(	const BoxType *	b,
		void *	cl
	)		`[static]`

seg_in_region().

This prunes the search for boxes that don't intersect the segment.

Definition at line 612 of file polygon1.c.

References info::b, info::m, max, min, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by contour_bounds_touch().

static int seg_in_seg	(	const BoxType *	b,
		void *	cl
	)		`[static]`

seg_in_seg().

This routine checks if the segment in the tree intersect the search segment. If it does, the plines are marked as intersected and the point is marked for the cvclist. If the point is not already a vertex, a new vertex is inserted and the search for intersections starts over at the beginning. That is potentially a significant time penalty, but it does solve the snap rounding problem.

Todo:: There are efficient algorithms for finding intersections with snap rounding, but I don't have time to implement them right now.

Definition at line 659 of file polygon1.c.

References cnt, DEBUGP, info::env, PLINE::Flags, seg::intersected, ISECTED, VNODE::next, node_add_single_point(), info::node_insert_list, seg::p, VNODE::point, prepend_insert_node_task(), info::s, PLINE::status, info::touch, TOUCHES, info::v, seg::v, and vect_inters2().

Referenced by contour_bounds_touch().

Here is the call graph for this function:

static int SubJ_Rule	(	char	p,
		VNODE *	v,
		DIRECTION *	cdir
	)		`[static]`

Definition at line 1590 of file polygon1.c.

References BACKW, FALSE, VNODE::Flags, FORW, INSIDE, OUTSIDE, SHARED2, VNODE::status, and TRUE.

Referenced by cntr_Collect().

static int SubS_Rule	(	VNODE *	cur,
		DIRECTION *	initdir
	)		`[static]`

Definition at line 1537 of file polygon1.c.

References FORW, NODE_LABEL, OUTSIDE, and SHARED2.

Referenced by cntr_Collect().

BOOLp Touching	(	POLYAREA *	a,
		POLYAREA *	b
	)

Determine if two polygons touch or overlap.

Definition at line 2326 of file polygon1.c.

References FALSE, M_POLYAREA_intersect(), M_POLYAREA_label(), poly_Valid(), TOUCHES, and TRUE.

Referenced by isects().

Here is the call graph for this function:

static int UniteJ_Rule	(	char	p,
		VNODE *	v,
		DIRECTION *	cdir
	)		`[static]`

Definition at line 1567 of file polygon1.c.

References VNODE::Flags, FORW, OUTSIDE, SHARED, and VNODE::status.

Referenced by cntr_Collect().

static int UniteS_Rule	(	VNODE *	cur,
		DIRECTION *	initdir
	)		`[static]`

Definition at line 1523 of file polygon1.c.

References FORW, NODE_LABEL, OUTSIDE, and SHARED.

Referenced by cntr_Collect().

double vect_det2	(	Vector	v1,
		Vector	v2
	)

Value has sign of angle between vectors.

Definition at line 3461 of file polygon1.c.

Referenced by inside_sector(), poly_PreContour(), and vect_inters2().

double vect_dist2	(	Vector	v1,
		Vector	v2
	)

Definition at line 3449 of file polygon1.c.

Referenced by poly_ChkContour().

int vect_equal	(	Vector	v1,
		Vector	v2
	)

Definition at line 3417 of file polygon1.c.

Referenced by new_descriptor(), and node_add_single().

void vect_init	(	Vector	v,
		double	x,
		double	y
	)

Definition at line 3406 of file polygon1.c.

int vect_inters2	(	Vector	p1,
		Vector	p2,
		Vector	q1,
		Vector	q2,
		Vector	S1,
		Vector	S2
	)

vect_inters2.

Definition at line 3490 of file polygon1.c.

References max, min, ROUND, s, Vcpy2, vect_det2(), vect_m_dist(), Vequ2, Vsub2, and Vswp2.

Referenced by poly_ChkContour(), and seg_in_seg().

Here is the call graph for this function:

double vect_len2 ( Vector v1 )

Definition at line 3443 of file polygon1.c.

static double vect_m_dist	(	Vector	v1,
		Vector	v2
	)		`[static]`

Definition at line 3467 of file polygon1.c.

Referenced by vect_inters2().

void vect_max	(	Vector	res,
		Vector	v2,
		Vector	v3
	)

Definition at line 3436 of file polygon1.c.

void vect_min	(	Vector	res,
		Vector	v2,
		Vector	v3
	)

Definition at line 3429 of file polygon1.c.

void vect_sub	(	Vector	res,
		Vector	v2,
		Vector	v3
	)

Definition at line 3424 of file polygon1.c.

References Vsub.

Referenced by inside_sector(), and new_descriptor().

static int XorJ_Rule	(	char	p,
		VNODE *	v,
		DIRECTION *	cdir
	)		`[static]`

Definition at line 1574 of file polygon1.c.

References BACKW, FALSE, VNODE::Flags, FORW, INSIDE, OUTSIDE, VNODE::status, and TRUE.

Referenced by cntr_Collect().

static int XorS_Rule	(	VNODE *	cur,
		DIRECTION *	initdir
	)		`[static]`

Definition at line 1544 of file polygon1.c.

References BACKW, FALSE, VNODE::Flags, FORW, INSIDE, OUTSIDE, VNODE::status, and TRUE.

Referenced by cntr_Collect().

Variable Documentation

Vector vect_zero = { (long) 0, (long) 0 }

Definition at line 3401 of file polygon1.c.

Referenced by new_descriptor().

polygon1.c File Reference

Data Structures

Defines

Typedefs

Enumerations

Functions

Variables

Detailed Description

Copyright.

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation