Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/intern/convexhull_2d.c')
-rw-r--r--source/blender/blenlib/intern/convexhull_2d.c71
1 files changed, 34 insertions, 37 deletions
diff --git a/source/blender/blenlib/intern/convexhull_2d.c b/source/blender/blenlib/intern/convexhull_2d.c
index 33d1a68a76e..9e3fb230d3c 100644
--- a/source/blender/blenlib/intern/convexhull_2d.c
+++ b/source/blender/blenlib/intern/convexhull_2d.c
@@ -39,8 +39,9 @@ static float is_left(const float p0[2], const float p1[2], const float p2[2])
return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1]);
}
-int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[])
+static int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[])
{
+ BLI_assert(n >= 2); /* Doesn't handle trivial cases. */
/* the output array r_points[] will be used as the stack */
int bot = 0;
int top = -1; /* indices for bottom and top of the stack */
@@ -66,6 +67,7 @@ int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points
r_points[++top] = minmax;
}
r_points[++top] = minmin; /* add polygon endpoint */
+ BLI_assert(top + 1 <= n);
return top + 1;
}
@@ -122,16 +124,18 @@ int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points
}
if (points[i][0] == points[r_points[0]][0] && points[i][1] == points[r_points[0]][1]) {
+ BLI_assert(top + 1 <= n);
return top + 1; /* special case (mgomes) */
}
r_points[++top] = i; /* push points[i] onto stack */
}
- if (minmax != minmin) {
+ if (minmax != minmin && r_points[0] != minmin) {
r_points[++top] = minmin; /* push joining endpoint onto stack */
}
+ BLI_assert(top + 1 <= n);
return top + 1;
}
@@ -162,35 +166,38 @@ static int pointref_cmp_yx(const void *a_, const void *b_)
int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[])
{
+ BLI_assert(n >= 0);
+ if (n < 2) {
+ if (n == 1) {
+ r_points[0] = 0;
+ }
+ return n;
+ }
struct PointRef *points_ref = MEM_mallocN(sizeof(*points_ref) * (size_t)n, __func__);
float(*points_sort)[2] = MEM_mallocN(sizeof(*points_sort) * (size_t)n, __func__);
- int *points_map;
- int points_hull_num, i;
- for (i = 0; i < n; i++) {
+ for (int i = 0; i < n; i++) {
points_ref[i].pt = points[i];
}
- /* Sort the points by X, then by Y (required by the algorithm) */
+ /* Sort the points by X, then by Y. */
qsort(points_ref, (size_t)n, sizeof(struct PointRef), pointref_cmp_yx);
- for (i = 0; i < n; i++) {
+ for (int i = 0; i < n; i++) {
memcpy(points_sort[i], points_ref[i].pt, sizeof(float[2]));
}
- points_hull_num = BLI_convexhull_2d_sorted(points_sort, n, r_points);
+ int points_hull_num = BLI_convexhull_2d_sorted(points_sort, n, r_points);
- /* map back to the original index values */
- points_map = (int *)points_sort; /* abuse float array for temp storage */
- for (i = 0; i < points_hull_num; i++) {
- points_map[i] = (int)((const float(*)[2])points_ref[r_points[i]].pt - points);
+ /* Map back to the unsorted index values. */
+ for (int i = 0; i < points_hull_num; i++) {
+ r_points[i] = (int)((const float(*)[2])points_ref[r_points[i]].pt - points);
}
- memcpy(r_points, points_map, (size_t)points_hull_num * sizeof(*points_map));
-
MEM_freeN(points_ref);
MEM_freeN(points_sort);
+ BLI_assert(points_hull_num <= n);
return points_hull_num;
}
@@ -202,14 +209,13 @@ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[])
/** \name Utility Convex-Hull Functions
* \{ */
-float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n)
+static float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], int n)
{
- unsigned int i, i_prev;
float area_best = FLT_MAX;
float dvec_best[2]; /* best angle, delay atan2 */
- i_prev = n - 1;
- for (i = 0; i < n; i++) {
+ int i_prev = n - 1;
+ for (int i = 0; i < n; i++) {
const float *ev_a = points_hull[i];
const float *ev_b = points_hull[i_prev];
float dvec[2]; /* 2d rotation matrix */
@@ -218,10 +224,9 @@ float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned in
if (normalize_v2(dvec) != 0.0f) {
/* rotation matrix */
float min[2] = {FLT_MAX, FLT_MAX}, max[2] = {-FLT_MAX, -FLT_MAX};
- unsigned int j;
float area;
- for (j = 0; j < n; j++) {
+ for (int j = 0; j < n; j++) {
float tvec[2];
mul_v2_v2_cw(tvec, dvec, points_hull[j]);
@@ -249,32 +254,24 @@ float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned in
return (area_best != FLT_MAX) ? atan2f(dvec_best[0], dvec_best[1]) : 0.0f;
}
-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)
{
- int *index_map;
- int points_hull_num;
+ BLI_assert(n >= 0);
+ float angle = 0.0f;
- float angle;
+ int *index_map = MEM_mallocN(sizeof(*index_map) * (size_t)n, __func__);
- index_map = MEM_mallocN(sizeof(*index_map) * n * 2, __func__);
+ int points_hull_num = BLI_convexhull_2d(points, n, index_map);
- points_hull_num = BLI_convexhull_2d(points, (int)n, index_map);
-
- if (points_hull_num) {
- float(*points_hull)[2];
- int j;
-
- points_hull = MEM_mallocN(sizeof(*points_hull) * (size_t)points_hull_num, __func__);
- for (j = 0; j < points_hull_num; j++) {
+ if (points_hull_num > 1) {
+ float(*points_hull)[2] = MEM_mallocN(sizeof(*points_hull) * (size_t)points_hull_num, __func__);
+ for (int j = 0; j < points_hull_num; j++) {
copy_v2_v2(points_hull[j], points[index_map[j]]);
}
- angle = BLI_convexhull_aabb_fit_hull_2d(points_hull, (unsigned int)points_hull_num);
+ angle = BLI_convexhull_aabb_fit_hull_2d(points_hull, points_hull_num);
MEM_freeN(points_hull);
}
- else {
- angle = 0.0f;
- }
MEM_freeN(index_map);