checkpoint

[anneal.git] / src / Geom.java

diff --git a/src/Geom.java b/src/Geom.java
index 445c896..8c00066 100644 (file)
--- 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); }
@@ -191,20 +193,27 @@ public class Geom implements Iterable<Geom.T> {
     public class BindingGroup {
         public HashSet<E> es = new HashSet<E>();
         public BindingGroup() { }
-        public merge(E e) {
-            if (e.bg != null) merge(e.bg);
-            else { es.add(e); e.bg = this; }
+        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 merge(BindingGroup bg) {
+        public void merge(BindingGroup bg) {
             for(E e : bg.es) {
-                e.bg = this;
-                this.bg.add(e);
+                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
@@ -212,18 +221,10 @@ public class Geom implements Iterable<Geom.T> {
         E pair;  // partner half-edge
 
 
-        public BindingGroup bg = null;
+        public BindingGroup bg = new BindingGroup(this);
 
         public void bind(E e) { bind(e, new M()); }
-        public void bind(E e, M m) {
-            if (e.bg != null) e.bg.merge(this);
-            else if (bg != null) bg.merge(e);
-            else {
-                bg = new BindingGroup();
-                bg.merge(this);
-                bg.merge(e);
-            }
-        }
+        public void bind(E e, M m) { e.bg.add(this); }
 
         public void dobind() {
             if (bg==null) return;
@@ -234,21 +235,52 @@ public class Geom implements Iterable<Geom.T> {
             }
         }
 
-        public boolean destroyed = false;
-        public void shatter() {
-            if (destroyed) return;
-            /*
-            HashSet<E> eh = new HashSet<E>();
-            eh.add(this);
-            for(E ex = bound_to; ex != this; ex = ex.bound_to) eh.add(ex);
-            E[] es = (E[])eh.toArray(new E[0]);
-            */
-            destroy();
+        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();
-            for(E ex = bound_to; ex != this; ex = ex.bound_to) ex.shatter();
+            destroy();
+
+            newT(r, p1, mid);
+            newT(r, mid, p2);
+            bg1.add(p1.getE(mid));
+            bg2.add(mid.getE(p2));
+            return mid;
         }
+
+        public boolean destroyed = false;
         public void destroy() {
-            this.destroyed = true;
+            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() {
@@ -258,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; }
@@ -401,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();
+        }
+    }
 }