Menge
Modular Pedestrian Simulation Framework for Research and Development
|
A kd-tree for performing nearest-neighbor searches. More...
#include <AgentKDTree.h>
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. | |
A kd-tree for performing nearest-neighbor searches.
The agents are partitioned according to a greedy partitioning algorithm.
void Menge::Agents::AgentKDTree::agentQuery | ( | ProximityQuery * | filter | ) | const |
gets agents within a range, and passes them to the supplied filter
filter | a pointer for the filter object |
|
protected |
Does the full work of constructing the kd-tree.
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. |
|
protected |
Computes the agent neighbors of the specified agent by doing a recursive search.
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. |