K-dimensional tree, specialised for 2-dimensional space. More...

#include <kdtree.hpp>

Data Structures
struct	node
	Type of a node in the tree. More...

Public Member Functions
	Kdtree ()
	Construct a new Kdtree with the given xyfunc.

template<typename It >
void	Build (It begin, It end)
	Clear and rebuild the tree from a new sequence of elements,.

void	Clear ()
	Clear the tree.

void	Rebuild ()
	Reconstruct the tree with the same elements, letting it be fully balanced.

void	Insert (const T &element)
	Insert a single element in the tree.

void	Remove (const T &element)
	Remove a single element from the tree, if it exists.

size_t	Count () const
	Get number of elements stored in tree.

T	FindNearest (CoordT x, CoordT y) const
	Find the element closest to given coordinate, in Manhattan distance.

template<typename Outputter >
void	FindContained (CoordT x1, CoordT y1, CoordT x2, CoordT y2, const Outputter &outputter) const
	Find all items contained within the given rectangle.

std::vector< T >	FindContained (CoordT x1, CoordT y1, CoordT x2, CoordT y2) const
	Find all items contained within the given rectangle.

Private Types
using	node_distance = std::pair< T, DistT >
	A data element and its distance to a searched-for point.

Private Member Functions
size_t	AddNode (const T &element)
	Create one new node in the tree, return its index in the pool.

template<typename It >
CoordT	SelectSplitCoord (It begin, It end, int level)
	Find a coordinate value to split a range of elements at.

template<typename It >
size_t	BuildSubtree (It begin, It end, int level)
	Construct a subtree from elements between begin and end iterators, return index of root.

bool	Rebuild (const T include_element, const T exclude_element)
	Rebuild the tree with all existing elements, optionally adding or removing one more.

void	InsertRecursive (const T &element, size_t node_idx, int level)
	Insert one element in the tree somewhere below node_idx.

std::vector< T >	FreeSubtree (size_t node_idx)
	Free all children of the given node.

size_t	RemoveRecursive (const T &element, size_t node_idx, int level)
	Find and remove one element from the tree.

DistT	ManhattanDistance (const T &element, CoordT x, CoordT y) const

node_distance	FindNearestRecursive (CoordT xy[2], size_t node_idx, int level, DistT limit=std::numeric_limits< DistT >::max()) const
	Search a sub-tree for the element nearest to a given point.

template<typename Outputter >
void	FindContainedRecursive (CoordT p1[2], CoordT p2[2], size_t node_idx, int level, const Outputter &outputter) const

size_t	CountValue (const T &element, size_t node_idx) const
	Debugging function, counts number of occurrences of an element regardless of its correct position in the tree.

void	IncrementUnbalanced (size_t amount=1)

bool	IsUnbalanced () const
	Check if the entire tree is in need of rebuilding.

void	CheckInvariant (size_t node_idx, int level, CoordT min_x, CoordT max_x, CoordT min_y, CoordT max_y) const
	Verify that the invariant is true for a sub-tree, assert if not.

void	CheckInvariant () const
	Verify the invariant for the entire tree, does nothing unless KDTREE_DEBUG is defined.

Static Private Member Functions
static node_distance	SelectNearestNodeDistance (const node_distance &a, const node_distance &b)
	Ordering function for node_distance objects, elements with equal distance are ordered by less-than comparison.

Private Attributes
std::vector< node >	nodes
	Pool of all nodes in the tree.

std::vector< size_t >	free_list
	List of dead indices in the nodes vector.

size_t	root
	Index of root node.

size_t	unbalanced
	Number approximating how unbalanced the tree might be.

Static Private Attributes
static const size_t	INVALID_NODE = SIZE_MAX
	Index value indicating no-such-node.

static const size_t	MIN_REBALANCE_THRESHOLD = 8
	Arbitrary value for "not worth rebalancing".

Detailed Description

template<typename T, typename TxyFunc, typename CoordT, typename DistT>
class Kdtree< T, TxyFunc, CoordT, DistT >

K-dimensional tree, specialised for 2-dimensional space.

This is not intended as a primary storage of data, but as an index into existing data. Usually the type stored by this tree should be an index into an existing array.

This implementation assumes Manhattan distances are used.

Be careful when using this in game code, depending on usage pattern, the tree shape may end up different for different clients in multiplayer, causing iteration order to differ and possibly having elements returned in different order. The using code should be designed to produce the same result regardless of iteration order.

The element type T must be less-than comparable for FindNearest to work.

Template Parameters

