Algorithms-I : 5-KdTrees: added, to be completed

1 files changed, 59 insertions, 0 deletions

diff --git a/Algorithms/Part-I/5-KdTrees/NearestNeighborVisualizer.java b/Algorithms/Part-I/5-KdTrees/NearestNeighborVisualizer.java
new file mode 100644
index 0000000..97cd1e4
--- /dev/null
+++ b/Algorithms/Part-I/5-KdTrees/NearestNeighborVisualizer.java
@@ -0,0 +1,59 @@
+/*************************************************************************
+ *  Compilation:  javac NearestNeighborVisualizer.java
+ *  Execution:    java NearestNeighborVisualizer input.txt
+ *  Dependencies: PointSET.java KdTree.java Point2D.java In.java StdDraw.java
+ *
+ *  Read points from a file (specified as a command-line argument) and
+ *  draw to standard draw. Highlight the closest point to the mouse.
+ *
+ *  The nearest neighbor according to the brute-force algorithm is drawn
+ *  in red; the nearest neighbor using the kd-tree algorithm is drawn in blue.
+ *
+ *************************************************************************/
+
+public class NearestNeighborVisualizer {
+
+    public static void main(String[] args) {
+        String filename = args[0];
+        In in = new In(filename);
+
+        StdDraw.show(0);
+
+        // initialize the two data structures with point from standard input
+        PointSET brute = new PointSET();
+        KdTree kdtree = new KdTree();
+        while (!in.isEmpty()) {
+            double x = in.readDouble();
+            double y = in.readDouble();
+            Point2D p = new Point2D(x, y);
+            kdtree.insert(p);
+            brute.insert(p);
+        }
+
+        while (true) {
+
+            // the location (x, y) of the mouse
+            double x = StdDraw.mouseX();
+            double y = StdDraw.mouseY();
+            Point2D query = new Point2D(x, y);
+
+            // draw all of the points
+            StdDraw.clear();
+            StdDraw.setPenColor(StdDraw.BLACK);
+            StdDraw.setPenRadius(.01);
+            brute.draw();
+
+            // draw in red the nearest neighbor (using brute-force algorithm)
+            StdDraw.setPenRadius(.03);
+            StdDraw.setPenColor(StdDraw.RED);
+            brute.nearest(query).draw();
+            StdDraw.setPenRadius(.02);
+
+            // draw in blue the nearest neighbor (using kd-tree algorithm)
+            StdDraw.setPenColor(StdDraw.BLUE);
+            kdtree.nearest(query).draw();
+            StdDraw.show(0);
+            StdDraw.show(40);
+        }
+    }
+}