1  /* Nearest Neighbor with threshold using a quadtree.
   2   * O(n) memory and O(log n) runtime for n points.
   3   *       by Frank W.
   4   */
   5  
   6  import java.util.*;
   7  
   8  class NearestQuad
   9  {
  10    private Area bounds;
  11    private Node tree;
  12  
  13    public NearestQuad(Area bounds)
  14    {
  15      this.bounds = bounds;
  16      this.tree = new Leaf(bounds);
  17    }
  18  
  19    public void addPoint(Point p)
  20    {
  21      tree = tree.insertPoint(p);
  22    }
  23  
  24    /* Returns null if no point matches */
  25    public Point findNearest(Point target, Area threshold)
  26    {
  27      List<Point> points = tree.getPoints(threshold);
  28  
  29      int min = Integer.MAX_VALUE;
  30      Point found = null;
  31      
  32      for (Point p : points) {
  33        int dist = target.distanceTo(p);
  34        if (dist < min) {
  35          min = dist;
  36          found = p;
  37        }
  38      }
  39      
  40      return found;
  41    }
  42  }
  43  
  44  class Point
  45  {
  46    private int x;
  47    private int y;
  48    
  49    public Point(int x, int y)
  50    {
  51      this.x = x;
  52      this.y = y;
  53    }
  54    
  55    public int getX()
  56    {
  57      return x;
  58    }
  59    
  60    public int getY()
  61    {
  62      return y;
  63    }
  64  
  65    /* Manhattan distance */
  66    public int distanceTo(Point p)
  67    {
  68      int dx = p.getX() - x;
  69      int dy = p.getY() - y;
  70      
  71      return Math.abs(dx) + Math.abs(dy);
  72    }
  73    
  74    public String toString()
  75    {
  76      return "(" + x + ", " + y + ")";
  77    }
  78  }
  79  
  80  class Area
  81  {
  82    private Point min;
  83    private Point max;
  84    
  85    public Area(Point max)
  86    {
  87      this.min = new Point(0, 0);
  88      this.max = max;
  89    }
  90  
  91    public Area(Point min, Point max)
  92    {
  93      this.min = min;
  94      this.max = max;
  95    }
  96    
  97    public Point getMin()
  98    {
  99      return min;
 100    }
 101    
 102    public Point getMax()
 103    {
 104      return max;
 105    }
 106  
 107    public boolean contains(Point p)
 108    {
 109      if (p.getX() >= min.getX() && p.getX() < max.getX()) {
 110        if (p.getY() >= min.getY() && p.getY() < max.getY()) {
 111          return true;
 112        }
 113      }
 114      
 115      return false;
 116    }
 117  
 118    public boolean intersects(Area a)
 119    {
 120      Point amin = a.getMin();
 121      Point amax = a.getMax();
 122      
 123      if (amax.getX() <= min.getX()) return false;
 124      if (amin.getX() >= max.getX()) return false;
 125      if (amax.getY() <= min.getY()) return false;
 126      if (amin.getY() >= max.getY()) return false;
 127      
 128      return true;
 129    }
 130  
 131    /* Split into 4 mostly equal areas: top left, top right, bottom left, and bottom right */
 132    public List<Area> split()
 133    {
 134      List<Area> l = new ArrayList<Area>(4);
 135      
 136      int midx = min.getX() + (max.getX() - min.getX()) / 2;
 137      int midy = min.getY() + (max.getY() - min.getY()) / 2;
 138      
 139      /* Top left */
 140      l.add(new Area(new Point(min.getX(), min.getY()), new Point(midx, midy)));
 141  
 142      /* Top right */
 143      l.add(new Area(new Point(midx, min.getY()), new Point(max.getX(), midy)));
 144  
 145      /* Bottom left */
 146      l.add(new Area(new Point(min.getX(), midy), new Point(midx, max.getY())));
 147  
 148      /* Bottom right */
 149      l.add(new Area(new Point(midx, midy), new Point(max.getX(), max.getY())));
 150  
 151      return l;
 152    }
 153    
 154    public String toString()
 155    {
 156      return "[" + min + " -> " + max + "]";
 157    }
 158  }
 159  
 160  interface Node
 161  {
 162    public Node insertPoint(Point p);
 163    public Area getBounds();
 164    public List<Point> getPoints(Area threshold);
 165  }
 166  
 167  class Branch implements Node
 168  {
 169    private Area bounds;
 170    private ArrayList<Node> children;
 171    
 172    public Branch(Area bounds, ArrayList<Node> children)
 173    {
 174      if (children.size() != 4) {
 175        throw new IllegalArgumentException("Expected exactly 4 children");
 176      }
 177      
 178      this.bounds = bounds;
 179      this.children = children;
 180    }
 181    
 182    public Node insertPoint(Point p)
 183    {
 184      if (!bounds.contains(p)) {
 185        throw new IllegalStateException("Can't add " + p + " to branch with bounds " + bounds);
 186      }
 187      
 188      for (int i = 0; i < children.size(); i++) {
 189        Node n = children.get(i);
 190        
 191        if (n.getBounds().contains(p)) {
 192          n = n.insertPoint(p);
 193          children.set(i, n);
 194          return this;
 195        }
 196      }
 197      
 198      throw new IllegalStateException("No child had bounds for " + p);
 199    }
 200    
 201    public Area getBounds()
 202    {
 203      return bounds;
 204    }
 205  
 206    public List<Point> getPoints(Area threshold)
 207    {
 208      List<Point> l = new ArrayList<Point>();
 209      
 210      for (Node n : children)
 211      {
 212        if (n.getBounds().intersects(threshold)) {
 213          l.addAll(n.getPoints(threshold));
 214        }
 215      }
 216      
 217      return l;
 218    }
 219  }
 220  
 221  class Leaf implements Node
 222  {
 223    Area bounds;
 224    List<Point> points; /* Up to 4 */
 225    
 226    public Leaf(Area bounds)
 227    {
 228      this.bounds = bounds;
 229      this.points = new ArrayList<Point>(4);
 230    }
 231    
 232    public Node insertPoint(Point p)
 233    {
 234      if (!bounds.contains(p)) {
 235        throw new IllegalStateException("Can't add " + p + " to leaf with bounds " + bounds);
 236      }
 237      
 238      if (points.size() < 4) {
 239        /* Add to this leaf since there is still room */
 240        points.add(p);
 241        return this;
 242      }
 243      
 244      /* Need to split... */
 245      List<Area> corners = bounds.split();
 246      ArrayList<Node> children = new ArrayList<Node>(4);
 247      
 248      for (Area a : corners)
 249      {
 250        Node n = new Leaf(a);
 251        
 252        for (Point exist : points) {
 253          if (a.contains(exist)) {
 254            n = n.insertPoint(exist);
 255          }
 256        }
 257        
 258        if (a.contains(p)) {
 259          n = n.insertPoint(p);
 260        }
 261        
 262        children.add(n);
 263      }
 264        
 265      return new Branch(bounds, children);
 266    }
 267    
 268    public Area getBounds()
 269    {
 270      return bounds;
 271    }
 272    
 273    public List<Point> getPoints(Area threshold)
 274    {
 275      List<Point> l = new ArrayList<Point>();
 276      
 277      for (Point p : points)
 278      {
 279        if (threshold.contains(p)) l.add(p);
 280      }
 281      
 282      return l;
 283    }
 284  }