src/edu/berkeley/qfat/geom/IntervalTree.java

   1 package edu.berkeley.qfat.geom;
   2 import javax.media.opengl.*;
   3
   4 public class IntervalTree<V extends HasBoundingBox> {
   5
   6
   7     private static final int X_AXIS = 0;
   8     private static final int Y_AXIS = 1;
   9     private static final int Z_AXIS = 2;
  10
  11     private class Node {
  12         int axis; /* 0, 1, 2 */
  13         V vthis;
  14         float maxmax, minmin;
  15         Node small, large;
  16         float bias = 0;
  17
  18         public Node(V vthis, int axis) {
  19             this.vthis = vthis;
  20             this.axis = axis;
  21             maxmax = getMax(vthis);
  22             minmin = getMin(vthis);
  23         }
  24
  25         private float getMin(V v) {
  26             switch(axis) {
  27                 case X_AXIS: return v.getMinX();
  28                 case Y_AXIS: return v.getMinY();
  29                 case Z_AXIS: return v.getMinZ();
  30             }
  31             throw new Error();
  32         }
  33         private float getMax(V v) {
  34             switch(axis) {
  35                 case X_AXIS: return v.getMaxX();
  36                 case Y_AXIS: return v.getMaxY();
  37                 case Z_AXIS: return v.getMaxZ();
  38             }
  39             throw new Error();
  40         }
  41         public Node insert(V vnew) {
  42             // FIXME bias
  43             if (getMax(vnew) > maxmax && getMin(vnew) < minmin) {
  44                 float diff = Math.abs(maxmax - getMax(vnew)) - Math.abs(minmin - getMin(vnew));
  45                 if (diff < 0) {
  46                     maxmax = getMax(vnew);
  47                 } else {
  48                     minmin = getMin(vnew);
  49                 }
  50             }
  51             if (getMax(vnew) <= maxmax) {
  52                 right++;
  53                 small = small == null ? new Node(vnew, (axis+1)%3) : small.insert(vnew);
  54                 bias = (left - right) / (float)(left + right);
  55                 if (Math.abs(bias) > Math.abs(maxbias)) maxbias = bias;
  56                 return this;
  57
  58             } else if (getMin(vnew) >= minmin) {
  59                 left++;
  60                 large = large == null ? new Node(vnew, (axis+1)%3) : large.insert(vnew);
  61                 bias = (left - right) / (float)(left + right);
  62                 if (Math.abs(bias) > Math.abs(maxbias)) maxbias = bias;
  63                 return this;
  64             }
  65
  66             throw new Error();
  67         }
  68         int left=0, right=0;
  69
  70     }
  71
  72     private Node root;
  73
  74     public void insert(V v) {
  75         if (root==null) {
  76             root = new Node(v, X_AXIS);
  77         } else {
  78             root.insert(v);
  79         }
  80         System.out.println(maxbias + " " + size);
  81         size++;
  82     }
  83     int size = 0;
  84     float maxbias = 0;
  85
  86     public V nearest(Point p) {
  87         return null;
  88     }
  89
  90 }