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         rect.set(v.getMinX(), v.getMinY(), v.getMinZ(), v.getMaxX(), v.getMaxY(), v.getMaxZ());
  58         rtree.delete(vToRect.get(v), id);
  59         vToRect.remove(v);
  60     }
  61
  62     public V nearest(Point p) { return nearest(p, null); }
  63     public V nearest(Point p, Visitor<V> ip) {
  64         point.set(p.x, p.y, p.z);
  65         this.visitor = ip;
  66         rtree.nearest(point, myIntProcedure, Float.POSITIVE_INFINITY);
  67         this.visitor = null;
  68         V ret = found;
  69         found = null;
  70         return ret;
  71     }
  72
  73     public void range(HasBoundingBox v, Visitor<V> vis) {
  74         visitor = vis;
  75         rect.set(v.getMinX(), v.getMinY(), v.getMinZ(), v.getMaxX(), v.getMaxY(), v.getMaxZ());
  76         rtree.intersects(rect, myIntProcedure);
  77         visitor = null;
  78     }
  79
  80     public void range(Point p1, Point p2, Visitor<V> vis) {
  81         visitor = vis;
  82         rect.set(p1.x, p1.y, p1.z, p2.x, p2.y, p2.z);
  83         rtree.intersects(rect, myIntProcedure);
  84         visitor = null;
  85     }
  86
  87     private class MyIntProcedure implements IntProcedure {
  88         public boolean execute(int id) {
  89             found = idToV.get(id);
  90             if (visitor != null) {
  91                 return visitor.visit(found);
  92             } else {
  93                 return false;
  94             }
  95         }
  96     }
  97 }