add mathutils.geometry.box_fit_2d() to wrap BLI_convexhull_aabb_fit_points_2d()
authorCampbell Barton <ideasman42@gmail.com>
Wed, 11 Sep 2013 06:56:51 +0000 (06:56 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Wed, 11 Sep 2013 06:56:51 +0000 (06:56 +0000)
source/blender/blenlib/BLI_convexhull2d.h
source/blender/blenlib/intern/convexhull2d.c
source/blender/editors/uvedit/uvedit_parametrizer.c
source/blender/python/mathutils/mathutils_geometry.c

index d6b5acbb95e0a1d582b2977bb812836ef67b0cb9..3f0787b37b19a9e390bb76e59afccdc829c4ad1e 100644 (file)
  *  \ingroup bli
  */
 
-int BLI_convexhull_2d_presorted(const float (*points)[2], const int n, int r_points[]);
+int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]);
 int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]);
 
-float BLI_convexhull_aabb_fit_2d(const float (*points_hull)[2], unsigned int n);
+float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n);
+float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n);
 
 #endif  /* __BLI_CONVEXHULL2D__ */
index 16bbf464d6596ca472acb199e05737bdc38b1440..536bb6d94e31f430ad2002dc1d604d6e14c308dd 100644 (file)
@@ -60,7 +60,7 @@ static float is_left(const float p0[2], const float p1[2], const float p2[2])
  * \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_presorted(const float (*points)[2], const int n, int r_points[])
+int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[])
 {
        /* the output array r_points[] will be used as the stack */
        int bot = 0;
@@ -207,7 +207,7 @@ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[])
                memcpy(points_sort[i], points_ref[i].pt, sizeof(float[2]));
        }
 
-       tot = BLI_convexhull_2d_presorted((const float (*)[2])points_sort, n, r_points);
+       tot = BLI_convexhull_2d_sorted((const float (*)[2])points_sort, n, r_points);
 
        /* map back to the original index values */
        points_map = (int *)points_sort;  /* abuse float array for temp storage */
@@ -237,9 +237,12 @@ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[])
  *
  * Intended to be used with #BLI_convexhull_2d
  *
+ * \param points  Orded hull points
+ * (result of #BLI_convexhull_2d mapped to a contiguous array).
+ *
  * \note we could return the index of the best edge too if its needed.
  */
-float BLI_convexhull_aabb_fit_2d(const float (*points_hull)[2], unsigned int n)
+float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n)
 {
        unsigned int i, i_prev;
        float area_best = FLT_MAX;
@@ -289,4 +292,42 @@ float BLI_convexhull_aabb_fit_2d(const float (*points_hull)[2], unsigned int n)
 
        return angle_best;
 }
+
+/**
+ * Wrap #BLI_convexhull_aabb_fit_hull_2d and do the convex hull calculation.
+ *
+ * \param points  arbitrary 2d points.
+ */
+float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n)
+{
+       int *index_map;
+       int tot;
+
+       float angle;
+
+       index_map = MEM_mallocN(sizeof(*index_map) * n, __func__);
+
+       tot = BLI_convexhull_2d((const float (*)[2])points, (int)n, index_map);
+
+       if (tot) {
+               float (*points_hull)[2];
+               int j;
+
+               points_hull = MEM_mallocN(sizeof(*points_hull) * (size_t)tot, __func__);
+               for (j = 0; j < tot; j++) {
+                       copy_v2_v2(points_hull[j], points[index_map[j]]);
+               }
+
+               angle = BLI_convexhull_aabb_fit_hull_2d((const float (*)[2])points_hull, (unsigned int)tot);
+               MEM_freeN(points_hull);
+       }
+       else {
+               angle = 0.0f;
+       }
+
+       MEM_freeN(index_map);
+
+       return angle;
+}
+
 /** \} */
index 4bc7aa8e2d003462602d281a680a74d7e0f8b216..f0e97ffe3b1b9c1b4e2ab60c3d55da2b630bfdbe 100644 (file)
@@ -4483,8 +4483,8 @@ static void param_pack_rotate(ParamHandle *handle)
 
        for (i = 0; i < phandle->ncharts; i++) {
                float (*points)[2];
-               int *index_map;
                int tot;
+               float angle;
 
                chart = phandle->charts[i];
 
@@ -4493,34 +4493,18 @@ static void param_pack_rotate(ParamHandle *handle)
                }
 
                points = MEM_mallocN(sizeof(*points) * chart->nverts, __func__);
-               index_map = MEM_mallocN(sizeof(*index_map) * chart->nverts, __func__);
 
                p_chart_uv_to_array(chart, points);
 
-               tot = BLI_convexhull_2d((const float (*)[2])points, chart->nverts, index_map);
+               angle = BLI_convexhull_aabb_fit_points_2d((const float (*)[2])points, tot);
 
