001package algs32.kdtree; 002import algs12.Point2D; 003import algs13.Queue; 004import stdlib.*; 005 006/* a set of points implemented as kd-tree */ 007public class KdTree { 008 009 private static class Node { 010 // TODO 011 } 012 private Node root; 013 014 /* construct an empty set of points */ 015 public KdTree() { 016 // TODO -- maybe nothing to do here... in which case you can remove this and use the default constructor 017 } 018 019 /* is the set empty? */ 020 public boolean isEmpty() { 021 // TODO 022 return false; 023 } 024 025 /* add the point p to the set (if it is not already in the set) */ 026 public void insert(Point2D p) { 027 // TODO 028 } 029 030 /* does the set contain the point p? */ 031 public boolean contains(Point2D target) { 032 // TODO 033 return false; 034 } 035 036 /* all points in the set that are inside the target rectangle */ 037 public Iterable<Point2D> range(RectHV target) { 038 // TODO 039 return new Queue<>(); 040 } 041 042 /* a nearest neighbor to target point; null if empty */ 043 public Point2D nearest(Point2D target) { 044 // TODO 045 return new Point2D (0, 0); 046 } 047 048 /* draw all of the points to standard draw */ 049 /* for x-node, use red line to draw the division between left/right */ 050 /* for y-node, use blue line to draw the division between top/bottom */ 051 /* see the writeup for examples */ 052 public void draw() { 053 // TODO 054 } 055 056 057 058 /* some test code */ 059 public void toGraphviz() { GraphvizBuilder.nodesToFile (root); } 060 private static void insert5Points (KdTree kdtree, double xoffset, double yoffset) { 061 kdtree.insert (new Point2D (0.7 + xoffset, 0.2 + yoffset)); 062 kdtree.insert (new Point2D (0.5 + xoffset, 0.4 + yoffset)); 063 kdtree.insert (new Point2D (0.2 + xoffset, 0.3 + yoffset)); 064 kdtree.insert (new Point2D (0.4 + xoffset, 0.7 + yoffset)); 065 kdtree.insert (new Point2D (0.9 + xoffset, 0.6 + yoffset)); 066 } 067 public static void main (String[] args) { 068 KdTree kdtree = new KdTree (); 069 insert5Points (kdtree, 0.0, 0.0); // after this there should be 5 points 070 insert5Points (kdtree, 0.0, 0.0); // after doing it twice there should still be 5 071 insert5Points (kdtree, 0.1, 0.0); // this should add 5 more points 072 insert5Points (kdtree, 0.0, 0.1); // this should add 5 more points 073 074 075 // kdtree.insert (new Point2D(0.15, 0.18)); 076 // kdtree.insert (new Point2D(0.86, 0.26)); 077 // kdtree.insert (new Point2D(0.70, 0.11)); 078 // kdtree.insert (new Point2D(0.16, 0.01)); 079 // kdtree.insert (new Point2D(0.62, 0.95)); 080 // kdtree.insert (new Point2D(0.98, 0.04)); 081 // kdtree.insert (new Point2D(0.87, 0.79)); 082 // kdtree.insert (new Point2D(0.83, 0.21)); 083 084 // Point2D mid = new Point2D (0.5, 0.5); 085 // Point2D less = new Point2D (0.5, 0.4); 086 // Point2D more = new Point2D (0.5, 0.6); 087 // kdtree.insert (mid); 088 // kdtree.insert (less); 089 // kdtree.insert (more); 090 // StdOut.println (kdtree.contains (less)); 091 // StdOut.println (kdtree.contains (more)); 092 // StdOut.println (kdtree.range (new RectHV (0.5, 0.4, 0.5, 0.6))); 093 // StdOut.println (kdtree.nearest (less)); 094 // StdOut.println (kdtree.nearest (more)); 095 096 StdOut.println (kdtree); 097 kdtree.toGraphviz (); 098 kdtree.draw (); 099 } 100}