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}