Dynamic R*-tree with SoA node layout and stored insertion bounding boxes. More...

#include <dynamic_rtree.h>

Classes
struct	BULK_ENTRY
	Entry type for bulk loading. More...

class	Iterator
	Iterator for traversing all data items in the tree. More...

class	SearchIterator
	Lazy iterator that traverses only nodes overlapping a query rectangle. More...

class	SearchRange
	Lazy range for iterating over items whose bounding boxes overlap a query rectangle. More...

struct	SPLIT_ENTRY

Public Types
using	NODE = RTREE_NODE<DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES>

Public Member Functions
	DYNAMIC_RTREE ()=default

	~DYNAMIC_RTREE ()

	DYNAMIC_RTREE (DYNAMIC_RTREE &&aOther) noexcept

DYNAMIC_RTREE &	operator= (DYNAMIC_RTREE &&aOther) noexcept

	DYNAMIC_RTREE (const DYNAMIC_RTREE &)=delete

DYNAMIC_RTREE &	operator= (const DYNAMIC_RTREE &)=delete

void	Insert (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)
	Insert an item with the given bounding box.

bool	Remove (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)
	Remove an item using its stored insertion bounding box.

template<class VISITOR>
int	Search (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], VISITOR &aVisitor) const
	Search for items whose bounding boxes overlap the query rectangle.

void	RemoveAll ()
	Remove all items from the tree.

void	BulkLoad (std::vector< BULK_ENTRY > &aEntries)
	Build the tree from a batch of entries using Hilbert-curve packed bulk loading.

size_t	size () const

bool	empty () const

size_t	MemoryUsage () const
	Return approximate memory usage in bytes.

Iterator	begin () const

Iterator	end () const

SearchRange	Overlapping (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS]) const
	Return a lazy range of items overlapping the query rectangle.

void	NearestNeighbors (const ELEMTYPE aPoint[NUMDIMS], int aK, std::vector< std::pair< int64_t, DATATYPE > > &aResults) const
	Nearest-neighbor search using Hjaltason & Samet's algorithm.

Static Public Attributes
static constexpr int	MAXNODES = TMAXNODES

static constexpr int	MINNODES = NODE::MINNODES

static constexpr int	REINSERT_COUNT = MAXNODES * 3 / 10

Private Member Functions
NODE *	allocNode ()

void	freeNode (NODE *aNode)

void	removeAllNodes (NODE *aNode)

void	insertImpl (const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData, uint32_t &aReinsertedLevels)
	Core insertion with forced reinsert tracking.

NODE *	chooseSubtree (NODE aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], std::vector< NODE > &aPath)
	R*-tree ChooseSubtree.

void	overflowTreatment (NODE aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData, std::vector< NODE > &aPath, uint32_t &aReinsertedLevels)
	Handle overflow: forced reinsert or split.

void	forcedReinsert (NODE aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData, std::vector< NODE > &aPath, uint32_t &aReinsertedLevels)
	R*-tree forced reinsert.

void	reinsertNode (NODE *aChild, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], int aLevel, uint32_t &aReinsertedLevels)
	Reinsert an internal node's child at its correct level.

NODE *	chooseSubtreeAtLevel (NODE aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], int aTargetLevel, std::vector< NODE > &aPath)
	ChooseSubtree targeting a specific level.

void	splitNode (NODE aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData, std::vector< NODE > &aPath, uint32_t &aReinsertedLevels)
	R*-tree split.

void	splitNodeInternal (NODE aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], NODE aChild, std::vector< NODE * > &aPath, uint32_t &aReinsertedLevels)
	Split an internal node to insert a new child.

template<class ENTRY_VEC>
int64_t	computeSplitPerimeters (const ENTRY_VEC &aEntries, int aTotalEntries) const
	Compute sum of perimeters for all valid split distributions.

template<class ENTRY_VEC>
int	findBestSplitIndex (const ENTRY_VEC &aEntries, int aTotalEntries) const
	Find the split index that minimizes overlap between the two groups.

