X-Git-Url: http://git.megacz.com/?p=anneal.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fqfat%2Fgeom%2FPointSet.java;h=11e48a224834d9f6afb0aa7fbe2ca71b20565dc5;hp=b69edb8c5b7b32556fdb6b39fb30afdb7940a3d7;hb=HEAD;hpb=0663e0593cddd90631fe5c82b160b80f8d4e8422

diff --git a/src/edu/berkeley/qfat/geom/PointSet.java b/src/edu/berkeley/qfat/geom/PointSet.java
index b69edb8..11e48a2 100644
--- a/src/edu/berkeley/qfat/geom/PointSet.java
+++ b/src/edu/berkeley/qfat/geom/PointSet.java
@@ -1,47 +1,85 @@
 package edu.berkeley.qfat.geom;
-import edu.wlu.cs.levy.CG.KDTree;
+import java.util.*;
 
-public class PointSet<V extends HasPoint> {
+/** a set of points, plus many useful methods operating over the set */
+public class PointSet<V extends HasPoint> implements Iterable<V> {
 
-    private /*final*/ KDTree kd = new KDTree(3);
-    private final double[] doubles = new double[3];
+    private RTree<V> rtree = new RTree<V>();
+
+    private HashMap<Point,V> exact = new HashMap<Point,V>();
+
+    public int size() { return exact.size(); }
+
+    public Iterator<V> iterator() { return rtree.iterator(); }
 
     public void clear() {
-        kd = new KDTree(3);
+        exact.clear();
+        rtree = new RTree<V>();
+    }
+
+    public V get(Point p) {
+        return exact.get(p);
     }
 
     public void add(V v) {
+        V x = get(v.getPoint());
+        if (x != null && x.equals(v)) return;
+        if (x != null) throw new Error("duplicates!");
         Point p = v.getPoint();
-        doubles[0] = p.x;
-        doubles[1] = p.y;
-        doubles[2] = p.z;
-        try {
-            kd.insert(doubles, v);
-        } catch (Exception e) {
-            throw new Error(e);
-        }
+        rtree.insert(v);
+        exact.put(p, v);
     }
 
-    public void remove(HasPoint v) { remove(v.getPoint()); }
-    public void remove(Point p) {
-        doubles[0] = p.x;
-        doubles[1] = p.y;
-        doubles[2] = p.z;
-        try {
-            kd.delete(doubles);
-        } catch (Exception e) { }
+    public void remove(V v) {
+        Point p = v.getPoint();
+        rtree.remove(v);
+        exact.remove(p);
+    }
+
+    public V nearest(Point p) { return nearest(p, null); }
+    public V nearest(Point p, Visitor<V> vis) {
+        if (exact.size()==0) return null;
+        return rtree.nearest(p, vis);
+    }
+
+    public Vec diagonal() {
+        float min_x = Float.MAX_VALUE;
+        float min_y = Float.MAX_VALUE;
+        float min_z = Float.MAX_VALUE;
+        float max_x = Float.MIN_VALUE;
+        float max_y = Float.MIN_VALUE;
+        float max_z = Float.MIN_VALUE;
+        for(V v : this) {
+            Point p = v.getPoint();
+            if (p.x < min_x) min_x = p.x;
+            if (p.y < min_y) min_y = p.y;
+            if (p.z < min_z) min_z = p.z;
+            if (p.x > max_x) max_x = p.x;
+            if (p.y > max_y) max_y = p.y;
+            if (p.z > max_z) max_z = p.z;
+        }
+        return new Vec(max_x - min_x, max_y - min_y, max_z - min_z);
     }
 
-    public V nearest(Point p) {
-        Object[] results;
-        try {
-            doubles[0] = p.x;
-            doubles[1] = p.y;
-            doubles[2] = p.z;
-            results = kd.nearest(doubles,1);
-        } catch (Exception e) {
-            throw new Error(e);
+    // FEATURE: compute incrementally?
+    public Point centroid() {
+        float min_x = Float.MAX_VALUE;
+        float min_y = Float.MAX_VALUE;
+        float min_z = Float.MAX_VALUE;
+        float max_x = Float.MIN_VALUE;
+        float max_y = Float.MIN_VALUE;
+        float max_z = Float.MIN_VALUE;
+        for(V v : this) {
+            Point p = v.getPoint();
+            if (p.x < min_x) min_x = p.x;
+            if (p.y < min_y) min_y = p.y;
+            if (p.z < min_z) min_z = p.z;
+            if (p.x > max_x) max_x = p.x;
+            if (p.y > max_y) max_y = p.y;
+            if (p.z > max_z) max_z = p.z;
         }
-        return (V)results[0];
+        return new Point((float)(max_x + min_x)/2,
+                     (float)(max_y + min_y)/2,
+                     (float)(max_z + min_z)/2);
     }
 }