Collaboration diagram for Convex Hulls:


This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.

## Functions

int bn_polyline_2d_chull (point2d_t **hull, const point2d_t *polyline, int n)
Routines for the computation of convex hulls in 2D and 3D. More...

int bn_2d_chull (point2d_t **hull, const point2d_t *points_2d, int n)
Find 2D convex hull for unordered co-planar point sets. More...

int bn_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 bn_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...

## Function Documentation

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

Routines for the computation of convex 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.

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

Definition at line 46 of file chull.c.

References bu_calloc(), bu_free(), isLeft, and top().

Referenced by bn_2d_chull(), and main().

Here is the call graph for this function:

 int bn_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.

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.

The input point array currently uses type point_t, but all Z values should be zero.

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.

Definition at line 124 of file chull.c.

References bn_polyline_2d_chull(), bu_calloc(), bu_free(), bu_sort(), and pnt_compare_2d().

Referenced by bn_3d_coplanar_chull(), bn_obr_calc(), and main().

Here is the call graph for this function:

 int bn_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_3d 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

Definition at line 151 of file chull.c.

Referenced by bn_3d_chull(), and main().

Here is the call graph for this function:

 int bn_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_points 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 Ken Clarkson's hull program from http://www.netlib.org/voronoi/hull.html - see the file chull3d.c for the full copyright and license statement.

Definition at line 1265 of file chull3d.cpp.

Referenced by ged_bot(), and main().

Here is the call graph for this function: