blob: 97cd1e442b451c18fdd0380b8cb4e9e8b4fa2f24 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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);
}
}
}
|
