Convex Hulls

Collaboration diagram for Convex Hulls:

Functions
int	bg_polyline_2d_chull (point2d_t **hull, const point2d_t *polyline, int n)
	Routines for the computation of convex and concave hulls in 2D and 3D. More...
int	bg_polyline_2d_chull2 (int **hull, const int *polyline, int n, const point2d_t *pnts)
int	bg_2d_polyline_gc (point2d_t **opoly, int n, int *polyline, const point2d_t *pnts)
	Return an array that contains just the set of 2D points active in the polyline. More...
int	bg_2d_chull (point2d_t **hull, const point2d_t *points_2d, int n)
	Find 2D convex hull for unordered co-planar point sets. More...
int	bg_2d_chull2 (int **hull, const point2d_t *points_2d, int n)
int	bg_3d_coplanar_chull (point_t **hull, const point_t *points_3d, int n)
	Find 3D coplanar point convex hull for unordered co-planar point sets. More...
int	bg_3d_coplanar_chull2 (int **hull, const point_t *points_3d, int n)
int	bg_3d_chull (int **faces, int *num_faces, point_t **vertices, int *num_vertices, const point_t *input_points_3d, int num_input_pnts)
	Find 3D point convex hull for unordered point sets. More...

Detailed Description

Function Documentation

bg_polyline_2d_chull()

int bg_polyline_2d_chull	(	point2d_t **	hull,
		const point2d_t *	polyline,
		int	n
	)

Routines for the computation of convex and concave hulls in 2D and 3D.

Melkman's 2D simple polyline O(n) convex hull algorithm

On-line construction of the convex hull of a simple polyline Melkman, Avraham A. Information Processing Letters 25.1 (1987): 11-12.

See also http://geomalgorithms.com/a12-_hull-3.html

Parameters

[out]	hull	convex hull array vertices in ccw orientation (max is n)
	polyline	The points defining the input polyline, stored with ccw orientation
	n	the number of points in polyline

Returns

the number of points in the output hull array

bg_polyline_2d_chull2()

int bg_polyline_2d_chull2	(	int **	hull,
		const int *	polyline,
		int	n,
		const point2d_t *	pnts
	)

bg_2d_polyline_gc()

int bg_2d_polyline_gc	(	point2d_t **	opoly,
		int	n,
		int *	polyline,
		const point2d_t *	pnts
	)

Return an array that contains just the set of 2D points active in the polyline.

Parameters

[out]	opoly	array containing just the active points in the polyline.
[in]	n	number of points in polyline
[in]	polyline	indices of polyline points in pnts array
[in]	pnts	array that holds the points defining the polyline

The output array will store the points in polyline order, avoiding the need for an explicit index array of point positions to define the polyline.

Returns

number of points in opoly if calculation was successful

-1 if error

bg_2d_chull()

int bg_2d_chull	(	point2d_t **	hull,
		const point2d_t *	points_2d,
		int	n
	)

Find 2D convex hull for unordered co-planar point sets.

The monotone chain algorithm's sorting approach is used to do the initial ordering of the points:

Another efficient algorithm for convex hulls in two dimensions. Andrew, A. M. Information Processing Letters 9.5 (1979): 216-219.

See also http://geomalgorithms.com/a10-_hull-1.html

From there, instead of using the monotonic chain hull assembly step, recognize that the points thus ordered can be viewed as defining a simple polyline and use Melkman's algorithm for the hull building.

Parameters

[out]	hull	2D convex hull array vertices in ccw orientation (max is n)
	points_2d	The input 2d points for which a convex hull will be built
	n	the number of points in the input set

Returns

the number of points in the output hull array or zero if error.

bg_2d_chull2()

int bg_2d_chull2	(	int **	hull,
		const point2d_t *	points_2d,
		int	n
	)

bg_3d_coplanar_chull()

int bg_3d_coplanar_chull	(	point_t **	hull,
		const point_t *	points_3d,
		int	n
	)

Find 3D coplanar point convex hull for unordered co-planar point sets.

This function assumes an input an array of 3D points which are coplanar in some arbitrary plane. This function:

1. Finds the plane that fits the points and picks an origin, x-axis and y-axis which allow 2D coordinates for all points to be calculated.
2. Calls 2D routines on the array found by step 1 to get a 2D convex hull
3. Translates the resultant 2D hull points back into 3D points so the hull array contains the bounding hull expressed in the 3D coordinate space of the original points.

Parameters

[out]	hull	convex hull array vertices using 3-space coordinates in ccw orientation (max is n)
	points_3d	The input points for which a convex hull will be built
	n	the number of points in the input set

Returns

the number of points in the output hull array

bg_3d_coplanar_chull2()

int bg_3d_coplanar_chull2	(	int **	hull,
		const point_t *	points_3d,
		int	n
	)

bg_3d_chull()

int bg_3d_chull	(	int **	faces,
		int *	num_faces,
		point_t **	vertices,
		int *	num_vertices,
		const point_t *	input_points_3d,
		int	num_input_pnts
	)

Find 3D point convex hull for unordered point sets.

This routine computes the convex hull of a three dimensional point set and returns the set of vertices and triangular faces that define that hull, as well as the numerical count of vertices and faces in the hull.

Parameters

[out]	faces	set of faces in the convex hull, stored as integer indices to the vertices. The first three indices are the vertices of the face, the second three define the second face, and so forth.
[out]	num_faces	the number of faces in the faces array
[out]	vertices	the set of vertices used by the convex hull.
[out]	num_vertices	the number of vertices in the convex hull.
	input_points_3d	The input points for which a convex hull will be built
	num_input_pnts	the number of points in the input set

Returns

dimension of output (3 is three dimensional faces and hulls, 2 is a polygon hull in a plane, etc.)

This routine is based off of Antti Kuukka's implementation of the QuickHull algorithm: https://github.com/akuukka/quickhull implementation