Polygons

Collaboration diagram for Polygons:

Data Structures
struct	bg_poly_contour
struct	bg_polygon
struct	bg_polygons

Macros
#define	CLIPPER_MAX   1518500249
	Functions for working with polygons. More...
#define	BG_POLYGON_NULL   {0, NULL, NULL, {0, 0, 0}, 0, 0}

Enumerations
enum	triangulation_t {   TRI_ANY = 0 , TRI_EAR_CLIPPING , TRI_CONSTRAINED_DELAUNAY , TRI_MONOTONE ,   TRI_HERTEL_MEHLHORN , TRI_KEIL_SNOEYINK , TRI_DELAUNAY }
enum	bg_clip_t {   bg_None , bg_Union , bg_Difference , bg_Intersection ,   bg_Xor }
	Functions for working with polygons. More...

Functions
fastf_t	bg_find_polygon_area (struct bg_polygon *gpoly, fastf_t sf, plane_t *vp, fastf_t size)
int	bg_polygons_overlap (struct bg_polygon *polyA, struct bg_polygon *polyB, plane_t *vp, const struct bn_tol *tol, fastf_t iscale)
struct bg_polygon *	bg_clip_polygon (bg_clip_t op, struct bg_polygon *subj, struct bg_polygon *clip, fastf_t sf, plane_t *vp)
struct bg_polygon *	bg_clip_polygons (bg_clip_t op, struct bg_polygons *subj, struct bg_polygons *clip, fastf_t sf, plane_t *vp)
void	bg_polygon_free (struct bg_polygon *gpp)
void	bg_polygons_free (struct bg_polygons *gpp)
void	bg_polygon_cpy (struct bg_polygon *dest, struct bg_polygon *src)
void	bg_polygon_view_bbox (point2d_t *bmin, point2d_t *bmax, struct bg_polygon *p, matp_t model2view)
	Find the 2D axis aligned bounding box of a bg_polygon in view coordinates. More...
int	bg_polygon_direction (size_t npts, const point2d_t *pts, const int *pt_indices)
	Test whether a polygon is clockwise (CW) or counter clockwise (CCW) More...
int	bg_pnt_in_polygon (size_t npts, const point2d_t *pts, const point2d_t *test_pt)
	test whether a point is inside a 2d polygon More...
int	bg_nested_poly_triangulate (int **faces, int *num_faces, point2d_t **out_pts, int *num_outpts, const int *poly, const size_t poly_npts, const int **holes_array, const size_t *holes_npts, const size_t nholes, const int *steiner, const size_t steiner_npts, const point2d_t *pts, const size_t npts, triangulation_t type)
	Triangulate a 2D polygon with holes. More...
int	bg_poly_triangulate (int **faces, int *num_faces, point2d_t **out_pts, int *num_outpts, const int *steiner, const size_t steiner_npts, const point2d_t *pts, const size_t npts, triangulation_t type)
	Triangulate a 2D polygon without holes. More...
int	bg_polygon_triangulate (int **faces, int *num_faces, point_t **out_pts, int *num_outpts, struct bg_polygon *p, triangulation_t type)
	Triangulate a bg_polygon. More...
int	bg_poly2tri_test (int **faces, int *num_faces, point2d_t **out_pts, int *num_outpts, const int *poly, const size_t poly_pnts, const int **holes_array, const size_t *holes_npts, const size_t nholes, const int *steiner, const size_t steiner_npts, const point2d_t *pts)
int	bg_3d_polygon_area (fastf_t *area, size_t npts, const point_t *pts)
	Calculate the interior area of a polygon in a 3D plane in space. More...
int	bg_3d_polygon_centroid (point_t *cent, size_t npts, const point_t *pts)
	Calculate the centroid of a non self-intersecting polygon in a 3D plane in space. More...
int	bg_3d_polygon_sort_ccw (size_t npts, point_t *pts, plane_t cmp)
	Sort an array of point_ts, building a convex polygon, counter-clockwise. More...
int	bg_3d_polygon_make_pnts_planes (size_t *npts, point_t **pts, size_t neqs, const plane_t *eqs)
	Calculate for an array of plane_eqs, which build a polyhedron, the point_t's for each face. More...
