Menge::Agents::ObstacleKDTree Class Reference

Defines an obstacle kd-tree. More...

#include <ObstacleKDTree.h>

Public Member Functions
	ObstacleKDTree ()
	Constructs an Obstacle kd-tree instance.
	~ObstacleKDTree ()
	Destroys this kd-tree instance.
void	buildTree (const std::vector< Obstacle * > obstacles)
	Builds an obstacle kd-tree on the given set of obstacles.
void	obstacleQuery (ProximityQuery *query) const
	Computes the obstacles within range square of a point. More...
bool	queryVisibility (const Vector2 &q1, const Vector2 &q2, float radius) const
	Queries the visibility between two points within a specified radius. More...

Protected Member Functions
ObstacleTreeNode *	buildTreeRecursive (const std::vector< Obstacle * > &obstacles)
	Does the full work of constructing the kd-tree. More...
void	queryTreeRecursive (ProximityQuery *query, Vector2 pt, float &rangeSq, const ObstacleTreeNode *node) const
	Computes the obstacle neighbors of the specified point by doing a recursive search. More...
bool	queryVisibilityRecursive (const Vector2 &q1, const Vector2 &q2, float radius, const ObstacleTreeNode *node) const
	Perform the work, recursively, to determine if q1 can see q2, w.r.t. the obstacles. More...
void	deleteTree ()
	Recursively deletes the obstacle tree.
void	deleteSubTree (ObstacleTreeNode *node)
	Recursively deletes an obstacle sub-tree. More...

Protected Attributes
std::vector< Obstacle * >	_obstacles
	The set of obstacles managed by this query structure. More...
ObstacleTreeNode *	_tree
	The query tree root.

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

Detailed Description

Defines an obstacle kd-tree.

This structure will create a static kd-tree node on the provided set of obstacles. It will modify the obstacles in that some obstacles may be cut.

Member Function Documentation

ObstacleTreeNode * Menge::Agents::ObstacleKDTree::buildTreeRecursive ( const std::vector< Obstacle * > &  obstacles )

protected

Does the full work of constructing the kd-tree.

Parameters

obstacles

The set of obstacles to construct this tree around

Returns

The root of the ObstacleKDTree for this set of obstacles

void Menge::Agents::ObstacleKDTree::deleteSubTree ( ObstacleTreeNode *  node )

protected

Recursively deletes an obstacle sub-tree.

Parameters

node	The root of the tree to delete.

void Menge::Agents::ObstacleKDTree::obstacleQuery

(

ProximityQuery *

query

)

const

Computes the obstacles within range square of a point.

Parameters

query

a pointer for the query to be performed

void Menge::Agents::ObstacleKDTree::queryTreeRecursive ( ProximityQuery *  query, Vector2  pt, float &  rangeSq, const ObstacleTreeNode *  node  ) const

protected

Computes the obstacle neighbors of the specified point by doing a recursive search.

Parameters

query	a pointer to the query being performed.
pt	the starting point from the query
rangeSq	The squared range around the agent.
node	The current node in the obstacle tree

bool Menge::Agents::ObstacleKDTree::queryVisibility	(	const Vector2 &	q1,
		const Vector2 &	q2,
		float	radius
	)		const

Queries the visibility between two points within a specified radius.

Parameters

q1	The first point between which visibility is to be tested.
q2	The second point between which visibility is to be tested.
radius	The radius within which visibility is to be tested.

Returns

True if q1 and q2 are mutually visible within the radius; false otherwise.

bool Menge::Agents::ObstacleKDTree::queryVisibilityRecursive ( const Vector2 &  q1, const Vector2 &  q2, float  radius, const ObstacleTreeNode *  node  ) const

protected

Perform the work, recursively, to determine if q1 can see q2, w.r.t. the obstacles.

Parameters

q1	The originating position.
q2	The target position.
radius	The radius within which visibility is to be tested.
node	The root of the tree to recursively search.

Returns

True if q1 and q2 are mutually visible within the radius, false otherwise.

Member Data Documentation

std::vector<Obstacle*> Menge::Agents::ObstacleKDTree::_obstacles

protected

The set of obstacles managed by this query structure.

This is not necessarily the same as the obstacles assigned. The set of obstacles can change as some obstacles may be sub-divided during the spatial decomposition. This needs to be corrected.

---

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

• src/menge/MengeCore/Agents/SpatialQueries/ObstacleKDTree.h
• src/menge/MengeCore/Agents/SpatialQueries/ObstacleKDTree.cpp