T	Type stored in the tree, should be cheap to copy.
TxyFunc	Functor type to extract coordinate from a T value and dimension index (0 or 1).
CoordT	Type of coordinate values extracted via TxyFunc.
DistT	Type to use for representing distance values.

Definition at line 35 of file kdtree.hpp.

Member Typedef Documentation

◆ node_distance

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

using Kdtree< T, TxyFunc, CoordT, DistT >::node_distance = std::pair<T, DistT>

private

A data element and its distance to a searched-for point.

Definition at line 229 of file kdtree.hpp.

Constructor & Destructor Documentation

◆ Kdtree()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

Kdtree< T, TxyFunc, CoordT, DistT >::Kdtree ( )

inline

Construct a new Kdtree with the given xyfunc.

Definition at line 353 of file kdtree.hpp.

Member Function Documentation

◆ AddNode()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

size_t Kdtree< T, TxyFunc, CoordT, DistT >::AddNode ( const T & element )

inlineprivate

Create one new node in the tree, return its index in the pool.

Definition at line 54 of file kdtree.hpp.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::BuildSubtree(), Kdtree< T, TxyFunc, CoordT, DistT >::Insert(), and Kdtree< T, TxyFunc, CoordT, DistT >::InsertRecursive().

◆ Build()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

template<typename It >

void Kdtree< T, TxyFunc, CoordT, DistT >::Build	(	It	begin,
		It	end
	)

inline

Clear and rebuild the tree from a new sequence of elements,.

Template Parameters

It	Iterator type for element sequence.

Parameters

begin	First element in sequence.
end	One past last element in sequence.

Definition at line 362 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::BuildSubtree(), and Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant().

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild().

◆ BuildSubtree()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

template<typename It >

size_t Kdtree< T, TxyFunc, CoordT, DistT >::BuildSubtree	(	It	begin,
		It	end,
		int	level
	)

inlineprivate

Construct a subtree from elements between begin and end iterators, return index of root.

Definition at line 78 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::AddNode(), Kdtree< T, TxyFunc, CoordT, DistT >::BuildSubtree(), Kdtree< T, TxyFunc, CoordT, DistT >::INVALID_NODE, and Kdtree< T, TxyFunc, CoordT, DistT >::SelectSplitCoord().

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Build(), Kdtree< T, TxyFunc, CoordT, DistT >::BuildSubtree(), and Kdtree< T, TxyFunc, CoordT, DistT >::RemoveRecursive().

◆ CheckInvariant() [1/2]

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

void Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant ( ) const

inlineprivate

Verify the invariant for the entire tree, does nothing unless KDTREE_DEBUG is defined.

Definition at line 344 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant().

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Build(), Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant(), Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant(), Kdtree< T, TxyFunc, CoordT, DistT >::Insert(), and Kdtree< T, TxyFunc, CoordT, DistT >::Remove().

◆ CheckInvariant() [2/2]

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

void Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant	(	size_t	node_idx,
		int	level,
		CoordT	min_x,
		CoordT	max_x,
		CoordT	min_y,
		CoordT	max_y
	)		const

inlineprivate

Verify that the invariant is true for a sub-tree, assert if not.

Definition at line 319 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant(), Kdtree< T, TxyFunc, CoordT, DistT >::node::element, Kdtree< T, TxyFunc, CoordT, DistT >::INVALID_NODE, Kdtree< T, TxyFunc, CoordT, DistT >::node::left, and Kdtree< T, TxyFunc, CoordT, DistT >::node::right.

◆ Clear()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

void Kdtree< T, TxyFunc, CoordT, DistT >::Clear ( )

inline

Clear the tree.

Definition at line 377 of file kdtree.hpp.

◆ Count()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

size_t Kdtree< T, TxyFunc, CoordT, DistT >::Count ( ) const

inline

Get number of elements stored in tree.

Definition at line 430 of file kdtree.hpp.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::FindContained(), Kdtree< T, TxyFunc, CoordT, DistT >::FindNearest(), HighlightTownLocalAuthorityTiles(), Kdtree< T, TxyFunc, CoordT, DistT >::Insert(), IsCloseToTown(), Kdtree< T, TxyFunc, CoordT, DistT >::IsUnbalanced(), Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild(), and Kdtree< T, TxyFunc, CoordT, DistT >::Remove().

◆ CountValue()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

size_t Kdtree< T, TxyFunc, CoordT, DistT >::CountValue	(	const T &	element,
		size_t	node_idx
	)		const

inlineprivate

Debugging function, counts number of occurrences of an element regardless of its correct position in the tree.

