Template Class KDTree

Nested Relationships

Nested Types

Class Documentation

template<typename PointT, unsigned int N = 3>
class KDTree

a kd-Tree Implementation for nearest Neighbor searches

Can contain any type of data, as long as it implements <float/double> operator[](uint axis) for axis in [0, N). Specifically, one could create a type like: struct PointWithNormal { Vector3f point; Vector3f normal; float operator[](uint i) const { return point[i]; } }; Or struct PointWithHandle { Vector3f point; VertexHandle handle; float operator[](uint i) const { return point[i]; } }; To have associated metadata with the points, that can then be obtained from the neighbors.

Template Parameters:

  • PointT – The type of the data to be stored in the tree

  • N – The dimensions of PointT

Public Types

using Ptr = std::shared_ptr<KDTree<PointT, N>>

Public Functions

virtual ~KDTree() = default
template<typename InPointT, typename FloatT>
bool nnSearch(const InPointT &point, PointT *&neighbor, FloatT &distance, double maxDistance = std::numeric_limits<double>::infinity()) const

Finds the nearest neighbor of ‘point’ that is within ‘maxDistance’ (defaults to infinity). The resulting neighbor is written into ‘neighbor’ (or nullptr if none is found).

Parameters:

  • point – The Point whose neighbor is searched

  • neighbor – A Pointer that is set to the neighbor or nullptr if none is found

  • distance – The final distance between point and neighbor

  • maxDistance – The maximum distance allowed between neighbors. Setting this value significantly speeds up the search.

Returns:

bool true if a neighbors was found, false otherwise

template<typename InPointT, typename FloatT>
size_t knnSearch(const InPointT &point, size_t k, std::vector<PointT*> &neighbors, std::vector<FloatT> &distances, double maxDistance = std::numeric_limits<double>::infinity()) const

Finds the ‘k’ nearest neighbor of ‘point’ that are within ‘maxDistance’ (defaults to infinity). The resulting neighbor is written into ‘neighbor’ (or nullptr if none is found).

Parameters:

  • point – The Point whose neighbor is searched

  • k – The number of neighbors to find

  • neighbors – Will be filled with the neighbors

  • distances – Will be filled with the distances to the neighbors

  • maxDistance – The maximum distance allowed between neighbors. Setting this value significantly speeds up the search.

Returns:

size_t The number of neighbors found (Usually k)

template<typename InPointT>
size_t knnSearch(const InPointT &point, size_t k, std::vector<PointT*> &neighbors, double maxDistance = std::numeric_limits<double>::infinity()) const

Same as knnSearch, but does not gather distances.

inline size_t numPoint() const

Returns the number of points in the tree.

inline const PointT *points() const

Returns the points stored in the tree.

Note that the order is different than the one passed to the constructor.

Public Static Functions

static Ptr create(std::unique_ptr<PointT[]> &&points, size_t numPoints, size_t maxLeafSize = 20)

Construct a new KDTree.

Parameters:

  • points – The points to be stored in the tree.

  • numPoints – The number of elements in points.

  • maxLeafSize – The maximum number of points per leaf.

Protected Types

using Queue = std::priority_queue<DistPoint>

A Priority queue to keep track of the k nearest Points.

using QueryPoint = Eigen::Matrix<double, N, 1>
using KDPtr = std::unique_ptr<KDTreeInternal>

Protected Functions

inline KDTree(std::unique_ptr<PointT[]> &&points, size_t numPoints)
inline KDTree(PointT *points, size_t numPoints)
template<typename InPointT>
inline QueryPoint toQueryPoint(const InPointT &point) const
void init(size_t maxLeafSize = 20)
KDPtr createRecursive(PointT *start, PointT *end, const QueryPoint &min, const QueryPoint &max, size_t maxLeafSize)

Protected Attributes

size_t m_numPoints
std::unique_ptr<PointT[]> m_points
std::unique_ptr<KDTreeInternal> m_tree
struct DistPoint

A Point with its squared distance to the query Point for easy comparison.

Public Functions

inline bool operator<(const DistPoint &other) const

Public Members

PointT *point
double distanceSq
class KDTreeInternal

Public Functions

virtual void nnInternal(const QueryPoint &point, DistPoint &neighbor) const = 0

Internal recursive version of nnSearch. Provided by subclasses.

Parameters:

  • point – The query Point to search around

  • neighbor – The current nearest neighbor or nullptr if none is found

  • worstDistSq – The remaining search radius for new Neighbors (squared)

virtual void knnInternal(const QueryPoint &point, size_t k, Queue &neighbors, double &worstDistSq) const = 0

Internal recursive version of knnSearch. Provided by subclasses.

Parameters:

  • point – The query Point to search around

  • neighbors – The Queue to place the Neighbors into

  • worstDistSq – The remaining search radius for new Neighbors (squared)

  • k – The number of Neighbors to find

virtual ~KDTreeInternal() = default