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