template<class ENTRY_VEC>
int64_t	computeSplitOverlap (const ENTRY_VEC &aEntries, int aSplitIdx, int aTotalEntries) const
	Compute the overlap area between two split groups.

int64_t	computeOverlap (NODE *aNode, int aIdx) const
	Compute total overlap of child i with all other children in the node.

int64_t	computeOverlapEnlarged (NODE *aNode, int aIdx, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS]) const
	Compute total overlap of child i (enlarged to include query box) with other children.

void	adjustPath (const std::vector< NODE * > &aPath, NODE *aBottomChild=nullptr)
	Adjust bounding boxes for all nodes in the path (root to leaf).

int	findChildSlot (NODE aParent, NODE aChild) const

bool	removeImpl (NODE aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData, std::vector< NODE > &aReinsertList)
	Remove an item from the tree, collecting underflowing nodes for reinsertion.

void	reinsertOrphans (std::vector< NODE * > &aReinsertList)
	Reinsert all entries from orphaned underflowing nodes.

void	condenseRoot ()
	If the root has only one child, replace it with that child.

template<class VISITOR>
bool	searchImpl (NODE *aNode, const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], VISITOR &aVisitor, int &aFound) const
	Recursive search.

int64_t	minDistSq (NODE *aNode, int aSlot, const ELEMTYPE aPoint[NUMDIMS]) const
	Compute minimum squared distance from a point to a child's bounding box.

Private Attributes
NODE *	m_root = nullptr

size_t	m_count = 0

SLAB_ALLOCATOR< NODE >	m_allocator

Detailed Description

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>
class KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >

Dynamic R*-tree with SoA node layout and stored insertion bounding boxes.

Supports O(log N) insert, remove, and query operations. Uses R*-tree split and forced reinsert heuristics for optimal tree quality.

Key features:

SoA node layout with configurable fanout for cache efficiency
Stored insertion bboxes eliminate O(N) fallback removal
Slab allocator for node memory
Move semantics (no raw pointer ownership issues)
Dual API: new ELEMTYPE-array API + raw-array compat

Template Parameters

DATATYPE	Type of data stored in leaf nodes
ELEMTYPE	Coordinate element type (typically int)
NUMDIMS	Number of dimensions (2 or 3)
TMAXNODES	Maximum children per node (fanout)

Definition at line 63 of file dynamic_rtree.h.

Member Typedef Documentation

◆ NODE

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

using KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::NODE = RTREE_NODE<DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES>

Definition at line 66 of file dynamic_rtree.h.

Constructor & Destructor Documentation

◆ DYNAMIC_RTREE() [1/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::DYNAMIC_RTREE ( )

default

◆ ~DYNAMIC_RTREE()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::~DYNAMIC_RTREE ( )

inline

Definition at line 76 of file dynamic_rtree.h.

◆ DYNAMIC_RTREE() [2/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::DYNAMIC_RTREE ( DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES > && aOther )

inlinenoexcept

Definition at line 84 of file dynamic_rtree.h.

◆ DYNAMIC_RTREE() [3/3]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::DYNAMIC_RTREE ( const DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES > & )

delete

Member Function Documentation

◆ adjustPath()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::adjustPath	(	const std::vector< NODE * > &	aPath,
		NODE *	aBottomChild = nullptr )

inlineprivate

Adjust bounding boxes for all nodes in the path (root to leaf).

Parameters

aPath	Path from root to the parent of the modified node
aBottomChild	The modified node (leaf or internal) whose parent's bbox needs updating. If nullptr, only updates between path entries.

Definition at line 1593 of file dynamic_rtree.h.

◆ allocNode()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

NODE * KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::allocNode ( )

inlineprivate

Definition at line 680 of file dynamic_rtree.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::Insert().

◆ begin()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

Iterator KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::begin ( ) const

inline

Definition at line 456 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE().

◆ BulkLoad()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::BulkLoad ( std::vector< BULK_ENTRY > & aEntries )

inline

Build the tree from a batch of entries using Hilbert-curve packed bulk loading.

This is dramatically faster than inserting items individually because it avoids the R*-tree forced-reinsertion cascades. Items are sorted by Hilbert curve index of their bounding box centers, then packed bottom-up into nodes.

Any existing tree contents are discarded.

Parameters

aEntries Entries to load. The vector may be reordered.

Definition at line 228 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

◆ chooseSubtree()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

NODE * KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::chooseSubtree	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		std::vector< NODE * > &	aPath )

inlineprivate

R*-tree ChooseSubtree.

At leaf level (level==1): minimize overlap increase. At higher levels: minimize area increase, tie-break by smallest area.

Definition at line 737 of file dynamic_rtree.h.

◆ chooseSubtreeAtLevel()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

NODE * KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::chooseSubtreeAtLevel	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		int	aTargetLevel,
		std::vector< NODE * > &	aPath )

