17#include <simgear/debug/logstream.hxx>
18#include <simgear/structure/exception.hxx>
19#include <simgear/timing/timestamp.hxx>
66 lines.push_back(aLine);
76 aLines.insert(aLines.end(),
lines.begin(),
lines.end());
81 return const_cast<Node*
>(
this);
84Leaf::Leaf(
const SGBoxd& aBox, int64_t aIdent,
bool persistent) :
Node(aBox, aIdent, persistent)
87 _childrenLoaded =
true;
95 int previousResultsSize = aResults.size();
101 ChildMap::const_iterator it = children.lower_bound(aFilter->
minType());
102 ChildMap::const_iterator end = children.upper_bound(aFilter->
maxType());
104 for (; it != end; ++it) {
106 double d = dist(aPos,
p->cart());
111 if (aFilter && !aFilter->
pass(
p)) {
119 if (addedCount == 0) {
125 std::sort(aResults.begin() + previousResultsSize, aResults.end());
128 std::inplace_merge(aResults.begin(),
129 aResults.begin() + previousResultsSize, aResults.end());
134 assert(_childrenLoaded);
143 auto it = std::find_if(children.begin(), children.end(), [
id](
const TypedPositioned&
p) {
144 return p.second == id;
147 if (it != children.end()) {
152void Leaf::loadChildren()
154 if (_childrenLoaded) {
161 children.insert(children.end(), tp);
164 _childrenLoaded =
true;
171 _children.fill(
nullptr);
173 _childrenLoaded =
true;
182 for (
unsigned int i=0;
i<8; ++
i) {
187 double d = _children[
i]->distToNearest(aPos);
203 for (
unsigned int i=0;
i<8; ++
i) {
208 double d = _children[
i]->distToNearest(aPos);
213 aQ.push_back(_children[
i]);
219 const SGVec3d aMin(a.getMin()),
223 for (
int i=0;
i<3; ++
i) {
224 if ((bMin[
i] < aMin[
i]) || (bMax[
i] > aMax[
i]))
return false;
236 for (
unsigned int i=0;
i<8; ++
i) {
237 const SGBoxd childBox(boxForChild(
i));
239 return childAtIndex(
i)->findNodeForBox(box);
246Node* Branch::childForPos(
const SGVec3d& aCart)
const
251 SGVec3d center(
_box.getCenter());
253 if (aCart.x() < center.x()) {
257 if (aCart.y() < center.y()) {
261 if (aCart.z() < center.z()) {
265 return childAtIndex(childIndex);
268Node* Branch::childAtIndex(
int childIndex)
const
270 Node* child = _children[childIndex];
272 SGBoxd cb(boxForChild(childIndex));
273 double d2 = dot(cb.getSize(), cb.getSize());
279 int64_t childIdent = (
_ident << 3) | childIndex;
289 _children[childIndex] = child;
298 return _children[childIndex];
301void Branch::loadChildren()
const
303 if (_childrenLoaded) {
308 for (
int i=0;
i<8; ++
i) {
309 if ((1 <<
i) & childrenMask) {
316 _childrenLoaded =
true;
322 for (
int i=0;
i<8; ++
i) {
338 double cut = aCutoffM;
343 while (!pq.empty() && (tm.elapsedMSec() < aCutoffMsec)) {
344 if (!results.empty()) {
347 double furthestResultOrder = results.back().order();
348 if ((results.size() >= aN) && (furthestResultOrder < pq.top().order())) {
355 Node* nd = pq.top().get();
358 nd->
visit(aPos, cut, aFilter, results, pq);
363 unsigned int numResults = std::min((
unsigned int) results.size(), aN);
365 aResults.resize(numResults);
366 for (
unsigned int r=0; r<numResults; ++r) {
367 aResults[r] = results[r].get();
380 double rng = aRangeM;
385 while (!pq.empty() && (tm.elapsedMSec() < aCutoffMsec)) {
386 Node* nd = pq.top().get();
389 nd->
visit(aPos, rng, aFilter, results, pq);
392 unsigned int numResults = results.size();
394 aResults.resize(numResults);
395 for (
unsigned int r=0; r<numResults; ++r) {
396 aResults[r] = results[r].get();
Predicate class to support custom filtering of FGPositioned queries Default implementation of this pa...
virtual Type maxType() const
virtual Type minType() const
virtual bool pass(FGPositioned *aPos) const
Over-rideable filter method.
void defineOctreeNode(Octree::Branch *pr, Octree::Node *nd)
TypedPositionedVec getOctreeLeafChildren(int64_t octreeNodeId)
given an octree leaf, return all its child positioned items and their types
int getOctreeBranchChildren(int64_t octreeNodeId)
Given an Octree node ID, return a bit-mask defining which of the child nodes exist.
FGPositionedRef loadById(PositionedID guid)
retrieve an FGPositioned from the cache.
static NavDataCache * instance()
Branch(const SGBoxd &aBox, int64_t aIdent, bool persistent)
virtual Node * findNodeForBox(const SGBoxd &box) const
virtual void visit(const SGVec3d &aPos, double aCutoff, FGPositioned::Filter *, FindNearestResults &, FindNearestPQueue &aQ)
virtual void visitForLines(const SGVec3d &aPos, double aCutoff, PolyLineList &aLines, FindLinesDeque &aQ) const
Leaf(const SGBoxd &aBox, int64_t aIdent, bool persistent)
void removeChild(PositionedID id)
virtual void visit(const SGVec3d &aPos, double aCutoff, FGPositioned::Filter *aFilter, FindNearestResults &aResults, FindNearestPQueue &)
void insertChild(FGPositioned::Type ty, PositionedID id)
Octree node base class, tracks its bounding box and provides various queries relating to it.
virtual void visit(const SGVec3d &aPos, double aCutoff, FGPositioned::Filter *aFilter, FindNearestResults &aResults, FindNearestPQueue &)=0
void addPolyLine(const PolyLineRef &)
virtual void visitForLines(const SGVec3d &aPos, double aCutoff, PolyLineList &aLines, FindLinesDeque &aQ) const
Node(const SGBoxd &aBox, int64_t aIdent, bool persistent)
bool contains(const SGVec3d &aPos) const
virtual Node * findNodeForBox(const SGBoxd &box) const
Decorate an object with a double value, and use that value to order items, for the purpoises of the S...
static std::unique_ptr< Node > global_transientOctree
Ordered< FGPositioned * > OrderedPositioned
std::deque< Node * > FindLinesDeque
static std::unique_ptr< Node > global_spatialOctree
bool findAllWithinRange(const SGVec3d &aPos, double aRangeM, FGPositioned::Filter *aFilter, FGPositionedList &aResults, int aCutoffMsec)
const double LEAF_SIZE_SQR
std::vector< OrderedPositioned > FindNearestResults
Node * globalTransientOctree()
bool findNearestN(const SGVec3d &aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter *aFilter, FGPositionedList &aResults, int aCutoffMsec)
Node * globalPersistentOctree()
std::priority_queue< OrderedNode, std::vector< OrderedNode >, FNPQCompare > FindNearestPQueue
the priority queue is fundamental to our search algorithm.
static bool boxContainsBox(const SGBoxd &a, const SGBoxd &b)
FlightPlan.hxx - defines a full flight-plan object, including departure, cruise, arrival information ...
std::pair< FGPositioned::Type, PositionedID > TypedPositioned
std::vector< PolyLineRef > PolyLineList
SGSharedPtr< PolyLine > PolyLineRef
std::vector< FGPositionedRef > FGPositionedList