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
35 #include <simgear/math/SGGeometry.hxx>
37 #include <Navaids/positioned.hxx>
38 #include <Navaids/NavDataCache.hxx>
46 const double LEAF_SIZE = SG_NM_TO_METER * 8.0;
47 const double LEAF_SIZE_SQR = LEAF_SIZE * LEAF_SIZE;
50 * Decorate an object with a double value, and use that value to order
51 * items, for the purpoises of the STL algorithms
57 Ordered(const T& v, double x) :
64 Ordered(const Ordered<T>& a) :
70 Ordered<T>& operator=(const Ordered<T>& a)
77 bool operator<(const Ordered<T>& other) const
79 return _order < other._order;
82 bool operator>(const Ordered<T>& other) const
84 return _order > other._order;
99 typedef Ordered<Node*> OrderedNode;
100 typedef std::greater<OrderedNode> FNPQCompare;
103 * the priority queue is fundamental to our search algorithm. When searching,
104 * we know the front of the queue is the nearest unexpanded node (to the search
105 * location). The default STL pqueue returns the 'largest' item from top(), so
106 * to get the smallest, we need to replace the default Compare functor (less<>)
109 typedef std::priority_queue<OrderedNode, std::vector<OrderedNode>, FNPQCompare> FindNearestPQueue;
111 typedef Ordered<FGPositioned*> OrderedPositioned;
112 typedef std::vector<OrderedPositioned> FindNearestResults;
114 extern Node* global_spatialOctree;
119 * Octree node base class, tracks its bounding box and provides various
120 * queries relating to it
128 const SGBoxd& bbox() const
131 bool contains(const SGVec3d& aPos) const
133 return intersects(aPos, _box);
136 double distToNearest(const SGVec3d& aPos) const
138 return dist(aPos, _box.getClosestPoint(aPos));
141 virtual void visit(const SGVec3d& aPos, double aCutoff,
142 FGPositioned::Filter* aFilter,
143 FindNearestResults& aResults, FindNearestPQueue&) = 0;
145 virtual Leaf* findLeafForPos(const SGVec3d& aPos) const = 0;
147 Node(const SGBoxd &aBox, int64_t aIdent) :
153 const int64_t _ident;
157 class Leaf : public Node
160 Leaf(const SGBoxd& aBox, int64_t aIdent);
162 virtual void visit(const SGVec3d& aPos, double aCutoff,
163 FGPositioned::Filter* aFilter,
164 FindNearestResults& aResults, FindNearestPQueue&);
166 virtual Leaf* findLeafForPos(const SGVec3d&) const
168 return const_cast<Leaf*>(this);
171 void insertChild(FGPositioned::Type ty, PositionedID id);
175 typedef std::multimap<FGPositioned::Type, PositionedID> ChildMap;
181 class Branch : public Node
184 Branch(const SGBoxd& aBox, int64_t aIdent);
186 virtual void visit(const SGVec3d& aPos, double aCutoff,
187 FGPositioned::Filter*,
188 FindNearestResults&, FindNearestPQueue& aQ);
190 virtual Leaf* findLeafForPos(const SGVec3d& aPos) const
193 return childForPos(aPos)->findLeafForPos(aPos);
196 int childMask() const;
198 Node* childForPos(const SGVec3d& aCart) const;
199 Node* childAtIndex(int childIndex) const;
202 * Return the box for a child touching the specified corner
204 SGBoxd boxForChild(unsigned int aCorner) const
206 SGBoxd r(_box.getCenter());
207 r.expandBy(_box.getCorner(aCorner));
211 void loadChildren() const;
213 mutable Node* children[8];
214 mutable bool childrenLoaded;
217 void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults);
218 void findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults);
219 } // of namespace Octree
222 } // of namespace flightgear
224 #endif // of FG_POSITIONED_OCTREE_HXX