src/org/ibex/graphics/Mesh.java

   1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
   2 // Licensed under the GNU General Public License version 2 ("the License").
   3 // You may not use this file except in compliance with the License.
   4
   5 package org.ibex.graphics;
   6 import java.util.*;
   7 import java.util.collections.*;
   8 import org.ibex.util.*;
   9 import java.awt.*;
  10
  11 // TODO:
  12
  13 // FIXME:   Not all triangles who get their dirty bit set wind up having fixup() called on them -- bad!!
  14
  15 // FEATURE: Delauanay refinement
  16
  17 //  - allow edge-constraint removal
  18 //  - store "which curve is inside me" pointer in Triangle
  19 //      - split if two curves enter
  20 //  - go to treating Vertex as a value class (epsilon==0)
  21 //  - union()
  22 //  - [??] preserve in/out-ness every time we delete() a triangle
  23
  24 /**
  25  *  An incremental, adaptive, addWeighted Delaunay Triangulation.
  26  *  @see Kallmann, Bieri, and Thalmann: Fully Dynamic AddWeighted Delaunay Triangulations
  27  */
  28 public final class Mesh {
  29
  30     private static final float epsilon = (float)0.0;
  31     private static final float epsilon2 = (float)0.0;
  32     private static final boolean debug = false;
  33     //private static final boolean check = true;
  34     private static final boolean check = false;
  35
  36     private  Vector    triangles   = new Vector();     /* we no longer need this */
  37     private  Hash      edges       = new Hash();       /* we no longer need this either */
  38     private  int       numvertices = 0;
  39     private  Triangle  triangle0   = null;
  40     private  Vertex    vertex0     = null;
  41     private  Vertex    vertex1     = null;
  42     private  Vertex    start       = null;
  43     private  Vertex    last        = null;
  44
  45     public Mesh copy() {
  46         Mesh m = new Mesh();
  47         m.vertex(triangle0.v(1));
  48         m.vertex(triangle0.v(2));
  49         m.vertex(triangle0.v(3));
  50         Object[] edges = this.edges.vals();
  51         for(int i=0; i<edges.length; i++) {
  52             Edge e = (Edge)edges[i];
  53             Vertex mv1 = m.vertex(e.v(1));
  54             Vertex mv2 = m.vertex(e.v(2));
  55             Edge me = m.getEdge(mv1, mv2);
  56             if (e.locked()) {
  57                 me.lock(mv1, 0);
  58                 me.weight = e.weight;
  59             }
  60         }
  61         m.setIn(true);
  62         return m;
  63     }
  64
  65     public void reset() {
  66         triangles.setSize(0);
  67         start = null;
  68         last = null;
  69     }
  70
  71     // Chain //////////////////////////////////////////////////////////////////////////////
  72
  73     public static interface Chain {
  74         public Mesh.Chain getMeshChainParent();
  75         public Affine     getAffine();
  76         public Mesh       getMesh();
  77     }
  78
  79     // Constructor //////////////////////////////////////////////////////////////////////////////
  80
  81     public Mesh() { }
  82     public Mesh(Path p, boolean evenOdd) { p.addTo(this, evenOdd); }
  83
  84     public void subtract(Mesh m, Affine a) { clipOp(m,a,true); }
  85     public void intersect(Mesh m, Affine a) { clipOp(m,a,false); }
  86     public void add(Mesh m, Affine a) { iterateTriangles(ITERATE_ADD, m, a); }
  87     public static long seekTime = 0;
  88
  89     public static final int ITERATE_SUBTRACT     = 1;
  90     public static final int ITERATE_INTERSECT    = 2;
  91     public static final int ITERATE_ADD          = 3;
  92     public static final int ITERATE_CLEAR_WASSET = 4;
  93     public static final int ITERATE_CLEAR        = 5;
  94     public static final int ITERATE_STROKE       = 6;
  95     int tick = 0;
  96     Triangle[] iter  = new Triangle[100];
  97
  98     private void iterateTriangles(int mode, Mesh m, Affine a) { iterateTriangles(mode, m, a, null, 0); }
  99     private void iterateTriangles(int mode, Mesh m, Affine a, PixelBuffer buf, int color) {
 100         tick++;
 101         int numiter = 0;
 102         if (iter.length < triangles.size()) iter = new Triangle[triangles.size()];
 103         iter[numiter++] = triangle0;
 104         while(numiter > 0) {
 105             Triangle t = iter[--numiter];
 106             if (t==null) return;  // FIXME: is this right?!?
 107             if (t.tick >= this.tick) continue;
 108             switch(mode) {
 109                 case ITERATE_STROKE:          t.stroke(buf, a, color); break;
 110                 case ITERATE_CLEAR:           t.clear(); break;
 111                 case ITERATE_CLEAR_WASSET:    t.inWasSet = false; break;
 112                 case ITERATE_INTERSECT:
 113                 case ITERATE_SUBTRACT: {
 114                     if (!t.in) break;
 115                     Point p = Imprecise.center(Mesh.this, t.v(1), t.v(2), t.v(3));
 116                     boolean oin = m.queryPoint(p.multiply(a));
 117                     t.in = (mode==ITERATE_SUBTRACT) ? (t.in && !oin) : (t.in && oin);
 118                     break;
 119                     }
 120                 case ITERATE_ADD: {
 121                     for(int i=1; i<=3; i++) {
 122                         Edge e = t.e(i);
 123                         if (e.t1 != null && e.t1.tick >= this.tick) continue;
 124                         if (e.t2 != null && e.t2.tick >= this.tick) continue;
 125                         if (!e.locked()) continue;
 126                         if ((e.t1==null || !e.t1.in) && (e.t2==null || !e.t2.in)) continue;
 127                         Point p1 = e.v(1).multiply(a);
 128                         Point p2 = e.v(2).multiply(a);
 129                         Vertex v1=null, v2=null;
 130                         v1 = m.vertex(p1);
 131                         v2 = m.vertex(p2);
 132                         if (v1==v2) continue;
 133                         m.getEdge(v1, v2).lock(v1, 0);
 134                     }
 135                     if (check) checkAllDelaunay();
 136                     break;
 137                 }
 138             }
 139             t.tick = this.tick;
 140             for(int i=1; i<=3; i++) {
 141                 Triangle ti = t.t(i);
 142                 if (ti == null) continue;
 143                 if (ti.tick >= this.tick) continue;
 144                 iter[numiter++] = ti;
 145             }
 146         }
 147     }
 148     public void checkAllDelaunay() {
 149         for(int i=0; i<triangles.size(); i++)
 150             ((Triangle)triangles.get(i)).checkDelaunay();
 151     }
 152
 153     public void clipOp(Mesh m, Affine a, boolean subtract) {
 154         seekTime = 0;
 155         long start = System.currentTimeMillis();
 156         m.add(this, a);
 157         iterateTriangles(subtract ? ITERATE_SUBTRACT : ITERATE_INTERSECT, m, a.inverse());
 158         float total = (float)((System.currentTimeMillis() - start));
 159         float seek  = (float)seekTime;
 160         if (total > 80) System.out.println("clip in " + (100 * (seek/total)) + "%");
 161     }
 162
 163     // Imprecise Geometry //////////////////////////////////////////////////////////////////////////////
 164     // (all of these can be off by a good margin and degrade only performance, not correctness) ////////
 165     ////////////////////////////////////////////////////////////////////////////////////////////////////
 166
 167     private static class Imprecise {
 168         public static Point center(Mesh m, Point v1, Point v2, Point v3) {
 169             return m.point((float)((double)v1.x+(double)v2.x+(double)v3.x)/3,
 170                            (float)(((double)v1.y+(double)v2.y+(double)v3.y)/3));
 171         }
 172         public static boolean near(Point a, Point b) {
 173             return ddistance(a.x, a.y, b.x, b.y) <= epsilon;
 174         }
 175         public static boolean incircle(Point v1, Point v2, Point v3, Point p) {
 176             /*
 177             float a = 0;
 178             Q: for(int q=0; q<2; q++) {
 179                 for(int i=0; i<3; i++) {
 180                     if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q;
 181                     Point t = v2; v2=v3; v3=v1; v1 = t;
 182                 }
 183                 Point t = v2; v2=v3; v3=t;
 184             }
 185             if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
 186             double a1  = (v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
 187             double a2  = (v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
 188             double ccx = (a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2;
 189             double ccy = (a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2;
 190             double r2  = (v1.x-ccx)*(v1.x-ccx)+(v1.y-ccy)*(v1.y-ccy);
 191             double pd  = (p.x-ccx)*(p.x-ccx)+(p.y-ccy)*(p.y-ccy);
 192             return r2 > pd;
 193             */
 194             return Predicates.incircle(v1.x, v1.y, v2.x, v2.y, v3.x, v3.y, p.x, p.y)>0;
 195         }
 196         public static Point midpoint(Mesh m, Point a, Point b) { return m.point((a.x+b.x)/2,(a.y+b.y)/2); }
 197         private static double ddistance(double x1, double y1, double x2, double y2) {
 198             return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
 199         public static float area(Point p1, Point p2, Point p3) {
 200             float x1 = p1.x;
 201             float x2 = p2.x;
 202             float x3 = p3.x;
 203             float y1 = p1.y;
 204             float y2 = p2.y;
 205             float y3 = p3.y;
 206             double a = ddistance(x1,y1,x2,y2);
 207             double b = ddistance(x2,y2,x3,y3);
 208             double c = ddistance(x3,y3,x1,y1);
 209             double s = (a+b+c)/2;
 210             double t = s*(s-a)*(s-b)*(s-c);
 211             if (t < 0) return 0;
 212             return (float)Math.sqrt(t);
 213         }
 214
 215         public static Point intersect(Mesh m, Point v1, Point v2, Point v3, Point v4) {
 216             double a1 = v2.y-v1.y;
 217             double a2 = v4.y-v3.y;
 218             double b1 = v1.x-v2.x;
 219             double b2 = v3.x-v4.x;
 220             double c1 = -1 * (a1*v1.x+b1*v1.y);
 221             double c2 = -1 * (a2*v3.x+b2*v3.y);
 222             double x = (b2*c1-c2*b1)/(b1*a2-b2*a1);
 223             double y = (a2*c1-c2*a1)/(a1*b2-a2*b1);
 224             if (Double.isNaN(x) || Double.isNaN(y)) throw new Error("cannot intersect:\n ");
 225             return m.point((float)x,(float)y);
 226         }
 227         public static int side(Point p1, Point p2, Point p3) {
 228             /*
 229             int ret = 0;
 230             float x0 = p1.x;
 231             float x = p2.x;
 232             float x2 = p3.x;
 233             float y0 = p1.y;
 234             float y = p2.y;
 235             float y2 = p3.y;
 236
 237             // this MUST be done to double precision
 238             double a = y-y0, b = x0-x, c = a*(x0 - x2) + b*(y0 - y2);
 239             if      (c > 0) ret = b>=0 ? -1 :  1;
 240             else if (c < 0) ret = b>=0 ?  1 : -1;
 241             else ret = 0;
 242             return ret;
 243             */
 244             return Predicates.side(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
 245         }
 246
 247     }
 248
 249     // Precise Geometry /////////////////////////////////////////////////////////////////////////////
 250
 251     static {
 252         Runtime.getRuntime().load(new java.io.File("Predicates.jnilib").getAbsolutePath());
 253     }
 254
 255
 256     // Vertex //////////////////////////////////////////////////////////////////////////////
 257
 258     public static int state = 0;
 259     public Vertex vertex(Point p, Affine a) { return vertex(p.multiply(a)); }
 260     public Vertex vertex(Point p) {
 261         Vertex ret = null;
 262         switch(numvertices) {
 263             case 0: return (vertex0 = new Vertex(p));
 264             case 1: return Imprecise.near(vertex0,p) ? vertex0 : (vertex1 = new Vertex(p));
 265             case 2: {
 266                 if (Imprecise.near(vertex0,p)) return vertex0;
 267                 if (Imprecise.near(vertex1,p)) return vertex1;
 268                 Vertex v2 = new Vertex(p);
 269                 triangle(newEdge(vertex0,vertex1), newEdge(vertex1,v2), newEdge(v2,vertex0));
 270                 return v2;
 271             }
 272             default: {
 273                 Triangle t = null;
 274                     t = triangle0.seek(p);
 275                 for(int i=1; i<=3; i++)
 276                     for(int j=1; j<=2; j++)
 277                         if (t != null && Imprecise.near(t.e(i).v(j),p))
 278                             return t.e(i).v(j);
 279                 // this will probably always need to be here since a vertex for which side()==0 could still
 280                 // be slightly off to one side (and hence part of a neighboring "sliver" triangle.
 281                 for(int k=1; k<=3; k++)
 282                     for(int i=1; i<=3; i++)
 283                         for(int j=1; j<=2; j++)
 284                             if (t != null && t.t(k)!=null && Imprecise.near(t.t(k).e(i).v(j),p))
 285                                 return t.t(k).e(i).v(j);
 286                 for(int i=0; i<vertices.size(); i++)
 287                     if (Imprecise.near(((Vertex)vertices.get(i)),p))
 288                         throw new Error("bah! " + p + " " + vertices.get(i) + " state: " + state +
 289                                         "\n  "   + t +
 290                                         "\n    " + t.t(1) +
 291                                         "\n    " + t.t(2) +
 292                                         "\n    " + t.t(3)
 293                                         );
 294                 Vertex v = new Vertex(p);
 295                 if      (t.e(3).intersects(p))          t.e(3).bisect(v);
 296                 else if (t.e(1).intersects(p))          t.e(1).bisect(v);
 297                 else if (t.e(2).intersects(p))          t.e(2).bisect(v);
 298                 else if (t.contains(v))                 t.trisect(v);
 299                 else                                    t.addHull(v);
 300                 return v;
 301             }
 302         }
 303     }
 304
 305     Vector vertices = new Vector();
 306
 307     private Point point(float x, float y) { return new Point(x,y); }
 308     //private Point point(Point p, Affine a) { return point(p.x(a), p.y(a)); }
 309     private class Point {
 310         public float x;
 311         public float y;
 312         public String toString() { return "("+x+","+y+")"; }
 313         public Point multiply(Affine a) { return point(x(a),y(a)); }
 314         public Point(float x, float y) { this.x = x; this.y = y; }
 315         public Point(Point p) { this(p.x,p.y); }
 316         public float x(Affine a) { return a.multiply_px(x,y); }
 317         public float y(Affine a) { return a.multiply_py(x,y); }
 318         public int xi(Affine a) { return (int)x(a); }
 319         public int yi(Affine a) { return (int)y(a); }
 320         public boolean intersects(Point p1, Point p2) {
 321             return
 322                 Imprecise.side(p1,p2,this)==0 &&
 323                 x <= Math.max(p1.x,p2.x) &&
 324                 x >= Math.min(p1.x,p2.x) &&
 325                 y <= Math.max(p1.y,p2.y) &&
 326                 y >= Math.min(p1.y,p2.y);
 327         }
 328     }
 329
 330     private final class Vertex extends Point implements org.ibex.classgen.opt.Arena.Gladiator {
 331         public Vertex(Point p) {
 332             super(p);
 333             numvertices++;
 334             vertices.add(this);
 335         }
 336     }
 337
 338     // Edge //////////////////////////////////////////////////////////////////////////////
 339
 340     public Edge newEdge(Vertex v1, Vertex v2) {
 341         return getEdge(v1,v2);
 342         /*
 343         if (v1==v2) throw new Error();
 344         Edge ret = (Edge)edges.get(v1,v2);
 345         //if (ret != null) throw new Error("tried to get an edge that already exists!");
 346         if (ret == null) ret = new Edge(v1,v2);
 347         return ret;
 348         */
 349     }
 350
 351     public Edge getEdge(Vertex v1, Vertex v2) {
 352         if (v1==v2) throw new Error();
 353         Edge ret = (Edge)edges.get(v1,v2);
 354         if (ret != null) return ret;
 355         //Edge ret = null;
 356         Triangle t = null;
 357         if (triangle0 != null) {
 358             t = triangle0.seek(Imprecise.midpoint(this, v1,v2));
 359             if (t != null)
 360                 for(int i=1; i<=3; i++)
 361                     if (t.e(i).hasVertex(v1) && t.e(i).hasVertex(v2)) ret = t.e(i);
 362         }
 363         if (ret == null) {
 364             ret = (Edge)edges.get(v1,v2);
 365             if (ret != null && (ret.t1 != null || ret.t2 != null)) throw new Error("bah! " + ret);
 366         }
 367         if (ret == null) ret = new Edge(v1,v2);
 368         return ret;
 369     }
 370
 371     private final class Edge implements org.ibex.classgen.opt.Arena.Gladiator {
 372         private final Vertex v1;
 373         private final Vertex v2;
 374         Triangle t1 = null;
 375         Triangle t2 = null;
 376
 377         private int locks = 0;
 378         private int weight = 0;
 379
 380         public void delete() {
 381             if (t1!=null || t2!=null) throw new Error("tried to remove an edge before its triangles");
 382             edges.put(v1,v2,null);
 383             edges.put(v2,v1,null);
 384         }
 385
 386         public Vertex v(int i) {
 387             switch(i) {
 388                 case 1: return v1;
 389                 case 2: return v2;
 390                 default: return null;
 391             }
 392         }
 393
 394         public Edge rotate(Vertex v, boolean clockwise) {
 395             Triangle t = v==v1 ? (clockwise?t1:t2) : v==v2 ? (clockwise?t2:t1) : null;
 396             if (t==null) return null;
 397             for(int i=1; i<=3; i++) if (t.e(i)!=this && t.e(i).hasVertex(v)) return t.e(i);
 398             return null;
 399         }
 400         public Edge rotateHull(boolean clockwise) {
 401             if (t1!=null && t2!=null) throw new Error("nextHull() called on non-hull edge");
 402             Vertex v = rotate(v1, !clockwise) == null ? v2 : v1;
 403             Edge e = rotate(v, !clockwise);
 404             while(!e.hasTriangle(null) && e!=this) e = e.rotate(v, !clockwise);
 405             if (e==this) throw new Error("confused");
 406             return e;
 407         }
 408
 409         public boolean isNear(Point p) { return Imprecise.area(v1,v2,p) <= epsilon2; }
 410         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; }
 411         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; }
 412         public Vertex opposingVertex(Vertex v) { return v1==v ? v2 : v1; }
 413         public int weight() { return weight; }
 414         public int weight(Vertex v) { return v==v1?weight:(-1*weight); }
 415         public boolean locked() { return locks > 0; }
 416         public boolean partitions(Point va, Point vb) { return side(va,vb)==-1; }
 417         public int     side(Point a, Point b) { return side(a) * side(b); }
 418         public int     side(Point a)          { return Imprecise.side(v(1), v(2), a); }
 419         public boolean hasVertex(Vertex v) { return v1==v || v2==v; }
 420         public boolean hasTriangle(Triangle t) { return t==t1 || t==t2; }
 421         public String toString() { return v(1) + "--" + v(2); }
 422         public void rmTriangle(Triangle t) {
 423             if (t1==t) t1 = null;
 424             else if (t2==t) t2 = null;
 425             else throw new Error();
 426             if (t1==null && t2==null) delete();
 427         }
 428         public boolean convex() { return this.intersects(t1.opposingVertex(t2), t2.opposingVertex(t1)); }
 429
 430         public boolean intersects(Point p) { return p.intersects(v1, v2); }
 431         public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); }
 432         public boolean intersects(Point va, Point vb) {
 433             return
 434                 !Imprecise.near(v1,va) &&
 435                 !Imprecise.near(v1,vb) &&
 436                 !Imprecise.near(v2,va) &&
 437                 !Imprecise.near(v2,vb) &&
 438                 partitions(va, vb) &&
 439                 Imprecise.side(va, vb, v1) * Imprecise.side(va, vb, v2) == -1;
 440         }
 441
 442         public Triangle opposingTriangle(Triangle t) {
 443             if (t1 == t) return t2;
 444             if (t2 == t) return t1;
 445             throw new Error();
 446         }
 447         public void addTriangle(Triangle tnew) {
 448             if (t1==null) t1 = tnew;
 449             else if (t2==null) t2 = tnew;
 450             else throw new Error("attempted to addTriangle("+tnew+")\n  t1="+t1+"\n  t2="+t2);
 451             if (t1==t2) throw new Error("same triangle can't be both sides of an edge");
 452             if (v1.x==v2.x) {
 453                 boolean b  = side(t1.opposingVertex(this)) == side(point(Float.MAX_VALUE, v1.y));
 454                 Triangle right = b ? t1 : t2;       // right side
 455                 Triangle left  = b ? t2 : t1;       // left side
 456                 t1 = right;
 457                 t2 = left;
 458             } else {
 459                 boolean b       = side(t1.opposingVertex(this)) == side(point(0, Float.MAX_VALUE));
 460                 Triangle top    = b ? t1 : t2;
 461                 Triangle bottom = b ? t2 : t1;
 462                 if (v1.y==v2.y) {                         // horizontal
 463                     t1 = bottom;
 464                     t2 = top;
 465                 } else if (v1.x > v2.x) {                 // positive slope
 466                     t1 = top;
 467                     t2 = bottom;
 468                 } else {                                  // negative slope
 469                     t1 = bottom;
 470                     t2 = top;
 471                 }
 472             }
 473         }
 474         public void bisect(Vertex v) {
 475             if (v==this.v(1)) throw new Error("this should never happen");
 476             if (v==this.v(2)) throw new Error("this should never happen");
 477             Edge e = this;
 478             Triangle t1 = this.t1==null?this.t2:this.t1;
 479             Triangle t  = t1==this.t1?this.t2:this.t1;
 480             Vertex opposing = t1.opposingVertex(e);
 481             Triangle top = null, ton = null;
 482             Vertex left = e.v(1);
 483             Vertex right = e.v(2);
 484             Vertex tov = null;
 485             boolean in1 = t1.in;
 486             boolean in2 = false;
 487             Triangle opposingTriangleLeft = t1.opposingTriangle(left);
 488             Triangle opposingTriangleRight = t1.opposingTriangle(right);
 489             Edge right_v = newEdge(right, v);
 490             Edge left_v = newEdge(left, v);
 491             Edge opposing_v = newEdge(opposing, v);
 492             Edge tov_v = null;
 493             Edge right_tov = null;
 494             Edge left_tov = null;
 495             Edge right_opposing = t1.opposingEdge(left);
 496             Edge left_opposing = t1.opposingEdge(right);
 497             if (t != null) {
 498                 t.check();
 499                 right_tov = t.opposingEdge(left);
 500                 left_tov = t.opposingEdge(right);
 501                 top = t.opposingTriangle(left);
 502                 ton = t.opposingTriangle(right);
 503                 tov = t.opposingVertex(t1);
 504                 in2 = t.in;
 505                 tov_v = newEdge(tov, v);
 506                 if (top == t1) top = null;                                    // is this possible?
 507                 if (ton == t1) ton = null;                                    // is this possible?
 508                 if (opposingTriangleLeft == t) opposingTriangleLeft = null;   // is this possible?
 509                 if (opposingTriangleRight == t) opposingTriangleRight = null; // is this possible?
 510                 t.delete();
 511             }
 512             t1.delete();
 513             Triangle ta, tb, tc=null, td=null;
 514             ta = triangle(right_opposing, opposing_v, right_v);
 515             tb = triangle(left_opposing, opposing_v, left_v);
 516             ta.in = in1;
 517             tb.in = in1;
 518             if (t != null) {
 519                 if (tov_v==left_v) throw new Error("barf");
 520                 if (tov_v==right_v) throw new Error("barf");
 521                 if (tov_v==left_tov) throw new Error("barf");
 522                 if (tov_v==right_tov) throw new Error("barf");
 523                 if (right_v==right_tov) throw new Error("barf");
 524                 if (left_v==left_tov) throw new Error("barf " + tov + " " + left);
 525                 tc = triangle(left_tov, tov_v, left_v);
 526                 td = triangle(right_tov, tov_v, right_v);
 527                 tc.in = in2;
 528                 td.in = in2;
 529             }
 530             if (locked()) fracture(v);
 531             else          ta.fixup();
 532             if (ta!=null) ta.check();
 533             if (tb!=null) tb.check();
 534             if (tc!=null) tc.check();
 535             if (td!=null) td.check();
 536         }
 537         public Edge flip() {
 538             if (locked()) throw new Error("attempted to remove a locked edge: " + this);
 539             boolean in = t1.in && t2.in;
 540
 541             Edge e3   = rotate(v1, true);
 542             Vertex vb = e3.unCommonVertex(this);
 543             Edge e6   = e3.rotate(vb, true);
 544
 545             Edge e4   = rotate(v2, true);
 546             Vertex va = e4.unCommonVertex(this);
 547             Edge e1   = e4.rotate(va, true);
 548
 549             Edge e    = newEdge(va, vb);
 550
 551             t1.delete();
 552             t2.delete();
 553             Triangle ta, tb;
 554             ta = triangle(e1, e, e3);
 555             tb = triangle(e4, e, e6);
 556             ta.in = in;
 557             tb.in = in;
 558             return ta.getSharedEdge(tb);
 559         }
 560         public void fracture(Vertex vx) {
 561             if (!locked()) throw new Error("attempt to fracture an edge which does not exist: " + v1 + " " + v2);
 562             // delete-me
 563             Edge v1vx = newEdge(v1, vx);
 564             Edge vxv2 = newEdge(vx, v2);
 565             v1vx.locks += locks;
 566             vxv2.locks += locks;
 567             locks = 0;
 568             v1vx.weight += v(1)==v1vx.v(1) ? weight : (-1 * weight);
 569             vxv2.weight += v(2)==vxv2.v(2) ? weight : (-1 * weight);
 570             weight = 0;
 571             v1vx.lock();
 572             vxv2.lock();
 573         }
 574         public void fracture(Edge e) {
 575             triangle0=e.t1==null?e.t2:e.t1;
 576             Vertex v0 = vertex(Imprecise.intersect(Mesh.this, v1,v2,e.v(1),e.v(2)));
 577             if (v0 != e.v(1) && v0 != e.v(2) && e.locked()) e.fracture(v0);
 578             if (v0 != v1 && v0 != v2) fracture(v0);
 579         }
 580         public void lock(Vertex v1, int delta) {
 581             weight += this.v(1)==v1 ? delta : (-1 * delta);
 582             locks += 1;
 583             lock();
 584         }
 585         public void lock() {
 586             Triangle t = t1==null ? t2 : t1;
 587             if (t==null) t = triangle0.seek(v1);
 588             if (!t.hasVertex(v1)) throw new Error("this sucks balls");
 589             boolean skipfo = false;
 590             for(Triangle told = null; t != told; t = told==null ? t : t.followVector(v1,v2)) {
 591                 told = t;
 592                 if (!t.encounters(v1,v2)) break;
 593                 if (!t.encounters(v2,v1)) break;
 594                 Triangle tlast = t.followVector(v2,v1);
 595                 if (tlast == null) throw new Error("seek from: " + tlast + "\n  " + v1 + " -> " + v2);
 596                 if (tlast == t) { if (t.hasVertex(v1)) continue; throw new Error("no predecessor"); }
 597                 Edge e = t.getSharedEdge(tlast);
 598                 if (!e.convex()) continue;
 599                 if (e.v(1)==v1 || e.v(1)==v2 || e.v(2)==v1 || e.v(2)==v2) { continue; }
 600                 if (this.intersects(e.v(1))) { fracture(e.v(1)); return; }
 601                 if (this.intersects(e.v(2))) { fracture(e.v(2)); return; }
 602                 if (!this.intersects(e)) continue;
 603                 if (e.locked()) {
 604                     fracture(e);
 605                     return;
 606                 } else {
 607                     Edge eold = e = e.flip();
 608                     t = e.t1;
 609                     if (t==null || !t.intersects(this)) t = e.t2;
 610                     told = t;
 611                     if (eold.intersects(this)) {
 612                         t = t.followVector(v1,v2);
 613                         if (t != e.t1 && t != e.t2) t = told;
 614                         continue;
 615                     } else {
 616                         told = null;
 617                         while(t.intersects(this)) {
 618                             if (t==told) break;
 619                             told = t;
 620                             /*
 621                             System.out.println("I think that " + this + " intersects:\n  "+t);
 622                             for(int i=1; i<=3; i++)
 623                                 System.out.println("    " + t.e(i) + ": " + t.e(i).intersects(this));
 624                             */
 625                             t = t.followVector(v2,v1);
 626                         }
 627                         t = told;
 628                         told = null;
 629                         continue;
 630                     }
 631                 }
 632             }
 633             if (t1!=null) t1.fixup();
 634             if (t2!=null) t2.fixup();
 635         }
 636
 637         public boolean violated = false;
 638         public void stroke(PixelBuffer buf, Affine a, int color) {
 639             int c =
 640                 violated
 641                 ? 0xffff0000
 642                 : debug
 643                 ? (weight() == 0 ? color : 0xffff0000)
 644                 : (weight() != 0 ? color : 0);
 645             if (c != 0) buf.drawLine(v1.xi(a), v1.yi(a), v2.xi(a), v2.yi(a), c);
 646         }
 647         public Edge(Vertex v1, Vertex v2) {
 648             boolean b = v1.y < v2.y || (v1.y==v2.y && v1.x < v2.x);
 649             this.v1 = b ? v1 : v2;
 650             this.v2 = b ? v2 : v1;
 651             edges.put(v1, v2, this);
 652             edges.put(v2, v1, this);
 653         }
 654     }
 655
 656     // Triangle //////////////////////////////////////////////////////////////////////////////
 657
 658     public Triangle triangle(Edge e1, Edge e2, Edge e3) {
 659         if (e3.t1!=null && e3.t1.hasEdge(e2) && e3.t1.hasEdge(e1)) return e3.t1;
 660         if (e3.t2!=null && e3.t2.hasEdge(e2) && e3.t2.hasEdge(e1)) return e3.t2;
 661         if (e2.t1!=null && e2.t1.hasEdge(e2) && e2.t1.hasEdge(e1)) return e2.t1;
 662         if (e2.t2!=null && e2.t2.hasEdge(e2) && e2.t2.hasEdge(e1)) return e2.t2;
 663         if (e1.t1!=null && e1.t1.hasEdge(e2) && e1.t1.hasEdge(e1)) return e1.t1;
 664         if (e1.t2!=null && e1.t2.hasEdge(e2) && e1.t2.hasEdge(e1)) return e1.t2;
 665         Triangle t = new Triangle(e1, e2, e3);
 666         if (debug) t.check();
 667         if (triangle0 == null) triangle0 = t;
 668         return t;
 669     }
 670
 671     public static boolean fixing = false;
 672     public static int count = 0;
 673     private final class Triangle implements org.ibex.classgen.opt.Arena.Gladiator {
 674
 675         //final double r2;
 676         //final Point cc;
 677
 678         private Edge e1, e2, e3;    // should be final =(
 679         private Vertex v1, v2, v3;
 680         public int tick;
 681
 682         boolean in = false;
 683         boolean inWasSet = false;
 684         boolean painted = false;
 685         boolean dirty = true;
 686
 687         //public Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; }
 688         public Edge e(int i) {
 689             switch(i) {
 690                 case 1: return e1;
 691                 case 2: return e2;
 692                 case 3: return e3;
 693                 default: return null;
 694             } }
 695
 696         //public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); }
 697         public Vertex v(int i) {
 698             switch(i) {
 699                 case 1: return v1;
 700                 case 2: return v2;
 701                 case 3: return v3;
 702                 default: return null;
 703             } }
 704         public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; }
 705         public Vertex closestVertex(Point p) {
 706             double d1 = Math.sqrt((v(1).x-p.x)*(v(1).x-p.x)+(v(1).y-p.y)*(v(1).y-p.y));
 707             double d2 = Math.sqrt((v(2).x-p.x)*(v(2).x-p.x)+(v(2).y-p.y)*(v(2).y-p.y));
 708             double d3 = Math.sqrt((v(3).x-p.x)*(v(3).x-p.x)+(v(3).y-p.y)*(v(3).y-p.y));
 709             return (d1 < d2 && d1 < d3) ? v(1) : (d2 < d3) ? v(2) : v(3);
 710         }
 711
 712         public boolean encounters(Point p1, Point p2) {
 713             for(int i=1; i<=3; i++) {
 714                 if (Imprecise.near(v(i),p1)) return true;
 715                 if (Imprecise.near(v(i),p2)) return true;
 716                 if (v(i).intersects(p1,p2)) return true;
 717                 if (e(i).intersects(p1,p2)) return true;
 718             }
 719             return contains(p1) || contains(p2);
 720         }
 721         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; }
 722         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; }
 723
 724         public boolean intersects(Vertex va, Vertex vb){return e(1).intersects(va,vb)||e(2).intersects(va,vb)||e(3).intersects(va,vb);}
 725         public boolean intersects(Edge e){ return intersects(e.v(1),e.v(2)); }
 726         public boolean intersects(Point p){ return e(1).intersects(p) || e(2).intersects(p) || e(3).intersects(p); }
 727         public boolean hasEdge(Edge e) { return e.t1==this || e.t2==this; }
 728         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)); }
 729         public boolean hasVertex(Vertex a) { return a==v(1) || a==v(2) || a==v(3); }
 730         public Vertex opposingVertex(Triangle t) { return t(3)==t ? v(3) : t(1)==t ? v(1) : t(2)==t ? v(2) : null; }
 731         public Vertex opposingVertex(Edge e) { return e==e(1) ? v(1) : e==e(2) ? v(2) : e==e(3) ? v(3) : null; }
 732         public Edge   opposingEdge(Vertex v) { return v==v(1) ? e(1) : v==v(2) ? e(2) : v==v(3) ? e(3) : null; }
 733         public Triangle opposingTriangle(Vertex v) { return v(1)==v ? t(1) : v(2)==v ? t(2) : v(3)==v ? t(3) : null; }
 734         public String toString() { return "<<"+v(1)+""+v(2)+""+v(3)+">>"; }
 735
 736         public void stroke(PixelBuffer buf, Affine a, int color) {
 737             for(int i=1; i<=3; i++) if (in || debug) e(i).stroke(buf, a, color);
 738         }
 739         public Triangle fixup() {
 740             if (!dirty) return this;
 741             dirty = false;
 742             for(int i=1; i<=3; i++) {
 743                 Triangle t = t(i);
 744                 if (t==null) continue;
 745                 if (!t.cc(v(i))) continue;
 746                 Edge e = e(i);
 747                 if (e.locked()) { t.fixup(); continue; }
 748                 return e.flip().t1.fixup();
 749             }
 750             return this;
 751         }
 752         public void addHull(Vertex vnew) {
 753             Edge e = e(1).hasTriangle(null) ? e(1) : e(2).hasTriangle(null) ? e(2) : e(3).hasTriangle(null) ? e(3) : null;
 754             Triangle t = e.opposingTriangle(null), newt = null;
 755             while (!e.partitions(vnew, t.opposingVertex(e))) {
 756                 e = e.rotateHull(true);
 757                 t = e.opposingTriangle(null);
 758             }
 759             Edge ea = newEdge(e.v(1), vnew);
 760             Edge eb = newEdge(e.v(2), vnew);
 761             newt = triangle(e, ea, eb);
 762             if (ea.rotateHull(true) != eb) { Edge temp = ea; ea = eb; eb = temp; }
 763             for(int i=1; i<=2; i++)
 764                 for(Edge ex = i==1?eb:ea; ;) {
 765                     e = ex.rotateHull(i==1);
 766                     t = e.opposingTriangle(null);
 767                     if (!e.partitions(vnew, t.opposingVertex(e))) break;
 768                     Edge ep = newEdge(vnew, e.unCommonVertex(ex));
 769                     newt = triangle(e, ex, ep);
 770                     ex = ep;
 771                 }
 772             if (newt==null) throw new Error("couldn't find a place to add a triangle for " + vnew);
 773             newt.fixup();
 774         }
 775         public Triangle seek(Point p) {
 776             Triangle t = this;
 777             try {
 778             while (true) {
 779                 count++;
 780                 //System.out.println("seek " + t + " -> " + p + " / " + count);
 781                 if      (t.contains(p)) { state = -1; return t; }
 782                 else if (t.intersects(p))    { state = 1; return t; }
 783                 else if (t.e(3).intersects(p))                { state = 2; return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t; }
 784                 else if (t.e(1).intersects(p))                { state = 3; return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t; }
 785                 else if (t.e(2).intersects(p))                {state = 4;  return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t; }
 786                 else {
 787                     // we "slingshot" back from the centroid in case we're inside of a "sliver" triangle
 788                     //Point p0 = t.c();
 789                     //Triangle t2 = t.followVector(p0, p);
 790                     Triangle t2 = t.followVector(t.closestVertex(p), p);
 791                     if (t2==null || t2==t) {
 792                         if      (t.e(1).partitions(p, t.v(1)) && t.t(1)!=null) t = t.t(1);
 793                         else if (t.e(2).partitions(p, t.v(2)) && t.t(2)!=null) t = t.t(2);
 794                         else if (t.e(3).partitions(p, t.v(3)) && t.t(3)!=null) t = t.t(3);
 795                         else {
 796                             state = 5;
 797                             return t;
 798                         }
 799                     } else {
 800                         t = t2;
 801                     }
 802                 }
 803             }
 804             } finally { if (t!=null) triangle0 = t; }
 805         }
 806
 807         // gives the triangle across the edge through which the ray v(1)-->v(2) exits this triangle
 808         public Triangle followVector(Point p1, Point p2) {
 809             Triangle ret = followVector2(p1, p2);
 810             if (ret==null) return ret;
 811             triangle0 = ret;
 812             if (!ret.encounters(p1,p2)) return this;
 813             return ret;
 814         }
 815         public Triangle followVector2(Point p1, Point p2) {
 816             if (contains(p2) || intersects(p2) || Imprecise.near(v(1),p2) || Imprecise.near(v(2),p2) || Imprecise.near(v(3),p2))
 817                 return this;
 818             for(int i=1; i<=3; i++) if (!Imprecise.near(v(i),p1) && v(i).intersects(p1,p2)) return followVector(v(i),p2);
 819             Triangle t1 = t(1);
 820             Triangle t2 = t(2);
 821             Triangle t3 = t(3);
 822             for(int i=1; i<=3; i++) {
 823                 int k1 = i==1?3:i==2?1:i==3?2:0;
 824                 int k2 = i==1?2:i==2?3:i==3?1:0;
 825                 int k3 = i==1?1:i==2?2:i==3?3:0;
 826                 if (Imprecise.near(v(i),p1)) {
 827                     if (e(k1).partitions(v(k1),p2)) return t(k1);
 828                     if (e(k2).partitions(v(k2),p2)) return t(k2);
 829                     if (e(k3).partitions(v(k3),p2)) return t(k3);
 830                     throw new Error("bad!");
 831                 }
 832             }
 833             //if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2))
 834             for(int i=1; i<=3; i++)
 835                 if (e(i).intersects(p1,p2))
 836                     if (e(i).side(v(i)) * e(i).side(p2) == -1)
 837                         return t(i);
 838             for(int i=1; i<=3; i++)
 839                 if (e(i).partitions(p1,p2))
 840                     return t(i);
 841             for(int i=1; i<=3; i++)
 842                 if (e(i).partitions(v(i),p2))
 843                     return t(i);
 844             for(int i=1; i<=3; i++)
 845                 if (v(i).intersects(p1,p2))
 846                     throw new Error("bad news: \n  "+p1+" -> "+p2+"\n  " + this);
 847
 848             System.out.println("slingshot from: " + p1 + " to " + p2 + " on " + this + "\n" +
 849                                (e(1).side(v(1)) * e(1).side(p2))+" "+
 850                                (e(2).side(v(2)) * e(2).side(p2))+" "+
 851                                (e(3).side(v(3)) * e(3).side(p2))
 852                                );
 853             /*
 854             return followVector(new Point(2*p1.x-p2.x, 2*p1.y-p2.y), p2);
 855             */
 856             //throw new Error("giving up: \n  "+p1+" -> "+p2+"\n  " + this);
 857
 858             final Point pp1 = p1;
 859             final Point pp2 = p2;
 860             new Frame() {
 861                 public void paint(Graphics g) {
 862                     g.setColor(java.awt.Color.white);
 863                     g.fillRect(0, 0, getWidth(), getHeight());
 864                     g.setColor(java.awt.Color.black);
 865                     g.drawLine((int)v(1).x+100, (int)v(1).y+100, (int)v(2).x+100, (int)v(2).y+100);
 866                     g.drawLine((int)v(3).x+100, (int)v(3).y+100, (int)v(2).x+100, (int)v(2).y+100);
 867                     g.drawLine((int)v(1).x+100, (int)v(1).y+100, (int)v(3).x+100, (int)v(3).y+100);
 868
 869                     g.setColor(java.awt.Color.red);
 870                     g.drawLine((int)pp1.x+100, (int)pp1.y+100, (int)pp2.x+100, (int)pp2.y+100);
 871                 }
 872             }.show();
 873             try { Thread.sleep(100000); } catch (Exception e) { }
 874             return null;
 875
 876             /*
 877             throw new Error("invoked followVector() on a Triangle which it does not encounter:\n" +
 878                             "  p1=" + p1 + "\n" +
 879                             "  p2=" + p2 + "\n" +
 880                             "  t =" + this + " (area "+area(v(1)+100,v(2),v(3))+")\n");
 881             */
 882         }
 883
 884         public void check() {
 885             if (e1==null && e2==null && e3==null) return;
 886             if (check) {
 887                 for(int i=1; i<=3; i++) {
 888                     if (e(i).v(1) != v(1) && e(i).v(1) != v(2) && e(i).v(1) != v(3)) throw new Error("inconsistent");
 889                     if (e(i).t1 != this && e(i).t2 != this) throw new Error("inconsistent");
 890                     if (e(i).t1 == e(i).t2) throw new Error("same triangle on both sides of edge");
 891                 }
 892                 if (e(1)==e(2) || e(2)==e(3) || e(3)==e(1)) throw new Error("identical edges");
 893                 for(int i=1; i<=3; i++) {
 894                     if (t(i) == null) continue;
 895                     if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)");
 896                     if (t(i).getSharedEdge(this) != e(i)) throw new Error("blark");
 897                     if (!e(i).hasTriangle(t(i))) throw new Error("blark2");
 898                     if (!e(i).hasTriangle(this)) throw new Error("blark3");
 899                 }
 900                 for(int i=1; i<=3; i++)
 901                     if (e(i).commonVertex(e(i==3?1:(i+1)))==null)
 902                         throw new Error("edges have no common vertex");
 903                 // check that delauanay property is preserved
 904             }
 905         }
 906
 907         public void checkDelaunay() {
 908             for(int i=1; i<=3; i++) {
 909                 if (t(i) == null) continue;
 910                 Vertex v = t(i).opposingVertex(e(i));
 911                 if (!e(i).locked() && /*Imprecise.incircle(v(1), v(2), v(3), v)*/cc(v) /*&& !dirty && !t(i).dirty*/) {
 912                     //throw new Error("Delaunay violation: vertex " + v + "\n  triangle: " + this);
 913                     //System.out.println("violation: " + e(i));
 914                     e(i).violated = true;
 915                 } else {
 916                     e(i).violated = false;
 917                 }
 918             }
 919         }
 920
 921         public void trisect(Vertex v) {
 922             if (!contains(v)) throw new Error("trisect(v) but I don't contain v = " + v);
 923             if (hasVertex(v)) throw new Error("attempt to trisect a triangle at one of its own vertices");
 924             for(int i=3; i>0; i--) if (e(i).intersects(v)/* || e(i).isNear(v)*/) {
 925                 e(i).bisect(v);
 926                 return;
 927             }
 928             Triangle a=null,b=null,c=null;
 929
 930             boolean oldIn = in;
 931             Edge v1v = newEdge(v(1), v);
 932             Edge v2v = newEdge(v(2), v);
 933             Edge v3v = newEdge(v(3), v);
 934             Edge e1 = this.e(1);
 935             Edge e2 = this.e(2);
 936             Edge e3 = this.e(3);
 937             delete();
 938
 939             a = triangle(e3, v1v, v2v);
 940             b = triangle(e2, v1v, v3v);
 941             c = triangle(e1, v3v, v2v);
 942             a.in = oldIn;
 943             b.in = oldIn;
 944             c.in = oldIn;
 945             a.fixup();
 946             a.check();
 947             b.check();
 948             c.check();
 949         }
 950
 951         public void setIn(boolean evenOdd, int weight) {
 952             if (inWasSet) return;
 953             inWasSet = true;
 954             in = (evenOdd && weight%2!=0) || (!evenOdd && weight!=0);
 955             for(int i=1; i<=3; i++) if (t(i) != null) t(i).setIn(evenOdd, weight + e(i).weight());
 956         }
 957
 958         public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
 959             if (painted) return;
 960             painted = true;
 961             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);
 962             for(int i=1; i<=3; i++)
 963                 if (t(i) != null) {
 964                     boolean prepaint = t(i).painted;
 965                     //if (debug) e(i).stroke(buf, a, color);
 966                     t(i).fill(buf, a, clip, color, strokeOnly);
 967                 }
 968         }
 969
 970         public Triangle(Edge e1, Edge e2, Edge e3) {
 971             this.e1 = e1;
 972             this.e2 = e2;
 973             this.e3 = e3;
 974             /*Vertex*/ this.v1 = e(2).unCommonVertex(e(1));
 975             /*Vertex*/ this.v2 = e(3).unCommonVertex(e(2));
 976             /*Vertex*/ this.v3 = e(1).unCommonVertex(e(3));
 977             if (e(1).intersects(v1)) throw new Error("triangle points are colinear");
 978             if (e(2).intersects(v2)) throw new Error("triangle points are colinear");
 979             if (e(3).intersects(v3)) throw new Error("triangle points are colinear");
 980             e(1).addTriangle(this);
 981             e(2).addTriangle(this);
 982             e(3).addTriangle(this);
 983             triangles.add(this);
 984         }
 985         public boolean cc(Point p) {
 986             /*
 987             Vertex v1 = e(2).unCommonVertex(e(1));
 988             Vertex v2 = e(3).unCommonVertex(e(2));
 989             Vertex v3 = e(1).unCommonVertex(e(3));
 990             */
 991             return Imprecise.incircle(v1, v2, v3, p);
 992         }
 993         public void clear() {
 994             if (!painted) return;
 995             painted = false;
 996             if (t(3) != null) t(3).clear();
 997             if (t(1) != null) t(1).clear();
 998             if (t(2) != null) t(2).clear();
 999         }
