K-d tree, used for hierarchical clustering of particles and accelerated Kn queries. More...
#include <KdTree.h>
Inheritance diagram for KdTree< TNode, TMetric >:
Public Member Functions | |
| KdTree (const Size leafSize=25, const Size maxParallelDepth=50) | |
| template<bool FindAll> | |
| Size | find (const Vector &pos, const Size index, const Float radius, Array< NeighbourRecord > &neighs) const |
| INLINE TNode & | getNode (const Size nodeIdx) |
| Returns the node with given index. More... | |
| INLINE const TNode & | getNode (const Size nodeIdx) const |
| Returns the node with given index. More... | |
| INLINE Size | getNodeCnt () const |
| Returns the number of nodes in the tree. More... | |
| INLINE LeafIndexSequence | getLeafIndices (const LeafNode< TNode > &leaf) const |
| Returns the sequence of particles indices belonging to given leaf. More... | |
| Outcome | sanityCheck () const |
| Performs some checks of KdTree consistency, returns SUCCESS if everything is OK. More... | |
 Public Member Functions inherited from FinderTemplate< KdTree< TNode, EuclideanMetric > > | |
| virtual Size | findAll (const Size index, const Float radius, Array< NeighbourRecord > &neighbours) const override |
| Finds all neighbours within given radius from the point given by index. More... | |
| virtual Size | findAll (const Vector &pos, const Float radius, Array< NeighbourRecord > &neighbours) const override |
| Finds all points within given radius from given position. More... | |
| virtual Size | findLowerRank (const Size index, const Float radius, Array< NeighbourRecord > &neighbours) const override |
| Finds all points within radius that have a lower rank in smoothing length. More... | |
| Public Member Functions inherited from ISymmetricFinder | |
| void | build (IScheduler &scheduler, ArrayView< const Vector > points, Flags< FinderFlag > flags=FinderFlag::MAKE_RANK) |
| Constructs the struct with an array of vectors. More... | |
| template<typename TCompare > | |
| void | buildWithRank (IScheduler &scheduler, ArrayView< const Vector > points, TCompare &&comp) |
| Constructs the struct with custom predicate for ordering particles. More... | |
| Public Member Functions inherited from IBasicFinder | |
| void | build (IScheduler &scheduler, ArrayView< const Vector > points) |
| Constructs the struct with an array of vectors. More... | |
| Public Member Functions inherited from Polymorphic | |
| virtual | ~Polymorphic () |
Protected Member Functions | |
| virtual void | buildImpl (IScheduler &scheduler, ArrayView< const Vector > points) override |
| Builds finder from set of vectors. More... | |
Additional Inherited Members | |
| Protected Attributes inherited from ISymmetricFinder | |
| Order | rank |
| Ranks of particles according to their smoothing lengths. More... | |
| Protected Attributes inherited from IBasicFinder | |
| ArrayView< const Vector > | values |
| View of the source datapoints, updated every time (re)build is called. More... | |
Detailed Description
template<typename TNode, typename TMetric = EuclideanMetric>
class KdTree< TNode, TMetric >
K-d tree, used for hierarchical clustering of particles and accelerated Kn queries.
Allows storing arbitrary data at each node of the tree.
https://www.cs.umd.edu/~mount/Papers/cgc99-smpack.pdf
- Template Parameters
-
TNode Nodes of the tree, should always derive from KdNode and should be POD structs. TMetric Functor returning the squared distance of two vectors.
Constructor & Destructor Documentation
◆ KdTree()
Member Function Documentation
◆ buildImpl()
template<typename TNode , typename TMetric >
|
overrideprotectedvirtual |
Builds finder from set of vectors.
This must be called before findAll, can be called more than once.
- Parameters
-
scheduler Scheduler that can be used for parallelization. points View of the array of points in space.
Implements IBasicFinder.
Definition at line 11 of file KdTree.inl.h.
◆ find()
template<typename TNode , typename TMetric >
template<bool FindAll>
| Size KdTree< TNode, TMetric >::find | ( | const Vector & | pos, |
| const Size | index, | ||
| const Float | radius, | ||
| Array< NeighbourRecord > & | neighs | ||
| ) | const |
- Todo:
- order part
Definition at line 316 of file KdTree.inl.h.
◆ getLeafIndices()
template<typename TNode , typename TMetric = EuclideanMetric>
|
inline |
◆ getNode() [1/2]
◆ getNode() [2/2]
◆ getNodeCnt()
◆ sanityCheck()
Performs some checks of KdTree consistency, returns SUCCESS if everything is OK.
Definition at line 394 of file KdTree.inl.h.
Member Data Documentation
◆ leafSize
◆ maxParallelDepth
The documentation for this class was generated from the following files:
- /home/pavel/projects/astro/sph/src/core/objects/finders/KdTree.h
- /home/pavel/projects/astro/sph/src/core/objects/finders/KdTree.inl.h
