NCollection_KDTree< ThePointType, TheDimension, HasRadii > Class Template Reference

Static KD-Tree for efficient point set queries. More...

#include <NCollection_KDTree.hxx>

Public Member Functions
	NCollection_KDTree ()
	Empty constructor. Creates an empty tree.
template<bool R = HasRadii, typename = std::enable_if_t<!R>>
void	Build (const ThePointType *thePoints, size_t theCount)
	Build the tree from a C array of points (no radii). Only available when HasRadii is false.
template<bool R = HasRadii, typename = std::enable_if_t<!R>>
void	Build (const NCollection_Array1< ThePointType > &thePoints)
	Build the tree from an NCollection_Array1 (no radii). Only available when HasRadii is false.
template<bool R = HasRadii, typename = std::enable_if_t<R>>
void	Build (const ThePointType *thePoints, const double *theRadii, size_t theCount)
	Build the tree from a C array of points with per-point radii. Only available when HasRadii is true.
template<bool R = HasRadii, typename = std::enable_if_t<R>>
void	Build (const NCollection_Array1< ThePointType > &thePoints, const NCollection_Array1< double > &theRadii)
	Build the tree from NCollection_Array1 of points with radii. Only available when HasRadii is true.
bool	IsEmpty () const
	Returns true if the tree contains no points.
size_t	Size () const
	Returns the number of points in the tree.
void	Clear ()
	Clears the tree.
const ThePointType &	Point (size_t theIndex) const
	Returns the point at the given 1-based original index.
template<bool R = HasRadii, typename = std::enable_if_t<R>>
double	Radius (size_t theIndex) const
	Returns the radius of the point at the given 1-based original index. Only available when HasRadii is true.
size_t	NearestPoint (const ThePointType &theQuery) const
	Finds the nearest point to theQuery.
size_t	NearestPoint (const ThePointType &theQuery, double &theSqDistance) const
	Finds the nearest point to theQuery and returns the squared distance.
NCollection_DynamicArray< size_t >	NearestPoints (const ThePointType &theQuery, double theTolerance, double &theSqDistance) const
	Finds all nearest points to theQuery that share the same minimum distance. Useful when multiple points are equidistant from the query. First finds the nearest distance via tree traversal, then collects all points at that distance using a range search with theTolerance for floating-point comparison.
size_t	KNearestPoints (const ThePointType &theQuery, size_t theK, NCollection_Array1< size_t > &theIndices, NCollection_Array1< double > &theSqDistances) const
	Finds the K nearest points to theQuery. Results are sorted by distance (closest first).
NCollection_DynamicArray< size_t >	RangeSearch (const ThePointType &theQuery, double theRadius) const
	Finds all points within theRadius of theQuery (sphere search).
template<typename Functor >
void	ForEachInRange (const ThePointType &theQuery, double theRadius, Functor theFunctor) const
	Calls theFunctor for each point within theRadius of theQuery. Zero-allocation alternative to RangeSearch - avoids DynamicArray overhead. Indices passed to theFunctor are 1-based (same convention as RangeSearch).
NCollection_DynamicArray< size_t >	BoxSearch (const ThePointType &theMin, const ThePointType &theMax) const
	Finds all points within the axis-aligned bounding box [theMin, theMax].
template<bool R = HasRadii, typename = std::enable_if_t<R>>
NCollection_DynamicArray< size_t >	ContainingSearch (const ThePointType &theQuery) const
	Finds all points whose sphere contains theQuery. Point i "contains" theQuery if dist(theQuery, point_i) <= radius_i. Only available when HasRadii is true.
template<bool R = HasRadii, typename = std::enable_if_t<R>>
size_t	NearestWeighted (const ThePointType &theQuery) const
	Finds the point whose sphere surface is closest to theQuery. Minimizes gap distance = dist(theQuery, point_i) - radius_i. Negative gap means theQuery is inside the sphere. Only available when HasRadii is true.
template<bool R = HasRadii, typename = std::enable_if_t<R>>
size_t	NearestWeighted (const ThePointType &theQuery, double &theGapDistance) const
	Finds the point whose sphere surface is closest to theQuery. Minimizes gap distance = dist(theQuery, point_i) - radius_i. Negative gap means theQuery is inside the sphere. Only available when HasRadii is true.
	NCollection_KDTree (const NCollection_KDTree &theOther)=default
	Copy constructor.
	NCollection_KDTree (NCollection_KDTree &&theOther) noexcept
	Move constructor.
NCollection_KDTree &	operator= (const NCollection_KDTree &theOther)
	Copy assignment.
NCollection_KDTree &	operator= (NCollection_KDTree &&theOther) noexcept
	Move assignment.

Detailed Description

template<class ThePointType, int TheDimension, bool HasRadii = false>
class NCollection_KDTree< ThePointType, TheDimension, HasRadii >

Static KD-Tree for efficient point set queries.

NCollection_KDTree is a balanced KD-Tree built once from a set of points, supporting efficient nearest-neighbor, k-nearest, range (sphere), and box (AABB) queries.

Key features:

• O(N log N) construction via median-split (std::nth_element)
• O(log N) nearest-neighbor search with bounding box pruning
• O(N^(1-1/d) + k) range and box search
• Cache-friendly permutation-based layout (no node allocations)
• Optional per-point radii for sphere-aware queries (compile-time, zero overhead when unused)
• Works with any point type providing Coord(int) with 1-based indexing

Best suited for:

• Static point clouds (build once, query many times)
• Nearest-neighbor and k-nearest queries
• Spatial range filtering
• Sphere containment and weighted nearest queries (when HasRadii = true)

Required interface for ThePointType (besides copy constructor and operator =):

class MyPointType
{
public:
  double Coord(int theIndex) const;
  // Returns coordinate along theIndex axis (1-based, from 1 to TheDimension)
};

Works out-of-the-box with gp_Pnt, gp_Pnt2d, gp_XYZ, gp_XY.

Template Parameters

ThePointType	Point type providing Coord(int) with 1-based indexing
TheDimension	Spatial dimension (compile-time constant, typically 2 or 3)
HasRadii	When true, enables per-point radii for ContainingSearch and NearestWeighted queries (default: false)

Constructor & Destructor Documentation

NCollection_KDTree() [1/3]

template<class ThePointType , int TheDimension, bool HasRadii = false>

NCollection_KDTree< ThePointType, TheDimension, HasRadii >::NCollection_KDTree ( )

inline

Empty constructor. Creates an empty tree.

NCollection_KDTree() [2/3]

template<class ThePointType , int TheDimension, bool HasRadii = false>

NCollection_KDTree< ThePointType, TheDimension, HasRadii >::NCollection_KDTree ( const NCollection_KDTree< ThePointType, TheDimension, HasRadii > & theOther )

default

Copy constructor.

NCollection_KDTree() [3/3]

template<class ThePointType , int TheDimension, bool HasRadii = false>

NCollection_KDTree< ThePointType, TheDimension, HasRadii >::NCollection_KDTree ( NCollection_KDTree< ThePointType, TheDimension, HasRadii > && theOther )

inlinenoexcept

Move constructor.

Member Function Documentation

BoxSearch()

template<class ThePointType , int TheDimension, bool HasRadii = false>

NCollection_DynamicArray< size_t > NCollection_KDTree< ThePointType, TheDimension, HasRadii >::BoxSearch ( const ThePointType & theMin, const ThePointType & theMax ) const

inline

Finds all points within the axis-aligned bounding box [theMin, theMax].

Parameters

[in]	theMin	minimum corner of the box
[in]	theMax	maximum corner of the box

Returns

array of 1-based indices of found points

Build() [1/4]

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<bool R = HasRadii, typename = std::enable_if_t<!R>>

void NCollection_KDTree< ThePointType, TheDimension, HasRadii >::Build ( const NCollection_Array1< ThePointType > & thePoints )

inline

Build the tree from an NCollection_Array1 (no radii). Only available when HasRadii is false.

Parameters

[in]

thePoints

array of points (any lower bound)

Build() [2/4]

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<bool R = HasRadii, typename = std::enable_if_t<R>>

void NCollection_KDTree< ThePointType, TheDimension, HasRadii >::Build ( const NCollection_Array1< ThePointType > & thePoints, const NCollection_Array1< double > & theRadii )

inline

Build the tree from NCollection_Array1 of points with radii. Only available when HasRadii is true.

Parameters

[in]	thePoints	array of points (any lower bound)
[in]	theRadii	array of radii (same length as thePoints)

Build() [3/4]

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<bool R = HasRadii, typename = std::enable_if_t<R>>

void NCollection_KDTree< ThePointType, TheDimension, HasRadii >::Build ( const ThePointType * thePoints, const double * theRadii, size_t theCount )

inline

Build the tree from a C array of points with per-point radii. Only available when HasRadii is true.

Parameters

[in]	thePoints	pointer to contiguous array of points
[in]	theRadii	pointer to contiguous array of radii (one per point)
[in]	theCount	number of points

Build() [4/4]

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<bool R = HasRadii, typename = std::enable_if_t<!R>>

void NCollection_KDTree< ThePointType, TheDimension, HasRadii >::Build ( const ThePointType * thePoints, size_t theCount )

inline

Build the tree from a C array of points (no radii). Only available when HasRadii is false.

Parameters

[in]	thePoints	pointer to contiguous array of points
[in]	theCount	number of points

Clear()

template<class ThePointType , int TheDimension, bool HasRadii = false>

void NCollection_KDTree< ThePointType, TheDimension, HasRadii >::Clear ( )

inline

Clears the tree.

ContainingSearch()

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<bool R = HasRadii, typename = std::enable_if_t<R>>

NCollection_DynamicArray< size_t > NCollection_KDTree< ThePointType, TheDimension, HasRadii >::ContainingSearch ( const ThePointType & theQuery ) const

inline

Finds all points whose sphere contains theQuery. Point i "contains" theQuery if dist(theQuery, point_i) <= radius_i. Only available when HasRadii is true.

Parameters

[in]

theQuery

query point

Returns

array of 1-based indices of containing points

ForEachInRange()

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<typename Functor >

void NCollection_KDTree< ThePointType, TheDimension, HasRadii >::ForEachInRange ( const ThePointType & theQuery, double theRadius, Functor theFunctor ) const

inline

Calls theFunctor for each point within theRadius of theQuery. Zero-allocation alternative to RangeSearch - avoids DynamicArray overhead. Indices passed to theFunctor are 1-based (same convention as RangeSearch).

Template Parameters

Functor

callable with signature void(size_t theIndex)

Parameters

[in]	theQuery	query point
[in]	theRadius	search radius
[in]	theFunctor	callback invoked for each found 1-based index

IsEmpty()

template<class ThePointType , int TheDimension, bool HasRadii = false>

bool NCollection_KDTree< ThePointType, TheDimension, HasRadii >::IsEmpty ( ) const

inline

Returns true if the tree contains no points.

KNearestPoints()

template<class ThePointType , int TheDimension, bool HasRadii = false>

size_t NCollection_KDTree< ThePointType, TheDimension, HasRadii >::KNearestPoints ( const ThePointType & theQuery, size_t theK, NCollection_Array1< size_t > & theIndices, NCollection_Array1< double > & theSqDistances ) const

inline

Finds the K nearest points to theQuery. Results are sorted by distance (closest first).

Parameters

[in]	theQuery	query point
[in]	theK	number of nearest points to find
[out]	theIndices	1-based indices of the found points (resized internally)
[out]	theSqDistances	squared distances of the found points (resized internally)

Returns

actual count of points found (may be less than theK)

NearestPoint() [1/2]

template<class ThePointType , int TheDimension, bool HasRadii = false>

size_t NCollection_KDTree< ThePointType, TheDimension, HasRadii >::NearestPoint ( const ThePointType & theQuery ) const

inline

Finds the nearest point to theQuery.

Parameters

[in]

theQuery

query point

Returns

1-based index of nearest point, 0 if tree is empty

NearestPoint() [2/2]

template<class ThePointType , int TheDimension, bool HasRadii = false>

size_t NCollection_KDTree< ThePointType, TheDimension, HasRadii >::NearestPoint ( const ThePointType & theQuery, double & theSqDistance ) const

inline

Finds the nearest point to theQuery and returns the squared distance.

Parameters

[in]	theQuery	query point
[out]	theSqDistance	squared distance to the nearest point

Returns

1-based index of nearest point, 0 if tree is empty