void	bg_polygon_plot_2d (const char *filename, const point2d_t *pnts, int npnts, int r, int g, int b)
void	bg_polygon_plot (const char *filename, const point_t *pnts, int npnts, int r, int g, int b)
void	bg_tri_plot_2d (const char *filename, const int *faces, int num_faces, const point2d_t *pnts, int r, int g, int b)

Detailed Description

Macro Definition Documentation

CLIPPER_MAX

#define CLIPPER_MAX   1518500249

Functions for working with polygons.

Definition at line 53 of file polygon.h.

BG_POLYGON_NULL

#define BG_POLYGON_NULL   {0, NULL, NULL, {0, 0, 0}, 0, 0}

Definition at line 62 of file polygon_types.h.

Enumeration Type Documentation

triangulation_t

enum triangulation_t

Triangulation is the process of finding a set of triangles that as a set cover the same total surface area as a polygon. There are many algorithms for this operation, which have various trade-offs in speed and output quality.

Enumerator
TRI_ANY
TRI_EAR_CLIPPING
TRI_CONSTRAINED_DELAUNAY
TRI_MONOTONE
TRI_HERTEL_MEHLHORN
TRI_KEIL_SNOEYINK
TRI_DELAUNAY

Definition at line 153 of file polygon.h.

bg_clip_t

enum bg_clip_t

Functions for working with polygons.

Enumerator
bg_None
bg_Union
bg_Difference
bg_Intersection
bg_Xor

Definition at line 40 of file polygon_types.h.

Function Documentation

bg_find_polygon_area()

fastf_t bg_find_polygon_area	(	struct bg_polygon *	gpoly,
		fastf_t	sf,
		plane_t *	vp,
		fastf_t	size
	)

bg_polygons_overlap()

int bg_polygons_overlap	(	struct bg_polygon *	polyA,
		struct bg_polygon *	polyB,
		plane_t *	vp,
		const struct bn_tol *	tol,
		fastf_t	iscale
	)

bg_clip_polygon()

struct bg_polygon* bg_clip_polygon	(	bg_clip_t	op,
		struct bg_polygon *	subj,
		struct bg_polygon *	clip,
		fastf_t	sf,
		plane_t *	vp
	)

bg_clip_polygons()

struct bg_polygon* bg_clip_polygons	(	bg_clip_t	op,
		struct bg_polygons *	subj,
		struct bg_polygons *	clip,
		fastf_t	sf,
		plane_t *	vp
	)

bg_polygon_free()

void bg_polygon_free

(

struct bg_polygon *

gpp

)

bg_polygons_free()

void bg_polygons_free

(

struct bg_polygons *

gpp

)

bg_polygon_cpy()

void bg_polygon_cpy	(	struct bg_polygon *	dest,
		struct bg_polygon *	src
	)

bg_polygon_view_bbox()

void bg_polygon_view_bbox	(	point2d_t *	bmin,
		point2d_t *	bmax,
		struct bg_polygon *	p,
		matp_t	model2view
	)

Find the 2D axis aligned bounding box of a bg_polygon in view coordinates.

NOTE: If the polygon's internal data is defined in the XY plane and no view projection is desired, pass MAT_IDN to model2view to get the raw data's bbox.

bg_polygon_direction()

int bg_polygon_direction	(	size_t	npts,
		const point2d_t *	pts,
		const int *	pt_indices
	)

Test whether a polygon is clockwise (CW) or counter clockwise (CCW)

