BRL-CAD
Collaboration diagram for Convex Hulls:

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

Detailed Description

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.

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

Parameters
[out]hullconvex hull array vertices in ccw orientation (max is n)
polylineThe points defining the input polyline, stored with ccw orientation
nthe 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.

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.

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

Parameters
[out]hull2D convex hull array vertices in ccw orientation (max is n)
points_2dThe input 2d points for which a convex hull will be built
nthe 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_3dconvex hull array vertices using 3-space coordinates in ccw orientation (max is n)
points_3dThe input points for which a convex hull will be built
nthe 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.

References bn_2d_chull(), bu_calloc(), bu_malloc(), coplanar_2d_coord_sys(), coplanar_2d_to_3d(), and coplanar_3d_to_2d().

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]facesset 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_facesthe number of faces in the faces array
[out]verticesthe set of vertices used by the convex hull.
[out]num_verticesthe number of vertices in the convex hull.
input_points_3dThe input points for which a convex hull will be built
num_input_pointsthe 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.

References bn_3d_coplanar_chull(), bu_free(), BU_GET, bu_log(), BU_PTBL_LEN, BU_PUT, chull3d_data::cdim, chull3d_data::center_pnt, chull3d_build_convex_hull(), chull3d_collect_faces(), chull3d_collect_hull_pnts(), CHULL3D_COUNT_THRESHOLD, chull3d_data_free(), chull3d_data_init(), CHULL3D_DELTA_THRESHOLD, chull3d_free_hull_storage(), chull3d_get_next_site(), chull3d_intermediate_set(), chull3d_make_shuffle(), chull3d_site_numm(), chull3d_visit_hull(), chull3d_data::face_cnt, chull3d_data::faces, chull3d_data::input_vert_array, chull3d_data::output_pnts, chull3d_data::pdim, chull3d_data::vert_array, and chull3d_data::vert_cnt.

Referenced by ged_bot(), and main().

Here is the call graph for this function: