1 package edu.berkeley.qfat.geom;
2 import edu.wlu.cs.levy.CG.KDTree;
5 public class PointSet<V extends HasPoint> implements Iterable<V> {
7 private final RTree<V> rtree = new RTree<V>();
9 private /*final*/ KDTree kd = new KDTree(3);
10 private final double[] doubles = new double[3];
12 public int size() { return exact.size(); }
13 private HashMap<Point,V> exact = new HashMap<Point,V>();
15 public Iterator<V> iterator() {
16 return exact.values().iterator();
20 exact = new HashMap<Point,V>();
23 public V get(Point p) {
27 public void rebuild() {
29 HashMap<Point,V> old_exact = exact;
30 exact = new HashMap<Point,V>();
32 for(V v : old_exact.values()) add(v);
36 public void add(V v) {
37 V x = get(v.getPoint());
38 if (x != null && x.equals(v)) return;
39 if (x != null) throw new Error("duplicates!");
40 Point p = v.getPoint();
46 kd.insert(doubles, v);
47 } catch (Exception e) {
55 public void remove(V v) {
56 Point p = v.getPoint();
63 } catch (Exception e) { }
69 public V nearest(Point p) {
70 if (exact.size()==0) return null;
77 results = kd.nearest(doubles,1);
78 } catch (Exception e) {
81 V kd_says = (V)results[0];
83 V rt_says = rtree.nearest(p);
84 //if (kd_says != rt_says) System.err.println("disagree: " + p + " " + kd_says + " " + rt_says);
89 public Vec diagonal() {
90 float min_x = Float.MAX_VALUE;
91 float min_y = Float.MAX_VALUE;
92 float min_z = Float.MAX_VALUE;
93 float max_x = Float.MIN_VALUE;
94 float max_y = Float.MIN_VALUE;
95 float max_z = Float.MIN_VALUE;
96 for(Point p : exact.keySet()) {
97 if (p.x < min_x) min_x = p.x;
98 if (p.y < min_y) min_y = p.y;
99 if (p.z < min_z) min_z = p.z;
100 if (p.x > max_x) max_x = p.x;
101 if (p.y > max_y) max_y = p.y;
102 if (p.z > max_z) max_z = p.z;
104 return new Vec(max_x - min_x, max_y - min_y, max_z - min_z);
107 public Point centroid() {
108 float min_x = Float.MAX_VALUE;
109 float min_y = Float.MAX_VALUE;
110 float min_z = Float.MAX_VALUE;
111 float max_x = Float.MIN_VALUE;
112 float max_y = Float.MIN_VALUE;
113 float max_z = Float.MIN_VALUE;
114 for(Point p : exact.keySet()) {
115 if (p.x < min_x) min_x = p.x;
116 if (p.y < min_y) min_y = p.y;
117 if (p.z < min_z) min_z = p.z;
118 if (p.x > max_x) max_x = p.x;
119 if (p.y > max_y) max_y = p.y;
120 if (p.z > max_z) max_z = p.z;
122 return new Point((float)(max_x + min_x)/2,
123 (float)(max_y + min_y)/2,
124 (float)(max_z + min_z)/2);