inlineprivate

ChooseSubtree targeting a specific level.

Definition at line 1009 of file dynamic_rtree.h.

◆ computeOverlap()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

int64_t KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::computeOverlap	(	NODE *	aNode,
		int	aIdx ) const

inlineprivate

Compute total overlap of child i with all other children in the node.

Definition at line 1538 of file dynamic_rtree.h.

◆ computeOverlapEnlarged()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

int64_t KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::computeOverlapEnlarged	(	NODE *	aNode,
		int	aIdx,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] ) const

inlineprivate

Compute total overlap of child i (enlarged to include query box) with other children.

Definition at line 1558 of file dynamic_rtree.h.

◆ computeSplitOverlap()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

template<class ENTRY_VEC>

int64_t KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::computeSplitOverlap	(	const ENTRY_VEC &	aEntries,
		int	aSplitIdx,
		int	aTotalEntries ) const

inlineprivate

Compute the overlap area between two split groups.

Definition at line 1482 of file dynamic_rtree.h.

◆ computeSplitPerimeters()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

template<class ENTRY_VEC>

int64_t KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::computeSplitPerimeters	(	const ENTRY_VEC &	aEntries,
		int	aTotalEntries ) const

inlineprivate

Compute sum of perimeters for all valid split distributions.

Definition at line 1384 of file dynamic_rtree.h.

◆ condenseRoot()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::condenseRoot ( )

inlineprivate

If the root has only one child, replace it with that child.

Definition at line 1725 of file dynamic_rtree.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::Remove().

◆ empty()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

bool KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::empty ( ) const

inline

Definition at line 352 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

◆ end()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

Iterator KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::end ( ) const

inline

Definition at line 457 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE().

◆ findBestSplitIndex()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

template<class ENTRY_VEC>

int KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::findBestSplitIndex	(	const ENTRY_VEC &	aEntries,
		int	aTotalEntries ) const

inlineprivate

Find the split index that minimizes overlap between the two groups.

Definition at line 1427 of file dynamic_rtree.h.

◆ findChildSlot()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

int KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::findChildSlot	(	NODE *	aParent,
		NODE *	aChild ) const

inlineprivate

Definition at line 1617 of file dynamic_rtree.h.

◆ forcedReinsert()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::forcedReinsert	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData,
		std::vector< NODE * > &	aPath,
		uint32_t &	aReinsertedLevels )

inlineprivate

R*-tree forced reinsert.

Temporarily adds the new entry, then removes the REINSERT_COUNT entries farthest from the node center, and reinserts them.

Definition at line 841 of file dynamic_rtree.h.

◆ freeNode()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::freeNode ( NODE * aNode )

inlineprivate

Definition at line 685 of file dynamic_rtree.h.

◆ Insert()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Insert	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData )

inline

Insert an item with the given bounding box.

Definition at line 115 of file dynamic_rtree.h.

◆ insertImpl()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::insertImpl	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData,
		uint32_t &	aReinsertedLevels )

