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     private static final Properties props = new Properties();
  19     static {
  20         props.put("MinNodeEntries", "1");
  21         props.put("MaxNodeEntries", "5");
  22     }
  23
  24     public RTree() { clear(); }
  25
  26     public void clear() {
  27         idToV.clear();
  28         vToId.clear();
  29         rtree.init(props);
  30     }
  31
  32     public void add(V v) { insert(v); }
  33     public void insert(V v) {
  34         int id = lowid++;
  35         idToV.put(id, v);
  36         vToId.put(v, id);
  37         rtree.add(new com.infomatiq.jsi.Rectangle(v.getMinX(), v.getMinY(), v.getMinZ(),
  38                                                   v.getMaxX(), v.getMaxY(), v.getMaxZ()),
  39                   id);
  40     }
  41
  42     public void remove(V v) {
  43         Integer idi = vToId.get(v);
  44         if (idi==null) return;
  45         int id = idi;
  46         idToV.remove(id);
  47         vToId.remove(v);
  48         rtree.delete(new com.infomatiq.jsi.Rectangle(v.getMinX(), v.getMinY(), v.getMinZ(),
  49                                                      v.getMaxX(), v.getMaxY(), v.getMaxZ()),
  50                      id);
  51     }
  52
  53     // gross...
  54     V found = null;
  55     private IntProcedure finder = new IntProcedure() {
  56             public boolean execute(int id) {
  57                 found = idToV.get(id);
  58                 return false;
  59             }
  60         };
  61
  62     public V nearest(Point p) {
  63         rtree.nearest(new com.infomatiq.jsi.Point(p.x, p.y, p.z), finder, Float.POSITIVE_INFINITY);
  64         V ret = found;
  65         found = null;
  66         return ret;
  67     }
  68
  69     Visitor<V> visitor = null;
  70     private IntProcedure searcher = new IntProcedure() {
  71             public boolean execute(int id) {
  72                 V v = idToV.get(id);
  73                 visitor.visit(v);
  74                 return true;
  75             }
  76         };
  77     public void range(HasBoundingBox v, Visitor vis) {
  78         visitor = vis;
  79         rtree.intersects(new com.infomatiq.jsi.Rectangle(v.getMinX(), v.getMinY(), v.getMinZ(),
  80                                                          v.getMaxX(), v.getMaxY(), v.getMaxZ()),
  81                          searcher);
  82         visitor = null;
  83     }
  84
  85 }