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