[brlcad-commits] SF.net SVN: brlcad:[58391] brlcad/trunk
Open Source Solid Modeling CAD
Brought to you by:
brlcad
From: <sta...@us...> - 2013-11-01 15:40:39
|
Revision: 58391 http://sourceforge.net/p/brlcad/code/58391 Author: starseeker Date: 2013-11-01 15:40:36 +0000 (Fri, 01 Nov 2013) Log Message: ----------- Break out the convex hull logic into its own bn function and file. Modified Paths: -------------- brlcad/trunk/include/bn.h brlcad/trunk/src/libbn/CMakeLists.txt brlcad/trunk/src/libbn/obr.c Added Paths: ----------- brlcad/trunk/src/libbn/chull.c Modified: brlcad/trunk/include/bn.h =================================================================== --- brlcad/trunk/include/bn.h 2013-11-01 12:05:50 UTC (rev 58390) +++ brlcad/trunk/include/bn.h 2013-11-01 15:40:36 UTC (rev 58391) @@ -492,7 +492,32 @@ /** @} */ +/*----------------------------------------------------------------------*/ + +/* chull.c */ +/* + * Routines for the computation of convex hulls in 2D and 3D + */ + +/** + * @brief + * Melkman's 2D simple polyline O(n) convex hull algorithm + * + * On-line construction of the convex hull of a simple polyline + * AA Melkman - Information Processing Letters, 1987 + * + * See also <a href="http://geomalgorithms.com/a12-_hull-3.html">http://geomalgorithms.com/a12-_hull-3.html</a> + * + * @param[out] hull output convex hull array of vertices in ccw orientation (max is n) + * @param polyline The points defining the input polyline, stored with ccw orientation + * @param n the number of points in polyline + * @return the number of points in the output hull array + */ +BN_EXPORT int bn_polyline_2D_hull(point_t** hull, const point_t* polyline, int n); + + + /*----------------------------------------------------------------------*/ Modified: brlcad/trunk/src/libbn/CMakeLists.txt =================================================================== --- brlcad/trunk/src/libbn/CMakeLists.txt 2013-11-01 12:05:50 UTC (rev 58390) +++ brlcad/trunk/src/libbn/CMakeLists.txt 2013-11-01 15:40:36 UTC (rev 58391) @@ -10,6 +10,7 @@ anim.c axis.c complex.c + chull.c font.c globals.c list.c Added: brlcad/trunk/src/libbn/chull.c =================================================================== --- brlcad/trunk/src/libbn/chull.c (rev 0) +++ brlcad/trunk/src/libbn/chull.c 2013-11-01 15:40:36 UTC (rev 58391) @@ -0,0 +1,115 @@ +/* C H U L L . C + * BRL-CAD + * + * Copyright (c) 2013 United States Government as represented by + * the U.S. Army Research Laboratory. + * + * Copyright 2001 softSurfer, 2012 Dan Sunday + * This code may be freely used and modified for any purpose + * providing that this copyright notice is included with it. + * SoftSurfer makes no warranty for this code, and cannot be held + * liable for any real or imagined damage resulting from its use. + * Users of this code must verify correctness for their application. + * + */ +/** @file chull.c + * + * This file implements various algorithms for finding convex hull + * of point sets in 2D and 3D. + * + * The implementation of Melkman's algorithm for convex hulls of simple + * polylines is a translation of softSurfer's implementation: + * http://geomalgorithms.com/a12-_hull-3.html + * + */ + + +#include "common.h" +#include <stdlib.h> + +#include "bn.h" + +/* isLeft(): test if a point is Left|On|Right of an infinite line. + * Input: three points L0, L1, and p + * Return: >0 for p left of the line through L0 and L1 + * =0 for p on the line + * <0 for p right of the line + */ +#define isLeft(L0, L1, p) ((L1[X] - L0[X])*(p[Y] - L0[Y]) - (p[X] - L0[X])*(L1[Y] - L0[Y])) + +int +bn_polyline_2D_hull(point_t** hull, const point_t* polyline, int n) +{ + int i; + + /* initialize a deque D[] from bottom to top so that the + 1st three vertices of P[] are a ccw triangle */ + point_t* D = (point_t *)bu_calloc(2*n+1, sizeof(fastf_t)*3, "dequeue"); + + /* hull vertex counter */ + int h; + + /* initial bottom and top deque indices */ + int bot = n-2; + int top = bot+3; + + /* 3rd vertex is a both bot and top */ + VMOVE(D[top], polyline[2]); + VMOVE(D[bot], D[top]); + if (isLeft(polyline[0], polyline[1], polyline[2]) > 0) { + VMOVE(D[bot+1],polyline[0]); + VMOVE(D[bot+2],polyline[1]); /* ccw vertices are: 2,0,1,2 */ + } + else { + VMOVE(D[bot+1],polyline[1]); + VMOVE(D[bot+2],polyline[0]); /* ccw vertices are: 2,1,0,2 */ + } + + /* compute the hull on the deque D[] */ + for (i = 3; i < n; i++) { /* process the rest of vertices */ + /* test if next vertex is inside the deque hull */ + if ((isLeft(D[bot], D[bot+1], polyline[i]) > 0) && + (isLeft(D[top-1], D[top], polyline[i]) > 0) ) + continue; /* skip an interior vertex */ + + /* incrementally add an exterior vertex to the deque hull + get the rightmost tangent at the deque bot */ + while (isLeft(D[bot], D[bot+1], polyline[i]) <= 0) + bot = bot + 1; /* remove bot of deque */ + VMOVE(D[bot-1],polyline[i]); /* insert P[i] at bot of deque */ + bot = bot - 1; + + /* get the leftmost tangent at the deque top */ + while (isLeft(D[top-1], D[top], polyline[i]) <= 0) + top = top - 1; /* pop top of deque */ + VMOVE(D[top+1],polyline[i]); /* push P[i] onto top of deque */ + top = top + 1; + } + + /* transcribe deque D[] to the output hull array hull[] */ + + (*hull) = (point_t *)bu_calloc(top - bot + 2, sizeof(fastf_t)*3, "hull"); + for (h=0; h <= (top-bot); h++) + VMOVE((*hull)[h],D[bot + h]); + + bu_free(D, "free queue"); + return h-1; +} + + +/* TODO - the melkman algorithm isn't going to be enough if we accept generic coplanar point sets + * as valid input - need to do the full convex hull algorithm, maybe exposing this option as a + * special purpose faster function when the input properties can be guaranteed */ + + + +/* + * Local Variables: + * mode: C + * tab-width: 8 + * indent-tabs-mode: t + * c-file-style: "stroustrup" + * End: + * ex: shiftwidth=4 tabstop=8 + */ + Property changes on: brlcad/trunk/src/libbn/chull.c ___________________________________________________________________ Added: svn:mime-type ## -0,0 +1 ## +text/plain \ No newline at end of property Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Modified: brlcad/trunk/src/libbn/obr.c =================================================================== --- brlcad/trunk/src/libbn/obr.c 2013-11-01 12:05:50 UTC (rev 58390) +++ brlcad/trunk/src/libbn/obr.c 2013-11-01 15:40:36 UTC (rev 58391) @@ -31,14 +31,6 @@ * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER * DEALINGS IN THE SOFTWARE. * - * - * Copyright 2001 softSurfer, 2012 Dan Sunday - * This code may be freely used and modified for any purpose - * providing that this copyright notice is included with it. - * SoftSurfer makes no warranty for this code, and cannot be held - * liable for any real or imagined damage resulting from its use. - * Users of this code must verify correctness for their application. - * */ /** @file obr.c * @@ -57,10 +49,6 @@ * http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp * http://www.geometrictools.com/LibMathematics/Algebra/Wm5Vector2.inl * - * The implementation of Melkman's algorithm for convex hulls of simple - * polylines is a translation of softSurfer's implementation: - * http://geomalgorithms.com/a12-_hull-3.html - * */ @@ -145,85 +133,6 @@ return 1; } - -/* TODO - the melkman algorithm isn't going to be enough if we accept generic coplanar point sets - * as valid input - need to do the full convex hull algorithm, maybe exposing this option as a - * special purpose faster function when the input properties can be guaranteed */ - -/* isLeft(): test if a point is Left|On|Right of an infinite line. - * Input: three points L0, L1, and p - * Return: >0 for p left of the line through L0 and L1 - * =0 for p on the line - * <0 for p right of the line - */ -#define isLeft(L0, L1, p) ((L1[X] - L0[X])*(p[Y] - L0[Y]) - (p[X] - L0[X])*(L1[Y] - L0[Y])) - - -/* melkman_hull(): Melkman's 2D simple polyline O(n) convex hull algorithm - * Input: polyline[] = array of 2D vertex points for a simple polyline - * n = the number of points in V[] - * Output: hull[] = output convex hull array of vertices in ccw orientation (max is n) - * Return: h = the number of points in hull[] - */ -int -melkman_hull(const point_t* polyline, int n, point_t** hull) -{ - int i; - - /* initialize a deque D[] from bottom to top so that the - 1st three vertices of P[] are a ccw triangle */ - point_t* D = (point_t *)bu_calloc(2*n+1, sizeof(fastf_t)*3, "dequeue"); - - /* hull vertex counter */ - int h; - - /* initial bottom and top deque indices */ - int bot = n-2; - int top = bot+3; - - /* 3rd vertex is a both bot and top */ - VMOVE(D[top], polyline[2]); - VMOVE(D[bot], D[top]); - if (isLeft(polyline[0], polyline[1], polyline[2]) > 0) { - VMOVE(D[bot+1],polyline[0]); - VMOVE(D[bot+2],polyline[1]); /* ccw vertices are: 2,0,1,2 */ - } - else { - VMOVE(D[bot+1],polyline[1]); - VMOVE(D[bot+2],polyline[0]); /* ccw vertices are: 2,1,0,2 */ - } - - /* compute the hull on the deque D[] */ - for (i = 3; i < n; i++) { /* process the rest of vertices */ - /* test if next vertex is inside the deque hull */ - if ((isLeft(D[bot], D[bot+1], polyline[i]) > 0) && - (isLeft(D[top-1], D[top], polyline[i]) > 0) ) - continue; /* skip an interior vertex */ - - /* incrementally add an exterior vertex to the deque hull - get the rightmost tangent at the deque bot */ - while (isLeft(D[bot], D[bot+1], polyline[i]) <= 0) - bot = bot + 1; /* remove bot of deque */ - VMOVE(D[bot-1],polyline[i]); /* insert P[i] at bot of deque */ - bot = bot - 1; - - /* get the leftmost tangent at the deque top */ - while (isLeft(D[top-1], D[top], polyline[i]) <= 0) - top = top - 1; /* pop top of deque */ - VMOVE(D[top+1],polyline[i]); /* push P[i] onto top of deque */ - top = top + 1; - } - - /* transcribe deque D[] to the output hull array hull[] */ - - (*hull) = (point_t *)bu_calloc(top - bot + 2, sizeof(fastf_t)*3, "hull"); - for (h=0; h <= (top-bot); h++) - VMOVE((*hull)[h],D[bot + h]); - - bu_free(D, "free queue"); - return h-1; -} - struct obr_vals { fastf_t area; vect_t u; @@ -327,7 +236,7 @@ /* Bound convex hull using rotating calipers */ /* 1. Get convex hull */ - hull_pnt_cnt = melkman_hull(pnts, pnt_cnt, &hull_pnts); + hull_pnt_cnt = bn_polyline_2D_hull(&hull_pnts, pnts, pnt_cnt); /* 2. Get edge unit vectors */ edge_unit_vects = (vect_t *)bu_calloc(hull_pnt_cnt + 1, sizeof(fastf_t) * 3, "unit vects for edges"); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |