Changeset 181 for trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

Timestamp:

07/18/05 21:22:46 (19 years ago)

Author:

bittner

Message:

bug with find neighbors fixed

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

@@ -674 +674 @@
   return NULL;
 }
+
+int
+KdTree::FindNeighbors(KdNode *n,
+                      vector<KdNode *> &neighbors,
+                      bool onlyUnmailed
+                      )
+{
+  stack<KdNode *> nodeStack;
+  
+  nodeStack.push(mRoot);
+
+  AxisAlignedBox3 box = GetBox(n);
+
+  while (!nodeStack.empty()) {
+    KdNode *node = nodeStack.top();
+    nodeStack.pop();
+    if (node->IsLeaf()) {
+      if ( node != n && (!onlyUnmailed || !node->Mailed()) ) 
+        neighbors.push_back(node);
+    } else {
+      KdInterior *interior = (KdInterior *)node;
+      if (interior->mPosition > box.Max(interior->mAxis))
+        nodeStack.push(interior->mBack);
+      else
+        if (interior->mPosition < box.Min(interior->mAxis))
+          nodeStack.push(interior->mFront);
+        else {
+          // random decision
+            nodeStack.push(interior->mBack);
+            nodeStack.push(interior->mFront);
+        }
+    }
+  }
+  
+  return neighbors.size();
+}