001package algs32.kdtree;
002import algs12.Point2D;
003import stdlib.*;
004/* ***********************************************************************
005 *  Compilation:  javac NearestNeighborVisualizer.java
006 *  Execution:    java NearestNeighborVisualizer input.txt
007 *  Dependencies: PointSET.java KdTree.java Point2D.java In.java StdDraw.java
008 *
009 *  Read points from a file (specified as a command-line argument) and
010 *  draw to standard draw. Highlight the closest point to the mouse.
011 *
012 *  The nearest neighbor according to the brute-force algorithm is drawn
013 *  in red; the nearest neighbor using the kd-tree algorithm is drawn in blue.
014 *
015 *************************************************************************/
016
017public class NearestNeighborVisualizer {
018
019        public static void main(String[] args) {
020                //args = new String [] { "src/algs32/kdtree/kdtree-input10K.txt" };
021                //args = new String [] { "src/algs32/kdtree/kdtree-circle4.txt" };
022                args = new String [] { "src/algs32/kdtree/kdtree-circle10.txt" };
023                //args = new String [] { "src/algs32/kdtree/kdtree-circle100.txt" };
024                //args = new String [] { "src/algs32/kdtree/kdtree-horizontal8.txt" };
025                //args = new String [] { "src/algs32/kdtree/kdtree-vertical7.txt" };
026
027                String filename = args[0];
028                In in = new In(filename);
029
030                StdDraw.show(0);
031
032                // initialize the two data structures with point from standard input
033                PointSET brute = new PointSET();
034                KdTree kdtree = new KdTree();
035                while (!in.isEmpty()) {
036                        double x = in.readDouble();
037                        double y = in.readDouble();
038                        Point2D p = new Point2D(x, y);
039                        kdtree.insert(p);
040                        brute.insert(p);
041                }
042
043                while (true) {
044
045                        // the location (x, y) of the mouse
046                        double x = StdDraw.mouseX();
047                        double y = StdDraw.mouseY();
048                        Point2D query = new Point2D(x, y);
049                        // query = new Point2D(.5, .5);
050                        Point2D b = brute.nearest(query);
051                        Point2D k = kdtree.nearest (query);
052                        double diff = query.distanceTo(b) - query.distanceTo (k);
053                        if (diff != 0.0) StdOut.format ("diff = %f\n", diff);
054
055                        // draw all of the points
056                        StdDraw.clear();
057                        StdDraw.setPenColor(StdDraw.BLACK);
058                        StdDraw.setPenRadius(.01);
059                        brute.draw();
060                        query.draw();
061
062                        // draw in red the nearest neighbor according to the brute-force algorithm
063                        StdDraw.setPenRadius(.03);
064                        StdDraw.setPenColor(StdDraw.RED);
065                        b.draw();
066
067                        // draw in blue the nearest neighbor according to the kd-tree algorithm
068                        StdDraw.setPenRadius(.02);
069                        StdDraw.setPenColor(StdDraw.BLUE);
070                        k.draw();
071
072                        StdDraw.show(0);
073                        StdDraw.show(40);
074                }
075        }
076}