inlineprivate

Core insertion with forced reinsert tracking.

Definition at line 707 of file dynamic_rtree.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::Insert().

◆ MemoryUsage()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

size_t KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::MemoryUsage ( ) const

inline

Return approximate memory usage in bytes.

Definition at line 357 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

◆ minDistSq()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

int64_t KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::minDistSq	(	NODE *	aNode,
		int	aSlot,
		const ELEMTYPE	aPoint[NUMDIMS] ) const

inlineprivate

Compute minimum squared distance from a point to a child's bounding box.

Definition at line 1780 of file dynamic_rtree.h.

◆ NearestNeighbors()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::NearestNeighbors	(	const ELEMTYPE	aPoint[NUMDIMS],
		int	aK,
		std::vector< std::pair< int64_t, DATATYPE > > &	aResults ) const

inline

Nearest-neighbor search using Hjaltason & Samet's algorithm.

Parameters

aPoint	Query point coordinates
aK	Maximum number of neighbors to return
aResults	Output vector of (squared_distance, data) pairs, sorted by distance

Definition at line 621 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE().

◆ operator=() [1/2]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

DYNAMIC_RTREE & KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::operator= ( const DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES > & )

delete

◆ operator=() [2/2]

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

DYNAMIC_RTREE & KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::operator= ( DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES > && aOther )

inlinenoexcept

Definition at line 93 of file dynamic_rtree.h.

◆ overflowTreatment()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::overflowTreatment	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData,
		std::vector< NODE * > &	aPath,
		uint32_t &	aReinsertedLevels )

inlineprivate

Handle overflow: forced reinsert or split.

Definition at line 808 of file dynamic_rtree.h.

◆ Overlapping()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

SearchRange KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Overlapping	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS] ) const

inline

Return a lazy range of items overlapping the query rectangle.

More efficient than Search() when callers may break early or only need to check emptiness.

Definition at line 608 of file dynamic_rtree.h.

Referenced by EE_RTREE::EE_TYPE::EE_TYPE(), and EE_RTREE::EE_TYPE::EE_TYPE().

◆ reinsertNode()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::reinsertNode	(	NODE *	aChild,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		int	aLevel,
		uint32_t &	aReinsertedLevels )

inlineprivate

Reinsert an internal node's child at its correct level.

Definition at line 984 of file dynamic_rtree.h.

◆ reinsertOrphans()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::reinsertOrphans ( std::vector< NODE * > & aReinsertList )

inlineprivate

Reinsert all entries from orphaned underflowing nodes.

Definition at line 1690 of file dynamic_rtree.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::Remove().

◆ Remove()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

bool KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Remove	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData )

inline

Remove an item using its stored insertion bounding box.

Returns: true if the item was found and removed, false otherwise

Definition at line 137 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

◆ RemoveAll()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::RemoveAll ( )

inline

Remove all items from the tree.

Definition at line 200 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE().

◆ removeAllNodes()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::removeAllNodes ( NODE * aNode )

inlineprivate

Definition at line 690 of file dynamic_rtree.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::BulkLoad(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::operator=(), KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::RemoveAll(), and KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::~DYNAMIC_RTREE().

◆ removeImpl()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

bool KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::removeImpl	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData,
		std::vector< NODE * > &	aReinsertList )

inlineprivate

Remove an item from the tree, collecting underflowing nodes for reinsertion.

Definition at line 1631 of file dynamic_rtree.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::Remove().

◆ Search()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

template<class VISITOR>

int KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::Search	(	const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		VISITOR &	aVisitor ) const

inline

Search for items whose bounding boxes overlap the query rectangle.

Parameters

aMin	Minimum corner of query rectangle
aMax	Maximum corner of query rectangle
aVisitor	Callback invoked for each matching item. Return false to stop early.

Returns: Number of items reported to visitor

Definition at line 186 of file dynamic_rtree.h.

◆ searchImpl()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

