Cleanup: improve 2D convex hull

Improve correctness, API, comments, memory usage and performance
of the 2D convex hull calculation.

Pre-requisite for UV packing improvements.

Differential Revision: https://developer.blender.org/D16055

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