Definition at line 298 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::CountValue(), Kdtree< T, TxyFunc, CoordT, DistT >::node::element, Kdtree< T, TxyFunc, CoordT, DistT >::INVALID_NODE, Kdtree< T, TxyFunc, CoordT, DistT >::node::left, and Kdtree< T, TxyFunc, CoordT, DistT >::node::right.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::CountValue().

◆ FindContained() [1/2]

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

std::vector< T > Kdtree< T, TxyFunc, CoordT, DistT >::FindContained	(	CoordT	x1,
		CoordT	y1,
		CoordT	x2,
		CoordT	y2
	)		const

inline

Find all items contained within the given rectangle.

Note: End coordinates are exclusive, x1<x2 && y1<y2 is a precondition.

Definition at line 475 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::FindContained().

◆ FindContained() [2/2]

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

template<typename Outputter >

void Kdtree< T, TxyFunc, CoordT, DistT >::FindContained	(	CoordT	x1,
		CoordT	y1,
		CoordT	x2,
		CoordT	y2,
		const Outputter &	outputter
	)		const

inline

Find all items contained within the given rectangle.

Note: Start coordinates are inclusive, end coordinates are exclusive. x1<x2 && y1<y2 is a precondition.

Parameters

x1	Start first coordinate, points found are greater or equals to this.
y1	Start second coordinate, points found are greater or equals to this.
x2	End first coordinate, points found are less than this.
y2	End second coordinate, points found are less than this.
outputter	Callback used to return values from the search.

Definition at line 459 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::Count().

Referenced by CheckClickOnViewportSign(), Kdtree< T, TxyFunc, CoordT, DistT >::FindContained(), and ForAllStationsRadius().

◆ FindContainedRecursive()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

template<typename Outputter >

void Kdtree< T, TxyFunc, CoordT, DistT >::FindContainedRecursive	(	CoordT	p1[2],
		CoordT	p2[2],
		size_t	node_idx,
		int	level,
		const Outputter &	outputter
	)		const

inlineprivate

Definition at line 275 of file kdtree.hpp.

◆ FindNearest()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

T Kdtree< T, TxyFunc, CoordT, DistT >::FindNearest	(	CoordT	x,
		CoordT	y
	)		const

inline

Find the element closest to given coordinate, in Manhattan distance.

For multiple elements with the same distance, the one comparing smaller with a less-than comparison is chosen.

Definition at line 441 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::Count(), and Kdtree< T, TxyFunc, CoordT, DistT >::FindNearestRecursive().

Referenced by CalcClosestTownFromTile(), HighlightTownLocalAuthorityTiles(), and IsCloseToTown().

◆ FindNearestRecursive()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

node_distance Kdtree< T, TxyFunc, CoordT, DistT >::FindNearestRecursive	(	CoordT	xy[2],
		size_t	node_idx,
		int	level,
		DistT	limit = `std::numeric_limits<DistT>::max()`
	)		const

inlineprivate

Search a sub-tree for the element nearest to a given point.

Definition at line 240 of file kdtree.hpp.

References abs(), Kdtree< T, TxyFunc, CoordT, DistT >::node::element, Kdtree< T, TxyFunc, CoordT, DistT >::FindNearestRecursive(), Kdtree< T, TxyFunc, CoordT, DistT >::INVALID_NODE, Kdtree< T, TxyFunc, CoordT, DistT >::node::left, Kdtree< T, TxyFunc, CoordT, DistT >::node::right, and Kdtree< T, TxyFunc, CoordT, DistT >::SelectNearestNodeDistance().

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::FindNearest(), and Kdtree< T, TxyFunc, CoordT, DistT >::FindNearestRecursive().

◆ FreeSubtree()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

std::vector< T > Kdtree< T, TxyFunc, CoordT, DistT >::FreeSubtree ( size_t node_idx )

inlineprivate

Free all children of the given node.

Returns: Collection of elements that were removed from tree.

Definition at line 153 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::node::element, Kdtree< T, TxyFunc, CoordT, DistT >::INVALID_NODE, Kdtree< T, TxyFunc, CoordT, DistT >::node::left, and Kdtree< T, TxyFunc, CoordT, DistT >::node::right.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild(), and Kdtree< T, TxyFunc, CoordT, DistT >::RemoveRecursive().

◆ IncrementUnbalanced()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

void Kdtree< T, TxyFunc, CoordT, DistT >::IncrementUnbalanced ( size_t amount = 1 )

inlineprivate

Definition at line 305 of file kdtree.hpp.

◆ Insert()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

void Kdtree< T, TxyFunc, CoordT, DistT >::Insert ( const T & element )

inline

