Extension of the Query class that allows to read the result of a range neighbor search on the KnnGraph. More...

#include <neighborGraphRangeQuery.h>

Inheritance diagram for Ponca::NeighborGraphRangeQuery< _NeighborGraph >:

Collaboration diagram for Ponca::NeighborGraphRangeQuery< _NeighborGraph >:

Public Types
using	NeighborGraph = _NeighborGraph

using	Traits = typename NeighborGraph::Traits

using	QueryType = RangeIndexQuery< typename Traits::IndexType, typename Traits::DataPoint::Scalar >

using	DataPoint = typename Traits::DataPoint

using	IndexType = typename Traits::IndexType

using	Scalar = typename DataPoint::Scalar

using	VectorType = typename DataPoint::VectorType

using	Iterator = NeighborGraphRangeIterator< NeighborGraph >

using	Self = NeighborGraphRangeQuery< NeighborGraph >

Public Types inherited from Ponca::Query< Input_, Output_ >
using	QueryInType = Input_
	Alias to the input type.

using	QueryOutType = Output_
	Alias to the output type.

Public Member Functions
	NeighborGraphRangeQuery (const NeighborGraph *graph, Scalar radius, int index)

Self &	operator() (int index, Scalar radius)
	Call the range neighbors query with new input and radius parameters.

Self &	operator() (int index)
	Call the range neighbors query with new input parameter.

Iterator	begin ()
	Returns an iterator to the beginning of the range neighbors query.

Iterator	end ()
	Returns an iterator to the end of the range neighbors query.

Public Member Functions inherited from Ponca::Query< Input_, Output_ >
	Query (const typename QueryInType::InputType &in)
	Default constructor that initialize the input parameter only.

	Query (const typename QueryOutType::OutputParameter &outParam, const typename QueryInType::InputType &in)
	Default constructor that initialize the input and output parameters.

template<typename Base , typename... outputType>
Base &	operator() (const typename QueryInType::InputType &in, outputType &&... out)
	Access operator that resets the input and output parameters.

template<typename Base >
Base &	operator() (const typename QueryInType::InputType &in)
	Access operator that resets the input parameter only.

Protected Member Functions
void	initialize (Iterator &iterator)

void	advance (Iterator &iterator)
	Helper function for the NeighborGraphRangeIterator that advances the range neighbors search using the k-nearest neighbors known by the NeighborGraphBase.

Protected Attributes
const NeighborGraph *	m_graph {nullptr}

Traits::KnnGraphRangeSet	m_flag
	Stores every visited neighbor ids.

Traits::KnnGraphRangeStack	m_stack
	Holds the next ids the Query should visit.

Friends
class	NeighborGraphRangeIterator< NeighborGraph >

Detailed Description

template<typename _NeighborGraph>
class Ponca::NeighborGraphRangeQuery< _NeighborGraph >

Extension of the Query class that allows to read the result of a range neighbor search on the KnnGraph.

Output result of a KnnGraph::rangeNeighbors query request.

See also: StaticKnnGraphBase

Contrary to the KdTreeRangeQuery this RangeIndexQuery needs to keep track of all the already visited neighbors using a Set, and to record the next neighbors to explore during the search using a Stack.

Traits::KnnGraphRangeSet A set of indices that is used to avoid the already visited neighbor in our search algorithm. Can either be :

Traits::KnnGraphRangeSet = std::set<int> for dynamic memory, which is not compatible with CUDA. (Used by NeighborGraphDefaultTraits)

-Traits::KnnGraphRangeSet = HashSet<K_MAX_NN> : Stores the index in a HashMap-like structure. The Best case complexity for insertion and search is O(1) and worst case is O(N), depending on the given dataset and on the chosen hashing function (Sparser hashing results will lead to a reduce look-up time). (Used by NeighborGraphPointerTraits)

See also: HashSet

Traits::KnnGraphRangeSet = BitSet<MAX_POINT_CLOUD_SIZE> : Stores the index in a set of bits by allocating a single bit to each possible indices. This structure provides better search and insert complexity at the cost of more memory use (trivial insertion and search, with O(1) complexity). Since we need to allocate a single memory bit for each possible indices, to indicate if the index was stored or not, the memory use of this BitSet type is dependant of the total size of the point cloud. Extensively big point clouds can therefore provoke memory allocation problems if we have a memory limit (e.g. if we are instantiating the NeighborGraphRangeQuery inside local memory, in a CUDA kernel).
See also
BitSet for more detailed information about the memory usage.
Traits::KnnGraphRangeStack The stack type storing the next neighbor to visit. Can either be :
Traits::KnnGraphRangeStack = std::set<int> A stack that dynamically allocates memory (Used by NeighborGraphDefaultTraits)
Traits::KnnGraphRangeStack = Stack<int, K_MAX_NN> : Has a limited amount of storage. Will throw out of bound exception in debug mode if elements are inserted above the maximum capacity of the stack. (Used by NeighborGraphPointerTraits)

Definition at line 54 of file neighborGraphRangeQuery.h.

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ DataPoint

◆ IndexType

◆ Iterator

◆ NeighborGraph

◆ QueryType

◆ Scalar

◆ Self

◆ Traits

◆ VectorType

Constructor & Destructor Documentation

◆ NeighborGraphRangeQuery()

Member Function Documentation

◆ advance()

◆ begin()

◆ end()

◆ initialize()

◆ operator()() [1/2]

◆ operator()() [2/2]

Friends And Related Symbol Documentation

◆ NeighborGraphRangeIterator< NeighborGraph >

Member Data Documentation

◆ m_flag

◆ m_graph

◆ m_stack