From ab67f7e8366d6ea5ce5798cb68394beed075585d Mon Sep 17 00:00:00 2001
From: adam <adam@megacz.com>
Date: Tue, 15 Feb 2005 12:19:19 +0000
Subject: [PATCH] fixed Mesh.java, made it really fast

darcs-hash:20050215121919-5007d-525fa45c4d4f5faa5731ae5dcf51adf4793780b5.gz
---
 src/org/ibex/core/Box.java      |    6 +-
 src/org/ibex/graphics/Mesh.java | 1076 +++++++++++++++------------------------
 2 files changed, 422 insertions(+), 660 deletions(-)

diff --git a/src/org/ibex/core/Box.java b/src/org/ibex/core/Box.java
index b68480f..8c312de 100644
--- a/src/org/ibex/core/Box.java
+++ b/src/org/ibex/core/Box.java
@@ -244,7 +244,11 @@ public final class Box extends JS.Obj implements Callable {
             } 
             // FIXME: texture
         } else {
-            if (mesh == null) mesh = new Mesh(new Polygon(path, Affine.identity()));
+            if (mesh == null) {
+                Log.warn(this, "generating mesh...");
+                mesh = new Mesh(new Polygon(path, Affine.identity()));
+                Log.warn(this, "  done generating mesh.");
+            }
             mesh.fill(buf, a, fillcolor, true, false);
             mesh.stroke(buf, a, strokecolor);
             //mesh.fill(buf, a, fillcolor, true, true);
diff --git a/src/org/ibex/graphics/Mesh.java b/src/org/ibex/graphics/Mesh.java
index 43875eb..12f71d7 100644
--- a/src/org/ibex/graphics/Mesh.java
+++ b/src/org/ibex/graphics/Mesh.java
@@ -13,79 +13,135 @@ import org.ibex.util.*;
  */
 public final class Mesh {
 
-    private static final double epsilon = (double)0.00000001;
-    private static final boolean debug = true;
+    //#define Vertex int
 
-    private              Vector vertices = new Vector();
-    private              Vector triangles = new Vector();
+    private static final float epsilon = (float)0.001;
+    private static final boolean debug = false;
 
-    public static double B = 5;
-    public static double Q = 0.4;
+    private              Vector triangles = new Vector();
 
-    // Utilities //////////////////////////////////////////////////////////////////////////////
+    public static float B = (float)5.0;
+    public static float Q = (float)0.4;
 
-    public static double distance(double x1, double y1, double x2, double y2) {
-        return (double)Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
-    }
-    public static int side(Vertex v1, Vertex v2, Vertex v3) { return side(v1, v2, v3.x, v3.y); }
-    public static int side(Vertex v1, Vertex v2, double x, double y) { return side(v1, v2.x, v2.y, x, y); }
-    public static int side(Vertex v1, double x, double y, Vertex v3) { return side(v1, x, y, v3.x, v3.y); }
-    public static int side(Vertex v1, double x, double y, double x2, double y2) {
-        double a = y-v1.y, b = v1.x-x, c = -1 * (a*v1.x+b*v1.y);
-        return (- (a*x2+c)/b > y2) ? -1 : (- (a*x2+c)/b < y2) ? 1 : 0;
+    public static Hashtable nexter = new Hashtable();
+    public static LinkedList next(Vertex v) {
+        LinkedList hs = (LinkedList)nexter.get(new Integer(v));
+        if (hs == null) nexter.put(new Integer(v), hs = new LinkedList());
+        return hs;
     }
 
-    public boolean isect(Vertex v1, Vertex v2, Vertex v3, Vertex v4) {
-        if (v1==v3 || v1==v4 || v2==v3 || v2==v4) return false;
-        double a = side(v1,v2,v3);
-        double b = side(v1,v2,v4);
-        double c = side(v3,v4,v1);
-        double d = side(v3,v4,v2);
-        return a!=b && c!=d && a!=0 && b!=0 && c!=0 && d!=0;
-    }
-
-    private void drawLine(PixelBuffer buf, double x1, double y1, double x2, double y2, Affine a, int color) {
-        buf.drawLine((int)a.multiply_px((float)x1, (float)y1),
-                     (int)a.multiply_py((float)x1, (float)y1),
-                     (int)a.multiply_px((float)x2, (float)y2),
-                     (int)a.multiply_py((float)x2, (float)y2),
-                     color);
-    }
-    public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, boolean strokeOnly) {
-        for (int i=0; i<triangles.size(); i++) ((Triangle)triangles.elementAt(i)).clear();
-        ((Triangle)triangles.elementAt(0)).fill(buf, a, color, evenOdd, 1, strokeOnly);
+    // Vertices //////////////////////////////////////////////////////////////////////////////
+
+    public Vertex v(float x, float y) {
+        if (numvertices >= this.x.length-1) {
+            if (debug) Log.debug(Mesh.class, "expanding vertex arrays from " + this.x.length + " to " + this.x.length*2);
+            float[] newx = new float[this.x.length * 2];
+            float[] newy = new float[this.y.length * 2];
+            System.arraycopy(this.x, 0, newx, 0, this.x.length);
+            System.arraycopy(this.y, 0, newy, 0, this.y.length);
+            this.x = newx;
+            this.y = newy;
+        }
+        this.x[numvertices] = x;
+        this.y[numvertices] = y;
+        return numvertices++;
     }
-    public void stroke(PixelBuffer buf, Affine a, int color) {
-        if (debug)
-            for (int i=0; i<vertices.size(); i++) {
-                Vertex v = (Vertex)vertices.elementAt(i);
-                for(Iterator it = v.next.iterator(); it.hasNext();) {
-                    Vertex v2 = (Vertex)it.next();
-                    drawLine(buf, v.x, v.y, v2.x, v2.y, a, 0xffff0000);
+    public int numvertices = 0;
+    public float x[] = new float[255];
+    public float y[] = new float[255];
+    public String s(Vertex v) { return "("+x(v)+","+y(v)+")"; }
+    public float  x(Vertex v) { return x[v]; }
+    public float  y(Vertex v) { return y[v]; }
+
+    public static final Vertex NULLVERTEX = -1;
+
+    public Vertex newVertex(float x, float y) {
+        Vertex ret = NULLVERTEX;
+        for(int k=0; k<numvertices; k++) {
+            Vertex v = k;
+            if (distance(v,x,y)<epsilon) if (ret==NULLVERTEX || distance(v,x,y) < distance(ret,x,y)) ret = v;
+        }
+        if (ret != NULLVERTEX) return ret;
+        Vector vec = new Vector();
+        boolean interior = false;
+        int edges = 0;
+        Vertex v = v(x,y);
+        if (numvertices<=2) return v;
+        if (numvertices==3) { newTriangle(0, 1, 2, "first three points"); return v; }
+        for(int i=0; i<triangles.size(); i++) {
+            Triangle t = (Triangle)triangles.elementAt(i);
+            if (t.contains(v)) {
+                Triangle t12 = t.t12;
+                Triangle t23 = t.t23;
+                Triangle t31 = t.t31;
+                t.delete();
+                vec.addElement(newTriangle(v, t.v1, t.v2, "vertexinsertion " + v));
+                vec.addElement(newTriangle(v, t.v3, t.v2, "vertexinsertion " + v));
+                vec.addElement(newTriangle(v, t.v1, t.v3, "vertexinsertion " + v));
+                //#repeat t23/t31/t12 v1/v2/v3 v2/v3/v1 v3/v1/v2
+            } else if (t.t23 != null && isect(t.v2, t.v3, v)) {
+                Triangle tt = t.t23;
+                Vertex va = tt.opposingVertex(t);
+                tt.delete();
+                t.delete();
+                vec.addElement(newTriangle(v, t.v1, t.v3, "vertexinsertion " + v));
+                vec.addElement(newTriangle(v, t.v1, t.v2, "vertexinsertion " + v));
+                vec.addElement(newTriangle(v, t.v3, va  , "vertexinsertion " + v));
+                vec.addElement(newTriangle(v, t.v2, va  , "vertexinsertion " + v));
+                //#end
+            } else {
+                continue;
+            }
+            fixup(vec, v);
+            return v;
+        }
+        boolean good = false;
+        while(true) {
+            for(int j=0; j<triangles.size(); j++) {
+                Triangle t = (Triangle)triangles.elementAt(j);
+                if (t.v1==v || t.v2==v || t.v3==v) continue;
+                //#repeat t12/t23/t31 v3/v1/v2 v2/v3/v1 v1/v2/v3
+                if (t.t12==null) {
+                    boolean bad = false;
+                    for(int k=0; k<triangles.size(); k++) {
+                        Triangle tt = (Triangle)triangles.elementAt(k);
+                        if (tt.intersectsSegment(v, t.v1)) { bad = true; break; }
+                        if (tt.intersectsSegment(v, t.v2)) { bad = true; break; }
+                    }
+                    if (!bad) {
+                        vec.addElement(newTriangle(v,t.v1,t.v2, "hull expansion"));
+                        good = true;
+                    }
                 }
+                //#end
             }
-        for (int i=0; i<triangles.size(); i++) {
-            Triangle t = ((Triangle)triangles.elementAt(i));
-            Vertex v1 = t.v1;
-            Vertex v2 = t.v2;
-            Vertex v3 = t.v3;
-            drawLine(buf, v1.x, v1.y, v2.x, v2.y, a, (debug && t.wind(v1,v2)!=0) ? 0xffffffff : color);
-            drawLine(buf, v3.x, v3.y, v2.x, v2.y, a, (debug && t.wind(v3,v2)!=0) ? 0xffffffff : color);
-            drawLine(buf, v1.x, v1.y, v3.x, v3.y, a, (debug && t.wind(v1,v3)!=0) ? 0xffffffff : color);
+            break;
         }
+        if (!good) throw new Error("couldn't figure out where to put " + s(v));
+        fixup(vec, v);
+        return v;
     }
 
-    // Static //////////////////////////////////////////////////////////////////////////////
-
-    public Vertex newVertex(double x, double y) {
-        Vertex ret = null;
-        for(int k=0; k<vertices.size(); k++) {
-            Vertex v = (Vertex)vertices.elementAt(k);
-            if (v.distance(x,y)<epsilon) if (ret==null || v.distance(x,y) < ret.distance(x,y)) ret = v;
+    public void fixup(Vector vec, Vertex v) {
+        while(vec.size() > 0) {
+            Triangle t = (Triangle)vec.lastElement();
+            vec.setSize(vec.size() - 1);
+            if (t.deleted) continue;
+            //if (t.wind(t.nextVertex(v), t.prevVertex(v)) != 0) continue;    // FIXME
+            Triangle to = t.opposingTriangle(v);
+            if (to==null)  continue; //throw new Error("fixup invoked with a triangle which does not have me as a vertex");
+            if (to.deleted) throw new Error("v should not happen");
+            if (to.r < distance(v,to.ccx, to.ccy)) continue;
+            Vertex v2 = to.opposingVertex(t);
+            t.delete();
+            to.delete();
+            vec.addElement(newTriangle(v, t.nextVertex(v), v2, "fixup"));
+            vec.addElement(newTriangle(v, t.prevVertex(v), v2, "fixup"));
         }
-        return ret==null ? new Vertex(x,y) : ret;
     }
 
+    // Static //////////////////////////////////////////////////////////////////////////////
+
     public Triangle newTriangle(Vertex v1, Vertex v2, Vertex v3, String source) {
         if (v1==v2 || v2==v3 || v3==v1) throw new Error("identical vertices");
         for(int i=0; i<triangles.size(); i++) {
@@ -105,15 +161,6 @@ public final class Mesh {
     public void checktri() {
         for(int i=0; i<triangles.size(); i++) {
             Triangle t = (Triangle)triangles.elementAt(i);
-                /*
-            for(int j=0; j<vertices.size(); j++) {
-                Vertex v = (Vertex)vertices.elementAt(j);
-                if (t.contains(v)) {
-                    t.special = true;
-                    throw new Error("triangle "+t+" contains vertex " + v);
-                }
-            }
-                */
             if (t.t12 != null && (t.t12.t12 != t && t.t12.t23 != t && t.t12.t31 != t)) throw new Error("t12");
             if (t.t23 != null && (t.t23.t12 != t && t.t23.t23 != t && t.t23.t31 != t)) throw new Error("t23");
             if (t.t31 != null && (t.t31.t12 != t && t.t31.t23 != t && t.t31.t31 != t)) throw new Error("t31");
@@ -132,323 +179,181 @@ public final class Mesh {
 
     // Vertex //////////////////////////////////////////////////////////////////////////////
 
-    private final class Vertex {
-        final double x, y;
-        LinkedList next = new LinkedList();
-        boolean forced = false;
-        public String toString() { return "("+x+","+y+")"; }
-        public double distance(Vertex v) { return distance(v.x, v.y); }
-        public double distance(double x, double y) { return Mesh.distance(this.x,this.y,x,y); }
-        public Vertex(double x, double y) {
-            this.x = x;
-            this.y = y;
-            vertices.addElement(this);
-            Vector vec = new Vector();
-            Vector vec2 = new Vector();
-            boolean interior = false;
-            int edges = 0;
-            Vertex v = this;
-            boolean good = false;
-            for(int i=0; i<triangles.size(); i++) {
-                Triangle t = (Triangle)triangles.elementAt(i);
-                if (good) throw new Error("impossible: Vertex() -> good twice");
-                if (t.contains(this)) {
-                    System.out.println(t + " contains me");
-                    Triangle t12 = t.t12;
-                    Triangle t23 = t.t23;
-                    Triangle t31 = t.t31;
-                    t.delete(vec);
-                    vec2.addElement(newTriangle(this, t.v1, t.v2, "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v3, t.v2, "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v1, t.v3, "vertexinsertion " + this));
-                    fixup(vec2);
-                    good = true;
-                    break;
-                } else if (t.t23 != null && v.intersectsSegment(t.v2, t.v3)) {
-                    System.out.println("on an edge");
-                    good = true;
-                    Triangle tt = t.t23;
-                    tt.delete(null);
-                    t.delete(null);
-                    Vertex va =
-                        ((tt.v1==t.v3&&tt.v2==t.v2)||(tt.v1==t.v2&&tt.v2==t.v3)) ? tt.v3 :
-                        ((tt.v2==t.v3&&tt.v3==t.v2)||(tt.v2==t.v2&&tt.v3==t.v3)) ? tt.v1 :
-                        ((tt.v1==t.v3&&tt.v3==t.v2)||(tt.v1==t.v2&&tt.v3==t.v3)) ? tt.v2 : null;
-                    vec2.addElement(newTriangle(this, t.v1, t.v3, "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v1, t.v2, "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v3, va  , "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v2, va  , "vertexinsertion " + this));
-                    fixup(vec2);
-                    break;
-                } else if (t.t31 != null && v.intersectsSegment(t.v1, t.v3)) {
-                    good = true;
-                    System.out.println("on an edge");
-                    Triangle tt = t.t31;
-                    tt.delete(null);
-                    t.delete(null);
-                    Vertex va =
-                        ((tt.v1==t.v1&&tt.v2==t.v3)||(tt.v1==t.v3&&tt.v2==t.v1)) ? tt.v3 :
-                        ((tt.v2==t.v1&&tt.v3==t.v3)||(tt.v2==t.v3&&tt.v3==t.v1)) ? tt.v1 :
-                        ((tt.v1==t.v1&&tt.v3==t.v3)||(tt.v1==t.v3&&tt.v3==t.v1)) ? tt.v2 : null;
-                    vec2.addElement(newTriangle(this, t.v2, t.v1, "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v2, t.v3, "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v1, va  , "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v3, va  , "vertexinsertion " + this));
-                    fixup(vec2);
-                    break;
-                } else if (t.t12 != null && v.intersectsSegment(t.v1, t.v2)) {
-                    System.out.println("on an edge");
-                    good = true;
-                    Triangle tt = t.t12;
-                    tt.delete(null);
-                    t.delete(null);
-                    Vertex va =
-                        ((tt.v1==t.v1&&tt.v2==t.v2)||(tt.v1==t.v2&&tt.v2==t.v1)) ? tt.v3 :
-                        ((tt.v2==t.v1&&tt.v3==t.v2)||(tt.v2==t.v2&&tt.v3==t.v1)) ? tt.v1 :
-                        ((tt.v1==t.v1&&tt.v3==t.v2)||(tt.v1==t.v2&&tt.v3==t.v1)) ? tt.v2 : null;
-                    vec2.addElement(newTriangle(this, t.v3, t.v1, "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v3, t.v2, "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v1, va  , "vertexinsertion " + this));
-                    vec2.addElement(newTriangle(this, t.v2, va  , "vertexinsertion " + this));
-                    fixup(vec2);
-                    break;
-                }
-            }
-            if (triangles.size() > 2 && !good)
-                throw new Error("vertex "+this+" did not fall within a triangle or on the edge of at least two");
-        }
-        public void fixup(Vector vec) {
-            while(vec.size() > 0) {
-                Triangle t = (Triangle)vec.lastElement();
-                vec.setSize(vec.size() - 1);
-                if (t.deleted) continue;
-                Triangle to = t.v1==this ? t.t23 : t.v2==this ? t.t31 : t.v3==this ? t.t12 : null;
-                if (to==null)  continue;
-                    //throw new Error("fixup invoked with a triangle which does not have me as a vertex");
-                if (to.deleted) throw new Error("this should not happen");
-                if (to.r < this.distance(to.ccx, to.ccy)) continue;
-                if (t.v1==this) {
-                    //if (t.v2.next.contains(t.v3)) continue;
-                    //if (t.v3.next.contains(t.v2)) continue;
-                    Vertex v =
-                        (to.v1!=t.v2 && to.v1!=t.v3) ? to.v1 :
-                        (to.v2!=t.v2 && to.v2!=t.v3) ? to.v2 :
-                        (to.v3!=t.v2 && to.v3!=t.v3) ? to.v3 : null;
-                    t.delete(null);
-                    to.delete(null);
-                    vec.addElement(newTriangle(this, t.v2, v, "fixup"));
-                    vec.addElement(newTriangle(this, t.v3, v, "fixup"));
-                } else if (t.v2==this) {
-                    //if (t.v3.next.contains(t.v1)) continue;
-                    //if (t.v1.next.contains(t.v3)) continue;
-                    Vertex v =
-                        (to.v1!=t.v1 && to.v1!=t.v3) ? to.v1 :
-                        (to.v2!=t.v1 && to.v2!=t.v3) ? to.v2 :
-                        (to.v3!=t.v1 && to.v3!=t.v3) ? to.v3 : null;
-                    t.delete(null);
-                    to.delete(null);
-                    vec.addElement(newTriangle(this, t.v1, v, "fixup"));
-                    vec.addElement(newTriangle(this, t.v3, v, "fixup"));
-                    
-                } else if (t.v3==this) {
-                    //if (t.v1.next.contains(t.v2)) continue;
-                    //if (t.v2.next.contains(t.v1)) continue;
-                    Vertex v =
-                        (to.v1!=t.v2 && to.v1!=t.v1) ? to.v1 :
-                        (to.v2!=t.v2 && to.v2!=t.v1) ? to.v2 :
-                        (to.v3!=t.v2 && to.v3!=t.v1) ? to.v3 : null;
-                    t.delete(null);
-                    to.delete(null);
-                    vec.addElement(newTriangle(this, t.v2, v, "fixup"));
-                    vec.addElement(newTriangle(this, t.v1, v, "fixup"));
-                } else {
-                    throw new Error("this should not happen");
-                }
-                System.out.println("> made a swap");
-            }
-        }
-
-        public boolean makeNonDegenerate(Vector vec) {
-            Vertex v1 = this;
-            for(int i2 = 0; i2<next.size(); i2++) {
-                Vertex v2 = (Vertex)next.get(i2);
-                for(int i3 = 0; i3<vertices.size(); i3++) {
-                    Vertex v3 = (Vertex)vertices.get(i3);
-                    for(int i4=0; i4<v3.next.size(); i4++) {
-                        Vertex v4 = (Vertex)v3.next.get(i4);
-                        if (v1==v3||v1==v4||v2==v3||v2==v4) continue;
-                        if (isect(v1,v2,v3,v4)) {
-                            double a1 = v2.y-v1.y;
-                            double a2 = v4.y-v3.y;
-                            double b1 = v1.x-v2.x;
-                            double b2 = v3.x-v4.x;
-                            double c1 = -1 * (a1*v1.x+b1*v1.y);
-                            double c2 = -1 * (a2*v3.x+b2*v3.y);
-                            // a1x+b1y+c1=0
-                            // y=-(a1x+c1)/b1
-                            // a2x-(a1x+c1)(b2/b1)+c2=0
-                            // a2b1x-b2(a1x+c1)+b1c2=0
-                            // a2b1x-a1b2x-b2c1+b1c2=0
-                            // x(a2b1-a1b2)-b2c1+b1c2=0
-                            // x(a2b1-a1b2)=b2c1-b1c2
-                            // x=(b2c1-b1c2)/(a2b1-a1b2)
-                            double xq = (b2*c1-c2*b1)/(b1*a2-b2*a1);
-                            Vertex v0 = newVertex(xq, -1 * (a1*xq+c1) / b1);
-                            //if (v0==v1||v0==v2||v0==v3||v0==v4) continue;
-                            System.out.println("inserting new vertex " + v0+" between " + v1+"-"+v2 +" and "+ v3+"-"+v4);
-                            v1.next.remove(v2);
-                            v1.next.add(v0);
-                            v0.next.add(v2);
-                            v3.next.remove(v4);
-                            v3.next.add(v0);
-                            v0.next.add(v4);
-                            return true;
-                        }
-                    }
+        public boolean triangulate(Vertex vv, HashSet orphans, Vertex v, boolean first) {
+            if (first) {
+                HashSet left = new HashSet();
+                HashSet right = new HashSet();
+                for(Iterator it=orphans.iterator(); it.hasNext();) {
+                    Vertex o = ((Integer)it.next()).intValue();
+                    if (o==v||o==vv) continue;
+                    if (side(vv, v, o) == -1) left.add(new Integer(o));
+                    else if (side(vv, v, o) == 1) right.add(new Integer(o));
+                    else throw new Error("impossible "+vv+" "+v + " " + o);
                 }
+                triangulate(vv, left, v, false);
+                triangulate(v, right, vv, false);
+                return false;
             }
-            return false;
-        }
-
-        public boolean force() {
-            if (forced) return false;
-            forced = true;
-            boolean ret = false;
-            OUTER: for(Iterator it=next.iterator(); it.hasNext();) {
-                Vertex v = (Vertex)it.next();
-
-                for(int k=0; k<vertices.size(); k++) {
-                    Vertex v2 = (Vertex)vertices.elementAt(k);
-                    if (v2==this||v2==v) continue;
-                    //if (next.contains(v2) || v2.next.contains(this)) continue;
-                    if (v2.intersectsSegment(v,this)) {
-                        System.out.println("breaking line " + this+"-"+v + " at vertex " + v2);
-                        next.remove(v);
-                        next.add(v2);
-                        v2.next.add(v);
-                        ret = true;
-                        break OUTER;
-                    }
-                }
-                boolean good = false;
-                for (int i=0; i<triangles.size(); i++) {
-                    Triangle t = ((Triangle)triangles.elementAt(i));
-                    if (t.v1==this && t.v2==v) { good = true; break; }
-                    if (t.v3==this && t.v1==v) { good = true; break; }
-                    if (t.v3==this && t.v2==v) { good = true; break; }
-                    if (t.v1==v && t.v2==this) { good = true; break; }
-                    if (t.v3==v && t.v1==this) { good = true; break; }
-                    if (t.v3==v && t.v2==this) { good = true; break; }
-                }
-                if (good) continue;
-                HashSet orphans = new HashSet();
-                for (int i=0; i<triangles.size(); i++) {
-                    Triangle t = ((Triangle)triangles.elementAt(i));
-                    if (t.deleted) continue;
-                    if (t.intersectsSegment(this, v)) {
-                        System.out.println("removing triangle " + t + " because it intersects segment " + this+"-"+v);
-                        Vector vec = new Vector();
-                        orphans.add(t.v1);
-                        orphans.add(t.v2);
-                        orphans.add(t.v3);
-                        orphans.remove(v);
-                        orphans.remove(this);
-                        t.delete(vec);
-                        i--;
-                        ret = true;
-                    }
-                }
-                orphans.remove(this);
-                orphans.remove(v);
-                triangulate(orphans, v);
-                break;
-            }
-            return ret;
-        }
-        public void triangulate(HashSet orphans, Vertex v) {
-            HashSet left = new HashSet();
-            HashSet right = new HashSet();
-            for(Iterator it=orphans.iterator(); it.hasNext();) {
-                Vertex o = (Vertex)it.next();
-                if (o==v||o==this) continue;
-                if (side(this, v, o) == -1) left.add(o);
-                else if (side(this, v, o) == 1) right.add(o);
-                else throw new Error("impossible "+this+" "+v + " " + o);
-            }
-            triangulate2(left, v, false);
-            v.triangulate2(right, this, false);
-        }
-        public boolean triangulate2(HashSet orphans, Vertex v, boolean skip) {
-            Vertex farthest = null;
-            double dist = 0;
-            System.out.println("orphans: " + orphans.size());
+            Vertex farthest = NULLVERTEX;
+            float dist = 0;
             if (orphans.size()==0) return true;
-            Vertex o = (Vertex)orphans.iterator().next();
+            Vertex o = ((Integer)orphans.iterator().next()).intValue();
             if (orphans.size()==1) {
-                Triangle t = newTriangle(this, v, o, "triangulate2 " + v + " " + this);
-                if (((t.v1==this && t.v2==v)||(t.v1==v && t.v2==this)) && t.t12==null) return true;
-                if (((t.v3==this && t.v2==v)||(t.v3==v && t.v2==this)) && t.t23==null) return true;
-                if (((t.v1==this && t.v3==v)||(t.v1==v && t.v3==this)) && t.t31==null) return true;
+                Triangle t = newTriangle(vv, v, o, "triangulate2 " + v + " " + vv);
+                if (((t.v1==vv && t.v2==v)||(t.v1==v && t.v2==vv)) && t.t12==null) return true;
+                if (((t.v3==vv && t.v2==v)||(t.v3==v && t.v2==vv)) && t.t23==null) return true;
+                if (((t.v1==vv && t.v3==v)||(t.v1==v && t.v3==vv)) && t.t31==null) return true;
                 return false;
             }
 
-            Vertex best = null;
+            Vertex best = NULLVERTEX;
             OUTER: for(Iterator it=orphans.iterator(); it.hasNext();) {
-                o = (Vertex)it.next();
+                o = ((Integer)it.next()).intValue();
                 if (o==v) continue;
-                Triangle t = new Triangle("temp", this, v, o, true);
+                Triangle t = new Triangle("temp", vv, v, o, true);
                 for(Iterator it2=orphans.iterator(); it2.hasNext();) {
-                    Vertex z = (Vertex)it2.next();
+                    Vertex z = ((Integer)it2.next()).intValue();
                     if (z==o) continue;
                     if (z==v) continue;
-                    if (z==this) continue;
-                    if (z.distance(t.ccx, t.ccy) < t.r || t.contains(z)) continue OUTER;
+                    if (z==vv) continue;
+                    if (distance(z,t.ccx,t.ccy) < t.r || t.contains(z)) continue OUTER;
                 }
-                if (best==null || new Triangle("temp",this,v,best,true).area() > new Triangle("temp",this,v,o,true).area())
+                if (best==NULLVERTEX || new Triangle("temp",vv,v,best,true).area() > new Triangle("temp",vv,v,o,true).area())
                     best = o;
             }
-            if (best==null) throw new Error("notgood, #orphans = " + orphans.size());
+            if (best==NULLVERTEX) throw new Error("notgood, #orphans = " + orphans.size());
             o = best;
             HashSet left = new HashSet();
             HashSet right = new HashSet();
             for(Iterator it2=orphans.iterator(); it2.hasNext();) {
-                Vertex x = (Vertex)it2.next();
-                if (o==x||this==x||v==x) continue;
-                int side_of_x    = side(o,(this.x+v.x)/2,(this.y+v.y)/2,x);
-                int side_of_v    = side(o,(this.x+v.x)/2,(this.y+v.y)/2,v);
-                int side_of_this = side(o,(this.x+v.x)/2,(this.y+v.y)/2,this);
-                if (side_of_x==side_of_this && side_of_this!=0) right.add(x);
-                else if (side_of_x==side_of_v && side_of_v!=0) left.add(x);
-                else throw new Error("impossible "+this+" "+v + " " + o + " ==> " + x);
+                Vertex x = ((Integer)it2.next()).intValue();
+                if (o==x||vv==x||v==x) continue;
+                int side_of_x    = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,x);
+                int side_of_v    = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,v);
+                int side_of_vv = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,vv);
+                if (side_of_x==side_of_vv && side_of_vv!=0) right.add(new Integer(x));
+                else if (side_of_x==side_of_v && side_of_v!=0) left.add(new Integer(x));
+                else throw new Error("impossible "+vv+" "+v + " " + o + " ==> " + x);
             }
             boolean doit = true;
-            doit &= o.triangulate2(left, v, false);
-            doit &= o.triangulate2(right, this, false);
+            doit &= triangulate(o, left, v, false);
+            doit &= triangulate(o, right, vv, false);
             if (doit) {
-                Triangle t = newTriangle(v, this, o,"triangulate 0/0");
-                if (((t.v1==this && t.v2==v)||(t.v1==v && t.v2==this)) && t.t12==null) return true;
-                if (((t.v3==this && t.v2==v)||(t.v3==v && t.v2==this)) && t.t23==null) return true;
-                if (((t.v1==this && t.v3==v)||(t.v1==v && t.v3==this)) && t.t31==null) return true;
+                Triangle t = newTriangle(v, vv, o,"triangulate 0/0");
+                if (((t.v1==vv && t.v2==v)||(t.v1==v && t.v2==vv)) && t.t12==null) return true;
+                if (((t.v3==vv && t.v2==v)||(t.v3==v && t.v2==vv)) && t.t23==null) return true;
+                if (((t.v1==vv && t.v3==v)||(t.v1==v && t.v3==vv)) && t.t31==null) return true;
                 return false;
             }
             return true;
         }
 
-        public int wind(Vertex v) {
-            if (v.next.contains(this) && next.contains(v)) return 0;
-            if (v.y < y || (v.y==y && v.x<x)) return v.wind(this);
-            if (next.contains(v)) return 1;
-            if (v.next.contains(this)) return -1;
-            return 0;
+    public void force() {
+        while(true) {
+            boolean redo = false;
+            for(int k=0; k<numvertices; k++) {
+                Vertex v = k;
+                redo |= force(v);
+            }
+            if (!redo) break;
+        }
+    }
+    public boolean force(Vertex vv) {
+        boolean ret = false;
+        OUTER: for(Iterator it=next(vv).iterator(); it.hasNext();) {
+            Vertex v = ((Integer)it.next()).intValue();
+            for(int k=0; k<numvertices; k++) {
+                Vertex v2 = k;
+                if (v2==vv||v2==v) continue;
+                //if (next(vv).contains(v2) || next(v2).contains(vv)) continue;
+                if (isect(v,vv,v2)) {
+                    if (debug) Log.debug(Mesh.class,"breaking line " + vv+"-"+v + " at vertex " + v2);
+                    next(vv).remove(new Integer(v));
+                    next(vv).add(new Integer(v2));
+                    next(v2).add(new Integer(v));
+                    ret = true;
+                    break OUTER;
+                }
+            }
+            boolean good = false;
+            for (int i=0; i<triangles.size(); i++)
+                if (((Triangle)triangles.elementAt(i)).hasEdge(vv,v)) { good = true; break; }
+            if (good) continue;
+            HashSet orphans = new HashSet();
+            for (int i=0; i<triangles.size(); i++) {
+                Triangle t = ((Triangle)triangles.elementAt(i));
+                if (t.deleted) continue;
+                if (t.intersectsSegment(vv, v)) {
+                    if (debug) Log.debug(Mesh.class,"removing triangle " + t + " because it intersects segment " + vv+"-"+v);
+                    Vector vec = new Vector();
+                    orphans.add(new Integer(t.v1));
+                    orphans.add(new Integer(t.v2));
+                    orphans.add(new Integer(t.v3));
+                    orphans.remove(new Integer(v));
+                    orphans.remove(new Integer(vv));
+                    t.delete();
+                    i--;
+                    ret = true;
+                }
+            }
+            orphans.remove(new Integer(vv));
+            orphans.remove(new Integer(v));
+            triangulate(vv, orphans, v, true);
+            break;
+        }
+        return ret;
+    }
+
+    public void makeNonDegenerate() {
+        while(true) {
+            boolean redo = false;
+            for(int k=0; k<numvertices; k++) {
+                Vector vec = new Vector();
+                Vertex vx = k;
+                redo |= makeNonDegenerate(vec, vx);
+            }
+            if (!redo) break;
         }
-        public boolean intersectsSegment(Vertex v1, Vertex v2) {
-            return
-                side(v1,v2,this)==0 &&
-                x - Math.max(v1.x,v2.x) < 0 &&
-                x - Math.min(v1.x,v2.x) > 0 &&
-                y - Math.max(v1.y,v2.y) < 0 &&
-                y - Math.min(v1.y,v2.y) > 0;
+    }
+    public boolean makeNonDegenerate(Vector vec, Vertex v1) {
+        for(int i2 = 0; i2<next(v1).size(); i2++) {
+            Vertex v2 = ((Integer)next(v1).get(i2)).intValue();
+            for(int i3 = 0; i3<numvertices; i3++) {
+                Vertex v3 = i3;
+                for(int i4=0; i4<next(v3).size(); i4++) {
+                    Vertex v4 = ((Integer)next(v3).get(i4)).intValue();
+                    if (v1==v3||v1==v4||v2==v3||v2==v4) continue;
+                    if (isect(v1,v2,v3,v4)) {
+                        float a1 = y(v2)-y(v1);
+                        float a2 = y(v4)-y(v3);
+                        float b1 = x(v1)-x(v2);
+                        float b2 = x(v3)-x(v4);
+                        float c1 = -1 * (a1*x(v1)+b1*y(v1));
+                        float c2 = -1 * (a2*x(v3)+b2*y(v3));
+                        // a1x+b1y+c1=0
+                        // y=-(a1x+c1)/b1
+                        // a2x-(a1x+c1)(b2/b1)+c2=0
+                        // a2b1x-b2(a1x+c1)+b1c2=0
+                        // a2b1x-a1b2x-b2c1+b1c2=0
+                        // x(a2b1-a1b2)-b2c1+b1c2=0
+                        // x(a2b1-a1b2)=b2c1-b1c2
+                        // x=(b2c1-b1c2)/(a2b1-a1b2)
+                        float xq = (b2*c1-c2*b1)/(b1*a2-b2*a1);
+                        Vertex v0 = newVertex(xq, -1 * (a1*xq+c1) / b1);
+                        //if (v0==v1||v0==v2||v0==v3||v0==v4) continue;
+                        if (debug) Log.debug(this,"inserting new vertex " + v0+" between " + v1+"-"+v2 +" and "+ v3+"-"+v4);
+                        next(v1).remove(new Integer(v2));
+                        next(v1).add(new Integer(v0));
+                        next(v0).add(new Integer(v2));
+                        next(v3).remove(new Integer(v4));
+                        next(v3).add(new Integer(v0));
+                        next(v0).add(new Integer(v4));
+                        return true;
+                    }
+                }
+            }
         }
+        return false;
     }
 
     // Triangle //////////////////////////////////////////////////////////////////////////////
@@ -461,29 +366,33 @@ public final class Mesh {
         boolean painted = false;
         boolean special = false;
         final String source;
-        final double ccx, ccy, r;
+        final float ccx, ccy, r;
 
+        public boolean hasEdge(Vertex a, Vertex b) { return a!=b && (a==v1||a==v2||a==v3) && (b==v1||b==v2||b==v3); }
+        public Vertex opposingVertex(Triangle t) { return t12==t ? v3 : t23==t ? v1 : t31==t ? v2 : NULLVERTEX; }
+        public Triangle opposingTriangle(Vertex v) { return v1==v ? t23 : v2==v ? t31 : v3==v ? t12 : null; }
+        public Vertex nextVertex(Vertex v) { return v1==v ? v2 : v2==v ? v3 : v3==v ? v1 : NULLVERTEX; }
+        public Vertex prevVertex(Vertex v) { return v1==v ? v3 : v2==v ? v1 : v3==v ? v2 : NULLVERTEX; }
         public String toString() { return "<<"+v1+""+v2+""+v3+">>"; }
         public boolean intersectsSegment(Vertex a, Vertex b) { return isect(v1,v2,a,b) || isect(v3,v2,a,b) || isect(v1,v3,a,b); }
-        public double area() {
-            double a = v1.distance(v2);
-            double b = v3.distance(v2);
-            double c = v1.distance(v3);
-            double s = (a+b+c)/2;
-            return Math.sqrt(s*(s-a)*(s-b)*(s-c));
+        public float area() {
+            float a = distance(v1,v2);
+            float b = distance(v2,v3);
+            float c = distance(v3,v1);
+            float s = (a+b+c)/2;
+            return (float)Math.sqrt(s*(s-a)*(s-b)*(s-c));
         }
 
         public boolean checkSkinny() {
-            if (!(r / Math.min(Math.min(v1.distance(v2), v2.distance(v3)), v3.distance(v1)) > B)) return false;
-            System.out.println("skinny triangle " + this);
-            for (Iterator it = vertices.iterator(); it.hasNext();) {
-                Vertex v = (Vertex)it.next();
-                for (Iterator nit = v.next.iterator(); nit.hasNext();) {
-                    Vertex v2 = (Vertex)nit.next();
-                    double midx = (v.x+v2.x)/2;
-                    double midy = (v.y+v2.y)/2;
-                    if (distance(midx,midy,ccx,ccy) <= v.distance(midx,midy)) {
-                        System.out.println("  but splitting it would encroach on a segment");
+            if (!(r / Math.min(Math.min(distance(v1,v2), distance(v2,v3)), distance(v3,v1)) > B)) return false;
+            if (debug) Log.debug(this,"skinny triangle " + this);
+            for (Vertex v=0; v<numvertices; v++) {
+                for (Iterator nit = next(v).iterator(); nit.hasNext();) {
+                    Vertex v2 = ((Integer)nit.next()).intValue();
+                    float midx = (x(v)+x(v2))/2;
+                    float midy = (y(v)+y(v2))/2;
+                    if (distance(midx,midy,ccx,ccy) <= distance(v,midx,midy)) {
+                        if (debug) Log.debug(this,"  but splitting it would encroach on a segment");
                         return false;
                     }
                 }
@@ -497,49 +406,49 @@ public final class Mesh {
             if (deleted) throw new Error("gargh!");
             if (!strokeOnly) {
                 if (special) {
-                    buf.fillTriangle((int)a.multiply_px((float)v1.x, (float)v1.y),
-                                     (int)a.multiply_py((float)v1.x, (float)v1.y),
-                                     (int)a.multiply_px((float)v2.x, (float)v2.y),
-                                     (int)a.multiply_py((float)v2.x, (float)v2.y),
-                                     (int)a.multiply_px((float)v3.x, (float)v3.y),
-                                     (int)a.multiply_py((float)v3.x, (float)v3.y),
+                    buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
+                                     (int)a.multiply_py((float)x(v1), (float)y(v1)),
+                                     (int)a.multiply_px((float)x(v2), (float)y(v2)),
+                                     (int)a.multiply_py((float)x(v2), (float)y(v2)),
+                                     (int)a.multiply_px((float)x(v3), (float)y(v3)),
+                                     (int)a.multiply_py((float)x(v3), (float)y(v3)),
                                      0xff0000ff);
                 } else if ((evenOdd && count%2!=0) || (!evenOdd && count!=0)) {
-                    buf.fillTriangle((int)a.multiply_px((float)v1.x, (float)v1.y),
-                                     (int)a.multiply_py((float)v1.x, (float)v1.y),
-                                     (int)a.multiply_px((float)v2.x, (float)v2.y),
-                                     (int)a.multiply_py((float)v2.x, (float)v2.y),
-                                     (int)a.multiply_px((float)v3.x, (float)v3.y),
-                                     (int)a.multiply_py((float)v3.x, (float)v3.y),
+                    buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
+                                     (int)a.multiply_py((float)x(v1), (float)y(v1)),
+                                     (int)a.multiply_px((float)x(v2), (float)y(v2)),
+                                     (int)a.multiply_py((float)x(v2), (float)y(v2)),
+                                     (int)a.multiply_px((float)x(v3), (float)y(v3)),
+                                     (int)a.multiply_py((float)x(v3), (float)y(v3)),
                                      color);
                 } else {
-                    buf.fillTriangle((int)a.multiply_px((float)v1.x, (float)v1.y),
-                                     (int)a.multiply_py((float)v1.x, (float)v1.y),
-                                     (int)a.multiply_px((float)v2.x, (float)v2.y),
-                                     (int)a.multiply_py((float)v2.x, (float)v2.y),
-                                     (int)a.multiply_px((float)v3.x, (float)v3.y),
-                                     (int)a.multiply_py((float)v3.x, (float)v3.y),
-                                     0xff000000 | ((color & 0x00ffffff) >> 8));
+                    if (debug)
+                        buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
+                                         (int)a.multiply_py((float)x(v1), (float)y(v1)),
+                                         (int)a.multiply_px((float)x(v2), (float)y(v2)),
+                                         (int)a.multiply_py((float)x(v2), (float)y(v2)),
+                                         (int)a.multiply_px((float)x(v3), (float)y(v3)),
+                                         (int)a.multiply_py((float)x(v3), (float)y(v3)),
+                                         0xff000000 | ((color & 0x00ffffff) >> 8));
                 }
             }
             painted = true;
+            //#repeat t12/t23/t31 v1/v2/v3 v2/v3/v1
             if (t12 != null && !t12.painted) {
                 t12.fill(buf, a, color, evenOdd, count + wind(v1, v2), strokeOnly);
-                drawLine(buf, (v1.x*2+v2.x)/3, (v1.y*2+v2.y)/3, (v1.x+2*v2.x)/3, (v1.y+2*v2.y)/3, a,
-                         wind(v2,v1)==0?0xff000000:0xff0000ff);
-            }
-            if (t23 != null && !t23.painted) {
-                t23.fill(buf, a, color, evenOdd, count + wind(v2, v3), strokeOnly);
-                drawLine(buf, (v2.x*2+v3.x)/3, (v2.y*2+v3.y)/3, (v2.x+2*v3.x)/3, (v2.y+2*v3.y)/3, a,
-                         wind(v3,v2)==0?0xff000000:0xff0000ff);
-            }
-            if (t31 != null && !t31.painted) {
-                t31.fill(buf, a, color, evenOdd, count + wind(v3, v1), strokeOnly);
-                drawLine(buf, (v1.x*2+v3.x)/3, (v1.y*2+v3.y)/3, (v1.x+2*v3.x)/3, (v1.y+2*v3.y)/3, a,
-                         wind(v3,v1)==0?0xff000000:0xff0000ff);
+                if (debug)
+                    drawLine(buf, (x(v1)*2+x(v2))/3, (y(v1)*2+y(v2))/3, (x(v1)+2*x(v2))/3, (y(v1)+2*y(v2))/3, a,
+                             wind(v2,v1)==0?0xff000000:0xff0000ff);
             }
+            //#end
+        }
+        public int wind(Vertex a, Vertex b) {
+            if (next(a).contains(new Integer(b)) && next(b).contains(new Integer(a))) return 0;
+            if (y(a) < y(b) || (y(a)==y(b) && x(a)<x(b))) return wind(b, a);
+            if (next(a).contains(new Integer(b))) return 1;
+            if (next(b).contains(new Integer(a))) return -1;
+            return 0;
         }
-        public int wind(Vertex a, Vertex b) { return a.wind(b); }
         public void clear() {
             if (!painted) return;
             painted = false;
@@ -551,236 +460,52 @@ public final class Mesh {
         public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake) { this(source, v1,v2,v3,fake,false); }
         public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake, boolean ignoreProblems) {
             this.source = source;
-            double a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
-            if (a==0) {
+            float a = 0;
+            for(int i=0; i<3; i++) {
+                a=(y(v2)-y(v3))*(x(v2)-x(v1))-(y(v2)-y(v1))*(x(v2)-x(v3));
+                if (a!=0) break;
                 Vertex t = v2; v2=v3; v3=v1; v1 = t; 
-                a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
-                if (a==0) {
-                    t = v2; v2=v3; v3=v1; v1 = t; 
-                    a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
-                }
-                if (a==0) {
-                    t = v2; v2=v3; v3=v1; v1 = t; 
-                    a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
-                }
-                if (a==0) {
-                    t = v1; v1=v3; v3=t;
-                    a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
-                }
-                if (a==0) {
-                    t = v2; v2=v3; v3=v1; v1 = t; 
-                    a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
-                }
-                if (a==0) {
-                    t = v2; v2=v3; v3=v1; v1 = t; 
-                    a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
-                }
-                if (a==0) {
-                    t = v2; v2=v3; v3=v1; v1 = t; 
-                    a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
-                }
             }
             if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
             this.v1 = v1; this.v2 = v2; this.v3 = v3;
-            double a1=(v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
-            double a2=(v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
-            ccx=(a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2;
-            ccy=(a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2;
-            r = v1.distance(ccx, ccy);
+            float a1=(x(v1)+x(v2))*(x(v2)-x(v1))+(y(v2)-y(v1))*(y(v1)+y(v2));
+            float a2=(x(v2)+x(v3))*(x(v2)-x(v3))+(y(v2)-y(v3))*(y(v2)+y(v3));
+            ccx=(a1*(y(v2)-y(v3))-a2*(y(v2)-y(v1)))/a/2;
+            ccy=(a2*(x(v2)-x(v1))-a1*(x(v2)-x(v3)))/a/2;
+            r = distance(v1,ccx, ccy);
             if (fake) return;
             for(int i=0; i<triangles.size(); i++) {
                 Triangle t = (Triangle)triangles.elementAt(i);
-                if ((t.v1==v1&&t.v2==v2)||(t.v1==v2&&t.v2==v1)) {
-                    if (t.t12!=null && !ignoreProblems) {
-                        System.out.println("v1=="+v1);
-                        System.out.println("v2=="+v2);
-                        System.out.println("t.v3=="+t.v3);
-                        System.out.println("v3=="+v3);
-                        special = true;
-                        t.special = true;
-                        triangles.add(this);
-                        System.out.println(t.t12.source);
-                        throw new Error();
-                        //t.t12.delete(null);
-                    }
-                    t.t12=this;
-                    t12=t;
-                    //continue;
-                }
-                if ((t.v1==v2&&t.v2==v3)||(t.v1==v3&&t.v2==v2)) {
-                    if (t.t12!=null && !ignoreProblems) {
-                        special = true;
-                        t.special = true;
-                        System.out.println("v2=="+v2);
-                        System.out.println("v3=="+v3);
-                        System.out.println("t.v3=="+t.v3);
-                        System.out.println("v1=="+v1);
-                        System.out.println("t.t12.v1=="+t.t12.v1);
-                        System.out.println("t.t12.v2=="+t.t12.v2);
-                        System.out.println("t.t12.v3=="+t.t12.v3);
-                        special = true;
-                        t.special = true;
-                        triangles.add(this);
-                        throw new Error();
-                        //t.t12.delete(null);
-                    }
-                    t.t12=this;
-                    t23=t;
-                    //continue;
-                }
-                if ((t.v1==v3&&t.v2==v1)||(t.v1==v1&&t.v2==v3)) {
-                    if (t.t12!=null && !ignoreProblems) {
-                        special = true;
-                        t.special = true;
-                        System.out.println("v1=="+v1);
-                        System.out.println("v3=="+v3);
-                        System.out.println("t.v3=="+t.v3);
-                        System.out.println("v2=="+v2);
-                        special = true;
-                        t.special = true;
-                        triangles.add(this);
-                        throw new Error();
-                        //t.t12.delete(null);
-                    }
-                    t.t12=this;
-                    t31=t;
-                    //continue;
-                }
-                if ((t.v2==v1&&t.v3==v2)||(t.v2==v2&&t.v3==v1)) {
-                    if (t.t23!=null && !ignoreProblems) {
-                        t = t.t23;
-                        System.out.println("v1=="+v1);
-                        System.out.println("v2=="+v2);
-                        System.out.println("t.v1=="+t.v1);
-                        System.out.println("v3=="+v3);
-                        special = true;
-                        t.special = true;
-                        triangles.add(this);
-                        System.out.println(t.source);
-                        throw new Error();
-                        //t.t23.delete(null);
-                    }
-                    t.t23=this;
-                    t12=t;
-                    //continue;
-                }
-                if ((t.v2==v2&&t.v3==v3)||(t.v2==v3&&t.v3==v2)) {
-                    if (t.t23!=null && !ignoreProblems) {
-                        special = true;
-                        t=t.t23;
-                        t.special = true;
-                        triangles.add(this);
-                        System.out.println(t.source);
-                        throw new Error();
-                        //t.t23.delete(null);
-                    }
-                    t.t23=this;
-                    t23=t;
-                    //continue;
-                }
-                if ((t.v2==v3&&t.v3==v1)||(t.v2==v1&&t.v3==v3)) {
-                    if (t.t23!=null && !ignoreProblems) {
-                        special = true;
-                        t = t.t23;
-                        t.special = true;
-                        System.out.println("v1=="+v1);
-                        System.out.println("v3=="+v3);
-                        System.out.println("t.v3=="+t.v3);
-                        System.out.println("v2=="+v2);
-                        special = true;
-                        t.special = true;
-                        System.out.println(t.source);
-                        triangles.add(this);
-                        throw new Error();
-                        //t.t23.delete(null);
-                    }
-                    t.t23=this;
-                    t31=t;
-                    //continue;
-                }
-                if ((t.v3==v1&&t.v1==v2)||(t.v3==v2&&t.v1==v1)) {
-                    if (t.t31!=null && !ignoreProblems) {
-                        t=t.t31;
-                        special = true;
-                        t.special = true;
-                        System.out.println("v1=="+v1);
-                        System.out.println("v2=="+v2);
-                        System.out.println("t.v2=="+t.v2);
-                        System.out.println("v3=="+v3);
-                        triangles.add(this);
-                        System.out.println(t.source);
-                        throw new Error();
-                        //t.t31.delete(null);
-                    }
-                    t.t31=this;
-                    t12=t;
-                    //continue;
-                }
-                if ((t.v3==v2&&t.v1==v3)||(t.v3==v3&&t.v1==v2)) {
-                    if (t.t31!=null && !ignoreProblems) {
-                        special = true;
-                        t=t.t31;
-                        t.special = true;
-                        triangles.add(this);
-                        System.out.println(t.source);
-                        throw new Error();
-                        //t.t31.delete(null);
-                    }
-                    t.t31=this;
-                    t23=t;
-                    //continue; 
-                }
-                if ((t.v3==v3&&t.v1==v1)||(t.v3==v1&&t.v1==v3)) {
-                    if (t.t31!=null && !ignoreProblems) {
-                        t=t.t31;
-                        System.out.println("t.v1="+t.v1);
-                        System.out.println("t.v2="+t.v2);
-                        System.out.println("t.v3="+t.v3);
-                        System.out.println("v1="+v1);
-                        System.out.println("v2="+v2);
-                        System.out.println("v3="+v3);
-                        special = true;
-                        t.special = true;
-                        triangles.add(this);
-                        System.out.println("source=="+source);
-                        System.out.println("t.source=="+t.source);
-                        throw new Error();
-                        //t.t31.delete(null);
-                    }
-                    t.t31=this;
-                    t31=t;
-                    //continue;
-                }
+                if ((t.v1==v1&&t.v2==v2)||(t.v1==v2&&t.v2==v1)) { if (t.t12!=null) throw new Error(); t.t12=this; t12=t; }
+                if ((t.v1==v2&&t.v2==v3)||(t.v1==v3&&t.v2==v2)) { if (t.t12!=null) throw new Error(); t.t12=this; t23=t; }
+                if ((t.v1==v3&&t.v2==v1)||(t.v1==v1&&t.v2==v3)) { if (t.t12!=null) throw new Error(); t.t12=this; t31=t; }
+                if ((t.v2==v1&&t.v3==v2)||(t.v2==v2&&t.v3==v1)) { if (t.t23!=null) throw new Error(); t.t23=this; t12=t; }
+                if ((t.v2==v2&&t.v3==v3)||(t.v2==v3&&t.v3==v2)) { if (t.t23!=null) throw new Error(); t.t23=this; t23=t; }
+                if ((t.v2==v3&&t.v3==v1)||(t.v2==v1&&t.v3==v3)) { if (t.t23!=null) throw new Error(); t.t23=this; t31=t; }
+                if ((t.v3==v1&&t.v1==v2)||(t.v3==v2&&t.v1==v1)) { if (t.t31!=null) throw new Error(); t.t31=this; t12=t; }
+                if ((t.v3==v2&&t.v1==v3)||(t.v3==v3&&t.v1==v2)) { if (t.t31!=null) throw new Error(); t.t31=this; t23=t; }
+                if ((t.v3==v3&&t.v1==v1)||(t.v3==v1&&t.v1==v3)) { if (t.t31!=null) throw new Error(); t.t31=this; t31=t; }
             }
             triangles.add(this);
         }
-        public void delete(Triangle t, Vertex v, Vector vec) {
-            if (deleted) return;
-            if (t12==t) { t12 = null; if (vec != null) { vec.add(v1); vec.add(v2); } }
-            if (t23==t) { t23 = null; if (vec != null) { vec.add(v2); vec.add(v3); } }
-            if (t31==t) { t31 = null; if (vec != null) { vec.add(v3); vec.add(v1); } }
-        }
-        public void delete(Vector vec) {
+        public void delete() {
             if (deleted) return;
             deleted = true;
             triangles.remove(this);
-            if (t12 != null) t12.delete(this,null,vec); else if (vec != null) { vec.add(v1); vec.add(v2); }
-            if (t23 != null) t23.delete(this,null,vec); else if (vec != null) { vec.add(v3); vec.add(v2); }
-            if (t31 != null) t31.delete(this,null,vec); else if (vec != null) { vec.add(v1); vec.add(v3); }
+            if (t12 != null) { if (t12.t12==this) t12.t12=null; if (t12.t23==this) t12.t23=null; if (t12.t31==this) t12.t31=null; }
+            if (t23 != null) { if (t23.t12==this) t23.t12=null; if (t23.t23==this) t23.t23=null; if (t23.t31==this) t23.t31=null; }
+            if (t31 != null) { if (t31.t12==this) t31.t12=null; if (t31.t23==this) t31.t23=null; if (t31.t31==this) t31.t31=null; }
         }
         public boolean contains(Vertex v) {
-            double x = v.x;
-            double y = v.y;
+            float x = x(v);
+            float y = y(v);
             if (v==v1) return false;
             if (v==v2) return false;
             if (v==v3) return false;
-            if (v.intersectsSegment(v1,v2)) return false;
-            if (v.intersectsSegment(v2,v3)) return false;
-            if (v.intersectsSegment(v3,v1)) return false;
-            int a = side(v1,v2,x,y);
-            int b = side(v3,v2,x,y);
-            int c = side(v1,v3,x,y);
-            return (a==side(v1,v2,v3)) && (b==side(v3,v2,v1)) && (c==side(v1,v3,v2));
+            if (isect(v1,v2,v)) return false;
+            if (isect(v2,v3,v)) return false;
+            if (isect(v3,v1,v)) return false;
+            return (side(v1,v2,x,y)==side(v1,v2,v3)) && (side(v3,v2,x,y)==side(v3,v2,v1)) && (side(v1,v3,x,y)==side(v1,v3,v2));
         }
     }
 
@@ -789,54 +514,34 @@ public final class Mesh {
     public Mesh(Polygon p) {
         p.sort();
         triangles.setSize(0);
-        vertices.setSize(0);
-
-        newTriangle(newVertex(p.minx-10, p.miny-10),
-                    newVertex(p.maxx+10, p.miny-10),
-                    newVertex(p.maxx+10, p.maxy+10), "original0");
-
-        newTriangle(newVertex(p.minx-10, p.miny-10),
-                    newVertex(p.minx-10, p.maxy+10),
-                    newVertex(p.maxx+10, p.maxy+10), "original");
-
         for(int i=0; i<p.numcontours-1; i++) {
-            Vertex last = null, first = null;
+            Vertex last = NULLVERTEX, first = NULLVERTEX;
             boolean good = false;
             for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
                 Vertex v = newVertex(p.x[j], p.y[j]);
                 if (v==last) continue;
                 if (v==first) continue;
-                if (last == null) { last = v; continue; }
-                if (first ==null) { first = v; continue; }
+                if (last == NULLVERTEX) { last = v; continue; }
+                if (first == NULLVERTEX) { first = v; continue; }
                 good = true;
                 break;
             }
-            System.out.println("contour " + i + " is " + (good?"good":"bad"));
+            if (debug) Log.debug(this,"contour " + i + " is " + (good?"good":"bad"));
             if (!good) continue;
-            last = null; first = null;
+            last = NULLVERTEX; first = NULLVERTEX;
             for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
-                System.out.println("****************************************");
                 Vertex v = newVertex(p.x[j], p.y[j]);
                 if (v==last) continue;
-                if (first==null) first=v;
-                if (last != null) last.next.add(v);
+                if (first==NULLVERTEX) first=v;
+                if (last != NULLVERTEX) next(last).add(new Integer(v));
                 last = v;
-                System.out.print(((int)v.x)+","+((int)v.y)+" ");
-            }
-            if (last!=first) last.next.add(first);
-            System.out.println();
-        }
-
-        while(true) {
-            boolean redo = false;
-            for(int k=0; k<vertices.size(); k++) {
-                Vector vec = new Vector();
-                Vertex vx = (Vertex)vertices.elementAt(k);
-                redo |= vx.makeNonDegenerate(vec);
+                makeNonDegenerate();
+                force();
             }
-            if (!redo) break;
+            if (last!=first) next(last).add(new Integer(first));
         }
-
+        makeNonDegenerate();
+        force();
         /*
         redo = true;
         for(; redo;) {
@@ -847,22 +552,75 @@ public final class Mesh {
             }
             break;
         }
-        System.out.println("I now have " + vertices.size() + " vertices");
+        System.out.println("I now have " + numvertices + " vertices");
         */
 
-        while(true) {
-            boolean redo = false;
-            for(int k=0; k<vertices.size(); k++) {
-                Vertex v = (Vertex)vertices.elementAt(k);
-                v.forced = false;
-            }
-            for(int k=0; k<vertices.size(); k++) {
-                Vertex v = (Vertex)vertices.elementAt(k);
-                redo |= v.force();
+    }
+
+    // Drawing //////////////////////////////////////////////////////////////////////////////
+
+    private void drawLine(PixelBuffer buf, float x1, float y1, float x2, float y2, Affine a, int color) {
+        buf.drawLine((int)a.multiply_px(x1, y1), (int)a.multiply_py(x1, y1),
+                     (int)a.multiply_px(x2, y2), (int)a.multiply_py(x2, y2),
+                     color);
+    }
+    public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, boolean strokeOnly) {
+        for (int i=0; i<triangles.size(); i++) ((Triangle)triangles.elementAt(i)).clear();
+        ((Triangle)triangles.elementAt(0)).fill(buf, a, color, evenOdd, 1, strokeOnly);
+    }
+
+    public void stroke(PixelBuffer buf, Affine a, int color) {
+        if (debug)
+            for (int i=0; i<numvertices; i++) {
+                Vertex v = i;
+                for(Iterator it = next(v).iterator(); it.hasNext();) {
+                    Vertex v2 = ((Integer)it.next()).intValue();
+                    drawLine(buf, x(v), y(v), x(v2), y(v2), a, 0xffff0000);
+                }
             }
-            if (!redo) break;
+        for (int i=0; i<triangles.size(); i++) {
+            Triangle t = ((Triangle)triangles.elementAt(i));
+            Vertex v1 = t.v1;
+            Vertex v2 = t.v2;
+            Vertex v3 = t.v3;
+            if (debug||t.wind(v1,v2)!=0) drawLine(buf,x(v1),y(v1),x(v2),y(v2),a,(debug && t.wind(v1,v2)!=0) ?0xffffffff:color);
+            if (debug||t.wind(v3,v2)!=0) drawLine(buf,x(v3),y(v3),x(v2),y(v2),a,(debug && t.wind(v3,v2)!=0) ?0xffffffff:color);
+            if (debug||t.wind(v1,v3)!=0) drawLine(buf,x(v1),y(v1),x(v3),y(v3),a,(debug && t.wind(v1,v3)!=0) ?0xffffffff:color);
         }
     }
+
+    // Geometric Utility Functions //////////////////////////////////////////////////////////////////////////////
+
+    public float distance(Vertex v1, Vertex v2) { return distance(x(v1), y(v1), x(v2), y(v2)); }
+    public float distance(Vertex v1, float x, float y) { return distance(x(v1),y(v1),x,y); }
+    public float distance(float x1,float y1,float x2,float y2) {return (float)Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
+    public int side(Vertex v1, Vertex v2, Vertex v3) { return side(v1, v2, x(v3), y(v3)); }
+    public int side(Vertex v1, Vertex v2, float x, float y) { return side(v1, x(v2), y(v2), x, y); }
+    public int side(Vertex v1, float x, float y, Vertex v3) { return side(v1, x, y, x(v3), y(v3)); }
+    public int side(Vertex v1, float x, float y, float x2, float y2) {
+        float a = y-y(v1), b = x(v1)-x, c = -1 * (a*x(v1)+b*y(v1));
+        return (- (a*x2+c)/b > y2) ? -1 : (- (a*x2+c)/b < y2) ? 1 : 0;
+    }
+
+    public boolean isect(Vertex v1, Vertex v2, Vertex v3, Vertex v4) {
+        if (v1==v3 || v1==v4 || v2==v3 || v2==v4) return false;
+        float a = side(v1,v2,v3);
+        float b = side(v1,v2,v4);
+        float c = side(v3,v4,v1);
+        float d = side(v3,v4,v2);
+        return a!=b && c!=d && a!=0 && b!=0 && c!=0 && d!=0;
+    }
+
+    public boolean isect(Vertex v1, Vertex v2, Vertex v) {
+        return
+            side(v1,v2,v)==0 &&
+            x(v) - Math.max(x(v1),x(v2)) < 0 &&
+            x(v) - Math.min(x(v1),x(v2)) > 0 &&
+            y(v) - Math.max(y(v1),y(v2)) < 0 &&
+            y(v) - Math.min(y(v1),y(v2)) > 0;
+    }
+
+
 }
 
 
-- 
1.7.10.4