-               if (tot) {
-                       float (*points_hull)[2];
-                       int j;
-                       float angle;
-
-                       points_hull = MEM_mallocN(sizeof(*points) * tot, __func__);
-                       for (j = 0; j < tot; j++) {
-                               copy_v2_v2(points_hull[j], points[index_map[j]]);
-                       }
-
-                       angle = BLI_convexhull_aabb_fit_2d((const float (*)[2])points_hull, tot);
-                       MEM_freeN(points_hull);
+               MEM_freeN(points);
 
-                       if (angle != 0.0f) {
-                               float mat[2][2];
-                               angle_to_mat2(mat, angle);
-                               p_chart_uv_transform(chart, mat);
-                       }
+               if (angle != 0.0f) {
+                       float mat[2][2];
+                       angle_to_mat2(mat, angle);
+                       p_chart_uv_transform(chart, mat);
                }
-
-               MEM_freeN(points);
-               MEM_freeN(index_map);
        }
 }
 
index a8c23d3b0f48e9edd0936ca615ff54501ff0fe88..06aa0cb275383c337158f06e8ab753e4dcb22a12 100644 (file)
@@ -1504,6 +1504,38 @@ static PyObject *M_Geometry_box_pack_2d(PyObject *UNUSED(self), PyObject *boxlis
        return ret;
 }
 
+PyDoc_STRVAR(M_Geometry_box_fit_2d_doc,
+".. function:: box_fit_2d(points)\n"
+"\n"
+"   Returns a list of indices into the list given\n"
+"\n"
+"   :arg points: list of 2d points.\n"
+"   :type points: list\n"
+"   :return: a list of indices\n"
+"   :rtype: list of ints\n"
+);
+static PyObject *M_Geometry_box_fit_2d(PyObject *UNUSED(self), PyObject *pointlist)
+{
+       float (*points)[2];
+       Py_ssize_t len;
+
+       float angle = 0.0f;
+
+       len = mathutils_array_parse_alloc_v(((float **)&points), 2, pointlist, "box_fit_2d");
+       if (len == -1) {
+               return NULL;
+       }
+
+       if (len) {
+               /* Non Python function */
+               angle = BLI_convexhull_aabb_fit_points_2d((const float (*)[2])points, len);
+
+               PyMem_Free(points);
+       }
+
+
+       return PyFloat_FromDouble(angle);
+}
 
 PyDoc_STRVAR(M_Geometry_convex_hull_2d_doc,
 ".. function:: convex_hull_2d(points)\n"
@@ -1517,42 +1549,24 @@ PyDoc_STRVAR(M_Geometry_convex_hull_2d_doc,
 );
 static PyObject *M_Geometry_convex_hull_2d(PyObject *UNUSED(self), PyObject *pointlist)
 {
+       float (*points)[2];
        Py_ssize_t len;
 
        PyObject *ret;
 
-       if (!PyList_Check(pointlist)) {
-               PyErr_SetString(PyExc_TypeError,
-                               "expected a list of Vectors");
+       len = mathutils_array_parse_alloc_v(((float **)&points), 2, pointlist, "convex_hull_2d");
+       if (len == -1) {
                return NULL;
        }
 
-       len = PyList_GET_SIZE(pointlist);
        if (len) {
-               float (*points)[2] = MEM_mallocN(sizeof(*points) * len, __func__);
                int *index_map;
                Py_ssize_t len_ret, i;
-               PyObject *list_item;
-               bool ok = true;
-
-               for (i = 0; i < len; i++) {
-                       list_item = PyList_GET_ITEM(pointlist, i);
-                       if (mathutils_array_parse(points[i], 2, 2, list_item, "convex_hull") == -1) {
-                               ok = false;
-                               break;
-                       }
-               }
-
-               if (ok == false) {
-                       MEM_freeN(points);
-                       return NULL;
-               }
 
                index_map  = MEM_mallocN(sizeof(*index_map) * len, __func__);
 
                /* Non Python function */
                len_ret = BLI_convexhull_2d((const float (*)[2])points, len, index_map);
-               MEM_freeN(points);
 
                ret = PyList_New(len_ret);
                for (i = 0; i < len_ret; i++) {
@@ -1560,11 +1574,14 @@ static PyObject *M_Geometry_convex_hull_2d(PyObject *UNUSED(self), PyObject *poi
                }
 
                MEM_freeN(index_map);
+
+               PyMem_Free(points);
        }
        else {
                ret = PyList_New(0);
        }
 
+
        return ret;
 }
 
@@ -1593,6 +1610,7 @@ static PyMethodDef M_Geometry_methods[] = {
        {"interpolate_bezier", (PyCFunction) M_Geometry_interpolate_bezier, METH_VARARGS, M_Geometry_interpolate_bezier_doc},
        {"tessellate_polygon", (PyCFunction) M_Geometry_tessellate_polygon, METH_O, M_Geometry_tessellate_polygon_doc},
        {"convex_hull_2d", (PyCFunction) M_Geometry_convex_hull_2d, METH_O, M_Geometry_convex_hull_2d_doc},
+       {"box_fit_2d", (PyCFunction) M_Geometry_box_fit_2d, METH_O, M_Geometry_box_fit_2d_doc},
        {"box_pack_2d", (PyCFunction) M_Geometry_box_pack_2d, METH_O, M_Geometry_box_pack_2d_doc},
 #endif
        {NULL, NULL, 0, NULL}