X-Git-Url: http://git.megacz.com/?p=org.ibex.core.git;a=blobdiff_plain;f=src%2Forg%2Fibex%2Fgraphics%2FMesh.java;h=0680a4c019cea79424dd115505ca9bd232d2c96a;hp=43875ebece97d96a0eaa7d83d8c81949b4c4f565;hb=8a3ef621b25ede6e315907956e590924a0291e2a;hpb=467c56cf21b99b367b3803e4283ece55c85e0d07

diff --git a/src/org/ibex/graphics/Mesh.java b/src/org/ibex/graphics/Mesh.java
index 43875eb..0680a4c 100644
--- a/src/org/ibex/graphics/Mesh.java
+++ b/src/org/ibex/graphics/Mesh.java
@@ -7,862 +7,889 @@ import java.util.*;
 import java.util.collections.*;
 import org.ibex.util.*;
 
+// TODO:
+//  - allow edge-constraint removal
+//
+//  ~30% of our time spent finding vertices => use a balanced quadtree
+//
+//  - store "which curve is inside me" pointer in Triangle
+//      - split if two curves enter
+//  - go to treating Vertex as a value class (epsilon==0)
+//  - union()
+//  - subtract()
+//  - [??] preserve in/out-ness every time we delete() a triangle
+
 /**
- *  An incremental, adaptive, constrained Delaunay Triangulation.
- *  @see Kallmann, Bieri, and Thalmann: Fully Dynamic Constrained Delaunay Triangulations
+ *  An incremental, adaptive, addWeighted Delaunay Triangulation.
+ *  @see Kallmann, Bieri, and Thalmann: Fully Dynamic AddWeighted Delaunay Triangulations
  */
 public final class Mesh {
 
-    private static final double epsilon = (double)0.00000001;
-    private static final boolean debug = true;
+    private static final float epsilon = (float)0.0001;
+    private static final float epsilon2 = (float)0.001;
+    private static final boolean debug = false;
+
+    private  Vector    triangles   = new Vector();     /* we no longer need this */
+    private  Hash      edges       = new Hash();       /* we no longer need this either */
+    private  int       numvertices = 0;
+    private  Triangle  triangle0   = null;
+    private  Vertex    vertex0     = null;
+    private  Vertex    vertex1     = null;
+    private  Vertex    start       = null;
+    private  Vertex    last        = null;
+
+    public Mesh copy() {
+        Mesh m = new Mesh();
+        m.vertex(triangle0.v(1));
+        m.vertex(triangle0.v(2));
+        m.vertex(triangle0.v(3));
+        Object[] edges = this.edges.vals();
+        for(int i=0; i<edges.length; i++) {
+            Edge e = (Edge)edges[i];
+            Vertex mv1 = m.vertex(e.v(1));
+            Vertex mv2 = m.vertex(e.v(2));
+            Edge me = m.getEdge(mv1, mv2);
+            if (e.locked()) {
+                me.lock(mv1, 0);
+                me.weight = e.weight;
+            }
+        }
+        m.setIn(true);
+        return m;
+    }
 
-    private              Vector vertices = new Vector();
-    private              Vector triangles = new Vector();
+    public void reset() {
+        triangles.setSize(0);
+        start = null;
+        last = null;
+    }
 
-    public static double B = 5;
-    public static double Q = 0.4;
+    // Chain //////////////////////////////////////////////////////////////////////////////
 
-    // Utilities //////////////////////////////////////////////////////////////////////////////
+    public static interface Chain {
+        public Mesh.Chain getMeshChainParent();
+        public Affine     getAffine();
+        public Mesh       getMesh();
+    }
+
+    // Constructor //////////////////////////////////////////////////////////////////////////////
 
-    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 Mesh() { }
+    public Mesh(Path p, boolean evenOdd) { p.addTo(this, evenOdd); }
+
+    public void subtract(Mesh m, Affine a) { clipOp(m,a,true); }
+    public void intersect(Mesh m, Affine a) { clipOp(m,a,false); }
+    public void add(Mesh m, Affine a) { iterateTriangles(ITERATE_ADD, m, a); }
+    public static long seekTime = 0;
+
+    public static final int ITERATE_SUBTRACT     = 1;
+    public static final int ITERATE_INTERSECT    = 2;
+    public static final int ITERATE_ADD          = 3;
+    public static final int ITERATE_CLEAR_WASSET = 4;
+    public static final int ITERATE_CLEAR        = 5;
+    public static final int ITERATE_STROKE       = 6;
+    int tick = 0;
+    Triangle[] iter  = new Triangle[100];
+
+    private void iterateTriangles(int mode, Mesh m, Affine a) { iterateTriangles(mode, m, a, null, 0); }
+    private void iterateTriangles(int mode, Mesh m, Affine a, PixelBuffer buf, int color) {
+        tick++;
+        int numiter = 0;
+        if (iter.length < triangles.size()) iter = new Triangle[triangles.size()];
+        iter[numiter++] = triangle0;
+        while(numiter > 0) {
+            Triangle t = iter[--numiter];
+            if (t.tick >= this.tick) continue;
+            switch(mode) {
+                case ITERATE_STROKE:          t.stroke(buf, a, color); break;
+                case ITERATE_CLEAR:           t.clear(); break;
+                case ITERATE_CLEAR_WASSET:    t.inWasSet = false; break;
+                case ITERATE_INTERSECT:
+                case ITERATE_SUBTRACT: {
+                    if (!t.in) break;
+                    boolean oin = m.queryPoint(t.c().multiply(a));
+                    t.in = (mode==ITERATE_SUBTRACT) ? (t.in && !oin) : (t.in && oin);
+                    break;
+                    }
+                case ITERATE_ADD: {
+                    for(int i=1; i<=3; i++) {
+                        Edge e = t.e(i);
+                        if (e.t1 != null && e.t1.tick >= this.tick) continue;
+                        if (e.t2 != null && e.t2.tick >= this.tick) continue;
+                        if (!e.locked()) continue; 
+                        if ((e.t1==null || !e.t1.in) && (e.t2==null || !e.t2.in)) continue;
+                        Point p1 = e.v(1).multiply(a);
+                        Point p2 = e.v(2).multiply(a);
+                        Vertex v1=null, v2=null;
+                            v1 = m.vertex(p1);
+                            v2 = m.vertex(p2);
+                        if (v1==v2) continue;
+                        m.getEdge(v1, v2).lock(v1, 0);
+                    }
+                    break;
+                }
+            }
+            t.tick = this.tick;
+            for(int i=1; i<=3; i++) {
+                Triangle ti = t.t(i);
+                if (ti == null) continue;
+                if (ti.tick >= this.tick) continue;
+                iter[numiter++] = ti;
+            }
+        }
     }
-    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 void clipOp(Mesh m, Affine a, boolean subtract) {
+        seekTime = 0;
+        long start = System.currentTimeMillis();
+        m.add(this, a);
+        iterateTriangles(subtract ? ITERATE_SUBTRACT : ITERATE_INTERSECT, m, a.inverse());
+        float total = (float)((System.currentTimeMillis() - start));
+        float seek  = (float)seekTime;
+        if (total > 80) System.out.println("clip in " + (100 * (seek/total)) + "%");
     }
 
-    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;
+    // Geometry //////////////////////////////////////////////////////////////////////////////
+
+    public static double ddistance(double x1, double y1, double x2, double y2) {
+        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
+    public static float area(Point p1, Point p2, Point p3) {
+        float x1 = p1.x;
+        float x2 = p2.x;
+        float x3 = p3.x;
+        float y1 = p1.y;
+        float y2 = p2.y;
+        float y3 = p3.y;
+        double a = ddistance(x1,y1,x2,y2);
+        double b = ddistance(x2,y2,x3,y3);
+        double c = ddistance(x3,y3,x1,y1);
+        double s = (a+b+c)/2;
+        double t = s*(s-a)*(s-b)*(s-c);
+        if (t < 0) return 0;
+        return (float)Math.sqrt(t);
     }
 
-    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 Point intersect(Point v1, Point v2, Point v3, Point 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);
+        double x = (b2*c1-c2*b1)/(b1*a2-b2*a1);
+        double y = (a2*c1-c2*a1)/(a1*b2-a2*b1);
+        if (Double.isNaN(x) || Double.isNaN(y)) throw new Error("cannot intersect:\n ");
+        return point((float)x,(float)y);
     }
-    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 static int side(Point p1, Point p2, Point p3) {
+        float x0 = p1.x;
+        float x = p2.x;
+        float x2 = p3.x;
+        float y0 = p1.y;
+        float y = p2.y;
+        float y2 = p3.y;
+        // this MUST be done to double precision
+        double a = y-y0, b = x0-x, c = a*(x0 - x2) + b*(y0 - y2);
+        if (c > 0) return b>=0 ? -1 :  1;
+        if (c < 0) return b>=0 ?  1 : -1;
+        return 0;
     }
-    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);
-                }
+
+    // Vertex //////////////////////////////////////////////////////////////////////////////
+
+    public Vertex vertex(Point p, Affine a) { return vertex(p.multiply(a)); }
+    public Vertex vertex(Point p) {
+        Vertex ret = null;
+        switch(numvertices) {
+            case 0: return (vertex0 = new Vertex(p));
+            case 1: return vertex0.distance(p)<=epsilon ? vertex0 : (vertex1 = new Vertex(p));
+            case 2: {
+                if (vertex0.distance(p)<=epsilon) return vertex0;
+                if (vertex1.distance(p)<=epsilon) return vertex1;
+                Vertex v2 = new Vertex(p);
+                triangle(newEdge(vertex0,vertex1), newEdge(vertex1,v2), newEdge(v2,vertex0));
+                return v2;
+            }
+            default: {
+                Triangle t = null;
+                    t = triangle0.seek(p);
+                for(int i=1; i<=3; i++)
+                    for(int j=1; j<=2; j++)
+                        if (t != null && t.e(i).v(j).distance(p)<=epsilon) return t.e(i).v(j);
+                Vertex v = new Vertex(p);
+                if      (t.e(3).intersects(p))          t.e(3).bisect(v);
+                else if (t.e(1).intersects(p))          t.e(1).bisect(v);
+                else if (t.e(2).intersects(p))          t.e(2).bisect(v);
+                else if (t.contains(v))                 t.trisect(v);
+                else                                    t.addHull(v);
+                return v;
             }
-        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);
         }
     }
 
