1 package edu.berkeley.qfat.geom;
2 import javax.media.opengl.*;
4 public class IntervalTree<V extends HasBoundingBox> {
7 private static final int X_AXIS = 0;
8 private static final int Y_AXIS = 1;
9 private static final int Z_AXIS = 2;
12 int axis; /* 0, 1, 2 */
18 public Node(V vthis, int axis) {
21 maxmax = getMax(vthis);
22 minmin = getMin(vthis);
25 private float getMin(V v) {
27 case X_AXIS: return v.getMinX();
28 case Y_AXIS: return v.getMinY();
29 case Z_AXIS: return v.getMinZ();
33 private float getMax(V v) {
35 case X_AXIS: return v.getMaxX();
36 case Y_AXIS: return v.getMaxY();
37 case Z_AXIS: return v.getMaxZ();
41 public Node insert(V vnew) {
43 if (getMax(vnew) > maxmax && getMin(vnew) < minmin) {
44 float diff = Math.abs(maxmax - getMax(vnew)) - Math.abs(minmin - getMin(vnew));
46 maxmax = getMax(vnew);
48 minmin = getMin(vnew);
51 if (getMax(vnew) <= maxmax) {
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;
58 } else if (getMin(vnew) >= minmin) {
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;
74 public void insert(V v) {
76 root = new Node(v, X_AXIS);
80 System.out.println(maxbias + " " + size);
86 public V nearest(Point p) {