1000         public void delete() {
1001             if (triangle0 == this) {
1002                 if (t(1) != null) triangle0 = t(1);
1003                 else if (t(2) != null) triangle0 = t(2);
1004                 else if (t(3) != null) triangle0 = t(3);
1005                 else triangle0 = null;
1006             }
1007             triangles.remove(this);
1008             e(1).rmTriangle(this);
1009             e(2).rmTriangle(this);
1010             e(3).rmTriangle(this);
1011             e1 = null;
1012             e2 = null;
1013             e3 = null;
1014         }
1015     }
1016
1017     // Queries /////////////////////////////////////////////////////////////////////////////////
1018
1019     public boolean queryPoint(Point p) {
1020         if (triangle0==null) return false;
1021         Triangle ret = triangle0.seek(p);
1022         return (ret.contains(p) || ret.intersects(p)) && ret.in;
1023     }
1024
1025
1026     // Drawing //////////////////////////////////////////////////////////////////////////////
1027
1028     public void setIn(boolean evenOdd) {
1029         iterateTriangles(ITERATE_CLEAR_WASSET, null, null);
1030         triangle0.setIn(evenOdd, 1);
1031     }
1032
1033     public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
1034         if (triangle0==null) return;
1035         iterateTriangles(ITERATE_CLEAR, null, null);
1036         triangle0.fill(buf, a, clip, color, strokeOnly);
1037     }
1038
1039     public void stroke(PixelBuffer buf, Affine a, int color) {
1040         if (triangle0==null) return;
1041         iterateTriangles(ITERATE_STROKE, null, a, buf, color);
1042     }
1043
1044     public void newcontour() {
1045         if (start != null) add(start.x, start.y);
1046         start = null;
1047         last = null;
1048     }
1049
1050     public Mesh addRect(float x, float y, float w, float h) {
1051         if (w==0 || h==0) return this;
1052         Vertex v1 = vertex(point(x,y));
1053         Vertex v2 = vertex(point(x+w,y));
1054         Vertex v3 = vertex(point(x+w,y+h));
1055         Vertex v4 = vertex(point(x,y+h));
1056         newEdge(v1,v2).lock(v1,1);
1057         newEdge(v2,v3).lock(v2,1);
1058         newEdge(v3,v4).lock(v3,1);
1059         newEdge(v4,v1).lock(v4,1);
1060         setIn(true);
1061         return this;
1062     }
1063
1064     public void add(float x, float y) {
1065         Vertex vx = vertex(point(x,y));
1066         if (vx==last) return;
1067         if (start==null) start = vx;
1068         try {
1069             if (last==null) return;
1070             if (numvertices<3) return;
1071             if (numvertices==3) getEdge(start, last).lock(start,1);
1072             getEdge(last,vx).lock(last,1);
1073         } finally {
1074             last = vx;
1075         }
1076         if (check) checkAllDelaunay();
1077     }
1078
1079 }
1080
1081