Determine if a set of points forming a polygon are in clockwise or counter-clockwise order (see http://stackoverflow.com/a/1165943)

Parameters

[in]	npts	number of points in polygon
[in]	pts	array of points
[in]	pt_indices	index values into pts array building a convex polygon. duplicated points aren't allowed.

If pt_indices is NULL, the first npts points in pts will be checked in array order.

Returns

BG_CCW if polygon is counter-clockwise

BG_CW if polygon is clockwise

0 if the test failed

bg_pnt_in_polygon()

int bg_pnt_in_polygon	(	size_t	npts,
		const point2d_t *	pts,
		const point2d_t *	test_pt
	)

test whether a point is inside a 2d polygon

franklin's test for point inclusion within a polygon - see https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html for more details and the implementation file polygon.c for license info.

Parameters

[in]	npts	number of points pts contains
[in]	pts	array of points, building a convex polygon. duplicated points aren't allowed. the points in the array will be sorted counter-clockwise.
[in]	test_pt	point to test.

Returns

0 if point is outside polygon

1 if point is inside polygon

bg_nested_poly_triangulate()

int bg_nested_poly_triangulate	(	int **	faces,
		int *	num_faces,
		point2d_t **	out_pts,
		int *	num_outpts,
		const int *	poly,
		const size_t	poly_npts,
		const int **	holes_array,
		const size_t *	holes_npts,
		const size_t	nholes,
		const int *	steiner,
		const size_t	steiner_npts,
		const point2d_t *	pts,
		const size_t	npts,
		triangulation_t	type
	)

Triangulate a 2D polygon with holes.

The primary polygon definition must be provided as an array of counter-clockwise indices to 2D points. If interior "hole" polygons are present, they must be passed in via the holes_array and their indices be ordered clockwise.

If no holes are present, caller should pass NULL for holes_array and holes_npts, and 0 for nholes, or use bg_polygon_triangulate instead.

This routine deliberately uses low level data types for both input and output to maximize the reusability of this logic.

Parameters

[out]	faces	Set of faces in the triangulation, stored as integer indices to the pts. The first three indices are the vertices of the first face, the second three define the second face, and so forth.
[out]	num_faces	Number of faces created
[out]	out_pts	output points used by faces set. If an algorithm was selected that generates new points, this will be a new array.
[out]	num_outpts	number of output points, if an algorithm was selected that generates new points
[in]	poly	Non-hole polygon, defined as a CCW array of indices into the pts array.
[in]	poly_npts	Number of points in non-hole polygon
[in]	holes_array	Array of hole polygons, each defined as a CW array of indices into the pts array.
[in]	holes_npts	Array of counts of points in hole polygons
[in]	nholes	Number of hole polygons contained in holes_array
[in]	steiner	Array of Steiner points
[in]	steiner_npts	Number of Steiner points
[in]	pts	Array of points defining a polygon. Duplicated points
[in]	npts	Number of points pts contains
[in]	type	Type of triangulation

Returns

0 if triangulation is successful

1 if triangulation is unsuccessful

bg_poly_triangulate()

int bg_poly_triangulate	(	int **	faces,
		int *	num_faces,
		point2d_t **	out_pts,
		int *	num_outpts,
		const int *	steiner,
		const size_t	steiner_npts,
		const point2d_t *	pts,
		const size_t	npts,
		triangulation_t	type
	)

Triangulate a 2D polygon without holes.

The polygon cannot have holes and must be provided as an array of counter-clockwise 2D points.

No points are added as part of this triangulation process - the result uses only those points in the original polygon, and hence only the face information is created as output.

The same fundamental routines are used here as in the bg_nested_polygon_triangulate logic - this is a convenience function to simplify calling the routine when specification of hole polygons is not needed.

This routine deliberately uses low level data types for both input and output to maximize the reusability of this logic.*

Parameters

[out]	faces	Set of faces in the triangulation, stored as integer indices to the pts. The first three indices are the vertices of the first face, the second three define the second face, and so forth.
[out]	num_faces	Number of faces created
[out]	out_pts	output points used by faces set, if an algorithm was selected that generates new points
[out]	num_outpts	number of output points, if an algorithm was selected that generates new points
[in]	steiner	Array of Steiner points
[in]	steiner_npts	Number of Steiner points
[in]	pts	Array of points defining a polygon. Duplicated points
[in]	npts	Number of points pts contains
[in]	type	Triangulation type

Returns

0 if triangulation is successful

1 if triangulation is unsuccessful

bg_polygon_triangulate()

int bg_polygon_triangulate	(	int **	faces,
		int *	num_faces,
		point_t **	out_pts,
		int *	num_outpts,
		struct bg_polygon *	p,
		triangulation_t	type
	)

Triangulate a bg_polygon.

Parameters

[out]	faces	Set of faces in the triangulation, stored as integer indices to the pts. The first three indices are the vertices of the first face, the second three define the second face, and so forth.
[out]	num_faces	Number of faces created
[out]	out_pts	output points used by faces set, if an algorithm was selected that generates new points
[out]	num_outpts	number of output points, if an algorithm was selected that generates new points
[in]	p	bg_polygon holding the polygon contours to be triangulated
[in]	type	Triangulation type

Returns

0 if triangulation is successful

1 if triangulation is unsuccessful

bg_poly2tri_test()

int bg_poly2tri_test	(	int **	faces,
		int *	num_faces,
		point2d_t **	out_pts,
		int *	num_outpts,
		const int *	poly,
		const size_t	poly_pnts,
		const int **	holes_array,
		const size_t *	holes_npts,
		const size_t	nholes,
		const int *	steiner,
		const size_t	steiner_npts,
		const point2d_t *	pts
	)

bg_3d_polygon_area()

int bg_3d_polygon_area	(	fastf_t *	area,
		size_t	npts,
		const point_t *	pts
	)

Calculate the interior area of a polygon in a 3D plane in space.

If npts > 4, Greens Theorem is used. The polygon mustn't be self-intersecting.

Parameters

[out]	area	The interior area of the polygon
[in]	npts	Number of point_ts, stored in pts
[in]	pts	All points of the polygon, sorted counter-clockwise. The array mustn't contain duplicated or non-coplanar points.

Returns

0 if calculation was successful

1 if calculation failed, e.g. because one parameter is a NULL-pointer

bg_3d_polygon_centroid()

int bg_3d_polygon_centroid	(	point_t *	cent,
		size_t	npts,
		const point_t *	pts
	)

Calculate the centroid of a non self-intersecting polygon in a 3D plane in space.

Parameters

[out]	cent	The centroid of the polygon
[in]	npts	Number of point_ts, stored in pts
[in]	pts	all points of the polygon, sorted counter-clockwise. The array mustn't contain duplicated points or non-coplanar points.

Returns

0 if calculation was successful

1 if calculation failed, e.g. because one in-parameter is a NULL-pointer

bg_3d_polygon_sort_ccw()

int bg_3d_polygon_sort_ccw	(	size_t	npts,
		point_t *	pts,
		plane_t	cmp
	)

Sort an array of point_ts, building a convex polygon, counter-clockwise.

Parameters

[in]	npts	Number of points, pts contains
	pts	Array of point_ts, building a convex polygon. Duplicated points aren't allowed. The points in the array will be sorted counter-clockwise.
[in]	cmp	Plane equation of the polygon

Returns

0 if calculation was successful

1 if calculation failed, e.g. because pts is a NULL-pointer

bg_3d_polygon_make_pnts_planes()

int bg_3d_polygon_make_pnts_planes	(	size_t *	npts,
		point_t **	pts,
		size_t	neqs,
		const plane_t *	eqs
	)

Calculate for an array of plane_eqs, which build a polyhedron, the point_t's for each face.

Parameters

[out]	npts	Array, which stores for every face the number of point_ts, added to pts. Needs to be allocated with npts[neqs] already.
[out]	pts	2D-array which stores the point_ts for every face. The array needs to be allocated with pts[neqs][neqs-1] already.
[in]	neqs	Number of plane_ts, stored in eqs
[in]	eqs	Array, that contains the plane equations, which build the polyhedron

Returns

0 if calculation was successful

1 if calculation failed, e.g. because one parameter is a NULL-Pointer

bg_polygon_plot_2d()

void bg_polygon_plot_2d	(	const char *	filename,
		const point2d_t *	pnts,
		int	npnts,
		int	r,
		int	g,
		int	b
	)

bg_polygon_plot()

void bg_polygon_plot	(	const char *	filename,
		const point_t *	pnts,
		int	npnts,
		int	r,
		int	g,
		int	b
	)

bg_tri_plot_2d()

void bg_tri_plot_2d	(	const char *	filename,
		const int *	faces,
		int	num_faces,
		const point2d_t *	pnts,
		int	r,
		int	g,
		int	b
	)