blob: 781782f5d89680d38a7ccf3e31b4199572959340 (
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
/*************************************************************************
* Compilation: javac RangeSearchVisualizer.java
* Execution: java RangeSearchVisualizer input.txt
* Dependencies: PointSET.java KdTree.java Point2D.java RectHV.java
* StdDraw.java In.java
*
* Read points from a file (specified as a command-line arugment) and
* draw to standard draw. Also draw all of the points in the rectangle
* the user selects by dragging the mouse.
*
* The range search results using the brute-force algorithm are drawn
* in red; the results using the kd-tree algorithms are drawn in blue.
*
*************************************************************************/
public class RangeSearchVisualizer {
public static void main(String[] args) {
String filename = args[0];
In in = new In(filename);
StdDraw.show(0);
// initialize the data structures with N points 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);
}
double x0 = 0.0, y0 = 0.0; // initial endpoint of rectangle
double x1 = 0.0, y1 = 0.0; // current location of mouse
boolean isDragging = false; // is the user dragging a rectangle
// draw the points
StdDraw.clear();
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(.01);
brute.draw();
while (true) {
StdDraw.show(40);
// user starts to drag a rectangle
if (StdDraw.mousePressed() && !isDragging) {
x0 = StdDraw.mouseX();
y0 = StdDraw.mouseY();
isDragging = true;
continue;
}
// user is dragging a rectangle
else if (StdDraw.mousePressed() && isDragging) {
x1 = StdDraw.mouseX();
y1 = StdDraw.mouseY();
continue;
}
// mouse no longer pressed
else if (!StdDraw.mousePressed() && isDragging) {
isDragging = false;
}
RectHV rect = new RectHV(Math.min(x0, x1), Math.min(y0, y1),
Math.max(x0, x1), Math.max(y0, y1));
// draw the points
StdDraw.clear();
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(.01);
brute.draw();
// draw the rectangle
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius();
rect.draw();
// draw the range search results for brute-force data structure in red
StdDraw.setPenRadius(.03);
StdDraw.setPenColor(StdDraw.RED);
for (Point2D p : brute.range(rect))
p.draw();
// draw the range search results for kd-tree in blue
StdDraw.setPenRadius(.02);
StdDraw.setPenColor(StdDraw.BLUE);
for (Point2D p : kdtree.range(rect))
p.draw();
StdDraw.show(40);
}
}
}
|
