[brlcad-commits] SF.net SVN: brlcad:[58623] brlcad/trunk/include/bn.h From: - 2013-11-22 18:02:32 ```Revision: 58623 http://sourceforge.net/p/brlcad/code/58623 Author: starseeker Date: 2013-11-22 18:02:27 +0000 (Fri, 22 Nov 2013) Log Message: ----------- Update bn_2d_hull description Modified Paths: -------------- brlcad/trunk/include/bn.h Modified: brlcad/trunk/include/bn.h =================================================================== --- brlcad/trunk/include/bn.h 2013-11-22 16:42:23 UTC (rev 58622) +++ brlcad/trunk/include/bn.h 2013-11-22 18:02:27 UTC (rev 58623) @@ -518,15 +518,20 @@ /** * @brief - * Monotone Chain 2D convex hull algorithm for unordered co-planar point sets + * 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; * - * The monotone chain algorithm is used here primarily due to its simpler, coordinate based - * comparison function. + * 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. * * @param[out] hull convex hull array vertices in ccw orientation (max is n) * @param pnts The input points for which a convex hull will be built @@ -536,6 +541,7 @@ BN_EXPORT int bn_2d_hull(point_t** hull, const point_t* polyline, int n); + /*----------------------------------------------------------------------*/ This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. ```