Insert a single element in the tree.

Repeatedly inserting single elements may cause the tree to become unbalanced. Undefined behaviour if the element already exists in the tree.

Definition at line 398 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::AddNode(), Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant(), Kdtree< T, TxyFunc, CoordT, DistT >::Count(), Kdtree< T, TxyFunc, CoordT, DistT >::InsertRecursive(), Kdtree< T, TxyFunc, CoordT, DistT >::IsUnbalanced(), and Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild().

Referenced by BuildStationPart(), DoCreateTown(), Station::MoveSign(), TownAuthorityWindow::OnClick(), Sign::UpdateVirtCoord(), Town::UpdateVirtCoord(), Station::UpdateVirtCoord(), and Waypoint::UpdateVirtCoord().

◆ InsertRecursive()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

void Kdtree< T, TxyFunc, CoordT, DistT >::InsertRecursive	(	const T &	element,
		size_t	node_idx,
		int	level
	)

inlineprivate

Insert one element in the tree somewhere below node_idx.

Definition at line 124 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::AddNode(), Kdtree< T, TxyFunc, CoordT, DistT >::node::element, Kdtree< T, TxyFunc, CoordT, DistT >::InsertRecursive(), Kdtree< T, TxyFunc, CoordT, DistT >::INVALID_NODE, Kdtree< T, TxyFunc, CoordT, DistT >::node::left, and Kdtree< T, TxyFunc, CoordT, DistT >::node::right.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Insert(), and Kdtree< T, TxyFunc, CoordT, DistT >::InsertRecursive().

◆ IsUnbalanced()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

bool Kdtree< T, TxyFunc, CoordT, DistT >::IsUnbalanced ( ) const

inlineprivate

Check if the entire tree is in need of rebuilding.

Definition at line 311 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::Count(), and Kdtree< T, TxyFunc, CoordT, DistT >::MIN_REBALANCE_THRESHOLD.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Insert(), and Kdtree< T, TxyFunc, CoordT, DistT >::Remove().

◆ ManhattanDistance()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

DistT Kdtree< T, TxyFunc, CoordT, DistT >::ManhattanDistance	(	const T &	element,
		CoordT	x,
		CoordT	y
	)		const

inlineprivate

Definition at line 223 of file kdtree.hpp.

◆ Rebuild() [1/2]

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

void Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild ( )

inline

Reconstruct the tree with the same elements, letting it be fully balanced.

Definition at line 388 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild().

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Insert(), Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild(), and Kdtree< T, TxyFunc, CoordT, DistT >::Remove().

◆ Rebuild() [2/2]

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

bool Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild	(	const T *	include_element,
		const T *	exclude_element
	)

inlineprivate

Rebuild the tree with all existing elements, optionally adding or removing one more.

Definition at line 99 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::Build(), Kdtree< T, TxyFunc, CoordT, DistT >::Count(), Kdtree< T, TxyFunc, CoordT, DistT >::FreeSubtree(), Kdtree< T, TxyFunc, CoordT, DistT >::MIN_REBALANCE_THRESHOLD, and Kdtree< T, TxyFunc, CoordT, DistT >::root.

◆ Remove()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

void Kdtree< T, TxyFunc, CoordT, DistT >::Remove ( const T & element )

inline

Remove a single element from the tree, if it exists.

Since elements are stored in interior nodes as well as leaf nodes, removing one may require a larger sub-tree to be re-built. Because of this, worst case run time is as bad as a full tree rebuild.

Definition at line 417 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant(), Kdtree< T, TxyFunc, CoordT, DistT >::Count(), Kdtree< T, TxyFunc, CoordT, DistT >::IsUnbalanced(), Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild(), and Kdtree< T, TxyFunc, CoordT, DistT >::RemoveRecursive().

Referenced by CmdDeleteTown(), CmdRenameSign(), Station::MoveSign(), TownAuthorityWindow::OnClick(), Sign::UpdateVirtCoord(), Town::UpdateVirtCoord(), Station::UpdateVirtCoord(), Waypoint::UpdateVirtCoord(), and Station::~Station().

◆ RemoveRecursive()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

size_t Kdtree< T, TxyFunc, CoordT, DistT >::RemoveRecursive	(	const T &	element,
		size_t	node_idx,
		int	level
	)

inlineprivate

Find and remove one element from the tree.

Parameters

element	The element to search for
node_idx	Sub-tree to search in
level	Current depth in the tree

Returns: New root node index of the sub-tree processed

Definition at line 184 of file kdtree.hpp.

