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>
40 #include <Navaids/PolyLine.hxx>
48 const double LEAF_SIZE = SG_NM_TO_METER * 8.0;
49 const double LEAF_SIZE_SQR = LEAF_SIZE * LEAF_SIZE;
52 * Decorate an object with a double value, and use that value to order
53 * items, for the purpoises of the STL algorithms
59 Ordered(const T& v, double x) :
66 Ordered(const Ordered<T>& a) :
72 Ordered<T>& operator=(const Ordered<T>& a)
79 bool operator<(const Ordered<T>& other) const
81 return _order < other._order;
84 bool operator>(const Ordered<T>& other) const
86 return _order > other._order;
101 typedef Ordered<Node*> OrderedNode;
102 typedef std::greater<OrderedNode> FNPQCompare;
105 * the priority queue is fundamental to our search algorithm. When searching,
106 * we know the front of the queue is the nearest unexpanded node (to the search
107 * location). The default STL pqueue returns the 'largest' item from top(), so
108 * to get the smallest, we need to replace the default Compare functor (less<>)
111 typedef std::priority_queue<OrderedNode, std::vector<OrderedNode>, FNPQCompare> FindNearestPQueue;
113 typedef Ordered<FGPositioned*> OrderedPositioned;
114 typedef std::vector<OrderedPositioned> FindNearestResults;
116 // for extracting lines, we don't care about distance ordering, since
117 // we're always grabbing all the lines in an area
118 typedef std::deque<Node*> FindLinesDeque;
120 extern Node* global_spatialOctree;
125 * Octree node base class, tracks its bounding box and provides various
126 * queries relating to it
134 const SGBoxd& bbox() const
137 bool contains(const SGVec3d& aPos) const
139 return intersects(aPos, _box);
142 double distToNearest(const SGVec3d& aPos) const
144 return dist(aPos, _box.getClosestPoint(aPos));
147 virtual void visit(const SGVec3d& aPos, double aCutoff,
148 FGPositioned::Filter* aFilter,
149 FindNearestResults& aResults, FindNearestPQueue&) = 0;
151 virtual Leaf* findLeafForPos(const SGVec3d& aPos) const = 0;
153 virtual void visitForLines(const SGVec3d& aPos, double aCutoff,
154 PolyLineList& aLines,
155 FindLinesDeque& aQ) const = 0;
158 Node(const SGBoxd &aBox, int64_t aIdent) :
164 const int64_t _ident;
168 class Leaf : public Node
171 Leaf(const SGBoxd& aBox, int64_t aIdent);
173 virtual void visit(const SGVec3d& aPos, double aCutoff,
174 FGPositioned::Filter* aFilter,
175 FindNearestResults& aResults, FindNearestPQueue&);
177 virtual Leaf* findLeafForPos(const SGVec3d&) const
179 return const_cast<Leaf*>(this);
182 void insertChild(FGPositioned::Type ty, PositionedID id);
184 void addPolyLine(PolyLineRef);
186 virtual void visitForLines(const SGVec3d& aPos, double aCutoff,
187 PolyLineList& aLines,
188 FindLinesDeque& aQ) const;
192 typedef std::multimap<FGPositioned::Type, PositionedID> ChildMap;
200 class Branch : public Node
203 Branch(const SGBoxd& aBox, int64_t aIdent);
205 virtual void visit(const SGVec3d& aPos, double aCutoff,
206 FGPositioned::Filter*,
207 FindNearestResults&, FindNearestPQueue& aQ);
209 virtual Leaf* findLeafForPos(const SGVec3d& aPos) const
212 return childForPos(aPos)->findLeafForPos(aPos);
215 int childMask() const;
217 virtual void visitForLines(const SGVec3d& aPos, double aCutoff,
218 PolyLineList& aLines,
219 FindLinesDeque& aQ) const;
221 Node* childForPos(const SGVec3d& aCart) const;
222 Node* childAtIndex(int childIndex) const;
225 * Return the box for a child touching the specified corner
227 SGBoxd boxForChild(unsigned int aCorner) const
229 SGBoxd r(_box.getCenter());
230 r.expandBy(_box.getCorner(aCorner));
234 void loadChildren() const;
236 mutable Node* children[8];
237 mutable bool childrenLoaded;
240 bool findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter* aFilter, FGPositionedList& aResults, int aCutoffMsec);
241 bool findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositionedList& aResults, int aCutoffMsec);
242 } // of namespace Octree
245 } // of namespace flightgear
247 #endif // of FG_POSITIONED_OCTREE_HXX