-    // 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;
+    private Point point(float x, float y) { return new Point(x,y); }
+    private Point point(Point a, Point b) { return new Point((a.x+b.x)/2,(a.y+b.y)/2); }
+    private Point point(Point p, Affine a) { return point(p.x(a), p.y(a)); }
+    private class Point {
+        public float x;
+        public float y;
+        public String toString() { return "("+x+","+y+")"; }
+        public Point multiply(Affine a) { return point(x(a),y(a)); }
+        public Point(float x, float y) { this.x = x; this.y = y; }
+        public Point(Point p) { this(p.x,p.y); }
+        public boolean equals(float x, float y) { return distance(x,y) <= epsilon; }
+        public boolean equals(Object o) { return (!(o instanceof Point)) ? false : ((Point)o).distance(this) <= epsilon; }
+        public float distance(Point v) { return distance(v.x,v.y); }
+        private float distance(float x, float y) { return (float)Math.sqrt(distance2(x, y)); }
+        public float distance2(Point v) { return distance2(v.x, v.y); }
+        private float distance2(float x, float y) { return (this.x-x)*(this.x-x)+(this.y-y)*(this.y-y); }
+        public float x(Affine a) { return a.multiply_px(x,y); }
+        public float y(Affine a) { return a.multiply_py(x,y); }
+        public int xi(Affine a) { return (int)x(a); }
+        public int yi(Affine a) { return (int)y(a); }
+        public boolean intersects(Point p1, Point p2) {
+            return
+                Mesh.side(p1,p2,this)==0 &&
+                x <= Math.max(p1.x,p2.x) &&
+                x >= Math.min(p1.x,p2.x) &&
+                y <= Math.max(p1.y,p2.y) &&
+                y >= Math.min(p1.y,p2.y);
         }
-        return ret==null ? new Vertex(x,y) : ret;
     }
 
