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