001package algs32.kdtree;
002import java.util.TreeSet;
003import algs12.Point2D;
004import stdlib.*;
005/* ***********************************************************************
006 *  Compilation:  javac RangeSearchVisualizer.java
007 *  Execution:    java RangeSearchVisualizer input.txt
008 *  Dependencies: PointSET.java KdTree.java Point2D.java RectHV.java
009 *                StdDraw.java In.java
010 *
011 *  Read points from a file (specified as a command-line arugment) and
012 *  draw to standard draw. Also draw all of the points in the rectangle
013 *  the user selects by dragging the mouse.
014 *
015 *  The range search results using the brute-force algorithm are drawn
016 *  in red; the results using the kd-tree algorithms are drawn in blue.
017 *
018 *************************************************************************/
019
020public class RangeSearchVisualizer {
021
022        public static void main(String[] args) {
023                //args = new String [] { "src/algs32/kdtree/kdtree-input10K.txt" };
024                //args = new String [] { "src/algs32/kdtree/kdtree-circle4.txt" };
025                //args = new String [] { "src/algs32/kdtree/kdtree-circle10.txt" };
026                //args = new String [] { "src/algs32/kdtree/kdtree-circle100.txt" };
027                //args = new String [] { "src/algs32/kdtree/kdtree-horizontal8.txt" };
028                //args = new String [] { "src/algs32/kdtree/kdtree-vertical7.txt" };
029                args = new String [] { "src/algs32/kdtree/kdtree-random500.txt" };
030
031                String filename = args[0];
032                In in = new In(filename);
033
034
035                StdDraw.show(0);
036
037                // initialize the data structures with N points from standard input
038                PointSET brute = new PointSET();
039                KdTree kdtree = new KdTree();
040                while (!in.isEmpty()) {
041                        double x = in.readDouble();
042                        double y = in.readDouble();
043                        Point2D p = new Point2D(x, y);
044                        kdtree.insert(p);
045                        brute.insert(p);
046                }
047
048                double x0 = 0.0, y0 = 0.0;      // initial endpoint of rectangle
049                double x1 = 0.0, y1 = 0.0;      // current location of mouse
050                boolean isDragging = false;     // is the user dragging a rectangle
051
052                // draw the points
053                StdDraw.clear();
054                StdDraw.setPenColor(StdDraw.BLACK);
055                StdDraw.setPenRadius(.01);
056                brute.draw();
057
058                while (true) {
059                        StdDraw.show(40);
060
061                        // user starts to drag a rectangle
062                        if (StdDraw.mousePressed() && !isDragging) {
063                                x0 = StdDraw.mouseX();
064                                y0 = StdDraw.mouseY();
065                                isDragging = true;
066                                continue;
067                        }
068
069                        // user is dragging a rectangle
070                        else if (StdDraw.mousePressed() && isDragging) {
071                                x1 = StdDraw.mouseX();
072                                y1 = StdDraw.mouseY();
073                                continue;
074                        }
075
076                        // mouse no longer pressed
077                        else if (!StdDraw.mousePressed() && isDragging) {
078                                isDragging = false;
079                        }
080
081
082                        RectHV rect = new RectHV(Math.min(x0, x1), Math.min(y0, y1),
083                                        Math.max(x0, x1), Math.max(y0, y1));
084                        // draw the points
085                        StdDraw.clear();
086                        StdDraw.setPenColor(StdDraw.BLACK);
087                        StdDraw.setPenRadius(.01);
088                        brute.draw();
089
090                        // draw the rectangle
091                        StdDraw.setPenColor(StdDraw.BLACK);
092                        StdDraw.setPenRadius();
093                        rect.draw();
094
095                        // draw the range search results for brute-force data structure in red
096                        StdDraw.setPenRadius(.03);
097                        StdDraw.setPenColor(StdDraw.RED);
098                        for (Point2D p : brute.range(rect))
099                                p.draw();
100
101                        // draw the range search results for kd-tree in blue
102                        StdDraw.setPenRadius(.02);
103                        StdDraw.setPenColor(StdDraw.BLUE);
104                        for (Point2D p : kdtree.range(rect))
105                                p.draw();
106
107                        StdDraw.show(40);
108
109                        // check to see that the results are the same
110                        TreeSet<Point2D> set = new TreeSet<> ();
111                        for (Point2D p : brute.range(rect))
112                                set.add (p);
113                        for (Point2D p : kdtree.range(rect))
114                                if (! set.remove (p)) StdOut.format ("KdTree has extra %s\n", p);
115                        for (Point2D p : set)
116                                StdOut.format ("KdTree missed %s\n", p);
117                }
118        }
119}