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

7 files changed, 399 insertions, 0 deletions

diff --git a/Algorithms/Part-I/5-KdTrees/KdTree.java b/Algorithms/Part-I/5-KdTrees/KdTree.java
new file mode 100644
index 0000000..877a2c3
--- /dev/null
+++ b/Algorithms/Part-I/5-KdTrees/KdTree.java
@@ -0,0 +1,51 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+public class KdTree
+{
+    // construct an empty tree of points
+    public KdTree()
+    {
+    }
+
+    // is the tree empty?
+    public boolean isEmpty()
+    {
+        return true;
+    }
+
+    // number of points in the tree
+    public int size()
+    {
+        return 0;
+    }
+
+    // add the point p to the tree (if it is not already in the tree)
+    public void insert(Point2D p)
+    {
+    }
+
+    // does the tree contain the point p?
+    public boolean contains(Point2D p)
+    {
+        return false;
+    }
+
+    // draw all of the points to standard draw
+    public void draw()
+    {
+    }
+
+    // all points in the tree that are inside the rectangle
+    public Iterable<Point2D> range(RectHV rect)
+    {
+        return null;
+    }
+
+    // a nearest neighbor in the tree to p; null if tree is empty
+    public Point2D nearest(Point2D p)
+    {
+        return null;
+    }
+
+}
+
diff --git a/Algorithms/Part-I/5-KdTrees/KdTreeVisualizer.java b/Algorithms/Part-I/5-KdTrees/KdTreeVisualizer.java
new file mode 100644
index 0000000..638a469
--- /dev/null
+++ b/Algorithms/Part-I/5-KdTrees/KdTreeVisualizer.java
@@ -0,0 +1,30 @@
+/*************************************************************************
+ *  Compilation:  javac KdTreeVisualizer.java
+ *  Execution:    java KdTreeVisualizer
+ *  Dependencies: StdDraw.java Point2D.java KdTree.java
+ *
+ *  Add the points that the user clicks in the standard draw window
+ *  to a kd-tree and draw the resulting kd-tree.
+ *
+ *************************************************************************/
+
+public class KdTreeVisualizer {
+
+    public static void main(String[] args) {
+        StdDraw.show(0);
+        KdTree kdtree = new KdTree();
+        while (true) {
+            if (StdDraw.mousePressed()) {
+                double x = StdDraw.mouseX();
+                double y = StdDraw.mouseY();
+                System.out.printf("%8.6f %8.6f\n", x, y);
+                Point2D p = new Point2D(x, y);
+                kdtree.insert(p);
+                StdDraw.clear();
+                kdtree.draw();
+            }
+            StdDraw.show(50);
+        }
+
+    }
+}
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);
+        }
+    }
+}
diff --git a/Algorithms/Part-I/5-KdTrees/PointSET.java b/Algorithms/Part-I/5-KdTrees/PointSET.java
new file mode 100644
index 0000000..aabceff
--- /dev/null
+++ b/Algorithms/Part-I/5-KdTrees/PointSET.java
@@ -0,0 +1,50 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+public class PointSET
+{
+    // construct an empty set of points
+    public PointSET()
+    {
+    }
+
+    // is the set empty?
+    public boolean isEmpty()
+    {
+        return true;
+    }
+
+    // number of points in the set
+    public int size()
+    {
+        return 0;
+    }
+
+    // add the point p to the set (if it is not already in the set)
+    public void insert(Point2D p)
+    {
+    }
+
+    // does the set contain the point p?
+    public boolean contains(Point2D p)
+    {
+        return false;
+    }
+
+    // draw all of the points to standard draw
+    public void draw()
+    {
+    }
+
+    // all points in the set that are inside the rectangle
+    public Iterable<Point2D> range(RectHV rect)
+    {
+        return null;
+    }
+
+    // a nearest neighbor in the set to p; null if set is empty
+    public Point2D nearest(Point2D p)
+    {
+        return null;
+    }
+}
+
diff --git a/Algorithms/Part-I/5-KdTrees/RangeSearchVisualizer.java b/Algorithms/Part-I/5-KdTrees/RangeSearchVisualizer.java
new file mode 100644
index 0000000..781782f
--- /dev/null
+++ b/Algorithms/Part-I/5-KdTrees/RangeSearchVisualizer.java
@@ -0,0 +1,99 @@
+/*************************************************************************
+ *  Compilation:  javac RangeSearchVisualizer.java
+ *  Execution:    java RangeSearchVisualizer input.txt
+ *  Dependencies: PointSET.java KdTree.java Point2D.java RectHV.java
+ *                StdDraw.java In.java
+ *
+ *  Read points from a file (specified as a command-line arugment) and
+ *  draw to standard draw. Also draw all of the points in the rectangle
+ *  the user selects by dragging the mouse.
+ *
+ *  The range search results using the brute-force algorithm are drawn
+ *  in red; the results using the kd-tree algorithms are drawn in blue.
+ *
+ *************************************************************************/
+
+public class RangeSearchVisualizer {
+
+    public static void main(String[] args) {
+
+        String filename = args[0];
+        In in = new In(filename);
+
+
+        StdDraw.show(0);
+
+        // initialize the data structures with N points 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);
+        }
+
+        double x0 = 0.0, y0 = 0.0;      // initial endpoint of rectangle
+        double x1 = 0.0, y1 = 0.0;      // current location of mouse
+        boolean isDragging = false;     // is the user dragging a rectangle
+
+        // draw the points
+        StdDraw.clear();
+        StdDraw.setPenColor(StdDraw.BLACK);
+        StdDraw.setPenRadius(.01);
+        brute.draw();
+
+        while (true) {
+            StdDraw.show(40);
+
+            // user starts to drag a rectangle
+            if (StdDraw.mousePressed() && !isDragging) {
+                x0 = StdDraw.mouseX();
+                y0 = StdDraw.mouseY();
+                isDragging = true;
+                continue;
+            }
+
+            // user is dragging a rectangle
+            else if (StdDraw.mousePressed() && isDragging) {
+                x1 = StdDraw.mouseX();
+                y1 = StdDraw.mouseY();
+                continue;
+            }
+
+            // mouse no longer pressed
+            else if (!StdDraw.mousePressed() && isDragging) {
+                isDragging = false;
+            }
+
+
+            RectHV rect = new RectHV(Math.min(x0, x1), Math.min(y0, y1),
+                                     Math.max(x0, x1), Math.max(y0, y1));
+            // draw the points
+            StdDraw.clear();
+            StdDraw.setPenColor(StdDraw.BLACK);
+            StdDraw.setPenRadius(.01);
+            brute.draw();
+
+            // draw the rectangle
+            StdDraw.setPenColor(StdDraw.BLACK);
+            StdDraw.setPenRadius();
+            rect.draw();
+
+            // draw the range search results for brute-force data structure in red
+            StdDraw.setPenRadius(.03);
+            StdDraw.setPenColor(StdDraw.RED);
+            for (Point2D p : brute.range(rect))
+                p.draw();
+
+            // draw the range search results for kd-tree in blue
+            StdDraw.setPenRadius(.02);
+            StdDraw.setPenColor(StdDraw.BLUE);
+            for (Point2D p : kdtree.range(rect))
+                p.draw();
+
+            StdDraw.show(40);
+        }
+    }
+}
diff --git a/Algorithms/Part-I/5-KdTrees/RectHV.java b/Algorithms/Part-I/5-KdTrees/RectHV.java
new file mode 100644
index 0000000..583385d
--- /dev/null
+++ b/Algorithms/Part-I/5-KdTrees/RectHV.java
@@ -0,0 +1,88 @@
+/*************************************************************************
+ *  Compilation:  javac RectHV.java
+ *  Execution:    java RectHV
+ *  Dependencies: Point2D.java
+ *
+ *  Implementation of 2D axis-aligned rectangle.
+ *
+ *************************************************************************/
+
+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      (p.x() < xmin) dx = p.x() - xmin;
+        else if (p.x() > xmax) dx = p.x() - xmax;
+        if      (p.y() < ymin) dy = p.y() - ymin;
+        else if (p.y() > ymax) dy = p.y() - ymax;
+        return dx*dx + dy*dy;
+    }
+
+    // does this axis-aligned rectangle contain p?
+    public boolean contains(Point2D p) {
+        return (p.x() >= xmin) && (p.x() <= xmax)
+            && (p.y() >= ymin) && (p.y() <= 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 + "]";
+    }
+
+}
diff --git a/Algorithms/Part-I/5-KdTrees/run.sh b/Algorithms/Part-I/5-KdTrees/run.sh
new file mode 100755
index 0000000..04a4561
--- /dev/null
+++ b/Algorithms/Part-I/5-KdTrees/run.sh
@@ -0,0 +1,22 @@
+#! /bin/bash
+
+export "CLASSPATH=$CLASSPATH:.:$HOME/algs4/algs4.jar:$HOME/algs4/stdlib.jar"
+
+CLASSES="PointSET KdTree"
+
+rm *.class *.zip 2>/dev/null
+
+echo "javac RectHV.java" && javac RectHV.java
+for kls in $CLASSES; do
+    ~/algs4/bin/checkstyle ${kls}.java
+    echo "javac ${kls}.java" && javac ${kls}.java
+done
+~/algs4/bin/findbugs *.class
+
+echo "RUN..."
+for kls in KdTreeVisualizer NearestNeighborVisualizer RangeSearchVisualizer; do
+    echo "javac ${kls}.java" && javac ${kls}.java && java ${kls}
+done
+
+
+zip kdtree.zip PointSET.java KdTree.java