-    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++) {
-            Triangle t = (Triangle)triangles.elementAt(i);
-            if (t.v1==v1&&t.v2==v2&&t.v3==v3) return t;
-            if (t.v1==v1&&t.v2==v3&&t.v3==v2) return t;
-            if (t.v1==v2&&t.v2==v3&&t.v3==v1) return t;
-            if (t.v1==v2&&t.v2==v1&&t.v3==v3) return t;
-            if (t.v1==v3&&t.v2==v1&&t.v3==v2) return t;
-            if (t.v1==v3&&t.v2==v2&&t.v3==v1) return t;
-        }
-        Triangle t = new Triangle(source, v1, v2, v3, false, false);
-        if (debug) checktri();
-        return t;
+    private final class Vertex extends Point implements org.ibex.classgen.opt.Arena.Gladiator {
+        public Vertex(Point p) { super(p); numvertices++; }
     }
 
-    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");
-            for(int j=0; j<triangles.size(); j++) {
-                Triangle t2 = (Triangle)triangles.elementAt(j);
-                if (t2==t) continue;
-                if (t.v1==t2.v1&&t.v2==t2.v2&&t.v3==t2.v3) throw new Error("poo");
-                if (t.v1==t2.v1&&t.v2==t2.v3&&t.v3==t2.v2) throw new Error("poo");
-                if (t.v1==t2.v2&&t.v2==t2.v3&&t.v3==t2.v1) throw new Error("poo");
-                if (t.v1==t2.v2&&t.v2==t2.v1&&t.v3==t2.v3) throw new Error("poo");
-                if (t.v1==t2.v3&&t.v2==t2.v1&&t.v3==t2.v2) throw new Error("poo");
-                if (t.v1==t2.v3&&t.v2==t2.v2&&t.v3==t2.v1) throw new Error("poo");
-            }
+    // Edge //////////////////////////////////////////////////////////////////////////////
+
+    public Edge newEdge(Vertex v1, Vertex v2) {
+        return getEdge(v1,v2);
+        /*
+        if (v1==v2) throw new Error();
+        Edge ret = (Edge)edges.get(v1,v2);
+        //if (ret != null) throw new Error("tried to get an edge that already exists!");
+        if (ret == null) ret = new Edge(v1,v2);
+        return ret;
+        */
+    }
+
+    public Edge getEdge(Vertex v1, Vertex v2) {
+        if (v1==v2) throw new Error();
+        //Edge ret = (Edge)edges.get(v1,v2);
+        Edge ret = null;
+        Triangle t = null;
+        if (triangle0 != null) {
+            t = triangle0.seek(point(v1,v2));
+            if (t != null)
+                for(int i=1; i<=3; i++)
+                    if (t.e(i).hasVertex(v1) && t.e(i).hasVertex(v2)) ret = t.e(i);
+        }
+        if (ret == null) {
+            ret = (Edge)edges.get(v1,v2);
+            if (ret != null && (ret.t1 != null || ret.t2 != null)) throw new Error("bah! " + ret);
         }
+        if (ret == null) ret = new Edge(v1,v2);
+        return ret;
     }
 
-    // Vertex //////////////////////////////////////////////////////////////////////////////
+    private final class Edge implements org.ibex.classgen.opt.Arena.Gladiator {
+        private final Vertex v1;
+        private final Vertex v2;
+        Triangle t1 = null;
+        Triangle t2 = null;
 
-    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");
-            }
+        private int locks = 0;
+        private int weight = 0;
+
+        public void delete() {
+            if (t1!=null || t2!=null) throw new Error("tried to remove an edge before its triangles");
+            edges.put(v1,v2,null);
+            edges.put(v2,v1,null);
         }
 
