source: josm/trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java@ 2197

Last change on this file since 2197 was 2197, checked in by stoecker, 15 years ago

fix 3587 - patch by Dave Hansen - NPE
File size: 28.8 KB
Line 
1package org.openstreetmap.josm.data.osm;
2import java.util.ArrayList;
3import java.util.Collection;
4import java.util.Collections;
5import java.util.Set;
6import java.util.SortedMap;
7import java.util.TreeMap;
8
9import org.openstreetmap.josm.data.coor.EastNorth;
10import org.openstreetmap.josm.data.osm.Node;
11import org.openstreetmap.josm.tools.Pair;
12
13import java.nio.MappedByteBuffer;
14import java.nio.DoubleBuffer;
15import java.nio.channels.FileChannel;
16import java.io.FileOutputStream;
17import java.io.RandomAccessFile;
18
19import java.io.IOException;
20import java.io.BufferedReader;
21import java.io.InputStreamReader;
22
23import java.util.Map.Entry;
24import java.awt.geom.Point2D;
25
26//import java.util.List;
27import java.util.*;
28import java.util.Collection;
29
30import org.openstreetmap.josm.data.coor.QuadTiling;
31import org.openstreetmap.josm.data.coor.CachedLatLon;
32import org.openstreetmap.josm.data.coor.EastNorth;
33import org.openstreetmap.josm.data.coor.LatLon;
34import org.openstreetmap.josm.data.osm.visitor.Visitor;
35
36
37public class QuadBuckets implements Collection<Node>
38{
39 public static boolean debug = false;
40 static boolean consistency_testing = false;
41
42 static void abort(String s)
43 {
44 out(s);
45 Object o = null;
46 o.hashCode();
47 }
48 static void out(String s)
49 {
50 System.out.println(s);
51 }
52 // periodic output
53 long last_out = -1;
54 void pout(String s)
55 {
56 long now = System.currentTimeMillis();
57 if (now - last_out < 300)
58 return;
59 last_out = now;
60 System.out.print(s + "\r");
61 }
62 void pout(String s, int i, int total)
63 {
64 long now = System.currentTimeMillis();
65 if ((now - last_out < 300) &&
66 ((i+1) < total))
67 return;
68 last_out = now;
69 // cast to float to keep the output size down
70 System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done \r");
71 }
72 // 24 levels of buckets gives us bottom-level
73 // buckets that are about 2 meters on a side.
74 // That should do. :)
75 public static int NR_LEVELS = 24;
76 public static double WORLD_PARTS = (1 << NR_LEVELS);
77
78 public static int MAX_OBJECTS_PER_LEVEL = 16;
79 // has to be a power of 2
80 public static int TILES_PER_LEVEL_SHIFT = 2;
81 public static int TILES_PER_LEVEL = 1<<TILES_PER_LEVEL_SHIFT;
82 class BBox
83 {
84 private double xmin;
85 private double xmax;
86 private double ymin;
87 private double ymax;
88 void sanity()
89 {
90 if (xmin < -180.0)
91 xmin = -180.0;
92 if (xmax > 180.0)
93 xmax = 180.0;
94 if (ymin < -90.0)
95 ymin = -90.0;
96 if (ymax > 90.0)
97 ymax = 90.0;
98 if ((xmin < -180.0) ||
99 (xmax > 180.0) ||
100 (ymin < -90.0) ||
101 (ymax > 90.0)) {
102 out("bad BBox: " + this);
103 Object o = null;
104 o.hashCode();
105 }
106 }
107 public String toString()
108 {
109 return "[ " + xmin + " -> " + xmax + ", " +
110 ymin + " -> " + ymax + " ]";
111 }
112 double min(double a, double b)
113 {
114 if (a < b)
115 return a;
116 return b;
117 }
118 double max(double a, double b)
119 {
120 if (a > b)
121 return a;
122 return b;
123 }
124 public BBox(LatLon a, LatLon b)
125 {
126 xmin = min(a.lon(), b.lon());
127 xmax = max(a.lon(), b.lon());
128 ymin = min(a.lat(), b.lat());
129 ymax = max(a.lat(), b.lat());
130 sanity();
131 }
132 public BBox(double a_x, double a_y, double b_x, double b_y)
133 {
134 xmin = min(a_x, b_x);
135 xmax = max(a_x, b_x);
136 ymin = min(a_y, b_y);
137 ymax = max(a_y, b_y);
138 sanity();
139 }
140 public double height()
141 {
142 return ymax-ymin;
143 }
144 public double width()
145 {
146 return xmax-xmin;
147 }
148 boolean bounds(BBox b)
149 {
150 if (!(xmin <= b.xmin) ||
151 !(xmax >= b.xmax) ||
152 !(ymin <= b.ymin) ||
153 !(ymax >= b.ymax))
154 return false;
155 return true;
156 }
157 boolean bounds(LatLon c)
158 {
159 if ((xmin <= c.lon()) &&
160 (xmax >= c.lon()) &&
161 (ymin <= c.lat()) &&
162 (ymax >= c.lat()))
163 return true;
164 return false;
165 }
166 boolean inside(BBox b)
167 {
168 if (xmin >= b.xmax)
169 return false;
170 if (xmax <= b.xmin)
171 return false;
172 if (ymin >= b.ymax)
173 return false;
174 if (ymax <= b.ymin)
175 return false;
176 return true;
177 }
178 boolean intersects(BBox b)
179 {
180 return this.inside(b) || b.inside(this);
181 }
182 }
183 class QBLevel
184 {
185 int level;
186 long quad;
187 QBLevel parent;
188
189 public List<Node> content;
190 public QBLevel children[];
191 public QBLevel(QBLevel parent)
192 {
193 init(parent);
194 }
195 String quads(Node n)
196 {
197 return Long.toHexString(QuadTiling.quadTile(n.getCoor()));
198 }
199 void split()
200 {
201 if (debug)
202 out("splitting "+this.bbox()+" level "+level+" with "
203 + content.size() + " entries (my dimensions: "
204 + this.bbox.width()+", "+this.bbox.height()+")");
205 if (children != null) {
206 abort("overwrote children");
207 }
208 children = new QBLevel[QuadTiling.TILES_PER_LEVEL];
209 // deferring allocation of children until use
210 // seems a bit faster
211 //for (int i = 0; i < TILES_PER_LEVEL; i++)
212 // children[i] = new QBLevel(this, i);
213 List<Node> tmpcontent = content;
214 content = null;
215 for (Node n : tmpcontent) {
216 int new_index = QuadTiling.index(n, level);
217 if (children[new_index] == null)
218 children[new_index] = new QBLevel(this, new_index);
219 QBLevel child = children[new_index];
220 if (debug)
221 out("putting "+n+"(q:"+quads(n)+") into ["+new_index+"] " + child.bbox());
222 child.add(n);
223 }
224 }
225 void add_leaf(Node n)
226 {
227 LatLon c = n.getCoor();
228 QBLevel ret = this;
229 if (content == null) {
230 if (debug)
231 out(" new content array");
232 // I chose a LinkedList because we do not do
233 // any real random access to this. We generally
234 // just run through the whole thing all at once
235 content = new LinkedList<Node>();
236 }
237 content.add(n);
238 if (content.size() > MAX_OBJECTS_PER_LEVEL) {
239 if (debug)
240 out("["+level+"] deciding to split");
241 if (level >= NR_LEVELS-1) {
242 out("can not split, but too deep: " + level + " size: " + content.size());
243 return;
244 }
245 int before_size = -1;
246 if (consistency_testing)
247 before_size = this.size();
248 this.split();
249 if (consistency_testing) {
250 int after_size = this.size();
251 if (before_size != after_size) {
252 abort("["+level+"] split done before: " + before_size + " after: " + after_size);
253 }
254 }
255 return;
256 }
257 if (debug) {
258 out(" plain content put now have " + content.size());
259 if (content.contains(c))
260 out(" and I already have that one");
261 }
262 }
263
264 List<Node> search(BBox bbox, LatLon point, double radius)
265 {
266 if (isLeaf())
267 return search_leaf(bbox, point, radius);
268 return search_branch(bbox, point, radius);
269 }
270 private List<Node> search_leaf(BBox bbox, LatLon point, double radius)
271 {
272 if (debug)
273 out("searching contents in tile " + this.bbox() + " for " + bbox);
274 /*
275 * It is possible that this was created in a split
276 * but never got any content populated.
277 */
278 if (content == null)
279 return null;
280 // We could delay allocating this. But, the way it is currently
281 // used, we almost always have a node in the area that we're
282 // searching since we're searching around other nodes.
283 //
284 // the iterator's calls to ArrayList.size() were showing up in
285 // some profiles, so I'm trying a LinkedList instead
286 List<Node> ret = new LinkedList<Node>();
287 for (Node n : content) {
288 // This supports two modes: one where the bbox is just
289 // an outline of the point/radius combo, and one where
290 // it is *just* the bbox. If it is *just* the bbox,
291 // don't consider the points below
292 if (point == null) {
293 ret.add(n);
294 continue;
295 }
296 LatLon c = n.getCoor();
297 // is greatCircleDistance really necessary?
298 double d = c.greatCircleDistance(point);
299 if (debug)
300 out("[" + level + "] Checking coor: " + c + " dist: " + d + " vs. " + radius + " " + quads(n));
301 if (d > radius)
302 continue;
303 if (debug)
304 out("hit in quad: "+Long.toHexString(this.quad)+"\n");
305 //if (ret == null)
306 // ret = new LinkedList<Node>();
307 ret.add(n);
308 }
309 if (debug)
310 out("done searching quad " + Long.toHexString(this.quad));
311 return ret;
312 }
313 /*
314 * This is stupid. I tried to have a QBLeaf and QBBranch
315 * class decending from a QBLevel. It's more than twice
316 * as slow. So, this throws OO out the window, but it
317 * is fast. Runtime type determination must be slow.
318 */
319 boolean isLeaf()
320 {
321 if (children == null)
322 return true;
323 return false;
324 }
325 QBLevel next_sibling()
326 {
327 boolean found_me = false;
328 if (parent == null)
329 return null;
330 int __nr = 0;
331 for (QBLevel sibling : parent.children) {
332 __nr++;
333 int nr = __nr-1;
334 if (sibling == null) {
335 if (debug)
336 out("[" + this.level + "] null child nr: " + nr);
337 continue;
338 }
339 // We're looking for the *next* child
340 // after us.
341 if (sibling == this) {
342 if (debug)
343 out("[" + this.level + "] I was child nr: " + nr);
344 found_me = true;
345 continue;
346 }
347 if (found_me) {
348 if (debug)
349 out("[" + this.level + "] next sibling was child nr: " + nr);
350 return sibling;
351 }
352 if (debug)
353 out("[" + this.level + "] nr: " + nr + " is before me, ignoring...");
354 }
355 return null;
356 }
357 QBLevel nextLeaf()
358 {
359 QBLevel next = this;
360 if (this.isLeaf()) {
361 QBLevel sibling = next.next_sibling();
362 // Walk back up the tree to find the
363 // next sibling node. It may be either
364 // a leaf or branch.
365 while (sibling == null) {
366 if (debug)
367 out("no siblings at level["+next.level+"], moving to parent");
368 next = next.parent;
369 if (next == null)
370 break;
371 sibling = next.next_sibling();
372 }
373 next = sibling;
374 }
375 if (next == null)
376 return null;
377 // all branches are guaranteed to have
378 // at least one leaf. It may not have
379 // any contents, but there *will* be a
380 // leaf. So, walk back down the tree
381 // and find the first leaf
382 while (!next.isLeaf()) {
383 if (debug)
384 out("["+next.level+"] next node is a branch, moving down...");
385 for (QBLevel child : next.children) {
386 if (child == null)
387 continue;
388 next = child;
389 break;
390 }
391 }
392 return next;
393 }
394 int size()
395 {
396 if (isLeaf())
397 return size_leaf();
398 return size_branch();
399 }
400 private int size_leaf()
401 {
402 if (content == null) {
403 if (debug)
404 out("["+level+"] leaf size: null content, children? " + children);
405 return 0;
406 }
407 if (debug)
408 out("["+level+"] leaf size: " + content.size());
409 return content.size();
410 }
411 private int size_branch()
412 {
413 int ret = 0;
414 for (QBLevel l : children) {
415 if (l == null)
416 continue;
417 ret += l.size();
418 }
419 if (debug)
420 out("["+level+"] branch size: " + ret);
421 return ret;
422 }
423 boolean contains(Node n)
424 {
425 QBLevel res = find_exact(n);
426 if (res == null)
427 return false;
428 return true;
429 }
430 QBLevel find_exact(Node n)
431 {
432 if (isLeaf())
433 return find_exact_leaf(n);
434 return find_exact_branch(n);
435 }
436 QBLevel find_exact_leaf(Node n)
437 {
438 QBLevel ret = null;
439 if (content != null && content.contains(n))
440 ret = this;
441 return ret;
442 }
443 QBLevel find_exact_branch(Node n)
444 {
445 QBLevel ret = null;
446 for (QBLevel l : children) {
447 if (l == null)
448 continue;
449 ret = l.find_exact(n);
450 if (ret != null)
451 break;
452 }
453 return ret;
454 }
455 boolean add(Node n)
456 {
457 if (isLeaf())
458 add_leaf(n);
459 else
460 add_branch(n);
461 return true;
462 }
463 QBLevel add_branch(Node n)
464 {
465 LatLon c = n.getCoor();
466 int index = QuadTiling.index(n, level);
467 if (debug)
468 out("[" + level + "]: " + n +
469 " index " + index + " levelquad:" + this.quads() + " level bbox:" + this.bbox());
470 if (debug)
471 out(" put in child["+index+"]");
472 if (children[index] == null)
473 children[index] = new QBLevel(this, index);
474 children[index].add(n);
475 /* this is broken at the moment because we need to handle the null n.getCoor()
476 if (consistency_testing && !children[index].bbox().bounds(n.getCoor())) {
477 out("target child["+index+"] does not bound " + children[index].bbox() + " " + c);
478 for (int i = 0; i < children.length; i++) {
479 QBLevel ch = children[i];
480 if (ch == null)
481 continue;
482 out("child["+i+"] quad: " + ch.quads() + " bounds: " + ch.bbox.bounds(n.getCoor()));
483 }
484 out(" coor quad: " + quads(n));
485 abort("");
486 }*/
487
488 if (consistency_testing) {
489 for (int i = 0; i < children.length; i++) {
490 QBLevel ch = children[i];
491 if (ch == null)
492 continue;
493 if (ch.bbox().bounds(c) && i != index) {
494 out("multible bounding?? expected: " + index + " but saw at " + i + " " + ch.quads());
495 out("child["+i+"] bbox: " + ch.bbox());
496 }
497 }
498 }
499 return this;
500 }
501 private List<Node> search_branch(BBox bbox, LatLon point, double radius)
502 {
503 List<Node> ret = null;
504 if (debug)
505 System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
506 if (!this.bbox().intersects(bbox)) {
507 if (debug) {
508 out("miss " + Long.toHexString(this.quad));
509 //QuadTiling.tile2xy(this.quad);
510 }
511 return ret;
512 }
513 if (debug)
514 out("hit " + this.quads());
515
516 if (debug)
517 out("[" + level + "] not leaf, moving down");
518 int child_nr = 0;
519 for (QBLevel q : children) {
520 if (q == null)
521 continue;
522 child_nr++;
523 if (debug)
524 System.out.print(child_nr+": ");
525 List<Node> coors = q.search(bbox, point, radius);
526 if (coors == null)
527 continue;
528 if (ret == null)
529 ret = coors;
530 else
531 ret.addAll(coors);
532 if (q.bbox().bounds(bbox)) {
533 search_cache = q;
534 // optimization: do not continue searching
535 // other tiles if this one wholly contained
536 // what we were looking for.
537 if (coors.size() > 0 ) {
538 if (debug)
539 out("break early");
540 break;
541 }
542 }
543 }
544 return ret;
545 }
546 public String quads()
547 {
548 return Long.toHexString(quad);
549 }
550 public void init(QBLevel parent)
551 {
552 this.parent = parent;
553 if (parent != null)
554 this.level = parent.level + 1;
555 this.quad = 0;
556 }
557 int index_of(QBLevel find_this)
558 {
559 if (this.isLeaf())
560 return -1;
561
562 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
563 if (children[i] == find_this)
564 return i;
565 }
566 return -1;
567 }
568 public QBLevel(QBLevel parent, int parent_index)
569 {
570 this.init(parent);
571 this.level = parent.level+1;
572 this.parent = parent;
573 int shift = (QuadBuckets.NR_LEVELS - level) * 2;
574 long mult = 1;
575 // Java blows the big one. It seems to wrap when
576 // you shift by > 31
577 if (shift >= 30) {
578 shift -= 30;
579 mult = 1<<30;
580 }
581 long this_quadpart = mult * (parent_index << shift);
582 this.quad = parent.quad | this_quadpart;
583 if (debug)
584 out("new level["+this.level+"] bbox["+parent_index+"]: " + this.bbox()
585 + " coor: " + this.coor()
586 + " quadpart: " + Long.toHexString(this_quadpart)
587 + " quad: " + Long.toHexString(this.quad));
588 }
589 /*
590 * Surely we can calculate these efficiently instead of storing
591 */
592 double width = Double.NEGATIVE_INFINITY;
593 double width()
594 {
595 if (width != Double.NEGATIVE_INFINITY)
596 return this.width;
597 if (level == 0) {
598 width = this.bbox().width();
599 } else {
600 width = parent.width()/2;
601 }
602 return width;
603 }
604 double height()
605 {
606 return width()/2;
607 }
608 BBox bbox = null;
609 public BBox bbox()
610 {
611 if (bbox != null) {
612 bbox.sanity();
613 return bbox;
614 }
615 if (level == 0) {
616 bbox = new BBox(-180, 90, 180, -90);
617 } else {
618 LatLon bottom_left = this.coor();
619 double lat = bottom_left.lat() + this.height();
620 double lon = bottom_left.lon() + this.width();
621 LatLon top_right = new LatLon(lat, lon);
622 bbox = new BBox(bottom_left, top_right);
623 }
624 bbox.sanity();
625 return bbox;
626 }
627 /*
628 * This gives the coordinate of the bottom-left
629 * corner of the box
630 */
631 LatLon coor()
632 {
633 return QuadTiling.tile2LatLon(this.quad);
634 }
635 }
636
637 private QBLevel root;
638 private QBLevel search_cache;
639 public QuadBuckets()
640 {
641 clear();
642 }
643 public void clear()
644 {
645 root = new QBLevel(null);
646 search_cache = null;
647 if (debug)
648 out("QuadBuckets() cleared: " + this);
649 }
650 public boolean add(Node n)
651 {
652 if (debug)
653 out(this + " QuadBuckets() add: " + n + " size now: " + this.size());
654 int before_size = -1;
655 if (consistency_testing)
656 before_size = root.size();
657 boolean ret = root.add(n);
658 if (consistency_testing) {
659 int end_size = root.size();
660 if (ret)
661 end_size--;
662 if (before_size != end_size)
663 abort("size inconsistency before add: " + before_size + " after: " + end_size);
664 }
665 return ret;
666 }
667 public void unsupported()
668 {
669 out("unsupported operation");
670 throw new UnsupportedOperationException();
671 }
672 public boolean retainAll(Collection nodes)
673 {
674 for (Node n : this) {
675 if (nodes.contains(n))
676 continue;
677 if (!this.remove(n))
678 return false;
679 }
680 return true;
681 }
682 public boolean removeAll(Collection nodes)
683 {
684 for (Object o : nodes) {
685 if (!(o instanceof Node))
686 return false;
687 Node n = (Node)o;
688 if (!this.remove(n))
689 return false;
690 }
691 return true;
692 }
693 public boolean addAll(Collection nodes)
694 {
695 for (Object o : nodes) {
696 if (!(o instanceof Node))
697 return false;
698 Node n = (Node)o;
699 if (!this.add(n))
700 return false;
701 }
702 return true;
703 }
704 public boolean containsAll(Collection nodes)
705 {
706 boolean ret = true;
707 for (Object o : nodes) {
708 if (!(o instanceof Node))
709 return false;
710 Node n = (Node)o;
711 if (!this.contains(n))
712 return false;
713 }
714 return true;
715 }
716 private void check_type(Object o)
717 {
718 if (o instanceof Node)
719 return;
720 unsupported();
721 }
722 public boolean remove(Object o)
723 {
724 check_type(o);
725 return this.remove((Node)o);
726 }
727 public boolean remove(Node n)
728 {
729 QBLevel bucket = root.find_exact(n);
730 if (!bucket.isLeaf())
731 abort("found branch where leaf expected");
732 return bucket.content.remove(n);
733 }
734 public boolean contains(Object o)
735 {
736 if (!(o instanceof Node))
737 return false;
738 QBLevel bucket = root.find_exact((Node)o);
739 if (bucket == null)
740 return false;
741 return true;
742 }
743 public ArrayList<Node> toArrayList()
744 {
745 ArrayList<Node> a = new ArrayList<Node>();
746 for (Node n : this)
747 a.add(n);
748 out("returning array list with size: " + a.size());
749 return a;
750 }
751 public Object[] toArray()
752 {
753 return this.toArrayList().toArray();
754 }
755 public <T> T[] toArray(T[] template)
756 {
757 return this.toArrayList().toArray(template);
758 }
759 class QuadBucketIterator implements Iterator<Node>
760 {
761 QBLevel current_leaf;
762 int index_in_leaf;
763 int iterated_over;
764 QBLevel next_leaf(QBLevel q)
765 {
766 if (q == null)
767 return null;
768 QBLevel orig = q;
769 QBLevel next = q.nextLeaf();
770 if (consistency_testing && (orig == next))
771 abort("got same leaf back leaf: " + q.isLeaf());
772 return next;
773 }
774 public QuadBucketIterator(QuadBuckets qb)
775 {
776 if (debug)
777 out(this + " is a new iterator qb.root: " + qb.root + " size: " + qb.size());
778 if (qb.root.isLeaf())
779 current_leaf = qb.root;
780 else
781 current_leaf = next_leaf(qb.root);
782 if (debug)
783 out("\titerator first leaf: " + current_leaf);
784 iterated_over = 0;
785 }
786 public boolean hasNext()
787 {
788 if (this.peek() == null) {
789 if (debug)
790 out(this + " no hasNext(), but iterated over so far: " + iterated_over);
791 return false;
792 }
793 return true;
794 }
795 Node peek()
796 {
797 if (current_leaf == null) {
798 if (debug)
799 out("null current leaf, nowhere to go");
800 return null;
801 }
802 while((current_leaf.content == null) ||
803 (index_in_leaf >= current_leaf.content.size())) {
804 if (debug)
805 out("moving to next leaf");
806 index_in_leaf = 0;
807 current_leaf = next_leaf(current_leaf);
808 if (current_leaf == null)
809 break;
810 }
811 if (current_leaf == null || current_leaf.content == null) {
812 if (debug)
813 out("late nowhere to go " + current_leaf);
814 return null;
815 }
816 return current_leaf.content.get(index_in_leaf);
817 }
818 public Node next()
819 {
820 Node ret = peek();
821 index_in_leaf++;
822 if (debug)
823 out("iteration["+iterated_over+"] " + index_in_leaf + " leaf: " + current_leaf);
824 iterated_over++;
825 if (ret == null) {
826 if (debug)
827 out(this + " no next node, but iterated over so far: " + iterated_over);
828 }
829 return ret;
830 }
831 public void remove()
832 {
833 // two uses
834 // 1. Back up to the thing we just returned
835 // 2. move the index back since we removed
836 // an element
837 index_in_leaf--;
838 current_leaf.content.remove(index_in_leaf);
839 }
840 }
841 public Iterator<Node> iterator()
842 {
843 return new QuadBucketIterator(this);
844 }
845 public int size()
846 {
847 // This can certainly by optimized
848 int ret = root.size();
849 if (debug)
850 out(this + " QuadBuckets size: " + ret);
851 return ret;
852 }
853 public boolean isEmpty()
854 {
855 if (this.size() == 0)
856 return true;
857 return false;
858 }
859 public BBox search_to_bbox(LatLon point, double radius)
860 {
861 BBox bbox = new BBox(point.lon() - radius, point.lat() - radius,
862 point.lon() + radius, point.lat() + radius);
863 if (debug)
864 out("search bbox before sanity: " + bbox);
865 bbox.sanity();
866 if (debug)
867 out("search bbox after sanity: " + bbox);
868 return bbox;
869 }
870 List<Node> search(LatLon point, double radius)
871 {
872 return this.search(search_to_bbox(point, radius), point, radius);
873 }
874 List<Node> search(BBox bbox)
875 {
876 return this.search(bbox, null, -1);
877 }
878 public List<Node> search(LatLon b1, LatLon b2)
879 {
880 BBox bbox = new BBox(b1.lon(), b1.lat(), b2.lon(), b2.lat());
881 bbox.sanity();
882 return this.search(bbox);
883 }
884 List<Node> search(BBox bbox, LatLon point, double radius)
885 {
886 if (debug) {
887 out("qb root search at " + point + " around: " + radius);
888 out("root bbox: " + root.bbox());
889 }
890 List<Node> ret = null;
891 // Doing this cuts down search cost on a real-life data
892 // set by about 25%
893 boolean cache_searches = true;
894 if (cache_searches) {
895 if (search_cache == null)
896 search_cache = root;
897 // Walk back up the tree when the last
898 // search spot can not cover the current
899 // search
900 while (!search_cache.bbox().bounds(bbox)) {
901 search_cache = search_cache.parent;
902 }
903 } else {
904 search_cache = root;
905 }
906 return search_cache.search(bbox, point, radius);
907 }
908}
Note: See TracBrowser for help on using the repository browser.