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