-        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;
-                        }
-                    }
-                }
-            }
-            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;
-                    }
+        public Vertex v(int i) { return i==1?v1:i==2?v2:null; }
+
+        public Edge rotate(Vertex v, boolean clockwise) {
+            Triangle t = v==v1 ? (clockwise?t1:t2) : v==v2 ? (clockwise?t2:t1) : null;
+            if (t==null) return null;
+            for(int i=1; i<=3; i++) if (t.e(i)!=this && t.e(i).hasVertex(v)) return t.e(i);
+            return null;
+        }
+        public Edge rotateHull(boolean clockwise) {
+            if (t1!=null && t2!=null) throw new Error("nextHull() called on non-hull edge");
+            Vertex v = rotate(v1, !clockwise) == null ? v2 : v1;
+            Edge e = rotate(v, !clockwise);
+            while(!e.hasTriangle(null) && e!=this) e = e.rotate(v, !clockwise);
+            if (e==this) throw new Error("confused");
+            return e;
+        }
+
+        public boolean isNear(Point p) { return area(v1,v2,p) < epsilon2; }
+        public Vertex commonVertex(Edge e) { return v1==e.v(1) || v1==e.v(2) ? v1 : v2==e.v(1) || v2==e.v(2) ? v2 : null; }
+        public Vertex unCommonVertex(Edge e) { return v1!=e.v(1) && v1!=e.v(2) ? v1 : v2!=e.v(1) && v2!=e.v(2) ? v2 : null; }
+        public Vertex opposingVertex(Vertex v) { return v1==v ? v2 : v1; }
+        public int weight() { return weight; }
+        public int weight(Vertex v) { return v==v1?weight:(-1*weight); }
+        public boolean locked() { return locks > 0; }
+        public boolean partitions(Point va, Point vb) { return side(va,vb)==-1; }
+        public int     side(Point a, Point b) { return side(a) * side(b); }
+        public int     side(Point a)          { return Mesh.side(v(1), v(2), a); }
+        public boolean hasVertex(Vertex v) { return v1==v || v2==v; }
+        public boolean hasTriangle(Triangle t) { return t==t1 || t==t2; }
+        public String toString() { return v(1) + "--" + v(2); }
+        public void rmTriangle(Triangle t) {
+            if (t1==t) t1 = null;
+            else if (t2==t) t2 = null;
+            else throw new Error();
+            if (t1==null && t2==null) delete();
+        }
+        public boolean convex() { return this.intersects(t1.opposingVertex(t2), t2.opposingVertex(t1)); }
+
+        public boolean colinear(Point v) { return area(v,v1,v2)<=epsilon; }
+
+        public boolean intersects(Point p) {
+            return
+                side(p)==0 &&
+                p.x <= Math.max(v1.x,v2.x) &&
+                p.x >= Math.min(v1.x,v2.x) &&
+                p.y <= Math.max(v1.y,v2.y) &&
+                p.y >= Math.min(v1.y,v2.y);
+        }
+        public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); }
+        public boolean intersects(Point va, Point vb) {
+            return
+                !v1.equals(va) &&
+                !v1.equals(vb) &&
+                !v2.equals(va) &&
+                !v2.equals(vb) &&
+                partitions(va, vb) &&
+                Mesh.side(va, vb, v1) * Mesh.side(va, vb, v2) == -1;
+        }
+        public Triangle opposingTriangle(Triangle t) {
+            if (t1 == t) return t2;
+            if (t2 == t) return t1;
+            throw new Error();
+        }
+        public void addTriangle(Triangle tnew) {
+            if (t1==null) t1 = tnew;
+            else if (t2==null) t2 = tnew;
+            else throw new Error("attempted to addTriangle("+tnew+")\n  t1="+t1+"\n  t2="+t2);
+            if (t1==t2) throw new Error("same triangle can't be both sides of an edge");
+            if (v1.x==v2.x) {
+                boolean b  = side(t1.opposingVertex(this)) == side(point(Float.MAX_VALUE, v1.y));
+                Triangle right = b ? t1 : t2;       // right side
+                Triangle left  = b ? t2 : t1;       // left side
+                t1 = right;
+                t2 = left;
+            } else {
+                boolean b       = side(t1.opposingVertex(this)) == side(point(0, Float.MAX_VALUE));
+                Triangle top    = b ? t1 : t2;
+                Triangle bottom = b ? t2 : t1;
+                if (v1.y==v2.y) {                         // horizontal
+                    t1 = bottom;
+                    t2 = top;
+                } else if (v1.x > v2.x) {                 // positive slope
+                    t1 = top;
+                    t2 = bottom;
+                } else {                                  // negative slope
+                    t1 = bottom;
+                    t2 = top;
                 }
-                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);
+        public void bisect(Vertex v) {
+            Edge e = this;
+            Triangle t1 = this.t1==null?this.t2:this.t1;
+            Triangle t  = t1==this.t1?this.t2:this.t1;
+            Vertex opposing = t1.opposingVertex(e);
+            Triangle top = null, ton = null;
+            Vertex left = e.v(1);
+            Vertex right = e.v(2);
+            Vertex tov = null;
+            boolean in1 = t1.in;
+            boolean in2 = false;
+            Triangle opposingTriangleLeft = t1.opposingTriangle(left);
+            Triangle opposingTriangleRight = t1.opposingTriangle(right);
+            Edge right_v = newEdge(right, v);
+            Edge left_v = newEdge(left, v);
+            Edge opposing_v = newEdge(opposing, v);
+            Edge tov_v = null;
+            Edge right_tov = null;
+            Edge left_tov = null;
+            Edge right_opposing = t1.opposingEdge(left);
+            Edge left_opposing = t1.opposingEdge(right);
+            if (t != null) {
+                t.check();
+                right_tov = t.opposingEdge(left);
+                left_tov = t.opposingEdge(right);
+                top = t.opposingTriangle(left);
+                ton = t.opposingTriangle(right);
+                tov = t.opposingVertex(t1);
+                in2 = t.in;
+                tov_v = newEdge(tov, v);
+                if (top == t1) top = null;
+                if (ton == t1) ton = null;
+                if (opposingTriangleLeft == t) opposingTriangleLeft = null;
+                if (opposingTriangleRight == t) opposingTriangleRight = null;
+                t.delete();
             }
-            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());
-            if (orphans.size()==0) return true;
-            Vertex o = (Vertex)orphans.iterator().next();
-            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;
-                return false;
+            t1.delete();
+            Triangle ta, tb, tc, td;
+            ta = triangle(right_opposing, opposing_v, right_v);
+            tb = triangle(left_opposing, opposing_v, left_v);
+            ta.in = in1;
+            tb.in = in1;
+            if (t != null) {
+                tc = triangle(left_tov, tov_v, left_v);
+                td = triangle(right_tov, tov_v, right_v);
+                tc.in = in2;
+                td.in = in2;
             }
-
-            Vertex best = null;
-            OUTER: for(Iterator it=orphans.iterator(); it.hasNext();) {
-                o = (Vertex)it.next();
-                if (o==v) continue;
-                Triangle t = new Triangle("temp", this, v, o, true);
-                for(Iterator it2=orphans.iterator(); it2.hasNext();) {
-                    Vertex z = (Vertex)it2.next();
-                    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 (locked()) fracture(v);
+            else ta.fixup();
+        }
+        public Edge flip() {
+            if (locked()) throw new Error("attempted to remove a locked edge: " + this);
+            boolean in = t1.in && t2.in;
+
+            Edge e3   = rotate(v1, true);
+            Vertex vb = e3.unCommonVertex(this);
+            Edge e6   = e3.rotate(vb, true);
+
+            Edge e4   = rotate(v2, true);
+            Vertex va = e4.unCommonVertex(this);
+            Edge e1   = e4.rotate(va, true);
+
+            Edge e    = newEdge(va, vb);
+
+            t1.delete();
+            t2.delete();
+            Triangle ta, tb;
+            ta = triangle(e1, e, e3);
+            tb = triangle(e4, e, e6);
+            ta.in = in;
+            tb.in = in;
+            return ta.getSharedEdge(tb);
+        }
+        public void fracture(Vertex vx) {
+            if (!locked()) throw new Error("attempt to fracture an edge which does not exist: " + v1 + " " + v2);
+            // delete-me
+            Edge v1vx = newEdge(v1, vx);
+            Edge vxv2 = newEdge(vx, v2);
+            v1vx.locks += locks;
+            vxv2.locks += locks;
+            locks = 0;
+            v1vx.weight += v(1)==v1vx.v(1) ? weight : (-1 * weight);
+            vxv2.weight += v(2)==vxv2.v(2) ? weight : (-1 * weight);
+            weight = 0;
+            v1vx.lock();
+            vxv2.lock();
+        }
+        public void fracture(Edge e) {
+            triangle0=e.t1==null?e.t2:e.t1;
+            Vertex v0 = vertex(Mesh.this.intersect(v1,v2,e.v(1),e.v(2)));
+            if (v0 != e.v(1) && v0 != e.v(2) && e.locked()) e.fracture(v0);
+            if (v0 != v1 && v0 != v2) fracture(v0);
+        }
+        public void lock(Vertex v1, int delta) {
+            weight += this.v(1)==v1 ? delta : (-1 * delta);
+            locks += 1;
+            lock();
+        }
+        public void lock() {
+            Triangle t = t1==null ? t2 : t1;
+            if (t==null) t = triangle0.seek(v1);
+            if (!t.hasVertex(v1)) throw new Error("this sucks balls");
+            boolean skipfo = false;
+            for(Triangle told = null; t != told; t = told==null ? t : t.followVector(v1,v2)) {
+                told = t;
+                if (!t.encounters(v1,v2)) break;
+                if (!t.encounters(v2,v1)) break;
+                Triangle tlast = t.followVector(v2,v1);
+                if (tlast == null) throw new Error("seek from: " + tlast + "\n  " + v1 + " -> " + v2);
+                if (tlast == t) { if (t.hasVertex(v1)) continue; throw new Error("no predecessor"); }
+                Edge e = t.getSharedEdge(tlast);
+                if (!e.convex()) continue;
+                if (e.v(1)==v1 || e.v(1)==v2 || e.v(2)==v1 || e.v(2)==v2) { continue; }
+                if (this.intersects(e.v(1))) { fracture(e.v(1)); return; }
+                if (this.intersects(e.v(2))) { fracture(e.v(2)); return; }
+                if (!this.intersects(e)) continue;
+                if (e.locked()) {
+                    fracture(e);
+                    return;
+                } else {
+                    Edge eold = e = e.flip();
+                    t = e.t1;
+                    if (t==null || !t.intersects(this)) t = e.t2;
+                    told = t;
+                    if (eold.intersects(this)) {
+                        t = t.followVector(v1,v2);
+                        if (t != e.t1 && t != e.t2) t = told;
+                        continue;
+                    } else {
+                        told = null;
+                        while(t.intersects(this)) {
+                            if (t==told) break;
+                            told = t;
+                            t = t.followVector(v2,v1);
+                        }
+                        t = told;
+                        told = null;
+                        continue;
+                    }
                 }
-                if (best==null || new Triangle("temp",this,v,best,true).area() > new Triangle("temp",this,v,o,true).area())
-                    best = o;
-            }
-            if (best==null) 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);
-            }
-            boolean doit = true;
-            doit &= o.triangulate2(left, v, false);
-            doit &= o.triangulate2(right, this, 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;
-                return false;
             }
-            return true;
+            if (t1!=null) t1.fixup();
+            if (t2!=null) t2.fixup();
         }
 
