polyarea.h File Reference

poly_Boolean: a polygon clip library. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	CVCList
struct	VNODE
struct	PLINE
struct	POLYAREA
Defines
#define	PLF_DIR   1
#define	PLF_INV   0
#define	PLF_MARK   1
#define	min(x, y)   ((x) < (y) ? (x) : (y))
#define	max(x, y)   ((x) > (y) ? (x) : (y))
#define	VertexEqu(a, b)   (memcmp((a),(b),sizeof(Vector))==0)
#define	VertexCpy(a, b)   memcpy((a),(b),sizeof(Vector))
Typedefs
typedef int	BOOLp
typedef Coord	vertex [2]
typedef vertex	Vector
typedef struct CVCList	CVCList
typedef struct VNODE	VNODE
typedef struct PLINE	PLINE
typedef struct POLYAREA	POLYAREA
Enumerations
enum	{ FALSE = 0, TRUE = 1 }
enum	{ err_no_memory = 2, err_bad_parm = 3, err_ok = 0 }
enum	PolygonBooleanOperation { PBO_UNITE, PBO_ISECT, PBO_SUB, PBO_XOR }
Functions
PLINE *	poly_NewContour (Vector v)
void	poly_IniContour (PLINE *c)
void	poly_ClrContour (PLINE *c)
void	poly_DelContour (PLINE **c)
BOOLp	poly_CopyContour (PLINE **dst, PLINE *src)
void	poly_PreContour (PLINE *c, BOOLp optimize)
void	poly_InvContour (PLINE *c)
VNODE *	poly_CreateNode (Vector v)
void	poly_InclVertex (VNODE *after, VNODE *node)
void	poly_ExclVertex (VNODE *node)
BOOLp	poly_M_Copy0 (POLYAREA **dst, const POLYAREA *srcfst)
void	poly_M_Incl (POLYAREA **list, POLYAREA *a)
BOOLp	poly_Copy0 (POLYAREA **dst, const POLYAREA *src)
BOOLp	poly_Copy1 (POLYAREA *dst, const POLYAREA *src)
BOOLp	poly_InclContour (POLYAREA *p, PLINE *c)
BOOLp	poly_ExclContour (POLYAREA *p, PLINE *c)
BOOLp	poly_ChkContour (PLINE *a)
BOOLp	poly_CheckInside (POLYAREA *c, Vector v0)
BOOLp	Touching (POLYAREA *p1, POLYAREA *p2)
	Determine if two polygons touch or overlap.
int	poly_InsideContour (PLINE *c, Vector v)
	Checks whether point lies within contour independently of its orientation.
int	poly_ContourInContour (PLINE *poly, PLINE *inner)
POLYAREA *	poly_Create (void)
void	poly_Free (POLYAREA **p)
void	poly_Init (POLYAREA *p)
void	poly_FreeContours (PLINE **pl)
BOOLp	poly_Valid (POLYAREA *p)
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 A, Vector B, Vector C, Vector D, Vector S1, Vector S2)
	vect_inters2.
int	poly_Boolean (const POLYAREA *a, const POLYAREA *b, POLYAREA **res, int action)
	The main clipping routines.
int	poly_Boolean_free (POLYAREA *a, POLYAREA *b, POLYAREA **res, int action)
	Just like poly_Boolean but frees the input polys.
int	poly_AndSubtract_free (POLYAREA *a, POLYAREA *b, POLYAREA **aandb, POLYAREA **aminusb)
	Compute the intersection and subtraction (divides "a" into two pieces) and frees the input polys.
int	SavePOLYAREA (POLYAREA *PA, char *fname)
Variables
Vector	vect_zero

---

Detailed Description

poly_Boolean: a polygon clip library.

---

Copyright.

Copyright (C) 1997 Alexey Nikitin, Michael Leonov

leonov@propro.iis.nsk.su

Copyright (C) 1997 Klamer Schutte (minor patches)

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

This library 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 Library 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.

Definition in file polyarea.h.

---

Define Documentation

#define max	(		x,
			y
	)		((x) > (y) ? (x) : (y))

Definition at line 56 of file polyarea.h.

#define min	(		x,
			y
	)		((x) < (y) ? (x) : (y))

Definition at line 52 of file polyarea.h.

#define PLF_DIR   1

Definition at line 47 of file polyarea.h.

Referenced by ContourToPoly(), do_hole(), find_inside(), find_inside_m_pa(), original_poly(), poly_ComputeInteriorPoint(), poly_InclContour(), poly_PreContour(), poly_Valid(), and PutContour().

#define PLF_INV   0

Definition at line 48 of file polyarea.h.

Referenced by original_poly(), poly_PreContour(), and poly_Valid().

#define PLF_MARK   1

Definition at line 49 of file polyarea.h.

#define VertexCpy	(		a,
			b
	)		memcpy((a),(b),sizeof(Vector))

Definition at line 64 of file polyarea.h.

#define VertexEqu	(		a,
			b
	)		(memcmp((a),(b),sizeof(Vector))==0)

Definition at line 63 of file polyarea.h.

---

Typedef Documentation

typedef int BOOLp

Definition at line 38 of file polyarea.h.

typedef struct CVCList CVCList

Definition at line 77 of file polyarea.h.

typedef struct PLINE PLINE

Definition at line 98 of file polyarea.h.

typedef struct POLYAREA POLYAREA

Definition at line 133 of file polyarea.h.

typedef vertex Vector

Definition at line 61 of file polyarea.h.

typedef Coord vertex[2]

longing point representation of coordinates.

Definition at line 60 of file polyarea.h.

typedef struct VNODE VNODE

Definition at line 78 of file polyarea.h.

---

Enumeration Type Documentation

anonymous enum

Enumerator:

FALSE
TRUE

Definition at line 41 of file polyarea.h.

anonymous enum

Enumerator:

err_no_memory
err_bad_parm
err_ok

Definition at line 69 of file polyarea.h.

enum PolygonBooleanOperation

Enumerator:

PBO_UNITE
PBO_ISECT
PBO_SUB
PBO_XOR

Definition at line 171 of file polyarea.h.

---

Function Documentation

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,
		const POLYAREA *	b,
		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 *	a,
		POLYAREA *	b,
		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 *	c,
		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:

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:

BOOLp poly_ExclContour	(	POLYAREA *	p,
		PLINE *	c
	)

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 **

pl

)

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	v
	)

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_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:

int SavePOLYAREA	(	POLYAREA *	PA,
		char *	fname
	)

BOOLp Touching	(	POLYAREA *	p1,
		POLYAREA *	p2
	)

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:

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_inters2	(	Vector	p1,
		Vector	p2,
		Vector	q1,
		Vector	q2,
		Vector	S1,
		Vector	S2
	)

vect_inters2.

(C) 1993 Klamer Schutte.

(C) 1997 Michael Leonov, Alexey Nikitin.

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.

---

Variable Documentation

Vector vect_zero

Definition at line 3401 of file polygon1.c.

Referenced by new_descriptor().