The Cuik KD-Tree Library
Implementation of a kd-tree. More... #include "cuik-kdtree.h" #include "definitions.h" #include "vector.h" #include "random.h" #include <assert.h> #include <stdio.h> #include <string.h>
Include dependency graph for cuik-kdtree.c:
Go to the source code of this file.
Detailed DescriptionImplementation of a kd-tree. This is used to speed up the search of nearest neighbours (or neighbours in a given ball) but also for sampling. This is an alternative to the DNN library, but here we use the kd-tree not only to search but also to sample. The DNN kd-tree is actually a forest of trees. To samle a single tree is necessary. So,instead of modifying the DNN implementation, we implemented a new kd-tree, even at the risk of being less efficient (specially when searching for neighbours). This implemetation follows the paper
Definition in file cuik-kdtree.c. Macro Definition Documentation
If set to 1, the split point when building the kd-tree is computing using the median. Otherwise, we use the mean as an approximation to the median. Using the median is supposed to produce more balanced trees. Definition at line 45 of file cuik-kdtree.c.
Indents accorging to the node height.
Definition at line 55 of file cuik-kdtree.c. Referenced by PrintKDtree(). Function Documentation
Kd-tree constructor.
Definition at line 132 of file cuik-kdtree.c. References TKDtree::ambient, TKDtree::boundingBox, CopyRectangle(), EnlargeRectangleWithLimits(), ExpandRectangle(), FALSE, GetRectangleLimits(), GetRectangleSplitDim(), TKDtree::height, TKDtree::id, INF, InitRectangleFromPoint(), TKDtree::isLeaf, KDTPTR, TKDtree::left, TKDtree::leftLeaf, TKDtree::m, TKDtree::n, TKDtree::nd, NEW, TKDtree::nextLeaf, NO_UINT, TKDtree::p, TKDtree::r, TKDtree::right, TKDtree::rightLeaf, TKDtree::samplingBox, SetRectangleLimits(), SetRectangleLowerLimit(), SetRectangleUpperLimit(), TKDtree::splitDim, TKDtree::splitValue, SWAP, TKDtree::topology, TRUE, and TKDtree::volume. Referenced by AddPoint2KDtree(), and InitKDTree().
Here is the call graph for this function:
Here is the caller graph for this function:
Auxiliary funciton for NearestNeighbour.
Definition at line 364 of file cuik-kdtree.c. References TKDtree::ambient, TKDtree::boundingBox, TKDtree::id, TKDtree::isLeaf, KDTPTR, TKDtree::left, TKDtree::n, TKDtree::nd, TKDtree::p, TKDtree::right, TKDtree::splitDim, SquaredDistanceToRectangle(), SquaredDistanceToRectangleDimension(), TKDtree::topology, and VectorSquaredDistanceTopologyMin(). Referenced by NearestNeighbour().
Here is the call graph for this function:
Here is the caller graph for this function:
Auxiliary funciton for NeighboursInBall.
Definition at line 421 of file cuik-kdtree.c. References TKDtree::ambient, TKDtree::boundingBox, TKDtree::id, TKDtree::isLeaf, KDTPTR, TKDtree::left, MEM_DUP, TKDtree::n, TKDtree::nd, TKDtree::p, TKDtree::right, TKDtree::splitDim, SquaredDistanceToRectangle(), SquaredDistanceToRectangleDimension(), TKDtree::topology, and VectorSquaredDistanceTopologyMin(). Referenced by NeighboursInBall().
Here is the call graph for this function:
Here is the caller graph for this function:
Kd-tree constructor.
Definition at line 544 of file cuik-kdtree.c. References ANGLE_ACCURACY, BuildKDTree(), GetRectangleDim(), GetRectangleLimits(), M_PI, SetRectangleLimits(), and TOPOLOGY_S. Referenced by main().
Here is the call graph for this function:
Here is the caller graph for this function:
Adds a point to a kd-tree.
Definition at line 582 of file cuik-kdtree.c. References AddPoint2KDtree(), TKDtree::ambient, TKDtree::boundingBox, BuildKDTree(), CopyRectangle(), DeleteKDtree(), EnlargeRectangleWithLimits(), ExpandRectangle(), TKDtree::height, TKDtree::id, INF, InitRectangleFromPoint(), TKDtree::isLeaf, KDTPTR, TKDtree::left, TKDtree::leftLeaf, TKDtree::m, TKDtree::n, TKDtree::nd, NEW, TKDtree::nextLeaf, TKDtree::p, TKDtree::r, TKDtree::right, TKDtree::rightLeaf, TKDtree::samplingBox, TKDtree::splitDim, TKDtree::splitValue, TKDtree::topology, VectorSquaredDistanceTopologyMin(), and TKDtree::volume. Referenced by AddPoint2KDtree(), and main().
Here is the call graph for this function:
Here is the caller graph for this function:
Uses the kd-tree to find the nearest-neighbour of a given point.
Definition at line 714 of file cuik-kdtree.c. References INF, TKDtree::n, NO_UINT, and SearchKDtree(). Referenced by main().
Here is the call graph for this function:
Here is the caller graph for this function:
Determines all the points in a given ball.
Definition at line 730 of file cuik-kdtree.c. References TKDtree::n, NEW, and SearchInBallKDtree(). Referenced by main().
Here is the call graph for this function:
Here is the caller graph for this function:
Geneates a random sample in the volume covered by the kd-tree expanded by a given factor ('r' given in the kd-tree construction) with uniform distribution.
Definition at line 747 of file cuik-kdtree.c. References TKDtree::isLeaf, KDTPTR, TKDtree::left, randomDouble(), RandomPointInRectangle(), TKDtree::right, SampleInKDtree(), TKDtree::samplingBox, and TKDtree::volume. Referenced by SampleInKDtree().
Here is the call graph for this function:
Here is the caller graph for this function:
Returns the sampling expansion used in the kd-tree.
Definition at line 764 of file cuik-kdtree.c. References TKDtree::r.
Prints a kd-tree. Used for debug.
Definition at line 769 of file cuik-kdtree.c. References TKDtree::boundingBox, TKDtree::id, TKDtree::isLeaf, KDTPTR, KDTREE_PRINT_INDENT, TKDtree::left, TKDtree::n, TKDtree::nd, TKDtree::p, PrintKDtree(), PrintRectangle(), TKDtree::right, TKDtree::splitDim, and TKDtree::splitValue. Referenced by PrintKDtree().
Here is the call graph for this function:
Here is the caller graph for this function:
Destructor Definition at line 833 of file cuik-kdtree.c. References TKDtree::ambient, TKDtree::boundingBox, DeleteKDtree(), DeleteRectangle(), TKDtree::id, TKDtree::isLeaf, KDTPTR, TKDtree::left, TKDtree::n, TKDtree::p, TKDtree::right, TKDtree::samplingBox, and TKDtree::topology. Referenced by AddPoint2KDtree(), DeleteKDtree(), and main().
Here is the call graph for this function:
Here is the caller graph for this function:
|
Follow us!