-        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 stroke(PixelBuffer buf, Affine a, int color) {
+            int c = debug
+                ? (weight() == 0 ? color : 0xffff0000)
+                : (weight() != 0 ? color : 0);
+            if (c != 0) buf.drawLine(v1.xi(a), v1.yi(a), v2.xi(a), v2.yi(a), c);
         }
-        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 Edge(Vertex v1, Vertex v2) {
+            boolean b = v1.y < v2.y || (v1.y==v2.y && v1.x < v2.x);
+            this.v1 = b ? v1 : v2;
+            this.v2 = b ? v2 : v1;
+            edges.put(v1, v2, this);
+            edges.put(v2, v1, this);
         }
     }
 
     // Triangle //////////////////////////////////////////////////////////////////////////////
 
-    private final class Triangle {
-        Triangle t12=null, t23=null, t31=null;
-        final Vertex v1, v2, v3;
+    public Triangle triangle(Edge e1, Edge e2, Edge e3) {
+        float x = (e1.v(1).x+e1.v(2).x+e2.v(1).x+e2.v(2).x+e3.v(1).x+e3.v(2).x)/6;
+        float y = (e1.v(1).y+e1.v(2).y+e2.v(1).y+e2.v(2).y+e3.v(1).y+e3.v(2).y)/6;
+        Point p = point(x,y);
+        Triangle t = triangle0==null ? null : triangle0.seek(p);
+        if (t != null &&
+            (t.contains(p) || t.intersects(p)) &&
+            t.hasEdge(e1) &&
+            t.hasEdge(e2) &&
+            t.hasEdge(e3))
+            return triangle0 = t;
+        t = new Triangle(e1, e2, e3);
+        if (debug) t.check();
+        if (triangle0 == null) triangle0 = t;
+        return t;
+    }
+
+        public static boolean fixing = false;
+    private final class Triangle implements org.ibex.classgen.opt.Arena.Gladiator {
+
+        final float r2;
+        final Point cc;
+
+        private Edge e1, e2, e3;    // should be final =(
+        public int tick;
+
         boolean in = false;
-        boolean deleted = false;
+        boolean inWasSet = false;
         boolean painted = false;
-        boolean special = false;
-        final String source;
-        final double ccx, ccy, r;
-
-        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 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");
-                        return false;
-                    }
-                }
+        boolean dirty = true;
+
+        public Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; }
+        public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); }
+        public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; }
+
+        public boolean encounters(Point p1, Point p2) {
+            for(int i=1; i<=3; i++) {
+                if (v(i).equals(p1)) return true;
+                if (v(i).equals(p2)) return true;
+                if (v(i).intersects(p1,p2)) return true;
+                if (e(i).intersects(p1,p2)) return true;
             }
-            newVertex(ccx, ccy);
-            return true;
+            return contains(p1) || contains(p2);
         }
