title: Quadtree Nearest Neighbour Algorithm
body: <p>I have implemented a quadtree structure for n points as well as a method for returning an array of points within a given rectangle.  I can't seem to find an algorithm to efficiently find the point that is closest to another given point.  Am I missing something obvious?  I assume a recursive solution is the correct approach?</p>
  
  <p>Am working in Objective C but pseudo code would be fine.  Additionally I am actually storing lat, long data and the distance between points is along a great circle. </p>
  
  <p><strong>EDIT:</strong>
  This is my tree insert and subdivide code</p>
  
  <pre><code>- (BOOL)insert:(id&lt;PASQuadTreeDataPoint&gt;)dataPoint {
  
      BOOL pointAdded = false;
  
      // If the point lies within the region
      if(CGRectContainsPoint(self.region, dataPoint.point)) {
  
          // If there are less than 4 points then add this point
          if(self.dataPoints.count &lt; kMaxPointsPerNode) {
              [self.dataPoints addObject:dataPoint];
              pointAdded = true;
          }
          else {
  
              // Subdivide into 4 quadrants if not already subdivided
              if(northEast == nil) [self subdivide];
  
              // Attempt to add the point to one of the 4 subdivided quadrants
              if([northEast insert:dataPoint]) return true;
              if([southEast insert:dataPoint]) return true;
              if([southWest insert:dataPoint]) return true;
              if([northWest insert:dataPoint]) return true;
          }
      }
  
      return pointAdded;
  }
  
  - (void)subdivide {
  
      // Compute the half width and the origin
      CGFloat width = self.region.size.width * 0.5f;
      CGFloat height = self.region.size.height * 0.5f;
      CGFloat x = self.region.origin.x;
      CGFloat y = self.region.origin.y;
  
      // Create a new child quadtree with the region divided into quarters
      self.northEast = [PASQuadTree quadTreeWithRegion:CGRectMake(x + width, y, width, height)];
      self.southEast = [PASQuadTree quadTreeWithRegion:CGRectMake(x + width, y + height, width, height)];
      self.southWest = [PASQuadTree quadTreeWithRegion:CGRectMake(x, y + height, width, height)];
      self.northWest = [PASQuadTree quadTreeWithRegion:CGRectMake(x, y, width, height)];
  }
  </code></pre>
  
  <p><strong>EDIT:</strong>
  Have written this code to find the smallest node (leaf) that would contain the point:</p>
  
  <pre><code>-(PASQuadTree *)nodeThatWouldContainPoint:(CGPoint)point {
  
      PASQuadTree *node = nil;
  
      // If the point is within the region
      if (CGRectContainsPoint(self.region, point)) {
  
          // Set the node to this node
          node = self;
  
          // If the node has children
          if (self.northEast != nil) {
  
              // Recursively check each child to see if it would contain the point
              PASQuadTree *childNode = [self.northEast nodeThatWouldContainPoint:point];
              if (!childNode) childNode = [self.southEast nodeThatWouldContainPoint:point];
              if (!childNode) childNode = [self.southWest nodeThatWouldContainPoint:point];
              if (!childNode) childNode = [self.northWest nodeThatWouldContainPoint:point];
              if (childNode) node = childNode;
          }
      }
  
      return node;
  }
  </code></pre>
  
  <p>Closer but no cigar!</p>