For the geometric queries you specify (the closest point), KD Tree is a great data structure. In addition, it is not very difficult to implement. I have a Java implementation. Not sure how effective it is for you. That was my assignment. Point2D and other utility classes are implemented here . You can view their source code. RectHV is another useful class. It is written by me.
public class RectHV { private final double xmin, ymin; // minimum x- and y-coordinates private final double xmax, ymax; // maximum x- and y-coordinates // construct the axis-aligned rectangle [xmin, xmax] x [ymin, ymax] public RectHV(double xmin, double ymin, double xmax, double ymax) { if (xmax < xmin || ymax < ymin) { throw new IllegalArgumentException("Invalid rectangle"); } this.xmin = xmin; this.ymin = ymin; this.xmax = xmax; this.ymax = ymax; } // accessor methods for 4 coordinates public double xmin() { return xmin; } public double ymin() { return ymin; } public double xmax() { return xmax; } public double ymax() { return ymax; } // width and height of rectangle public double width() { return xmax - xmin; } public double height() { return ymax - ymin; } // does this axis-aligned rectangle intersect that one? public boolean intersects(RectHV that) { return this.xmax >= that.xmin && this.ymax >= that.ymin && that.xmax >= this.xmin && that.ymax >= this.ymin; } // draw this axis-aligned rectangle public void draw() { StdDraw.line(xmin, ymin, xmax, ymin); StdDraw.line(xmax, ymin, xmax, ymax); StdDraw.line(xmax, ymax, xmin, ymax); StdDraw.line(xmin, ymax, xmin, ymin); } // distance from p to closest point on this axis-aligned rectangle public double distanceTo(Point2D p) { return Math.sqrt(this.distanceSquaredTo(p)); } // distance squared from p to closest point on this axis-aligned rectangle public double distanceSquaredTo(Point2D p) { double dx = 0.0, dy = 0.0; if (px() < xmin) dx = px() - xmin; else if (px() > xmax) dx = px() - xmax; if (py() < ymin) dy = py() - ymin; else if (py() > ymax) dy = py() - ymax; return dx*dx + dy*dy; } // does this axis-aligned rectangle contain p? public boolean contains(Point2D p) { return (px() >= xmin) && (px() <= xmax) && (py() >= ymin) && (py() <= ymax); } // are the two axis-aligned rectangles equal? public boolean equals(Object y) { if (y == this) return true; if (y == null) return false; if (y.getClass() != this.getClass()) return false; RectHV that = (RectHV) y; if (this.xmin != that.xmin) return false; if (this.ymin != that.ymin) return false; if (this.xmax != that.xmax) return false; if (this.ymax != that.ymax) return false; return true; } // return a string representation of this axis-aligned rectangle public String toString() { return "[" + xmin + ", " + xmax + "] x [" + ymin + ", " + ymax + "]"; } }
Here is the KD tree:
public class KdTree { private static class Node { private Point2D p; // the point private RectHV rect; // the axis-aligned rectangle corresponding to this node private Node lb; // the left/bottom subtree private Node rt; // the right/top subtree Node() { p = null; rect = null; lb = null; rt = null; } } private Node tree; private Point2D nearestPoint, infinitePoint; private int sz; private double nearestDist; // construct an empty set of points public KdTree() { tree = new Node(); sz = 0; infinitePoint = new Point2D(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } // is the set empty? public boolean isEmpty() { return (sz == 0); } // number of points in the set public int size() { return sz; } //////////////////////////////////////////////// // private function for inserting any element // //////////////////////////////////////////////// private void privateInsert( Node nd, Point2D p, int lv, double xmin, double ymin, double xmax, double ymax) { if(nd.p == null) { nd.p = p; nd.rect = new RectHV(xmin, ymin, xmax, ymax); nd.lb = new Node(); nd.rt = new Node(); sz = sz + 1; } else if( lv % 2 == 0 ) { double X = nd.px(); double x = px(); if( x <= X ) { xmax = X; privateInsert(nd.lb, p, lv+1, xmin, ymin, xmax, ymax); } else { xmin = X; privateInsert(nd.rt, p, lv+1, xmin, ymin, xmax, ymax); } } else { double Y = nd.py(); double y = py(); if( y <= Y ) { ymax = Y; privateInsert(nd.lb, p, lv+1, xmin, ymin, xmax, ymax); } else { ymin = Y; privateInsert(nd.rt, p, lv+1, xmin, ymin, xmax, ymax); } } } //////////////////////////////////////////////// // private function for searching any element // //////////////////////////////////////////////// private Node privateSearch( Node nd, Point2D p, int lv ) { if( nd.p == null ) return nd; else if( p.equals( nd.p ) == true ) return nd; if(lv % 2 == 0) { double X = nd.px(); double x = px(); if( x <= X ) { return privateSearch( nd.lb, p, lv+1 ); } else { return privateSearch( nd.rt, p, lv+1); } } else { double Y = nd.py(); double y = py(); if( y <= Y ) { return privateSearch(nd.lb, p, lv+1); } else { return privateSearch(nd.rt, p, lv+1); } } } ///////////////////////////////////////////////// // private function for drawing all the points // ///////////////////////////////////////////////// private void privateDraw (Node nd) { if(nd.p == null) return; StdDraw.setPenColor(StdDraw.BLACK); StdDraw.setPenRadius(.01); double x = nd.px(); double y = nd.py(); StdDraw.point( x, y ); privateDraw( nd.lb ); privateDraw( nd.rt ); } ////////////////////////////////////////// // private function for range searching // ////////////////////////////////////////// private void privateRange(Node nd, RectHV rect, Queue<Point2D> que){ if(nd.p == null) return; if( rect.contains( nd.p ) == true ) que.enqueue( nd.p ); if( nd.rect.intersects(rect) == true ) { privateRange(nd.lb, rect, que); privateRange(nd.rt, rect, que); return; } else return; } ////////////////////////////////////////////////////// // private function for searching nearest neighbour // ////////////////////////////////////////////////////// private void privateNearest( Node nd, Point2D p ) { if(nd.p == null) return; double d = p.distanceSquaredTo(nd.p); if(d < nearestDist) { nearestDist = d; nearestPoint = nd.p; } if(nd.lb.p != null && ( nd.lb.rect.distanceSquaredTo(p) < nearestDist) ) privateNearest(nd.lb, p); if(nd.rt.p != null && ( nd.rt.rect.distanceSquaredTo(p) < nearestDist) ) privateNearest(nd.rt, p); } // add the point p to the set (if it is not already in the set) public void insert(Point2D p) { if( contains( p ) == true ) { return; } else { privateInsert(tree, p, 0, 0.00, 0.00, 1.00, 1.00); } } // does the set contain the point p? public boolean contains(Point2D p) { Node nd = privateSearch(tree, p, 0); if(nd.p == null) return false; else return true; } // draw all of the points to standard draw public void draw() { privateDraw(tree); } // all points in the set that are inside the rectangle public Iterable<Point2D> range( RectHV rect ) { Queue<Point2D> que = new Queue<Point2D>(); privateRange(tree, rect, que); return que; } // a nearest neighbor in the set to p; null if set is empty public Point2D nearest(Point2D p) { nearestPoint = infinitePoint; nearestDist = Double.POSITIVE_INFINITY; privateNearest(tree, p); return nearestPoint; //return p; } }