A kd-tree for performing nearest-neighbor searches. More...

Public Member Functions
	AgentKDTree ()
	Constructs an Agent kd-tree instance.

void	setAgents (const std::vector< BaseAgent * > &agents)
	Define the set of agents on which kd-tree will query.

void	buildTree ()
	Builds a kd-tree on the set of agents.

void	agentQuery (ProximityQuery *filter) const
	gets agents within a range, and passes them to the supplied filter More...

Protected Member Functions
void	buildTreeRecursive (size_t begin, size_t end, size_t node)
	Does the full work of constructing the kd-tree. More...

void	queryTreeRecursive (ProximityQuery *filter, Vector2 pt, float &rangeSq, size_t node) const
	Computes the agent neighbors of the specified agent by doing a recursive search. More...

Protected Attributes
std::vector< const BaseAgent * >	_agents
	The agents being partitioned by the kd-tree.

std::vector< AgentTreeNode >	_tree
	The tree structure.

Static Protected Attributes
static const size_t	MAX_LEAF_SIZE = 10
	The maximum number of agents allowed in a tree leaf node.

Detailed Description

A kd-tree for performing nearest-neighbor searches.

The agents are partitioned according to a greedy partitioning algorithm.

Member Function Documentation

void Menge::Agents::AgentKDTree::agentQuery ( ProximityQuery * filter ) const

gets agents within a range, and passes them to the supplied filter

Parameters

filter a pointer for the filter object

void Menge::Agents::AgentKDTree::buildTreeRecursive	(	size_t	begin,
		size_t	end,
		size_t	node
	)

protected

Does the full work of constructing the kd-tree.

Parameters

begin	The index of the first agent in the region of the tree.
end	The index of the last (just outside). So, the agents in this branch are in the interval [begin, end)
node	The index of the node to build.

void Menge::Agents::AgentKDTree::queryTreeRecursive	(	ProximityQuery *	filter,
		Vector2	pt,
		float &	rangeSq,
		size_t	node
	)		const

protected

Computes the agent neighbors of the specified agent by doing a recursive search.

Parameters

filter	spatial query filter to use
pt	the start point for the query
rangeSq	The squared range around the agent.
node	The current node to search in.

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