53template<
typename CoordT>
61 PyLong_FromLong(nearest->
index),
62 PyFloat_FromDouble(nearest->
dist));
65template<
typename CoordT>
68 PyObject *py_retval = PyTuple_New(3);
75template<
typename CoordT>
78 PyObject *py_retval = PyTuple_New(3);
80 if (nearest->
index != -1) {
97#define UINT_IS_NEG(n) ((n) > INT_MAX)
103 const char *keywords[] = {
109 if (!PyArg_ParseTupleAndKeywords(args,
115 const_cast<char **
>(keywords),
123 PyErr_SetString(PyExc_ValueError,
"negative 'size' given");
127 if (dimensions == 2) {
130 else if (dimensions == 3) {
134 PyErr_SetString(PyExc_ValueError,
"dimensions must be 2 or 3");
156 Py_TYPE(self)->tp_free(
reinterpret_cast<PyObject *
>(self));
167 py_kdtree_insert_doc,
168 ".. method:: insert(co, index)\n"
170 " Insert a point into the KDTree.\n"
172 " :param co: Point position. Can be 2D or 3D, based on the KDTree dimensions.\n"
173 " :type co: Sequence[float]\n"
174 " :param index: The index of the point (must be non-negative).\n"
175 " :type index: int\n");
181 const char *keywords[] = {
"co",
"index",
nullptr};
183 if (!PyArg_ParseTupleAndKeywords(args,
188 const_cast<char **
>(keywords),
202 PyErr_SetString(PyExc_ValueError,
"negative index given");
207 PyErr_SetString(PyExc_RuntimeError,
"Trying to insert more items than KDTree has room for");
230 py_kdtree_balance_doc,
231 ".. method:: balance()\n"
233 " Balance the tree.\n"
237 " This builds the entire tree, avoid calling after each insertion.\n");
266 PyObject *py_args = PyTuple_New(1);
267 PyTuple_SET_ITEM(py_args, 0, PyLong_FromLong(
index));
268 PyObject *
result = PyObject_CallObject(
data->py_filter, py_args);
276 return int(use_node);
280 data->is_error =
true;
284template<
typename CoordT>
291 if (py_filter == Py_None) {
298 tree, co, &nearest, [&](
int index,
const CoordT & ,
float ) {
313 ".. method:: find(co, *, filter=None)\n"
315 " Find nearest point to ``co``.\n"
317 " :param co: Point position. Can be 2D or 3D, based on the KDTree dimensions.\n"
318 " :type co: Sequence[float]\n"
319 " :param filter: function which takes an index and returns True for indices to "
320 "include in the search.\n"
321 " :type filter: Callable[[int], bool] | None\n"
322 " :return: Returns (position, index, distance),\n"
323 " or (None, None, None) when no match is found.\n"
324 " :rtype: tuple[:class:`Vector`, int, float] | tuple[None, None, None]\n");
327 PyObject *py_co, *py_filter = Py_None;
329 const char *keywords[] = {
"co",
"filter",
nullptr};
331 if (!PyArg_ParseTupleAndKeywords(args,
337 const_cast<char **
>(keywords),
351 PyErr_SetString(PyExc_RuntimeError,
"KDTree must be balanced before calling find()");
367template<
typename CoordT>
374 PyObject *py_list = PyList_New(found);
376 for (
int i = 0; i < found; i++) {
387 py_kdtree_find_n_doc,
388 ".. method:: find_n(co, n)\n"
390 " Find nearest ``n`` points to ``co``.\n"
392 " :param co: Point position. Can be 2D or 3D, based on the KDTree dimensions.\n"
393 " :type co: Sequence[float]\n"
394 " :param n: Number of points to find.\n"
396 " :return: Returns a list of tuples (position, index, distance).\n"
397 " :rtype: list[tuple[:class:`Vector`, int, float]]\n");
403 const char *keywords[] = {
"co",
"n",
nullptr};
405 if (!PyArg_ParseTupleAndKeywords(args,
410 const_cast<char **
>(keywords),
424 PyErr_SetString(PyExc_RuntimeError,
"negative 'n' given");
429 PyErr_SetString(PyExc_RuntimeError,
"KDTree must be balanced before calling find_n()");
445template<
typename CoordT>
452 PyObject *py_list = PyList_New(found);
454 for (
int i = 0; i < found; i++) {
467 py_kdtree_find_range_doc,
468 ".. method:: find_range(co, radius)\n"
470 " Find all points within ``radius`` of ``co``.\n"
472 " :param co: Point position. Can be 2D or 3D, based on the KDTree dimensions.\n"
473 " :type co: Sequence[float]\n"
474 " :param radius: Maximum distance to search for points.\n"
475 " :type radius: float\n"
476 " :return: Returns a list of tuples (position, index, distance).\n"
477 " :rtype: list[tuple[:class:`Vector`, int, float]]\n");
484 const char *keywords[] = {
"co",
"radius",
nullptr};
486 if (!PyArg_ParseTupleAndKeywords(args,
491 const_cast<char **
>(keywords),
505 PyErr_SetString(PyExc_RuntimeError,
"negative radius given");
510 PyErr_SetString(PyExc_RuntimeError,
"KDTree must be balanced before calling find_range()");
529 py_kdtree_dimensions_doc,
530 "KDTree dimensions.\n"
546# pragma clang diagnostic push
547# pragma clang diagnostic ignored "-Wcast-function-type"
549# pragma GCC diagnostic push
550# pragma GCC diagnostic ignored "-Wcast-function-type"
557 static_cast<setter
>(
nullptr),
558 py_kdtree_dimensions_doc,
561 {
nullptr,
nullptr,
nullptr,
nullptr,
nullptr}
566# pragma clang diagnostic pop
568# pragma GCC diagnostic pop
576# pragma clang diagnostic push
577# pragma clang diagnostic ignored "-Wcast-function-type"
579# pragma GCC diagnostic push
580# pragma GCC diagnostic ignored "-Wcast-function-type"
587 METH_VARARGS | METH_KEYWORDS,
588 py_kdtree_insert_doc},
592 py_kdtree_balance_doc},
595 METH_VARARGS | METH_KEYWORDS,
599 METH_VARARGS | METH_KEYWORDS,
600 py_kdtree_find_n_doc},
603 METH_VARARGS | METH_KEYWORDS,
604 py_kdtree_find_range_doc},
605 {
nullptr,
nullptr, 0,
nullptr},
610# pragma clang diagnostic pop
612# pragma GCC diagnostic pop
619 ".. class:: KDTree(size, *, dimensions=3)\n"
621 " A KD-tree initialized to hold up to ``size`` items.\n"
623 " :param size: Maximum number of items.\n"
625 " :param dimensions: The dimensions of the tree (2 or 3).\n"
626 " :type dimensions: int\n"
630 " :meth:`KDTree.balance` must have been called before using any of the ``find`` "
633 PyVarObject_HEAD_INIT(
nullptr, 0)
669 static_cast<allocfunc
>(PyType_GenericAlloc),
670 static_cast<newfunc
>(PyType_GenericNew),
671 static_cast<freefunc
>(
nullptr),
678 static_cast<destructor
>(
nullptr),
687 "Generic 2D/3D KD-tree to perform spatial searches.");
A KD-tree for nearest neighbor search.
Read Blender memory allocation and freeing.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void kdtree_balance(KDTree< CoordT > *tree)
static PyGetSetDef PyKDTree_getseters[]
int PyC_ParseBool(PyObject *o, void *p)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static PyModuleDef kdtree_moduledef
static PyObject * py_kdtree_find_range_impl(PyKDTree *self, const float *co, float radius)
int kdtree_find_nearest_cb(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest, Filter &&filter_cb)
PyDoc_STRVAR(bpy_bm_new_doc, ".. function:: new(*, use_operators=True)\n" "\n" " :param use_operators: Support calling operators in :mod:`bmesh.ops` (uses some " "extra memory per vert/edge/face).\n" " :type use_operators: bool\n" " :return: Return a new, empty BMesh.\n" " :rtype: :class:`bmesh.types.BMesh`\n")
static PyObject * kdtree_nearest_to_py(const KDTreeNearest< CoordT > *nearest)
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
static PyObject * py_kdtree_find_n(PyKDTree *self, PyObject *args, PyObject *kwargs)
PyObject * Vector_CreatePyObject(const float *vec, const int vec_num, PyTypeObject *base_type)
static PyObject * kdtree_nearest_to_py_and_check(const KDTreeNearest< CoordT > *nearest)
BMesh const char void * data
int kdtree_find_nearest_n(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > r_nearest[], uint nearest_len_capacity)
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
int mathutils_array_parse(float *array, int array_num_min, int array_num_max, PyObject *value, const char *error_prefix)
static int py_find_nearest_cb(void *user_data, int index)
int kdtree_find_nearest(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest)
static KDTree< CoordT > * pykdtree_tree_get(PyKDTree *self)
static PyObject * py_kdtree_dimensions_get(PyKDTree *self, void *)
static PyObject * py_kdtree_find_n_impl(PyKDTree *self, const float *co, uint n)
static void kdtree_nearest_to_py_tuple(const KDTreeNearest< CoordT > *nearest, PyObject *py_retval)
static PyObject * py_kdtree_insert(PyKDTree *self, PyObject *args, PyObject *kwargs)
void kdtree_free(KDTree< CoordT > *tree)
void PyC_Tuple_Fill(PyObject *tuple, PyObject *value)
static int PyKDTree__tp_init(PyKDTree *self, PyObject *args, PyObject *kwargs)
static PyObject * py_kdtree_find(PyKDTree *self, PyObject *args, PyObject *kwargs)
PyMODINIT_FUNC PyInit_mathutils_kdtree()
int kdtree_range_search(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > **r_nearest, typename KDTree< CoordT >::ValueType range)
static void PyKDTree__tp_dealloc(PyKDTree *self)
static PyObject * py_kdtree_balance(PyKDTree *self)
static PyObject * py_kdtree_find_impl(PyKDTree *self, const float *co, PyObject *py_filter)
PyTypeObject PyKDTree_Type
static PyMethodDef PyKDTree_methods[]
static PyObject * py_kdtree_find_range(PyKDTree *self, PyObject *args, PyObject *kwargs)
#define PyTuple_SET_ITEMS(op_arg,...)