-
-        public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, int count, boolean strokeOnly) {
-            if (painted) return;
-            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),
-                                     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),
-                                     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));
-                }
-            }
-            painted = true;
-            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);
+        public Edge getSharedEdge(Triangle t) { return e(1).t1==t||e(1).t2==t?e(1):e(2).t1==t||e(2).t2==t?e(2):e(3).t1==t||e(3).t2==t?e(3):null; }
+        public boolean contains(Point p) { return e(1).side(v(1),p)==1 && e(2).side(v(2),p)==1 && e(3).side(v(3),p)==1; }
+        public Point c()  { return point(cx(),cy()); }
+        public float cx() { return (float)(((double)v(1).x+(double)v(2).x+(double)v(3).x)/3); }
+        public float cy() { return (float)(((double)v(1).y+(double)v(2).y+(double)v(3).y)/3); }
+        public boolean intersects(Vertex va, Vertex vb){return e(1).intersects(va,vb)||e(2).intersects(va,vb)||e(3).intersects(va,vb);}
+        public boolean intersects(Edge e){ return intersects(e.v(1),e.v(2)); }
+        public boolean intersects(Point p){ return e(1).intersects(p) || e(2).intersects(p) || e(3).intersects(p); }
+        public boolean hasEdge(Edge e) { return e.t1==this || e.t2==this; }
+        public boolean hasEdge(Vertex a, Vertex b) { return a!=b && (a==v(1)||a==v(2)||a==v(3)) && (b==v(1)||b==v(2)||b==v(3)); }
+        public boolean hasVertex(Vertex a) { return a==v(1) || a==v(2) || a==v(3); }
+        public Vertex opposingVertex(Triangle t) { return t(3)==t ? v(3) : t(1)==t ? v(1) : t(2)==t ? v(2) : null; }
+        public Vertex opposingVertex(Edge e) { return e==e(1) ? v(1) : e==e(2) ? v(2) : e==e(3) ? v(3) : null; }
+        public Edge   opposingEdge(Vertex v) { return v==v(1) ? e(1) : v==v(2) ? e(2) : v==v(3) ? e(3) : null; }
+        public Triangle opposingTriangle(Vertex v) { return v(1)==v ? t(1) : v(2)==v ? t(2) : v(3)==v ? t(3) : null; }
+        public String toString() { return "<<"+v(1)+""+v(2)+""+v(3)+">>"; }
+
+        public void stroke(PixelBuffer buf, Affine a, int color) {
+            for(int i=1; i<=3; i++) if (in || debug) e(i).stroke(buf, a, color);
+        }
+        public Triangle fixup() {
+            if (!dirty) return this;
+            dirty = false;
+            for(int i=1; i<=3; i++) {
+                Triangle t = t(i);
+                if (t==null) continue;
+                if (t.r2 <= v(i).distance2(t.cc)) continue;
+                Edge e = e(i);
+                if (e.locked()) { t.fixup(); continue; }
+                return e.flip().t1.fixup();
             }
+            return this;
         }
