diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-09-10 11:52:10 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-09-10 11:52:10 +0400 |
commit | 5dbe17cc125bf7d9e96b45c02bdfbd00b6103bdf (patch) | |
tree | 869a2065615d4a5eee145704abb1a28411fd87af /source/blender/python/mathutils/mathutils_geometry.c | |
parent | 46db99e7fdec050ffeef49faa05e6d34103217c4 (diff) |
add 2d convex hull utility function, BLI_convexhull_2d(), and python api mathutils.geometry.convex_hull_2d()
uses Andrew's monotone chain 2D convex hull algorithm.
Diffstat (limited to 'source/blender/python/mathutils/mathutils_geometry.c')
-rw-r--r-- | source/blender/python/mathutils/mathutils_geometry.c | 66 |
1 files changed, 66 insertions, 0 deletions
diff --git a/source/blender/python/mathutils/mathutils_geometry.c b/source/blender/python/mathutils/mathutils_geometry.c index b69e3eb23f8..0113efb8dc2 100644 --- a/source/blender/python/mathutils/mathutils_geometry.c +++ b/source/blender/python/mathutils/mathutils_geometry.c @@ -34,6 +34,7 @@ # include "MEM_guardedalloc.h" # include "BLI_blenlib.h" # include "BLI_boxpack2d.h" +# include "BLI_convexhull2d.h" # include "BKE_displist.h" # include "BKE_curve.h" #endif @@ -1503,6 +1504,70 @@ static PyObject *M_Geometry_box_pack_2d(PyObject *UNUSED(self), PyObject *boxlis return ret; } + +PyDoc_STRVAR(M_Geometry_convex_hull_2d_doc, +".. function:: convex_hull_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_convex_hull_2d(PyObject *UNUSED(self), PyObject *pointlist) +{ + Py_ssize_t len; + + PyObject *ret; + + if (!PyList_Check(pointlist)) { + PyErr_SetString(PyExc_TypeError, + "expected a list of Vectors"); + 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++) { + PyList_SET_ITEM(ret, i, PyLong_FromLong(index_map[i])); + } + + MEM_freeN(index_map); + } + else { + ret = PyList_New(0); + } + + return ret; +} + #endif /* MATH_STANDALONE */ @@ -1527,6 +1592,7 @@ static PyMethodDef M_Geometry_methods[] = { #ifndef MATH_STANDALONE {"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_pack_2d", (PyCFunction) M_Geometry_box_pack_2d, METH_O, M_Geometry_box_pack_2d_doc}, #endif {NULL, NULL, 0, NULL} |