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}