Logo Search packages:      
Sourcecode: 3depict version File versions  Download package

const Point3D * K3DTree::findNearest ( const Point3D searchPt,
const BoundCube domainCube,
float  deadDistSqr 
) const

Find the nearest point to a given P that lies outsid some dead zone.

deadDistSqr can be used ot disallow exact matching on NN searching simply pass epsilon =stdnumeric_limits<float>::epsilon() (include <limits>) Boundcube is the bounding box around the entire dataset

Definition at line 310 of file K3DTree.cpp.

References BoundCube::bounds, K3DNode::getLocRef(), K3DNode::getLocVal(), BoundCube::intersects(), K3DNode::left(), maxDepth, K3DNode::right(), root, and K3DNode::sqrDist().

Referenced by findKNearest(), and SpatialAnalysisFilter::refresh().

{
      enum { NODE_FIRST_VISIT, //First visit is when you descend the tree
            NODE_SECOND_VISIT, //Second visit is when you come back from ->Left()
            NODE_THIRD_VISIT // Third visit is when you come back from ->Right()
            };


      //The stacks are for the nodes above the current Node.
      const K3DNode *nodeStack[maxDepth+1];
      float domainStack[maxDepth+1][2];
      unsigned int visitStack[maxDepth+1];

      const Point3D *bestPoint;
      const K3DNode *curNode;

      BoundCube curDomain;
      unsigned int visit;
      unsigned int stackTop;
      unsigned int curAxis;
      
      float bestDistSqr;
      float tmpEdge;

      //Set the root as the best estimate
      
      bestPoint =0; 
      bestDistSqr =std::numeric_limits<float>::max();
      curDomain=domainCube;
      visit=NODE_FIRST_VISIT;
      curAxis=0;

      stackTop=0;
      
      curNode=root;     

      do
      {

            switch(visit)
            {
                  //Examine left branch
                  case NODE_FIRST_VISIT:
                  {
                        if(searchPt[curAxis] < curNode->getLocVal(curAxis))
                        {
                              if(curNode->left())
                              {
                                    //Check bounding box when shrunk overlaps best
                                    //estimate sphere
                                    tmpEdge= curDomain.bounds[curAxis][1];
                                    curDomain.bounds[curAxis][1] = curNode->getLocVal(curAxis);
                                    if(bestPoint && !curDomain.intersects(*bestPoint,bestDistSqr))
                                    {
                                          curDomain.bounds[curAxis][1] = tmpEdge; 
                                          visit++;
                                          continue;         
                                    }     
                                    
                                    //Preserve our current state.
                                    nodeStack[stackTop]=curNode;
                                    visitStack[stackTop] = NODE_SECOND_VISIT; //Oh, It will be. It will be.
                                    domainStack[stackTop][1] = tmpEdge;
                                    domainStack[stackTop][0]= curDomain.bounds[curAxis][0];
                                    stackTop++;
                                    
                                    //Update the current information
                                    curNode=curNode->left();
                                    visit=NODE_FIRST_VISIT;
                                    curAxis++;
                                    curAxis%=3;
                                    continue;   
                              }
                        }
                        else
                        {
                              if(curNode->right())
                              {
                                    //Check bounding box when shrunk overlaps best
                                    //estimate sphere
                                    tmpEdge= curDomain.bounds[curAxis][0];
                                    curDomain.bounds[curAxis][0] = curNode->getLocVal(curAxis);
                                    
                                    if(bestPoint && !curDomain.intersects(*bestPoint,bestDistSqr))
                                    {
                                          curDomain.bounds[curAxis][0] =tmpEdge; 
                                          visit++;
                                          continue;         
                                    }     
                                    //Preserve our current state.
                                    nodeStack[stackTop]=curNode;
                                    visitStack[stackTop] = NODE_SECOND_VISIT; //Oh, It will be. It will be.
                                    domainStack[stackTop][0] = tmpEdge;
                                    domainStack[stackTop][1]= curDomain.bounds[curAxis][1];
                                    stackTop++;

                                    //Update the information
                                    curNode=curNode->right();
                                    visit=NODE_FIRST_VISIT;
                                    curAxis++;
                                    curAxis%=3;
                                    continue;   
                              }

                        }
                        visit++;
                        //Fall through
                  }
                  //Examine right branch
                  case NODE_SECOND_VISIT:
                  {
                        if(searchPt[curAxis]< curNode->getLocVal(curAxis))
                        {
                              if(curNode->right())
                              {
                                    //Check bounding box when shrunk overlaps best
                                    //estimate sphere
                                    tmpEdge= curDomain.bounds[curAxis][0];
                                    curDomain.bounds[curAxis][0] = curNode->getLocVal(curAxis);
                                    
                                    if(bestPoint && !curDomain.intersects(*bestPoint,bestDistSqr))
                                    {
                                          curDomain.bounds[curAxis][0] = tmpEdge; 
                                          visit++;
                                          continue;         
                                    }
      
                                    nodeStack[stackTop]=curNode;
                                    visitStack[stackTop] = NODE_THIRD_VISIT; //Oh, It will be. It will be.
                                    domainStack[stackTop][0] = tmpEdge;
                                    domainStack[stackTop][1]= curDomain.bounds[curAxis][1];
                                    stackTop++;
                                    
                                    //Update the information
                                    curNode=curNode->right();
                                    visit=NODE_FIRST_VISIT;
                                    curAxis++;
                                    curAxis%=3;
                                    continue;   

                              }
                        }
                        else
                        {
                              if(curNode->left())
                              {
                                    //Check bounding box when shrunk overlaps best
                                    //estimate sphere
                                    tmpEdge= curDomain.bounds[curAxis][1];
                                    curDomain.bounds[curAxis][1] = curNode->getLocVal(curAxis);
                                    
                                    if(bestPoint && !curDomain.intersects(*bestPoint,bestDistSqr))
                                    {
                                          curDomain.bounds[curAxis][1] = tmpEdge; 
                                          visit++;
                                          continue;         
                                    }     
                                    //Preserve our current state.
                                    nodeStack[stackTop]=curNode;
                                    visitStack[stackTop] = NODE_THIRD_VISIT; //Oh, It will be. It will be.
                                    domainStack[stackTop][1] = tmpEdge;
                                    domainStack[stackTop][0]= curDomain.bounds[curAxis][0];
                                    stackTop++;
                                    
                                    //Update the information
                                    curNode=curNode->left();
                                    visit=NODE_FIRST_VISIT;
                                    curAxis++;
                                    curAxis%=3;
                                    continue;   

                              }
                        }
                        visit++;
                        //Fall through
                  }
                  //Go up
                  case NODE_THIRD_VISIT:
                  {
                        float tmpDistSqr;
                        tmpDistSqr = curNode->sqrDist(searchPt); 
                        if(tmpDistSqr < bestDistSqr &&  tmpDistSqr > deadDistSqr)
                        {
                              bestDistSqr  = tmpDistSqr;
                              bestPoint=curNode->getLocRef();
                        }

                        //DEBUG
                        ASSERT(stackTop%3 == curAxis)
                        //
                        if(curAxis)
                              curAxis--;
                        else
                              curAxis=2;


                        
                        ASSERT(stackTop < maxDepth+1);      
                        stackTop--;
                        visit=visitStack[stackTop];
                        curNode=nodeStack[stackTop];
                        curDomain.bounds[curAxis][0]=domainStack[stackTop][0];
                        curDomain.bounds[curAxis][1]=domainStack[stackTop][1];
                        
                        ASSERT((stackTop)%3 == curAxis)
                        break;
                  }
                  default:
                        ASSERT(false);


            }
            
      //Keep going until we meet the root nde for the third time (one left, one right, one finish)    
      }while(!(curNode==root &&  visit== NODE_THIRD_VISIT));

      return bestPoint; 

}


Generated by  Doxygen 1.6.0   Back to index