2 * PositionedOctree - define a spatial octree containing Positioned items
3 * arranged by their global cartesian position.
6 // Written by James Turner, started 2012.
8 // Copyright (C) 2012 James Turner
10 // This program is free software; you can redistribute it and/or
11 // modify it under the terms of the GNU General Public License as
12 // published by the Free Software Foundation; either version 2 of the
13 // License, or (at your option) any later version.
15 // This program is distributed in the hope that it will be useful, but
16 // WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 // General Public License for more details.
20 // You should have received a copy of the GNU General Public License
21 // along with this program; if not, write to the Free Software
22 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
24 #ifndef FG_POSITIONED_OCTREE_HXX
25 #define FG_POSITIONED_OCTREE_HXX
36 #include <simgear/math/SGGeometry.hxx>
38 #include <Navaids/positioned.hxx>
39 #include <Navaids/NavDataCache.hxx>
47 const double LEAF_SIZE = SG_NM_TO_METER * 8.0;
48 const double LEAF_SIZE_SQR = LEAF_SIZE * LEAF_SIZE;
51 * Decorate an object with a double value, and use that value to order
52 * items, for the purpoises of the STL algorithms
58 Ordered(const T& v, double x) :
65 Ordered(const Ordered<T>& a) :
71 Ordered<T>& operator=(const Ordered<T>& a)
78 bool operator<(const Ordered<T>& other) const
80 return _order < other._order;
83 bool operator>(const Ordered<T>& other) const
85 return _order > other._order;
100 typedef Ordered<Node*> OrderedNode;
101 typedef std::greater<OrderedNode> FNPQCompare;
104 * the priority queue is fundamental to our search algorithm. When searching,
105 * we know the front of the queue is the nearest unexpanded node (to the search
106 * location). The default STL pqueue returns the 'largest' item from top(), so
107 * to get the smallest, we need to replace the default Compare functor (less<>)
110 typedef std::priority_queue<OrderedNode, std::vector<OrderedNode>, FNPQCompare> FindNearestPQueue;
112 typedef Ordered<FGPositioned*> OrderedPositioned;
113 typedef std::vector<OrderedPositioned> FindNearestResults;
115 extern Node* global_spatialOctree;
120 * Octree node base class, tracks its bounding box and provides various
121 * queries relating to it
129 const SGBoxd& bbox() const
132 bool contains(const SGVec3d& aPos) const
134 return intersects(aPos, _box);
137 double distToNearest(const SGVec3d& aPos) const
139 return dist(aPos, _box.getClosestPoint(aPos));
142 virtual void visit(const SGVec3d& aPos, double aCutoff,
143 FGPositioned::Filter* aFilter,
144 FindNearestResults& aResults, FindNearestPQueue&) = 0;
146 virtual Leaf* findLeafForPos(const SGVec3d& aPos) const = 0;
148 Node(const SGBoxd &aBox, int64_t aIdent) :
154 const int64_t _ident;
158 class Leaf : public Node
161 Leaf(const SGBoxd& aBox, int64_t aIdent);
163 virtual void visit(const SGVec3d& aPos, double aCutoff,
164 FGPositioned::Filter* aFilter,
165 FindNearestResults& aResults, FindNearestPQueue&);
167 virtual Leaf* findLeafForPos(const SGVec3d&) const
169 return const_cast<Leaf*>(this);
172 void insertChild(FGPositioned::Type ty, PositionedID id);
176 typedef std::multimap<FGPositioned::Type, PositionedID> ChildMap;
182 class Branch : public Node
185 Branch(const SGBoxd& aBox, int64_t aIdent);
187 virtual void visit(const SGVec3d& aPos, double aCutoff,
188 FGPositioned::Filter*,
189 FindNearestResults&, FindNearestPQueue& aQ);
191 virtual Leaf* findLeafForPos(const SGVec3d& aPos) const
194 return childForPos(aPos)->findLeafForPos(aPos);
197 int childMask() const;
199 Node* childForPos(const SGVec3d& aCart) const;
200 Node* childAtIndex(int childIndex) const;
203 * Return the box for a child touching the specified corner
205 SGBoxd boxForChild(unsigned int aCorner) const
207 SGBoxd r(_box.getCenter());
208 r.expandBy(_box.getCorner(aCorner));
212 void loadChildren() const;
214 mutable Node* children[8];
215 mutable bool childrenLoaded;
218 void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults);
219 void findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults);
220 } // of namespace Octree
223 } // of namespace flightgear
225 #endif // of FG_POSITIONED_OCTREE_HXX