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     private int lowid = 0;
  13     private HashMap<Integer, V> idToV = new HashMap<Integer, V>();
  14     private 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         rect.set(v.getMinX(), v.getMinY(), v.getMinZ(), v.getMaxX(), v.getMaxY(), v.getMaxZ());
  38         rtree.add(rect, id);
  39     }
  40
  41     private com.infomatiq.jsi.Rectangle rect = new com.infomatiq.jsi.Rectangle(0,0,0,0,0,0);
  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         rect.set(v.getMinX(), v.getMinY(), v.getMinZ(), v.getMaxX(), v.getMaxY(), v.getMaxZ());
  49         rtree.delete(rect, id);
  50     }
  51
  52     // gross...
  53     V found = null;
  54     private IntProcedure finder = new IntProcedure() {
  55             public boolean execute(int id) {
  56                 found = idToV.get(id);
  57                 return false;
  58             }
  59         };
  60
  61     public V nearest(Point p) {
  62         rtree.nearest(new com.infomatiq.jsi.Point(p.x, p.y, p.z), finder, Float.POSITIVE_INFINITY);
  63         V ret = found;
  64         found = null;
  65         return ret;
  66     }
  67
  68     Visitor<V> visitor = null;
  69     private IntProcedure searcher = new IntProcedure() {
  70             public boolean execute(int id) {
  71                 V v = idToV.get(id);
  72                 visitor.visit(v);
  73                 return true;
  74             }
  75         };
  76     public void range(HasBoundingBox v, Visitor vis) {
  77         visitor = vis;
  78         rtree.intersects(new com.infomatiq.jsi.Rectangle(v.getMinX(), v.getMinY(), v.getMinZ(),
  79                                                          v.getMaxX(), v.getMaxY(), v.getMaxZ()),
  80                          searcher);
  81         visitor = null;
  82     }
  83
  84 }