diff options
author | Jérémy Zurcher <jeremy@asynk.ch> | 2013-03-26 17:55:52 +0100 |
---|---|---|
committer | Jérémy Zurcher <jeremy@asynk.ch> | 2013-11-15 17:38:45 +0100 |
commit | 0e2481dde36a5f188390a0a7ef24b785b5ba4faa (patch) | |
tree | 9a86fea297728ac7ac8f4cc0052611e0e59b4d7d /Algorithms/Part-I/5-KdTrees/PointSET.java | |
parent | 44e9d3d9e4e82d15208f753f08396ab94af133d2 (diff) | |
download | coursera-0e2481dde36a5f188390a0a7ef24b785b5ba4faa.zip coursera-0e2481dde36a5f188390a0a7ef24b785b5ba4faa.tar.gz |
Algorithms-I : 5-kdtrees: implement PointSET
Diffstat (limited to 'Algorithms/Part-I/5-KdTrees/PointSET.java')
-rw-r--r-- | Algorithms/Part-I/5-KdTrees/PointSET.java | 34 |
1 files changed, 29 insertions, 5 deletions
diff --git a/Algorithms/Part-I/5-KdTrees/PointSET.java b/Algorithms/Part-I/5-KdTrees/PointSET.java index aabceff..f5594de 100644 --- a/Algorithms/Part-I/5-KdTrees/PointSET.java +++ b/Algorithms/Part-I/5-KdTrees/PointSET.java @@ -1,50 +1,74 @@ /* vim: set expandtab tabstop=4 shiftwidth=4 : */ +import java.util.TreeSet; + public class PointSET { + private TreeSet<Point2D> set; // construct an empty set of points public PointSET() { + set = new TreeSet<Point2D>(); } // is the set empty? public boolean isEmpty() { - return true; + return set.isEmpty(); } // number of points in the set public int size() { - return 0; + return set.size(); } // add the point p to the set (if it is not already in the set) public void insert(Point2D p) { + set.add(p); } // does the set contain the point p? public boolean contains(Point2D p) { - return false; + return set.contains(p); } // draw all of the points to standard draw public void draw() { + for (Point2D p : set) p.draw(); } // all points in the set that are inside the rectangle public Iterable<Point2D> range(RectHV rect) { - return null; + Stack<Point2D> stack = new Stack<Point2D>(); + + for (Point2D p : set) + if (rect.contains(p)) stack.push(p); + + return stack; } // a nearest neighbor in the set to p; null if set is empty public Point2D nearest(Point2D p) { - return null; + if (set.isEmpty()) return null; + + Point2D p0 = null; + double d = Double.MAX_VALUE; + for (Point2D o : set) + { + double d2 = p.distanceTo(o); + if (d2 < d) { + d = d2; + p0 = o; + } + } + return p0; + } } |