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