-        public int wind(Vertex a, Vertex b) { return a.wind(b); }
-        public void clear() {
-            if (!painted) return;
-            painted = false;
-            if (t12 != null) t12.clear();
-            if (t23 != null) t23.clear();
-            if (t31 != null) t31.clear();
-        }
-        public Triangle(String source, Vertex v1, Vertex v2, Vertex v3) { this(source, v1, v2, v3, false, false); }
-        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) {
-                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);
-                }
+        public void addHull(Vertex vnew) {
+            Edge e = e(1).hasTriangle(null) ? e(1) : e(2).hasTriangle(null) ? e(2) : e(3).hasTriangle(null) ? e(3) : null;
+            Triangle t = e.opposingTriangle(null), newt = null;
+            while (!e.partitions(vnew, t.opposingVertex(e))) {
+                e = e.rotateHull(true);
+                t = e.opposingTriangle(null);
             }
-            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);
-            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;
+            Edge ea = newEdge(e.v(1), vnew);
+            Edge eb = newEdge(e.v(2), vnew);
+            newt = triangle(e, ea, eb);
+            if (ea.rotateHull(true) != eb) { Edge temp = ea; ea = eb; eb = temp; }
+            for(int i=1; i<=2; i++)
+                for(Edge ex = i==1?eb:ea; ;) {
+                    e = ex.rotateHull(i==1);
+                    t = e.opposingTriangle(null);
+                    if (!e.partitions(vnew, t.opposingVertex(e))) break;
+                    Edge ep = newEdge(vnew, e.unCommonVertex(ex));
+                    newt = triangle(e, ex, ep);
+                    ex = ep;
                 }
-                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 (newt==null) throw new Error("couldn't find a place to add a triangle for " + vnew);
+            newt.fixup();
+        }
+        public Triangle seek(Point p) {
+            Triangle t = this;
+            try {
+            while (true) {
+                if      (t.contains(p) || t.intersects(p))  return t;
+                else if (t.e(3).intersects(p))                return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t;
+                else if (t.e(1).intersects(p))                return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t;
+                else if (t.e(2).intersects(p))                return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t;
+                else {
+                    Triangle t2 = t.followVector(t.c(), p);
+                    if (t2==null || t2==t) return t;
+                    t = t2;
                 }
-                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;
+            }
+            } finally { if (t!=null) triangle0 = t; }
+        }
+
+        // gives the triangle across the edge through which the ray v(1)-->v(2) exits this triangle
+        public Triangle followVector(Point p1, Point p2) {
+            Triangle ret = followVector2(p1, p2);
+            if (ret==null) return ret;
+            triangle0 = ret;
+            if (!ret.encounters(p1,p2)) return this;
+            return ret;
+        }
+        public Triangle followVector2(Point p1, Point p2) {
+            if (contains(p2) || intersects(p2) || v(1).equals(p2) || v(2).equals(p2) || v(3).equals(p2)) return this;
+            for(int i=1; i<=3; i++) if (!v(i).equals(p1) && v(i).intersects(p1,p2)) return followVector(v(i),p2);
+            Triangle t1 = t(1);
+            Triangle t2 = t(2);
+            Triangle t3 = t(3);
+            for(int i=1; i<=3; i++) {
+                int k1 = i==1?3:i==2?1:i==3?2:0;
+                int k2 = i==1?2:i==2?3:i==3?1:0;
+                int k3 = i==1?1:i==2?2:i==3?3:0;
+                if (v(i).equals(p1)) {
+                    if (e(k1).partitions(v(k1),p2)) return t(k1);
+                    if (e(k2).partitions(v(k2),p2)) return t(k2);
+                    if (e(k3).partitions(v(k3),p2)) return t(k3);
+                    throw new Error("bad!");
                 }
-                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 (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2))
+                throw new Error("invoked followVector() on a Triangle which it does not encounter:\n" +
+                                "  p1=" + p1 + "\n" +
+                                "  p2=" + p2 + "\n" +
+                                "  t =" + this + " (area "+area(v(1),v(2),v(3))+")\n");
+            for(int i=1; i<=3; i++) if (e(i).intersects(p1,p2) && e(i).side(v(i)) * e(i).side(p2) == -1) return t(i);
+            throw new Error("giving up: \n  "+p1+" -> "+p2+"\n  " + this);
+        }
+
+        public void check() {
+            if (debug) {
+                for(int i=1; i<=3; i++) {
+                    if (e(i).v(1) != v(1) && e(i).v(1) != v(2) && e(i).v(1) != v(3)) throw new Error("inconsistent");
+                    if (e(i).t1 != this && e(i).t2 != this) throw new Error("inconsistent");
+                    if (e(i).t1 == e(i).t2) throw new Error("same triangle on both sides of edge");
                 }
-                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);
+                if (e(1)==e(2) || e(2)==e(3) || e(3)==e(1)) throw new Error("identical edges");
+                for(int i=1; i<=3; i++) {
+                    if (t(i) != null) if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)");
+                    if (t(i) != null) {
+                        if (t(i).getSharedEdge(this) != e(i)) throw new Error("blark");
+                        if (!e(i).hasTriangle(t(i))) throw new Error("blark2");
+                        if (!e(i).hasTriangle(this)) throw new Error("blark3");
                     }
-                    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; 
+                // check that edges all join up
+            }
+        }
+
+        public void trisect(Vertex v) {
+            if (!contains(v)) throw new Error("trisect(v) but I don't contain v = " + v);
+            if (hasVertex(v)) throw new Error("attempt to trisect a triangle at one of its own vertices");
+            for(int i=3; i>0; i--) if (e(i).isNear(v)) { e(i).bisect(v); return; }
+            Triangle a=null,b=null,c=null;
+
+            boolean oldIn = in;
+            Edge v1v = newEdge(v(1), v);
+            Edge v2v = newEdge(v(2), v);
+            Edge v3v = newEdge(v(3), v);
+            Edge e1 = this.e(1);
+            Edge e2 = this.e(2);
+            Edge e3 = this.e(3);
+            delete();
+
+            a = triangle(e3, v1v, v2v);
+            b = triangle(e2, v1v, v3v);
+            c = triangle(e1, v3v, v2v);
+            a.in = oldIn;
+            b.in = oldIn;
+            c.in = oldIn;
+            a.fixup();
+        }
+
+        public void setIn(boolean evenOdd, int weight) {
+            if (inWasSet) return;
+            inWasSet = true;
+            in = (evenOdd && weight%2!=0) || (!evenOdd && weight!=0);
+            for(int i=1; i<=3; i++) if (t(i) != null) t(i).setIn(evenOdd, weight + e(i).weight());
+        }
+
+        public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
+            if (painted) return;
+            painted = true;
+            if (in) buf.fillTriangle(v(1).xi(a), v(1).yi(a), v(2).xi(a), v(2).yi(a), v(3).xi(a), v(3).yi(a), color);
+            for(int i=1; i<=3; i++)
+                if (t(i) != null) {
+                    boolean prepaint = t(i).painted;
+                    if (debug) e(i).stroke(buf, a, color);
+                    t(i).fill(buf, a, clip, color, strokeOnly);
                 }