References Kdtree< T, TxyFunc, CoordT, DistT >::BuildSubtree(), Kdtree< T, TxyFunc, CoordT, DistT >::node::element, Kdtree< T, TxyFunc, CoordT, DistT >::FreeSubtree(), Kdtree< T, TxyFunc, CoordT, DistT >::INVALID_NODE, Kdtree< T, TxyFunc, CoordT, DistT >::node::left, Kdtree< T, TxyFunc, CoordT, DistT >::RemoveRecursive(), and Kdtree< T, TxyFunc, CoordT, DistT >::node::right.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Remove(), and Kdtree< T, TxyFunc, CoordT, DistT >::RemoveRecursive().

◆ SelectNearestNodeDistance()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

static node_distance Kdtree< T, TxyFunc, CoordT, DistT >::SelectNearestNodeDistance	(	const node_distance &	a,
		const node_distance &	b
	)

inlinestaticprivate

Ordering function for node_distance objects, elements with equal distance are ordered by less-than comparison.

Definition at line 231 of file kdtree.hpp.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::FindNearestRecursive().

◆ SelectSplitCoord()

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

template<typename It >

CoordT Kdtree< T, TxyFunc, CoordT, DistT >::SelectSplitCoord	(	It	begin,
		It	end,
		int	level
	)

inlineprivate

Find a coordinate value to split a range of elements at.

Definition at line 69 of file kdtree.hpp.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::BuildSubtree().

Field Documentation

◆ free_list

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

std::vector<size_t> Kdtree< T, TxyFunc, CoordT, DistT >::free_list

private

List of dead indices in the nodes vector.

Definition at line 49 of file kdtree.hpp.

◆ INVALID_NODE

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

const size_t Kdtree< T, TxyFunc, CoordT, DistT >::INVALID_NODE = SIZE_MAX

staticprivate

Index value indicating no-such-node.

Definition at line 45 of file kdtree.hpp.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::BuildSubtree(), Kdtree< T, TxyFunc, CoordT, DistT >::CheckInvariant(), Kdtree< T, TxyFunc, CoordT, DistT >::CountValue(), Kdtree< T, TxyFunc, CoordT, DistT >::FindNearestRecursive(), Kdtree< T, TxyFunc, CoordT, DistT >::FreeSubtree(), Kdtree< T, TxyFunc, CoordT, DistT >::InsertRecursive(), and Kdtree< T, TxyFunc, CoordT, DistT >::RemoveRecursive().

◆ MIN_REBALANCE_THRESHOLD

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

const size_t Kdtree< T, TxyFunc, CoordT, DistT >::MIN_REBALANCE_THRESHOLD = 8

staticprivate

Arbitrary value for "not worth rebalancing".

Definition at line 46 of file kdtree.hpp.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::IsUnbalanced(), and Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild().

◆ nodes

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

std::vector<node> Kdtree< T, TxyFunc, CoordT, DistT >::nodes

private

Pool of all nodes in the tree.

Definition at line 48 of file kdtree.hpp.

◆ root

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

size_t Kdtree< T, TxyFunc, CoordT, DistT >::root

private

Index of root node.

Definition at line 50 of file kdtree.hpp.

Referenced by Kdtree< T, TxyFunc, CoordT, DistT >::Rebuild().

◆ unbalanced

template<typename T , typename TxyFunc , typename CoordT , typename DistT >

size_t Kdtree< T, TxyFunc, CoordT, DistT >::unbalanced

private

Number approximating how unbalanced the tree might be.

Definition at line 51 of file kdtree.hpp.

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

src/core/kdtree.hpp

Data Structures

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ node_distance

Constructor & Destructor Documentation

◆ Kdtree()

Member Function Documentation

◆ AddNode()

◆ Build()

◆ BuildSubtree()

◆ CheckInvariant() [1/2]

◆ CheckInvariant() [2/2]

◆ Clear()

◆ Count()

◆ CountValue()

◆ FindContained() [1/2]

◆ FindContained() [2/2]

◆ FindContainedRecursive()

◆ FindNearest()

◆ FindNearestRecursive()

◆ FreeSubtree()

◆ IncrementUnbalanced()

◆ Insert()

◆ InsertRecursive()

◆ IsUnbalanced()

◆ ManhattanDistance()

◆ Rebuild() [1/2]

◆ Rebuild() [2/2]

◆ Remove()

◆ RemoveRecursive()

◆ SelectNearestNodeDistance()

◆ SelectSplitCoord()

Field Documentation

◆ free_list

◆ INVALID_NODE

◆ MIN_REBALANCE_THRESHOLD

◆ nodes

◆ root

◆ unbalanced