-
Notifications
You must be signed in to change notification settings - Fork 0
/
KdTreeST.java
333 lines (304 loc) · 9.47 KB
/
KdTreeST.java
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
package a05;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.Stack;
/**
* Creates a k-dimensional binary tree of 2D points (keys)
* and their values (values).
*
* @author insanorcross, manyanair
* @param <Value> - value associated with the key
*/
public class KdTreeST<Value>
{
// Fields:
private Node root;
private int size;
/**
* Creates a <@code Node> that contains the key and value pair.
* It also keeps references to the left and right nodes of
* this node and whether the plane of the node is vertical
* or horizontal.
*/
private class Node
{
// Fields:
private Point2D key;
private Value val;
private Node left, right;
private boolean vertical = true; // Plane: vertical if true, horizontal if false
// Constructor:
public Node(Point2D key, Value val)
{
this.key = key;
this.val = val;
}
}
// Constructor creates empty kd tree
public KdTreeST()
{
root = null;
size = 0;
}
/**
* Returns whether the symbol table is empty or not.
*
* @return true if symbol table is empty, false otherwise.
*/
public boolean isEmpty()
{
return root == null;
}
/**
* Returns how many points are in the symbol table
*
* @return number of points
*/
public int size()
{
return size;
}
/**
* Associates the value <@code val> with point <@code p> by
* adding it to the kd tree.
*
* @param p - 2D point
* @param val - value associated with <@code p>
* @throws NullPointerException if <@code p> or <@code val> is null
*/
public void put(Point2D p, Value val)
{
// Corner case
if (p == null|| val == null)
throw new NullPointerException("Argument(s) to put() is (are) null");
// Override value if key already exists
if (this.contains(p))
this.get(p);
// Start comparison at root
root = put(root, p, val, true);
}
/**
* Private method to implement recursive method
* of finding the right place to insert the new node
* or override the value of an existing point (key).
* Accesses whether to go left or right down the kd tree based on
* if the current plane is vertical or horizontal.
*
* @param n - Current node
* @param p - new Point2D to be inserted
* @param val - new value to be inserted
* @param vertical - boolean whether the plane is vertical or horizontal
* @return Node on lower level
*/
private Node put(Node n, Point2D p, Value val, boolean vertical)
{
// Create new node if at bottom of tree
if (n == null)
{
Node temp = new Node(p, val);
temp.vertical = vertical;
size++;
return temp;
}
// Compare Node to add to current node
// Coordinates of node to insert
double x = p.x();
double y = p.y();
// Coordinates of current node
double nx = n.key.x();
double ny = n.key.y();
// Compare coordinates of points based on whether the plane is vertical or horizontal
if (n.vertical == true)
{
// Vertical plane -> compare x coordinates
if (x > nx)
n.right = put(n.right, p, val, !n.vertical);
else if (x < nx)
n.left = put(n.left, p, val, !n.vertical);
// x coordinates are the same, go right if y does not equal ny and override val if y equals ny
else if (y != ny)
n.right = put(n.right, p, val, !n.vertical);
else
n.val = val;
}
else
{
// Horizontal plane -> compare y coordinates
if (y > ny)
n.right = put(n.right, p, val, !n.vertical);
else if (y < ny)
n.left = put(n.left, p, val, !n.vertical);
// y coordinates are the same, go top (right) if x does not equal nx and override val if x equals nx
else if (x != nx)
n.right = put(n.right, p, val, !n.vertical);
else
n.val = val;
}
return n;
}
/**
* Gets the value associates with point <@code p>.
*
* @param p - 2D point
* @return - value associated with p
*/
public Value get(Point2D p)
{
// Corner case
if (p == null)
throw new NullPointerException("Argument to get() is null");
// Search tree for point
Node n = root;
while (n != null)
{
if (n.vertical == true)
{
// Vertical plane -> compare x coordinates
if (p.x() > n.key.x())
n = n.right;
else if (p.x() < n.key.x())
n = n.left;
// x coordinates are the same, check y coordinates
else if (p.y() != n.key.y())
n = n.right;
else return n.val; // Node found
}
else // horizontal plane -> compare y values
{
if (p.y() > n.key.y())
n = n.right;
else if (p.y() < n.key.y()) n = n.left;
// y coordinates are the same, check x coordinates
else if (p.x() != n.key.x()) n = n.right;
else return n.val; // Node found
}
}
// Point is not in tree
return null;
}
/**
* Returns whether the point <@code p> is in the symbol table.
*
* @param p - 2D point
* @return true if p is the the symbol table, false otherwise
*/
public boolean contains(Point2D p)
{
// Corner case
if (p == null)
{
throw new NullPointerException("Argument to contains() is null\n");
}
// Go through kd tree to find a match
Node n = root;
while (n != null)
{
if (n.vertical == true)
{
// Vertical plane -> compare x coordinates
if (p.x() > n.key.x())
n = n.right;
else if (p.x() < n.key.x())
n = n.left;
// x coordinates are the same, check y coordinates
else if (p.y() != n.key.y())
n = n.right;
else return true; // Node found
}
else // horizontal plane -> compare y values
{
if (p.y() > n.key.y())
n = n.right;
else if (p.y() < n.key.y()) n = n.left;
// y coordinates are the same, check x coordinates
else if (p.x() != n.key.x()) n = n.right;
else return true; // Node found
}
}
// Node is not in tree
return false;
}
/**
* Iterates through points in tree in level-order.
*
* @return Iterable of points in level-order
*/
public Iterable<Point2D> points()
{
Queue<Point2D> keys = new Queue<Point2D>();
Queue<Node> queue = new Queue<Node>();
queue.enqueue(root);
while (!queue.isEmpty())
{
Node x = queue.dequeue();
if (x == null) continue;
keys.enqueue(x.key);
queue.enqueue(x.left);
queue.enqueue(x.right);
}
return keys;
}
/**
* Returns all points that are inside the rectangle <@code rect>.
*
* @param rect - rectangle to find all points in
* @return Iterable of all points inside <@code rect>
*/
public Iterable<Point2D> range(RectHV rect)
{
// Corner case
if (rect == null)
throw new NullPointerException("the argument to range() is null\n");
// Find boundaries of rectangle
double xmin = rect.xmin();
double ymin = rect.ymin();
double xmax = rect.xmax();
double ymax = rect.ymax();
// Create stack to store points in the rectangle
Stack<Point2D> pointsInRect = new Stack<Point2D>();
// Iterate through all points in points and check if they are
// in the rectangle, add to stack if they are
for (Point2D p : points())
{
double x = p.x();
double y = p.y();
if (x >= xmin && x <= xmax && y >= ymin && y <= ymax)
pointsInRect.push(p);
}
// Return Stack of points that are in rectangle
return pointsInRect;
}
/**
* Returns nearest neighbor to point p; null if the symbol table is empty.
*
* @param p - Point2D
* @return point closest to <@code p>
*/
public Point2D nearest(Point2D p)
{
// Corner case
if (p == null)
throw new NullPointerException("Argument to nearest() is null");
// Return null if symbol table is empty
if (this.isEmpty())
return null;
// Assume first point is closest
Point2D nearestP = root.key;
double dist = nearestP.distanceSquaredTo(p);
// Check if any other point is closer
for (Point2D temp : points())
{
if (temp.distanceSquaredTo(p) < dist)
{
dist = temp.distanceSquaredTo(p);
nearestP = temp;
}
}
// Return nearest point
return nearestP;
}
// unit testing of the methods (optional)
public static void main(String[] args)
{ }
}