1
2
3
4
5
6 import java.util.*;
7
8 class NearestQuad
9 {
10 private Area bounds;
11 private Node tree;
12
13 public NearestQuad(Area bounds)
14 {
15 this.bounds = bounds;
16 this.tree = new Leaf(bounds);
17 }
18
19 public void addPoint(Point p)
20 {
21 tree = tree.insertPoint(p);
22 }
23
24
25 public Point findNearest(Point target, Area threshold)
26 {
27 List<Point> points = tree.getPoints(threshold);
28
29 int min = Integer.MAX_VALUE;
30 Point found = null;
31
32 for (Point p : points) {
33 int dist = target.distanceTo(p);
34 if (dist < min) {
35 min = dist;
36 found = p;
37 }
38 }
39
40 return found;
41 }
42 }
43
44 class Point
45 {
46 private int x;
47 private int y;
48
49 public Point(int x, int y)
50 {
51 this.x = x;
52 this.y = y;
53 }
54
55 public int getX()
56 {
57 return x;
58 }
59
60 public int getY()
61 {
62 return y;
63 }
64
65
66 public int distanceTo(Point p)
67 {
68 int dx = p.getX() - x;
69 int dy = p.getY() - y;
70
71 return Math.abs(dx) + Math.abs(dy);
72 }
73
74 public String toString()
75 {
76 return "(" + x + ", " + y + ")";
77 }
78 }
79
80 class Area
81 {
82 private Point min;
83 private Point max;
84
85 public Area(Point max)
86 {
87 this.min = new Point(0, 0);
88 this.max = max;
89 }
90
91 public Area(Point min, Point max)
92 {
93 this.min = min;
94 this.max = max;
95 }
96
97 public Point getMin()
98 {
99 return min;
100 }
101
102 public Point getMax()
103 {
104 return max;
105 }
106
107 public boolean contains(Point p)
108 {
109 if (p.getX() >= min.getX() && p.getX() < max.getX()) {
110 if (p.getY() >= min.getY() && p.getY() < max.getY()) {
111 return true;
112 }
113 }
114
115 return false;
116 }
117
118 public boolean intersects(Area a)
119 {
120 Point amin = a.getMin();
121 Point amax = a.getMax();
122
123 if (amax.getX() <= min.getX()) return false;
124 if (amin.getX() >= max.getX()) return false;
125 if (amax.getY() <= min.getY()) return false;
126 if (amin.getY() >= max.getY()) return false;
127
128 return true;
129 }
130
131
132 public List<Area> split()
133 {
134 List<Area> l = new ArrayList<Area>(4);
135
136 int midx = min.getX() + (max.getX() - min.getX()) / 2;
137 int midy = min.getY() + (max.getY() - min.getY()) / 2;
138
139
140 l.add(new Area(new Point(min.getX(), min.getY()), new Point(midx, midy)));
141
142
143 l.add(new Area(new Point(midx, min.getY()), new Point(max.getX(), midy)));
144
145
146 l.add(new Area(new Point(min.getX(), midy), new Point(midx, max.getY())));
147
148
149 l.add(new Area(new Point(midx, midy), new Point(max.getX(), max.getY())));
150
151 return l;
152 }
153
154 public String toString()
155 {
156 return "[" + min + " -> " + max + "]";
157 }
158 }
159
160 interface Node
161 {
162 public Node insertPoint(Point p);
163 public Area getBounds();
164 public List<Point> getPoints(Area threshold);
165 }
166
167 class Branch implements Node
168 {
169 private Area bounds;
170 private ArrayList<Node> children;
171
172 public Branch(Area bounds, ArrayList<Node> children)
173 {
174 if (children.size() != 4) {
175 throw new IllegalArgumentException("Expected exactly 4 children");
176 }
177
178 this.bounds = bounds;
179 this.children = children;
180 }
181
182 public Node insertPoint(Point p)
183 {
184 if (!bounds.contains(p)) {
185 throw new IllegalStateException("Can't add " + p + " to branch with bounds " + bounds);
186 }
187
188 for (int i = 0; i < children.size(); i++) {
189 Node n = children.get(i);
190
191 if (n.getBounds().contains(p)) {
192 n = n.insertPoint(p);
193 children.set(i, n);
194 return this;
195 }
196 }
197
198 throw new IllegalStateException("No child had bounds for " + p);
199 }
200
201 public Area getBounds()
202 {
203 return bounds;
204 }
205
206 public List<Point> getPoints(Area threshold)
207 {
208 List<Point> l = new ArrayList<Point>();
209
210 for (Node n : children)
211 {
212 if (n.getBounds().intersects(threshold)) {
213 l.addAll(n.getPoints(threshold));
214 }
215 }
216
217 return l;
218 }
219 }
220
221 class Leaf implements Node
222 {
223 Area bounds;
224 List<Point> points;
225
226 public Leaf(Area bounds)
227 {
228 this.bounds = bounds;
229 this.points = new ArrayList<Point>(4);
230 }
231
232 public Node insertPoint(Point p)
233 {
234 if (!bounds.contains(p)) {
235 throw new IllegalStateException("Can't add " + p + " to leaf with bounds " + bounds);
236 }
237
238 if (points.size() < 4) {
239
240 points.add(p);
241 return this;
242 }
243
244
245 List<Area> corners = bounds.split();
246 ArrayList<Node> children = new ArrayList<Node>(4);
247
248 for (Area a : corners)
249 {
250 Node n = new Leaf(a);
251
252 for (Point exist : points) {
253 if (a.contains(exist)) {
254 n = n.insertPoint(exist);
255 }
256 }
257
258 if (a.contains(p)) {
259 n = n.insertPoint(p);
260 }
261
262 children.add(n);
263 }
264
265 return new Branch(bounds, children);
266 }
267
268 public Area getBounds()
269 {
270 return bounds;
271 }
272
273 public List<Point> getPoints(Area threshold)
274 {
275 List<Point> l = new ArrayList<Point>();
276
277 for (Point p : points)
278 {
279 if (threshold.contains(p)) l.add(p);
280 }
281
282 return l;
283 }
284 }