BRL-CAD
chull.h
Go to the documentation of this file.
1 /* C H U L L . H
2  * BRL-CAD
3  *
4  * Copyright (c) 2004-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 /*----------------------------------------------------------------------*/
22 /* @file chull.h */
23 /** @addtogroup chull */
24 /** @{ */
25 
26 /**
27  * @brief Routines for the computation of convex hulls in 2D and 3D
28  */
29 
30 #ifndef BN_CHULL_H
31 #define BN_CHULL_H
32 
33 #include "common.h"
34 #include "vmath.h"
35 #include "bn/defines.h"
36 
38 
39 /**
40  * @brief
41  * Melkman's 2D simple polyline O(n) convex hull algorithm
42  *
43  * On-line construction of the convex hull of a simple polyline
44  * Melkman, Avraham A. Information Processing Letters 25.1 (1987): 11-12.
45  *
46  * See also <a href="http://geomalgorithms.com/a12-_hull-3.html">http://geomalgorithms.com/a12-_hull-3.html</a>
47  *
48  * @param[out] hull convex hull array vertices in ccw orientation (max is n)
49  * @param polyline The points defining the input polyline, stored with ccw orientation
50  * @param n the number of points in polyline
51  * @return the number of points in the output hull array
52  */
53 BN_EXPORT int bn_polyline_2d_chull(point2d_t** hull, const point2d_t* polyline, int n);
54 
55 /**
56  * @brief
57  * Find 2D convex hull for unordered co-planar point sets
58  *
59  * The monotone chain algorithm's sorting approach is used to do
60  * the initial ordering of the points:
61  *
62  * Another efficient algorithm for convex hulls in two dimensions.
63  * Andrew, A. M. Information Processing Letters 9.5 (1979): 216-219.
64  *
65  * See also <a href="http://geomalgorithms.com/a10-_hull-1.html">http://geomalgorithms.com/a10-_hull-1.html</a>
66  *
67  * From there, instead of using the monotonic chain hull assembly
68  * step, recognize that the points thus ordered can be viewed as
69  * defining a simple polyline and use Melkman's algorithm for the
70  * hull building.
71  *
72  * The input point array currently uses type point_t, but all Z
73  * values should be zero.
74  *
75  * @param[out] hull 2D convex hull array vertices in ccw orientation (max is n)
76  * @param points_2d The input 2d points for which a convex hull will be built
77  * @param n the number of points in the input set
78  * @return the number of points in the output hull array or zero if error.
79  */
80 BN_EXPORT int bn_2d_chull(point2d_t** hull, const point2d_t* points_2d, int n);
81 
82 /**
83  * @brief
84  * Find 3D coplanar point convex hull for unordered co-planar point sets
85  *
86  * This function assumes an input an array of 3D points which are coplanar
87  * in some arbitrary plane. This function:
88  *
89  * 1. Finds the plane that fits the points and picks an origin, x-axis and y-axis
90  * which allow 2D coordinates for all points to be calculated.
91  * 2. Calls 2D routines on the array found by step 1 to get a 2D convex hull
92  * 3. Translates the resultant 2D hull points back into 3D points so the hull array
93  * contains the bounding hull expressed in the 3D coordinate space of the
94  * original points.
95  *
96  * @param[out] hull_3d convex hull array vertices using 3-space coordinates in ccw orientation (max is n)
97  * @param points_3d The input points for which a convex hull will be built
98  * @param n the number of points in the input set
99  * @return the number of points in the output hull array
100  */
101 BN_EXPORT int bn_3d_coplanar_chull(point_t** hull, const point_t* points_3d, int n);
102 
103 /**
104  * @brief
105  * Find 3D point convex hull for unordered point sets
106  *
107  * This routine computes the convex hull of a three dimensional point set and
108  * returns the set of vertices and triangular faces that define that hull, as
109  * well as the numerical count of vertices and faces in the hull.
110  *
111  * @param[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.
112  * @param[out] num_faces the number of faces in the faces array
113  * @param[out] vertices the set of vertices used by the convex hull.
114  * @param[out] num_vertices the number of vertices in the convex hull.
115  * @param input_points_3d The input points for which a convex hull will be built
116  * @param num_input_points the number of points in the input set
117  * @return dimension of output (3 is three dimensional faces and hulls, 2 is a polygon hull in a plane, etc.)
118  *
119  * This routine is based off of Ken Clarkson's hull program from
120  * http://www.netlib.org/voronoi/hull.html - see the file chull3d.c
121  * for the full copyright and license statement.
122 */
123 BN_EXPORT int bn_3d_chull(int **faces, int *num_faces, point_t **vertices, int *num_vertices,
124  const point_t *input_points_3d, int num_input_pnts);
125 
126 
128 
129 #endif /* BN_CHULL_H */
130 /** @} */
131 /*
132  * Local Variables:
133  * mode: C
134  * tab-width: 8
135  * indent-tabs-mode: t
136  * c-file-style: "stroustrup"
137  * End:
138  * ex: shiftwidth=4 tabstop=8
139  */
Header file for the BRL-CAD common definitions.
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.
Definition: chull3d.cpp:1265
#define __BEGIN_DECLS
Definition: common.h:73
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.
Definition: chull.c:151
#define __END_DECLS
Definition: common.h:74
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.
Definition: chull.c:46
int bn_2d_chull(point2d_t **hull, const point2d_t *points_2d, int n)
Find 2D convex hull for unordered co-planar point sets.
Definition: chull.c:124