src/edu/berkeley/qfat/geom/RTree.java

   1 package edu.berkeley.qfat.geom;
   2 import javax.media.opengl.*;
   3 import java.util.*;
   4 import com.infomatiq.jsi.*;
   5 import com.infomatiq.jsi.rtree.*;
   6
   7 public class RTree<V extends HasBoundingBox> implements Iterable<V> {
   8
   9     private com.infomatiq.jsi.rtree.RTree rtree =
  10         new com.infomatiq.jsi.rtree.RTree();
  11
  12     int lowid = 0;
  13     HashMap<Integer, V> idToV = new HashMap<Integer, V>();
  14     HashMap<V, Integer> vToId = new HashMap<V, Integer>();
  15
  16     public Iterator<V> iterator() { return vToId.keySet().iterator(); }
  17
  18     public RTree() {
  19         Properties props = new Properties();
  20         props.put("MinNodeEntries", "1");
  21         props.put("MaxNodeEntries", "5");
  22         rtree.init(props);
  23     }
  24
  25     public void add(V v) { insert(v); }
  26     public void insert(V v) {
  27         int id = lowid++;
  28         idToV.put(id, v);
  29         vToId.put(v, id);
  30         rtree.add(new com.infomatiq.jsi.Rectangle(v.getMinX(), v.getMinY(), v.getMinZ(),
  31                                                   v.getMaxX(), v.getMaxY(), v.getMaxZ()),
  32                   id);
  33     }
  34
  35     public void remove(V v) {
  36         Integer idi = vToId.get(v);
  37         if (idi==null) return;
  38         int id = idi;
  39         idToV.remove(id);
  40         vToId.remove(v);
  41         rtree.delete(new com.infomatiq.jsi.Rectangle(v.getMinX(), v.getMinY(), v.getMinZ(),
  42                                                      v.getMaxX(), v.getMaxY(), v.getMaxZ()),
  43                      id);
  44     }
  45
  46     // gross...
  47     V found = null;
  48     private IntProcedure finder = new IntProcedure() {
  49             public boolean execute(int id) {
  50                 found = idToV.get(id);
  51                 return false;
  52             }
  53         };
  54
  55     public V nearest(Point p) {
  56         rtree.nearest(new com.infomatiq.jsi.Point(p.x, p.y, p.z), finder, Float.POSITIVE_INFINITY);
  57         V ret = found;
  58         found = null;
  59         return ret;
  60     }
  61
  62     Visitor<V> visitor = null;
  63     private IntProcedure searcher = new IntProcedure() {
  64             public boolean execute(int id) {
  65                 V v = idToV.get(id);
  66                 visitor.visit(v);
  67                 return true;
  68             }
  69         };
  70     public void range(HasBoundingBox v, Visitor vis) {
  71         visitor = vis;
  72         rtree.intersects(new com.infomatiq.jsi.Rectangle(v.getMinX(), v.getMinY(), v.getMinZ(),
  73                                                          v.getMaxX(), v.getMaxY(), v.getMaxZ()),
  74                          searcher);
  75         visitor = null;
  76     }
  77
  78 }