-
Notifications
You must be signed in to change notification settings - Fork 15
KDTree SpatialDatabase
The KDTree spacial database is used to keep track of the spatial locations of items in the environment. It is a structure to facilitate fast spatial queries in the simulation. A k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space (Wikipedia, 2015).
The KDTree is not a dynamic structure on its own. After any point in the spatial database moves the database will need to be updated. This is done through two functions:
buildObstacleTree()
buildAgentTree()
buildObstacleTree() tree should be called after all of the obstacles are added to the scenario. If more obstacle are added at any point of if the obstacle move in any way then this method will need to be called more often. buildAgentTree() is called every frame as it is expected all of the agent will change their positions on every update.
Because KdTree only supports points the agents in the simulation are represented as points in this spatial database. Also because only points are possible in this data structure Obstacles are represented as single points with possible neighbours (next, previous) that can be used to construct lines. Typically a PolygonObstacle is used to represent a list of linked Obstacles that can be easily added to the database.
- This method needs to be paired with some other path planning method.