template<class VISITOR>

bool KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::searchImpl	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		VISITOR &	aVisitor,
		int &	aFound ) const

inlineprivate

Recursive search.

Returns true if search should continue, false if visitor stopped early.

Definition at line 1745 of file dynamic_rtree.h.

Referenced by KIRTREE::DYNAMIC_RTREE< SCH_ITEM *, int, 3 >::Search().

◆ size()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

size_t KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::size ( ) const

inline

Definition at line 351 of file dynamic_rtree.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

◆ splitNode()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::splitNode	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		const DATATYPE &	aData,
		std::vector< NODE * > &	aPath,
		uint32_t &	aReinsertedLevels )

inlineprivate

R*-tree split.

ChooseSplitAxis: for each axis, sort by min then max. Choose axis minimizing sum of perimeters across all valid distributions.

ChooseSplitIndex: along chosen axis, choose distribution minimizing overlap.

Definition at line 1052 of file dynamic_rtree.h.

◆ splitNodeInternal()

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

void KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::splitNodeInternal	(	NODE *	aNode,
		const ELEMTYPE	aMin[NUMDIMS],
		const ELEMTYPE	aMax[NUMDIMS],
		NODE *	aChild,
		std::vector< NODE * > &	aPath,
		uint32_t &	aReinsertedLevels )

inlineprivate

Split an internal node to insert a new child.

Definition at line 1258 of file dynamic_rtree.h.

Member Data Documentation

◆ m_allocator

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

SLAB_ALLOCATOR<NODE> KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::m_allocator

private

Definition at line 1806 of file dynamic_rtree.h.

◆ m_count

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

size_t KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::m_count = 0

private

Definition at line 1805 of file dynamic_rtree.h.

◆ m_root

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

NODE* KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::m_root = nullptr

private

Definition at line 1804 of file dynamic_rtree.h.

◆ MAXNODES

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

int KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::MAXNODES = TMAXNODES

staticconstexpr

Definition at line 68 of file dynamic_rtree.h.

◆ MINNODES

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

int KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::MINNODES = NODE::MINNODES

staticconstexpr

Definition at line 69 of file dynamic_rtree.h.

◆ REINSERT_COUNT

template<class DATATYPE, class ELEMTYPE = int, int NUMDIMS = 2, int TMAXNODES = 16>

int KIRTREE::DYNAMIC_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, TMAXNODES >::REINSERT_COUNT = MAXNODES * 3 / 10

staticconstexpr

Definition at line 72 of file dynamic_rtree.h.

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

dynamic_rtree.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ NODE

Constructor & Destructor Documentation

◆ DYNAMIC_RTREE() [1/3]

◆ ~DYNAMIC_RTREE()

◆ DYNAMIC_RTREE() [2/3]

◆ DYNAMIC_RTREE() [3/3]

Member Function Documentation

◆ adjustPath()

◆ allocNode()

◆ begin()

◆ BulkLoad()

◆ chooseSubtree()

◆ chooseSubtreeAtLevel()

◆ computeOverlap()

◆ computeOverlapEnlarged()

◆ computeSplitOverlap()

◆ computeSplitPerimeters()

◆ condenseRoot()

◆ empty()

◆ end()

◆ findBestSplitIndex()

◆ findChildSlot()

◆ forcedReinsert()

◆ freeNode()

◆ Insert()

◆ insertImpl()

◆ MemoryUsage()

◆ minDistSq()

◆ NearestNeighbors()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ overflowTreatment()

◆ Overlapping()

◆ reinsertNode()

◆ reinsertOrphans()

◆ Remove()

◆ RemoveAll()

◆ removeAllNodes()

◆ removeImpl()

◆ Search()

◆ searchImpl()

◆ size()

◆ splitNode()

◆ splitNodeInternal()

Member Data Documentation

◆ m_allocator

◆ m_count

◆ m_root

◆ MAXNODES

◆ MINNODES

◆ REINSERT_COUNT