Menge
Modular Pedestrian Simulation Framework for Research and Development
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
ObstacleKDTree.h
Go to the documentation of this file.
1 /*
2 
3 License
4 
5 Menge
6 Copyright and trademark 2012-14 University of North Carolina at Chapel Hill.
7 All rights reserved.
8 
9 Permission to use, copy, modify, and distribute this software and its documentation
10 for educational, research, and non-profit purposes, without fee, and without a
11 written agreement is hereby granted, provided that the above copyright notice,
12 this paragraph, and the following four paragraphs appear in all copies.
13 
14 This software program and documentation are copyrighted by the University of North
15 Carolina at Chapel Hill. The software program and documentation are supplied "as is,"
16 without any accompanying services from the University of North Carolina at Chapel
17 Hill or the authors. The University of North Carolina at Chapel Hill and the
18 authors do not warrant that the operation of the program will be uninterrupted
19 or error-free. The end-user understands that the program was developed for research
20 purposes and is advised not to rely exclusively on the program for any reason.
21 
22 IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL OR THE AUTHORS
23 BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
24 DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
25 DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL OR THE
26 AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL AND THE AUTHORS SPECIFICALLY
29 DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
30 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE AND ANY STATUTORY WARRANTY
31 OF NON-INFRINGEMENT. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND
32 THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL AND THE AUTHORS HAVE NO OBLIGATIONS
33 TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
34 
35 Any questions or comments should be sent to the authors {menge,geom}@cs.unc.edu
36 
37 */
38 
39 #ifndef __OBSTACLE_KD_TREE_H__
40 #define __OBSTACLE_KD_TREE_H__
41 
48 // STL
49 #include <vector>
50 
51 // PedModels
52 #include "CoreConfig.h"
53 #include "Obstacle.h"
55 
56 namespace Menge {
57 
58  namespace Agents {
59 
60  // FORWARD DECLARATIONS
61  class BaseAgent;
62 
63  // Forward declarations
64 
65  // TODO: This chops up obstacles for the kd-tree. I need to be able to reconstruct them
66  // i.e. if a piece is close to the agent, I'd like to be able to provide the full
67  // original line obstacle.
68 
77 
82 
87  };
88 
96  class MENGE_API ObstacleKDTree {
97  public:
101  explicit ObstacleKDTree();
102 
106  ~ObstacleKDTree();
107 
111  void buildTree( const std::vector< Obstacle * > obstacles );
112 
118  void obstacleQuery( ProximityQuery *query) const;
119 
133  bool queryVisibility(const Vector2& q1, const Vector2& q2, float radius) const;
134 
135  protected:
142  ObstacleTreeNode* buildTreeRecursive( const std::vector<Obstacle*>& obstacles );
143 
154  void queryTreeRecursive( ProximityQuery *query, Vector2 pt, float& rangeSq, const ObstacleTreeNode* node) const;
155 
165  bool queryVisibilityRecursive(const Vector2& q1, const Vector2& q2,
166  float radius,
167  const ObstacleTreeNode* node) const;
168 
172  void deleteTree();
173 
178  void deleteSubTree( ObstacleTreeNode * node );
179 
187  std::vector<Obstacle*> _obstacles;
188 
193 
197  static const size_t MAX_LEAF_SIZE = 10;
198  };
199  } // namespace Agents
200 } // namespace Menge
201 
202 #endif // __OBSTACLE_KD_TREE_H__
The core namespace. All elements of Menge are contained in this namespace.
Definition: AgentGenerator.cpp:43
Contains the Obstacle class.
Sets up the proper compiler directives for platform and dll export/import.
Defines an obstacle kd-tree.
Definition: ObstacleKDTree.h:96
ObstacleTreeNode * _right
The right obstacle tree node.
Definition: ObstacleKDTree.h:86
ObstacleTreeNode * _left
The left obstacle tree node.
Definition: ObstacleKDTree.h:76
The base class for filtering spatial queries according to proximity.
Definition: ProximityQuery.h:72
std::vector< Obstacle * > _obstacles
The set of obstacles managed by this query structure.
Definition: ObstacleKDTree.h:187
ObstacleTreeNode * _tree
The query tree root.
Definition: ObstacleKDTree.h:192
Defines static obstacles in the simulation.
Definition: Obstacle.h:56
The base class for all objects which actually perform filtering and store results from spatial querie...
Defines an obstacle kd-tree node.
Definition: ObstacleKDTree.h:72
The namespace that contains the basic simulation mechanisms.
const Obstacle * _obstacle
The obstacle number.
Definition: ObstacleKDTree.h:81