-                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;
+        }
+
+        public Triangle(Edge e1, Edge e2, Edge e3) {
+            this.e1 = e1;
+            this.e2 = e2;
+            this.e3 = e3;
+            Vertex v1 = e(2).unCommonVertex(e(1));
+            Vertex v2 = e(3).unCommonVertex(e(2));
+            Vertex v3 = e(1).unCommonVertex(e(3));
+            if (e(1).intersects(v1)) throw new Error("triangle points are colinear");
+            if (e(2).intersects(v2)) throw new Error("triangle points are colinear");
+            if (e(3).intersects(v3)) throw new Error("triangle points are colinear");
+            e(1).addTriangle(this);
+            e(2).addTriangle(this);
+            e(3).addTriangle(this);
+
+            float a = 0;
+            Q: for(int q=0; q<2; q++) {
+                for(int i=0; i<3; i++) {
+                    if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q;
+                    Vertex t = v2; v2=v3; v3=v1; v1 = t; 
                 }
+                Vertex t = v2; v2=v3; v3=t;
             }
+            if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
+            float a1=(v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
+            float a2=(v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
+            cc=point((a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2, (a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2);
+            r2 = v1.distance2(cc);
             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 clear() {
+            if (!painted) return;
+            painted = false;
+            if (t(3) != null) t(3).clear();
+            if (t(1) != null) t(1).clear();
+            if (t(2) != null) t(2).clear();
         }
-        public void delete(Vector vec) {
-            if (deleted) return;
-            deleted = true;
+        public void delete() {
+            if (triangle0 == this) {
+                if (t(1) != null) triangle0 = t(1);
+                else if (t(2) != null) triangle0 = t(2);
+                else if (t(3) != null) triangle0 = t(3);
+                else triangle0 = null;
+            }
             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); }
-        }
-        public boolean contains(Vertex v) {
-            double x = v.x;
-            double y = v.y;
-            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));
+            e(1).rmTriangle(this);
+            e(2).rmTriangle(this);
+            e(3).rmTriangle(this);
+            e1 = null;
+            e2 = null;
+            e3 = null;
         }
     }
 
-    // Constructor //////////////////////////////////////////////////////////////////////////////
+    // Queries /////////////////////////////////////////////////////////////////////////////////
+       
+    public boolean queryPoint(Point p) {
+        if (triangle0==null) return false;
+        Triangle ret = triangle0.seek(p);
+        return (ret.contains(p) || ret.intersects(p)) && ret.in;
+    }
 
-    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;
-            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; }
-                good = true;
-                break;
-            }
-            System.out.println("contour " + i + " is " + (good?"good":"bad"));
-            if (!good) continue;
-            last = null; first = null;
-            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);
-                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);
-            }
-            if (!redo) break;
-        }
+    // Drawing //////////////////////////////////////////////////////////////////////////////
 
-        /*
-        redo = true;
-        for(; redo;) {
-            redo = false;
-            for(int k=0; k<triangles.size(); k++) {
-                Triangle t = (Triangle)triangles.elementAt(k);
-                redo |= t.checkSkinny();
-            }
-            break;
-        }
-        System.out.println("I now have " + vertices.size() + " vertices");
-        */
+    public void setIn(boolean evenOdd) {
+        iterateTriangles(ITERATE_CLEAR_WASSET, null, null);
+        triangle0.setIn(evenOdd, 1);
+    }
 
-        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();
-            }
-            if (!redo) break;
+    public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
+        if (triangle0==null) return;
+        iterateTriangles(ITERATE_CLEAR, null, null);
+        triangle0.fill(buf, a, clip, color, strokeOnly);
+    }
+
+    public void stroke(PixelBuffer buf, Affine a, int color) {
+        if (triangle0==null) return;
+        iterateTriangles(ITERATE_STROKE, null, a, buf, color);
+    }
+
+    public void newcontour() {
+        if (start != null) add(start.x, start.y);
+        start = null;
+        last = null;
+    }
+
+    public Mesh addRect(float x, float y, float w, float h) {
+        if (w==0 || h==0) return this;
+        Vertex v1 = vertex(point(x,y));
+        Vertex v2 = vertex(point(x+w,y));
+        Vertex v3 = vertex(point(x+w,y+h));
+        Vertex v4 = vertex(point(x,y+h));
+        newEdge(v1,v2).lock(v1,1);
+        newEdge(v2,v3).lock(v2,1);
+        newEdge(v3,v4).lock(v3,1);
+        newEdge(v4,v1).lock(v4,1);
+        setIn(true);
+        return this;
+    }
+
+    public void add(float x, float y) {
+        Vertex vx = vertex(point(x,y));
+        if (vx==last) return;
+        if (start==null) start = vx;
+        try {
+            if (last==null) return;
+            if (numvertices<3) return;
+            if (numvertices==3) getEdge(start, last).lock(start,1);
+            getEdge(last,vx).lock(last,1);        
+        } finally {
+            last = vx;
         }
     }
+
 }