NearestPoints()

template<class ThePointType , int TheDimension, bool HasRadii = false>

NCollection_DynamicArray< size_t > NCollection_KDTree< ThePointType, TheDimension, HasRadii >::NearestPoints ( const ThePointType & theQuery, double theTolerance, double & theSqDistance ) const

inline

Finds all nearest points to theQuery that share the same minimum distance. Useful when multiple points are equidistant from the query. First finds the nearest distance via tree traversal, then collects all points at that distance using a range search with theTolerance for floating-point comparison.

Parameters

[in]	theQuery	query point
[in]	theTolerance	absolute tolerance for distance equality (default 0.0)
[out]	theSqDistance	squared distance to the nearest points

Returns

array of 1-based indices of all equidistant nearest points (empty if tree is empty)

NearestWeighted() [1/2]

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<bool R = HasRadii, typename = std::enable_if_t<R>>

size_t NCollection_KDTree< ThePointType, TheDimension, HasRadii >::NearestWeighted ( const ThePointType & theQuery ) const

inline

Finds the point whose sphere surface is closest to theQuery. Minimizes gap distance = dist(theQuery, point_i) - radius_i. Negative gap means theQuery is inside the sphere. Only available when HasRadii is true.

Parameters

[in]

theQuery

query point

Returns

1-based index of nearest-weighted point, 0 if tree is empty

NearestWeighted() [2/2]

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<bool R = HasRadii, typename = std::enable_if_t<R>>

size_t NCollection_KDTree< ThePointType, TheDimension, HasRadii >::NearestWeighted ( const ThePointType & theQuery, double & theGapDistance ) const

inline

Finds the point whose sphere surface is closest to theQuery. Minimizes gap distance = dist(theQuery, point_i) - radius_i. Negative gap means theQuery is inside the sphere. Only available when HasRadii is true.

Parameters

[in]	theQuery	query point
[out]	theGapDistance	gap distance to the nearest sphere surface (negative = inside)

Returns

1-based index of nearest-weighted point, 0 if tree is empty

operator=() [1/2]

template<class ThePointType , int TheDimension, bool HasRadii = false>

NCollection_KDTree & NCollection_KDTree< ThePointType, TheDimension, HasRadii >::operator= ( const NCollection_KDTree< ThePointType, TheDimension, HasRadii > & theOther )

inline

Copy assignment.

operator=() [2/2]

template<class ThePointType , int TheDimension, bool HasRadii = false>

NCollection_KDTree & NCollection_KDTree< ThePointType, TheDimension, HasRadii >::operator= ( NCollection_KDTree< ThePointType, TheDimension, HasRadii > && theOther )

inlinenoexcept

Move assignment.

Point()

template<class ThePointType , int TheDimension, bool HasRadii = false>

const ThePointType & NCollection_KDTree< ThePointType, TheDimension, HasRadii >::Point ( size_t theIndex ) const

inline

Returns the point at the given 1-based original index.

Parameters

[in]

theIndex

1-based point index

Returns

const reference to the point

Radius()

template<class ThePointType , int TheDimension, bool HasRadii = false>

template<bool R = HasRadii, typename = std::enable_if_t<R>>

double NCollection_KDTree< ThePointType, TheDimension, HasRadii >::Radius ( size_t theIndex ) const

inline

Returns the radius of the point at the given 1-based original index. Only available when HasRadii is true.

Parameters

[in]

theIndex

1-based point index

Returns

radius of the point

RangeSearch()

template<class ThePointType , int TheDimension, bool HasRadii = false>

NCollection_DynamicArray< size_t > NCollection_KDTree< ThePointType, TheDimension, HasRadii >::RangeSearch ( const ThePointType & theQuery, double theRadius ) const

inline

Finds all points within theRadius of theQuery (sphere search).

Parameters

[in]	theQuery	query point
[in]	theRadius	search radius

Returns

array of 1-based indices of found points

Size()

template<class ThePointType , int TheDimension, bool HasRadii = false>

size_t NCollection_KDTree< ThePointType, TheDimension, HasRadii >::Size ( ) const

inline

Returns the number of points in the tree.

---

The documentation for this class was generated from the following file:

• NCollection_KDTree.hxx