X-Git-Url: https://git.mxchange.org/?a=blobdiff_plain;f=src%2FNavaids%2FPositionedOctree.cxx;h=ae6ee5ec4b042e805c769749115572f70c7a6db5;hb=487546c848ad5559760b4de4aa36f19b9b8627a7;hp=261deb8beb29227b54652eaee7b2a6597e1eb211;hpb=9b900e94304b95337e2731946525cde4ef377da9;p=flightgear.git

diff --git a/src/Navaids/PositionedOctree.cxx b/src/Navaids/PositionedOctree.cxx
index 261deb8be..ae6ee5ec4 100644
--- a/src/Navaids/PositionedOctree.cxx
+++ b/src/Navaids/PositionedOctree.cxx
@@ -36,6 +36,8 @@
 #include <boost/foreach.hpp>
 
 #include <simgear/debug/logstream.hxx>
+#include <simgear/structure/exception.hxx>
+#include <simgear/timing/timestamp.hxx>
 
 namespace flightgear
 {
@@ -66,7 +68,6 @@ void Leaf::visit(const SGVec3d& aPos, double aCutoff,
   
   for (; it != end; ++it) {
     FGPositioned* p = cache->loadById(it->second);
-    assert(intersects(_box, p->cart()));
     double d = dist(aPos, p->cart());
     if (d > aCutoff) {
       continue;
@@ -112,7 +113,21 @@ void Leaf::loadChildren()
   
   childrenLoaded = true;
 }
-  
+    
+void Leaf::addPolyLine(PolyLineRef aLine)
+{
+    lines.push_back(aLine);
+}
+
+void Leaf::visitForLines(const SGVec3d& aPos, double aCutoff,
+                           PolyLineList& aLines,
+                           FindLinesDeque& aQ) const
+{
+    aLines.insert(aLines.end(), lines.begin(), lines.end());
+}
+    
+///////////////////////////////////////////////////////////////////////////////
+    
 Branch::Branch(const SGBoxd& aBox, int64_t aIdent) :
   Node(aBox, aIdent),
   childrenLoaded(false)
@@ -138,6 +153,24 @@ void Branch::visit(const SGVec3d& aPos, double aCutoff,
     aQ.push(Ordered<Node*>(children[i], d));
   } // of child iteration
 }
+    
+void Branch::visitForLines(const SGVec3d& aPos, double aCutoff,
+                           PolyLineList& aLines,
+                           FindLinesDeque& aQ) const
+{
+    for (unsigned int i=0; i<8; ++i) {
+        if (!children[i]) {
+            continue;
+        }
+        
+        double d = children[i]->distToNearest(aPos);
+        if (d > aCutoff) {
+            continue; // exceeded cutoff
+        }
+        
+        aQ.push_back(children[i]);
+    } // of child iteration
+}
 
 Node* Branch::childForPos(const SGVec3d& aCart) const
 {
@@ -222,7 +255,7 @@ int Branch::childMask() const
   return result;
 }
 
-void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults)
+bool findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter* aFilter, FGPositionedList& aResults, int aCutoffMsec)
 {
   aResults.clear();
   FindNearestPQueue pq;
@@ -230,13 +263,17 @@ void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPosit
   pq.push(Ordered<Node*>(global_spatialOctree, 0));
   double cut = aCutoffM;
 
-  while (!pq.empty()) {
+  SGTimeStamp tm;
+  tm.stamp();
+    
+  while (!pq.empty() && (tm.elapsedMSec() < aCutoffMsec)) {
     if (!results.empty()) {
       // terminate the search if we have sufficent results, and we are
       // sure no node still on the queue contains a closer match
       double furthestResultOrder = results.back().order();
-    //  std::cout << "furthest result:" << furthestResultOrder << ", top node order:" << pq.top().order() << std::endl;
       if ((results.size() >= aN) && (furthestResultOrder < pq.top().order())) {
+    // clear the PQ to mark this has 'full results' instead of partial
+        pq = FindNearestPQueue();
         break;
       }
     }
@@ -244,7 +281,6 @@ void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPosit
     Node* nd = pq.top().get();
     pq.pop();
   
-//    std::cout << "visiting:" << std::oct << nd->guid() << "(" << std::dec << nd->guid() << ")" << std::endl;
     nd->visit(aPos, cut, aFilter, results, pq);
   } // of queue iteration
 
@@ -256,9 +292,11 @@ void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPosit
   for (unsigned int r=0; r<numResults; ++r) {
     aResults[r] = results[r].get();
   }
+    
+  return !pq.empty();
 }
 
-void findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults)
+bool findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositionedList& aResults, int aCutoffMsec)
 {
   aResults.clear();
   FindNearestPQueue pq;
@@ -266,7 +304,10 @@ void findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filte
   pq.push(Ordered<Node*>(global_spatialOctree, 0));
   double rng = aRangeM;
 
-  while (!pq.empty()) {
+  SGTimeStamp tm;
+  tm.stamp();
+  
+  while (!pq.empty() && (tm.elapsedMSec() < aCutoffMsec)) {
     Node* nd = pq.top().get();
     pq.pop();
   
@@ -279,6 +320,8 @@ void findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filte
   for (unsigned int r=0; r<numResults; ++r) {
     aResults[r] = results[r].get();
   }
+      
+  return !pq.empty();
 }
       
 } // of namespace Octree