diff options
Diffstat (limited to 'source/blender/blenlib/BLI_convexhull_2d.h')
-rw-r--r-- | source/blender/blenlib/BLI_convexhull_2d.h | 37 |
1 files changed, 10 insertions, 27 deletions
diff --git a/source/blender/blenlib/BLI_convexhull_2d.h b/source/blender/blenlib/BLI_convexhull_2d.h index 0b4c3d486fb..044c1da6925 100644 --- a/source/blender/blenlib/BLI_convexhull_2d.h +++ b/source/blender/blenlib/BLI_convexhull_2d.h @@ -11,43 +11,26 @@ extern "C" { #endif /** - * A.M. Andrew's monotone chain 2D convex hull algorithm. - * - * \param points: An array of 2D points presorted by increasing x and y-coords. - * \param n: The number of points in points. - * \param r_points: An array of the convex hull vertex indices (max is n). - * \returns the number of points in r_points. - */ -int BLI_convexhull_2d_sorted(const float (*points)[2], int n, int r_points[]); -/** - * A.M. Andrew's monotone chain 2D convex hull algorithm. + * Extract 2D convex hull. * * \param points: An array of 2D points. * \param n: The number of points in points. * \param r_points: An array of the convex hull vertex indices (max is n). - * _must_ be allocated as `n * 2` because of how its used internally, - * even though the final result will be no more than \a n in size. - * \returns the number of points in r_points. - */ -int BLI_convexhull_2d(const float (*points)[2], int n, int r_points[]); - -/** - * \return The best angle for fitting the convex hull to an axis aligned bounding box. - * - * Intended to be used with #BLI_convexhull_2d + * \return The number of indices in r_points. * - * \param points_hull: Ordered hull points - * (result of #BLI_convexhull_2d mapped to a contiguous array). + * \note Performance is `O(n.log(n))`, same as `qsort`. * - * \note we could return the index of the best edge too if its needed. */ -float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n); +int BLI_convexhull_2d(const float (*points)[2], int n, int r_points[/* n */]); + /** - * Wrap #BLI_convexhull_aabb_fit_hull_2d and do the convex hull calculation. + * \return The best angle for fitting the points to an axis aligned bounding box. + * + * \note We could return the index of the best edge too if its needed. * - * \param points: arbitrary 2d points. + * \param points: Arbitrary 2d points. */ -float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n); +float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], int n); #ifdef __cplusplus } |