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