X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2FGeom.java;h=8c00066cf2cde1760da589d9d1e594082a9dbebe;hb=212e1516923584fac360e0084d38291cc99bef74;hp=42abd82b039ef1fd01ec3049e35efa33814fdd93;hpb=1a864cc577c2b31049cd46f4fd9ed703802d7d17;p=anneal.git

diff --git a/src/Geom.java b/src/Geom.java
index 42abd82..8c00066 100644
--- a/src/Geom.java
+++ b/src/Geom.java
@@ -14,7 +14,9 @@ public class Geom implements Iterable<Geom.T> {
     public static Random random = new Random();
 
     private HashMap<P,P> ps = new HashMap<P,P>();
-    private HashSet<T>   ts = new HashSet<T>();
+    public PriorityQueue<E>   es = new PriorityQueue<E>();
+    //private HashSet<T>   ts = new HashSet<T>();
+    public ArrayList<T>   ts = new ArrayList<T>();
 
     public Iterator<T> iterator() { return ts.iterator(); }
 
@@ -25,7 +27,7 @@ public class Geom implements Iterable<Geom.T> {
         if (p2 != null) return p2;
         ps.put(p,p);
         p.name = allname++;
-        try { kd.insert(new double[]{p.x,p.y,p.z},p); } catch (Exception e) { throw new Error(e); }
+        //try { kd.insert(new double[]{p.x,p.y,p.z},p); } catch (Exception e) { throw new Error(e); }
         return p;
     }
     
@@ -136,14 +138,14 @@ public class Geom implements Iterable<Geom.T> {
         public P(float x, float y, float z) {
             this.x = x; this.y = y; this.z = z;
         }
-
+        /*
         public P nearest() {
             Object[] results;
             try { results = kd.nearest(new double[]{x,y,z},2); } catch (Exception e) { throw new Error(e); }
             if (results[0] != this) throw new Error();
             return (P)results[1];
         }
-
+        */
         public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
         public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
         public P times(M m) { return m.apply(this); }
@@ -188,8 +190,30 @@ public class Geom implements Iterable<Geom.T> {
         public String toString() { return "<"+x+","+y+","+z+">"; }
     }
 
+    public class BindingGroup {
+        public HashSet<E> es = new HashSet<E>();
+        public BindingGroup() { }
+        public BindingGroup(E e) { es.add(e); }
+        public void add(E e) {
+            if (e.bg != null) { merge(e.bg); return; }
+            es.add(e);
+            e.bg = this;
+        }
+        public void merge(BindingGroup bg) {
+            for(E e : bg.es) {
+                e.bg = null;
+                add(e);
+            }
+        }
+    }
+
     /** [UNIQUE] an edge */
-    public final class E {
+    public final class E implements Comparable<E> {
+
+        public int compareTo(E e) {
+            return e.length() > length() ? 1 : -1;
+        }
+
         public final P p1, p2;
         T t;     // triangle to our "left"
         E prev;  // previous half-edge
@@ -197,27 +221,66 @@ public class Geom implements Iterable<Geom.T> {
         E pair;  // partner half-edge
 
 
-        public E bound_to = this;
-        public M bound_m  = new M();
+        public BindingGroup bg = new BindingGroup(this);
 
         public void bind(E e) { bind(e, new M()); }
-        public void bind(E e2, M m) {
-            E e1 = this;
-            while(e1.bound_to != e1) e1 = e1.bound_to;
-            while(e2.bound_to != e2) e2 = e2.bound_to;
-            e1.bound_to = e2;
-        }
+        public void bind(E e, M m) { e.bg.add(this); }
 
         public void dobind() {
-            if (bound_to == this) return;
-            E ex = this;
-            M m = new M();
-            while(ex.bound_to != ex) { m = m.times(ex.bound_m); ex = ex.bound_to; }
-            p1.bind(ex.bound_to.p1);
-            p2.bind(ex.bound_to.p2);
+            if (bg==null) return;
+            for(E ex : bg.es) {
+                if (ex==this) continue;
+                p1.bind(ex.p1);
+                p2.bind(ex.p2);
+            }
+        }
+
+        boolean shattered = false;
+        public P shatter() { return shatter(midpoint(), null, null); }
+        public P shatter(P mid, BindingGroup bg1, BindingGroup bg2) {
+            if (shattered) return mid;
+            shattered = true;
+
+            P r = next.p2;
+            E next = this.next;
+            E prev = this.prev;
+
+            if (bg1==null) bg1 = new BindingGroup();
+            if (bg2==null) bg2 = new BindingGroup();
+            for(E e : bg.es) e.shatter(e.midpoint(), bg1, bg2);
+            pair.shatter();
+            destroy();
+
+            newT(r, p1, mid);
+            newT(r, mid, p2);
+            bg1.add(p1.getE(mid));
+            bg2.add(mid.getE(p2));
+            return mid;
         }
 
-        public void shatter() {
+        public boolean destroyed = false;
+        public void destroy() {
+            if (destroyed) return;
+            destroyed = true;
+            pair.destroyed = true;
+            if (next.t != null) ts.remove(next.t);
+            if (prev.t != null) ts.remove(prev.t);
+            if (pair.next.t != null) ts.remove(pair.next.t);
+            if (pair.prev.t != null) ts.remove(pair.prev.t);
+            next.t = null;
+            prev.t = null;
+            pair.next.t = null;
+            pair.prev.t = null;
+            this.bg = null;
+            pair.bg = null;
+            pair.prev.next = next;
+            next.prev = pair.prev;
+            prev.next = pair.next;
+            pair.next = prev;
+            if (p1.e == this) p1.e = prev.next;
+            if (pair.p1.e == pair) pair.p1.e = pair.prev.next;
+            es.remove(this);
+            es.remove(pair);
         }
 
         private void sync() {
@@ -227,6 +290,7 @@ public class Geom implements Iterable<Geom.T> {
             if (this.next.p1 != p2) throw new Error();
             if (this.prev.p2 != p1) throw new Error();
             if (this.p1.e == null) this.p1.e = this;
+            es.add(this);
         }
 
         public T makeT() { return t==null ? (t = new T(this)) : t; }
@@ -370,4 +434,20 @@ public class Geom implements Iterable<Geom.T> {
         public M times(M m) { return this; }
     }
 
+    public void unbind() {
+        /*
+        for(Geom.T t : this) {
+            t.p1().unbind();
+            t.p2().unbind();
+            t.p3().unbind();
+        }
+        */
+    }
+    public void bind() {
+        for(Geom.T t : this) {
+            t.e1().dobind();
+            t.e2().dobind();
+            t.e3().dobind();
+        }
+    }
 }