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
  10 /**
  11  *  An incremental, adaptive, constrained Delaunay Triangulation.
  12  *  @see Kallmann, Bieri, and Thalmann: Fully Dynamic Constrained Delaunay Triangulations
  13  */
  14 public final class Mesh {
  15
  16     private static final double epsilon = (double)0.00000001;
  17     private static final boolean debug = true;
  18
  19     private              Vector vertices = new Vector();
  20     private              Vector triangles = new Vector();
  21
  22     public static double B = 5;
  23     public static double Q = 0.4;
  24
  25     // Utilities //////////////////////////////////////////////////////////////////////////////
  26
  27     public static double distance(double x1, double y1, double x2, double y2) {
  28         return (double)Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  29     }
  30     public static int side(Vertex v1, Vertex v2, Vertex v3) { return side(v1, v2, v3.x, v3.y); }
  31     public static int side(Vertex v1, Vertex v2, double x, double y) { return side(v1, v2.x, v2.y, x, y); }
  32     public static int side(Vertex v1, double x, double y, Vertex v3) { return side(v1, x, y, v3.x, v3.y); }
  33     public static int side(Vertex v1, double x, double y, double x2, double y2) {
  34         double a = y-v1.y, b = v1.x-x, c = -1 * (a*v1.x+b*v1.y);
  35         return (- (a*x2+c)/b > y2) ? -1 : (- (a*x2+c)/b < y2) ? 1 : 0;
  36     }
  37
  38     public boolean isect(Vertex v1, Vertex v2, Vertex v3, Vertex v4) {
  39         if (v1==v3 || v1==v4 || v2==v3 || v2==v4) return false;
  40         double a = side(v1,v2,v3);
  41         double b = side(v1,v2,v4);
  42         double c = side(v3,v4,v1);
  43         double d = side(v3,v4,v2);
  44         return a!=b && c!=d && a!=0 && b!=0 && c!=0 && d!=0;
  45     }
  46
  47     private void drawLine(PixelBuffer buf, double x1, double y1, double x2, double y2, Affine a, int color) {
  48         buf.drawLine((int)a.multiply_px((float)x1, (float)y1),
  49                      (int)a.multiply_py((float)x1, (float)y1),
  50                      (int)a.multiply_px((float)x2, (float)y2),
  51                      (int)a.multiply_py((float)x2, (float)y2),
  52                      color);
  53     }
  54     public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, boolean strokeOnly) {
  55         for (int i=0; i<triangles.size(); i++) ((Triangle)triangles.elementAt(i)).clear();
  56         ((Triangle)triangles.elementAt(0)).fill(buf, a, color, evenOdd, 1, strokeOnly);
  57     }
  58     public void stroke(PixelBuffer buf, Affine a, int color) {
  59         if (debug)
  60             for (int i=0; i<vertices.size(); i++) {
  61                 Vertex v = (Vertex)vertices.elementAt(i);
  62                 for(Iterator it = v.next.iterator(); it.hasNext();) {
  63                     Vertex v2 = (Vertex)it.next();
  64                     drawLine(buf, v.x, v.y, v2.x, v2.y, a, 0xffff0000);
  65                 }
  66             }
  67         for (int i=0; i<triangles.size(); i++) {
  68             Triangle t = ((Triangle)triangles.elementAt(i));
  69             Vertex v1 = t.v1;
  70             Vertex v2 = t.v2;
  71             Vertex v3 = t.v3;
  72             drawLine(buf, v1.x, v1.y, v2.x, v2.y, a, (debug && t.wind(v1,v2)!=0) ? 0xffffffff : color);
  73             drawLine(buf, v3.x, v3.y, v2.x, v2.y, a, (debug && t.wind(v3,v2)!=0) ? 0xffffffff : color);
  74             drawLine(buf, v1.x, v1.y, v3.x, v3.y, a, (debug && t.wind(v1,v3)!=0) ? 0xffffffff : color);
  75         }
  76     }
  77
  78     // Static //////////////////////////////////////////////////////////////////////////////
  79
  80     public Vertex newVertex(double x, double y) {
  81         Vertex ret = null;
  82         for(int k=0; k<vertices.size(); k++) {
  83             Vertex v = (Vertex)vertices.elementAt(k);
  84             if (v.distance(x,y)<epsilon) if (ret==null || v.distance(x,y) < ret.distance(x,y)) ret = v;
  85         }
  86         return ret==null ? new Vertex(x,y) : ret;
  87     }
  88
  89     public Triangle newTriangle(Vertex v1, Vertex v2, Vertex v3, String source) {
  90         if (v1==v2 || v2==v3 || v3==v1) throw new Error("identical vertices");
  91         for(int i=0; i<triangles.size(); i++) {
  92             Triangle t = (Triangle)triangles.elementAt(i);
  93             if (t.v1==v1&&t.v2==v2&&t.v3==v3) return t;
  94             if (t.v1==v1&&t.v2==v3&&t.v3==v2) return t;
  95             if (t.v1==v2&&t.v2==v3&&t.v3==v1) return t;
  96             if (t.v1==v2&&t.v2==v1&&t.v3==v3) return t;
  97             if (t.v1==v3&&t.v2==v1&&t.v3==v2) return t;
  98             if (t.v1==v3&&t.v2==v2&&t.v3==v1) return t;
  99         }
 100         Triangle t = new Triangle(source, v1, v2, v3, false, false);
 101         if (debug) checktri();
 102         return t;
 103     }
 104
 105     public void checktri() {
 106         for(int i=0; i<triangles.size(); i++) {
 107             Triangle t = (Triangle)triangles.elementAt(i);
 108                 /*
 109             for(int j=0; j<vertices.size(); j++) {
 110                 Vertex v = (Vertex)vertices.elementAt(j);
 111                 if (t.contains(v)) {
 112                     t.special = true;
 113                     throw new Error("triangle "+t+" contains vertex " + v);
 114                 }
 115             }
 116                 */
 117             if (t.t12 != null && (t.t12.t12 != t && t.t12.t23 != t && t.t12.t31 != t)) throw new Error("t12");
 118             if (t.t23 != null && (t.t23.t12 != t && t.t23.t23 != t && t.t23.t31 != t)) throw new Error("t23");
 119             if (t.t31 != null && (t.t31.t12 != t && t.t31.t23 != t && t.t31.t31 != t)) throw new Error("t31");
 120             for(int j=0; j<triangles.size(); j++) {
 121                 Triangle t2 = (Triangle)triangles.elementAt(j);
 122                 if (t2==t) continue;
 123                 if (t.v1==t2.v1&&t.v2==t2.v2&&t.v3==t2.v3) throw new Error("poo");
 124                 if (t.v1==t2.v1&&t.v2==t2.v3&&t.v3==t2.v2) throw new Error("poo");
 125                 if (t.v1==t2.v2&&t.v2==t2.v3&&t.v3==t2.v1) throw new Error("poo");
 126                 if (t.v1==t2.v2&&t.v2==t2.v1&&t.v3==t2.v3) throw new Error("poo");
 127                 if (t.v1==t2.v3&&t.v2==t2.v1&&t.v3==t2.v2) throw new Error("poo");
 128                 if (t.v1==t2.v3&&t.v2==t2.v2&&t.v3==t2.v1) throw new Error("poo");
 129             }
 130         }
 131     }
 132
 133     // Vertex //////////////////////////////////////////////////////////////////////////////
 134
 135     private final class Vertex {
 136         final double x, y;
 137         LinkedList next = new LinkedList();
 138         boolean forced = false;
 139         public String toString() { return "("+x+","+y+")"; }
 140         public double distance(Vertex v) { return distance(v.x, v.y); }
 141         public double distance(double x, double y) { return Mesh.distance(this.x,this.y,x,y); }
 142         public Vertex(double x, double y) {
 143             this.x = x;
 144             this.y = y;
 145             vertices.addElement(this);
 146             Vector vec = new Vector();
 147             Vector vec2 = new Vector();
 148             boolean interior = false;
 149             int edges = 0;
 150             Vertex v = this;
 151             boolean good = false;
 152             for(int i=0; i<triangles.size(); i++) {
 153                 Triangle t = (Triangle)triangles.elementAt(i);
 154                 if (good) throw new Error("impossible: Vertex() -> good twice");
 155                 if (t.contains(this)) {
 156                     System.out.println(t + " contains me");
 157                     Triangle t12 = t.t12;
 158                     Triangle t23 = t.t23;
 159                     Triangle t31 = t.t31;
 160                     t.delete(vec);
 161                     vec2.addElement(newTriangle(this, t.v1, t.v2, "vertexinsertion " + this));
 162                     vec2.addElement(newTriangle(this, t.v3, t.v2, "vertexinsertion " + this));
 163                     vec2.addElement(newTriangle(this, t.v1, t.v3, "vertexinsertion " + this));
 164                     fixup(vec2);
 165                     good = true;
 166                     break;
 167                 } else if (t.t23 != null && v.intersectsSegment(t.v2, t.v3)) {
 168                     System.out.println("on an edge");
 169                     good = true;
 170                     Triangle tt = t.t23;
 171                     tt.delete(null);
 172                     t.delete(null);
 173                     Vertex va =
 174                         ((tt.v1==t.v3&&tt.v2==t.v2)||(tt.v1==t.v2&&tt.v2==t.v3)) ? tt.v3 :
 175                         ((tt.v2==t.v3&&tt.v3==t.v2)||(tt.v2==t.v2&&tt.v3==t.v3)) ? tt.v1 :
 176                         ((tt.v1==t.v3&&tt.v3==t.v2)||(tt.v1==t.v2&&tt.v3==t.v3)) ? tt.v2 : null;
 177                     vec2.addElement(newTriangle(this, t.v1, t.v3, "vertexinsertion " + this));
 178                     vec2.addElement(newTriangle(this, t.v1, t.v2, "vertexinsertion " + this));
 179                     vec2.addElement(newTriangle(this, t.v3, va  , "vertexinsertion " + this));
 180                     vec2.addElement(newTriangle(this, t.v2, va  , "vertexinsertion " + this));
 181                     fixup(vec2);
 182                     break;
 183                 } else if (t.t31 != null && v.intersectsSegment(t.v1, t.v3)) {
 184                     good = true;
 185                     System.out.println("on an edge");
 186                     Triangle tt = t.t31;
 187                     tt.delete(null);
 188                     t.delete(null);
 189                     Vertex va =
 190                         ((tt.v1==t.v1&&tt.v2==t.v3)||(tt.v1==t.v3&&tt.v2==t.v1)) ? tt.v3 :
 191                         ((tt.v2==t.v1&&tt.v3==t.v3)||(tt.v2==t.v3&&tt.v3==t.v1)) ? tt.v1 :
 192                         ((tt.v1==t.v1&&tt.v3==t.v3)||(tt.v1==t.v3&&tt.v3==t.v1)) ? tt.v2 : null;
 193                     vec2.addElement(newTriangle(this, t.v2, t.v1, "vertexinsertion " + this));
 194                     vec2.addElement(newTriangle(this, t.v2, t.v3, "vertexinsertion " + this));
 195                     vec2.addElement(newTriangle(this, t.v1, va  , "vertexinsertion " + this));
 196                     vec2.addElement(newTriangle(this, t.v3, va  , "vertexinsertion " + this));
 197                     fixup(vec2);
 198                     break;
 199                 } else if (t.t12 != null && v.intersectsSegment(t.v1, t.v2)) {
 200                     System.out.println("on an edge");
 201                     good = true;
 202                     Triangle tt = t.t12;
 203                     tt.delete(null);
 204                     t.delete(null);
 205                     Vertex va =
 206                         ((tt.v1==t.v1&&tt.v2==t.v2)||(tt.v1==t.v2&&tt.v2==t.v1)) ? tt.v3 :
 207                         ((tt.v2==t.v1&&tt.v3==t.v2)||(tt.v2==t.v2&&tt.v3==t.v1)) ? tt.v1 :
 208                         ((tt.v1==t.v1&&tt.v3==t.v2)||(tt.v1==t.v2&&tt.v3==t.v1)) ? tt.v2 : null;
 209                     vec2.addElement(newTriangle(this, t.v3, t.v1, "vertexinsertion " + this));
 210                     vec2.addElement(newTriangle(this, t.v3, t.v2, "vertexinsertion " + this));
 211                     vec2.addElement(newTriangle(this, t.v1, va  , "vertexinsertion " + this));
 212                     vec2.addElement(newTriangle(this, t.v2, va  , "vertexinsertion " + this));
 213                     fixup(vec2);
 214                     break;
 215                 }
 216             }
 217             if (triangles.size() > 2 && !good)
 218                 throw new Error("vertex "+this+" did not fall within a triangle or on the edge of at least two");
 219         }
 220         public void fixup(Vector vec) {
 221             while(vec.size() > 0) {
 222                 Triangle t = (Triangle)vec.lastElement();
 223                 vec.setSize(vec.size() - 1);
 224                 if (t.deleted) continue;
 225                 Triangle to = t.v1==this ? t.t23 : t.v2==this ? t.t31 : t.v3==this ? t.t12 : null;
 226                 if (to==null)  continue;
 227                     //throw new Error("fixup invoked with a triangle which does not have me as a vertex");
 228                 if (to.deleted) throw new Error("this should not happen");
 229                 if (to.r < this.distance(to.ccx, to.ccy)) continue;
 230                 if (t.v1==this) {
 231                     //if (t.v2.next.contains(t.v3)) continue;
 232                     //if (t.v3.next.contains(t.v2)) continue;
 233                     Vertex v =
 234                         (to.v1!=t.v2 && to.v1!=t.v3) ? to.v1 :
 235                         (to.v2!=t.v2 && to.v2!=t.v3) ? to.v2 :
 236                         (to.v3!=t.v2 && to.v3!=t.v3) ? to.v3 : null;
 237                     t.delete(null);
 238                     to.delete(null);
 239                     vec.addElement(newTriangle(this, t.v2, v, "fixup"));
 240                     vec.addElement(newTriangle(this, t.v3, v, "fixup"));
 241                 } else if (t.v2==this) {
 242                     //if (t.v3.next.contains(t.v1)) continue;
 243                     //if (t.v1.next.contains(t.v3)) continue;
 244                     Vertex v =
 245                         (to.v1!=t.v1 && to.v1!=t.v3) ? to.v1 :
 246                         (to.v2!=t.v1 && to.v2!=t.v3) ? to.v2 :
 247                         (to.v3!=t.v1 && to.v3!=t.v3) ? to.v3 : null;
 248                     t.delete(null);
 249                     to.delete(null);
 250                     vec.addElement(newTriangle(this, t.v1, v, "fixup"));
 251                     vec.addElement(newTriangle(this, t.v3, v, "fixup"));
 252
 253                 } else if (t.v3==this) {
 254                     //if (t.v1.next.contains(t.v2)) continue;
 255                     //if (t.v2.next.contains(t.v1)) continue;
 256                     Vertex v =
 257                         (to.v1!=t.v2 && to.v1!=t.v1) ? to.v1 :
 258                         (to.v2!=t.v2 && to.v2!=t.v1) ? to.v2 :
 259                         (to.v3!=t.v2 && to.v3!=t.v1) ? to.v3 : null;
 260                     t.delete(null);
 261                     to.delete(null);
 262                     vec.addElement(newTriangle(this, t.v2, v, "fixup"));
 263                     vec.addElement(newTriangle(this, t.v1, v, "fixup"));
 264                 } else {
 265                     throw new Error("this should not happen");
 266                 }
 267                 System.out.println("> made a swap");
 268             }
 269         }
 270
 271         public boolean makeNonDegenerate(Vector vec) {
 272             Vertex v1 = this;
 273             for(int i2 = 0; i2<next.size(); i2++) {
 274                 Vertex v2 = (Vertex)next.get(i2);
 275                 for(int i3 = 0; i3<vertices.size(); i3++) {
 276                     Vertex v3 = (Vertex)vertices.get(i3);
 277                     for(int i4=0; i4<v3.next.size(); i4++) {
 278                         Vertex v4 = (Vertex)v3.next.get(i4);
 279                         if (v1==v3||v1==v4||v2==v3||v2==v4) continue;
 280                         if (isect(v1,v2,v3,v4)) {
 281                             double a1 = v2.y-v1.y;
 282                             double a2 = v4.y-v3.y;
 283                             double b1 = v1.x-v2.x;
 284                             double b2 = v3.x-v4.x;
 285                             double c1 = -1 * (a1*v1.x+b1*v1.y);
 286                             double c2 = -1 * (a2*v3.x+b2*v3.y);
 287                             // a1x+b1y+c1=0
 288                             // y=-(a1x+c1)/b1
 289                             // a2x-(a1x+c1)(b2/b1)+c2=0
 290                             // a2b1x-b2(a1x+c1)+b1c2=0
 291                             // a2b1x-a1b2x-b2c1+b1c2=0
 292                             // x(a2b1-a1b2)-b2c1+b1c2=0
 293                             // x(a2b1-a1b2)=b2c1-b1c2
 294                             // x=(b2c1-b1c2)/(a2b1-a1b2)
 295                             double xq = (b2*c1-c2*b1)/(b1*a2-b2*a1);
 296                             Vertex v0 = newVertex(xq, -1 * (a1*xq+c1) / b1);
 297                             //if (v0==v1||v0==v2||v0==v3||v0==v4) continue;
 298                             System.out.println("inserting new vertex " + v0+" between " + v1+"-"+v2 +" and "+ v3+"-"+v4);
 299                             v1.next.remove(v2);
 300                             v1.next.add(v0);
 301                             v0.next.add(v2);
 302                             v3.next.remove(v4);
 303                             v3.next.add(v0);
 304                             v0.next.add(v4);
 305                             return true;
 306                         }
 307                     }
 308                 }
 309             }
 310             return false;
 311         }
 312
 313         public boolean force() {
 314             if (forced) return false;
 315             forced = true;
 316             boolean ret = false;
 317             OUTER: for(Iterator it=next.iterator(); it.hasNext();) {
 318                 Vertex v = (Vertex)it.next();
 319
 320                 for(int k=0; k<vertices.size(); k++) {
 321                     Vertex v2 = (Vertex)vertices.elementAt(k);
 322                     if (v2==this||v2==v) continue;
 323                     //if (next.contains(v2) || v2.next.contains(this)) continue;
 324                     if (v2.intersectsSegment(v,this)) {
 325                         System.out.println("breaking line " + this+"-"+v + " at vertex " + v2);
 326                         next.remove(v);
 327                         next.add(v2);
 328                         v2.next.add(v);
 329                         ret = true;
 330                         break OUTER;
 331                     }
 332                 }
 333                 boolean good = false;
 334                 for (int i=0; i<triangles.size(); i++) {
 335                     Triangle t = ((Triangle)triangles.elementAt(i));
 336                     if (t.v1==this && t.v2==v) { good = true; break; }
 337                     if (t.v3==this && t.v1==v) { good = true; break; }
 338                     if (t.v3==this && t.v2==v) { good = true; break; }
 339                     if (t.v1==v && t.v2==this) { good = true; break; }
 340                     if (t.v3==v && t.v1==this) { good = true; break; }
 341                     if (t.v3==v && t.v2==this) { good = true; break; }
 342                 }
 343                 if (good) continue;
 344                 HashSet orphans = new HashSet();
 345                 for (int i=0; i<triangles.size(); i++) {
 346                     Triangle t = ((Triangle)triangles.elementAt(i));
 347                     if (t.deleted) continue;
 348                     if (t.intersectsSegment(this, v)) {
 349                         System.out.println("removing triangle " + t + " because it intersects segment " + this+"-"+v);
 350                         Vector vec = new Vector();
 351                         orphans.add(t.v1);
 352                         orphans.add(t.v2);
 353                         orphans.add(t.v3);
 354                         orphans.remove(v);
 355                         orphans.remove(this);
 356                         t.delete(vec);
 357                         i--;
 358                         ret = true;
 359                     }
 360                 }
 361                 orphans.remove(this);
 362                 orphans.remove(v);
 363                 triangulate(orphans, v);
 364                 break;
 365             }
 366             return ret;
 367         }
 368         public void triangulate(HashSet orphans, Vertex v) {
 369             HashSet left = new HashSet();
 370             HashSet right = new HashSet();
 371             for(Iterator it=orphans.iterator(); it.hasNext();) {
 372                 Vertex o = (Vertex)it.next();
 373                 if (o==v||o==this) continue;
 374                 if (side(this, v, o) == -1) left.add(o);
 375                 else if (side(this, v, o) == 1) right.add(o);
 376                 else throw new Error("impossible "+this+" "+v + " " + o);
 377             }
 378             triangulate2(left, v, false);
 379             v.triangulate2(right, this, false);
 380         }
 381         public boolean triangulate2(HashSet orphans, Vertex v, boolean skip) {
 382             Vertex farthest = null;
 383             double dist = 0;
 384             System.out.println("orphans: " + orphans.size());
 385             if (orphans.size()==0) return true;
 386             Vertex o = (Vertex)orphans.iterator().next();
 387             if (orphans.size()==1) {
 388                 Triangle t = newTriangle(this, v, o, "triangulate2 " + v + " " + this);
 389                 if (((t.v1==this && t.v2==v)||(t.v1==v && t.v2==this)) && t.t12==null) return true;
 390                 if (((t.v3==this && t.v2==v)||(t.v3==v && t.v2==this)) && t.t23==null) return true;
 391                 if (((t.v1==this && t.v3==v)||(t.v1==v && t.v3==this)) && t.t31==null) return true;
 392                 return false;
 393             }
 394
 395             Vertex best = null;
 396             OUTER: for(Iterator it=orphans.iterator(); it.hasNext();) {
 397                 o = (Vertex)it.next();
 398                 if (o==v) continue;
 399                 Triangle t = new Triangle("temp", this, v, o, true);
 400                 for(Iterator it2=orphans.iterator(); it2.hasNext();) {
 401                     Vertex z = (Vertex)it2.next();
 402                     if (z==o) continue;
 403                     if (z==v) continue;
 404                     if (z==this) continue;
 405                     if (z.distance(t.ccx, t.ccy) < t.r || t.contains(z)) continue OUTER;
 406                 }
 407                 if (best==null || new Triangle("temp",this,v,best,true).area() > new Triangle("temp",this,v,o,true).area())
 408                     best = o;
 409             }
 410             if (best==null) throw new Error("notgood, #orphans = " + orphans.size());
 411             o = best;
 412             HashSet left = new HashSet();
 413             HashSet right = new HashSet();
 414             for(Iterator it2=orphans.iterator(); it2.hasNext();) {
 415                 Vertex x = (Vertex)it2.next();
 416                 if (o==x||this==x||v==x) continue;
 417                 int side_of_x    = side(o,(this.x+v.x)/2,(this.y+v.y)/2,x);
 418                 int side_of_v    = side(o,(this.x+v.x)/2,(this.y+v.y)/2,v);
 419                 int side_of_this = side(o,(this.x+v.x)/2,(this.y+v.y)/2,this);
 420                 if (side_of_x==side_of_this && side_of_this!=0) right.add(x);
 421                 else if (side_of_x==side_of_v && side_of_v!=0) left.add(x);
 422                 else throw new Error("impossible "+this+" "+v + " " + o + " ==> " + x);
 423             }
 424             boolean doit = true;
 425             doit &= o.triangulate2(left, v, false);
 426             doit &= o.triangulate2(right, this, false);
 427             if (doit) {
 428                 Triangle t = newTriangle(v, this, o,"triangulate 0/0");
 429                 if (((t.v1==this && t.v2==v)||(t.v1==v && t.v2==this)) && t.t12==null) return true;
 430                 if (((t.v3==this && t.v2==v)||(t.v3==v && t.v2==this)) && t.t23==null) return true;
 431                 if (((t.v1==this && t.v3==v)||(t.v1==v && t.v3==this)) && t.t31==null) return true;
 432                 return false;
 433             }
 434             return true;
 435         }
 436
 437         public int wind(Vertex v) {
 438             if (v.next.contains(this) && next.contains(v)) return 0;
 439             if (v.y < y || (v.y==y && v.x<x)) return v.wind(this);
 440             if (next.contains(v)) return 1;
 441             if (v.next.contains(this)) return -1;
 442             return 0;
 443         }
 444         public boolean intersectsSegment(Vertex v1, Vertex v2) {
 445             return
 446                 side(v1,v2,this)==0 &&
 447                 x - Math.max(v1.x,v2.x) < 0 &&
 448                 x - Math.min(v1.x,v2.x) > 0 &&
 449                 y - Math.max(v1.y,v2.y) < 0 &&
 450                 y - Math.min(v1.y,v2.y) > 0;
 451         }
 452     }
 453
 454     // Triangle //////////////////////////////////////////////////////////////////////////////
 455
 456     private final class Triangle {
 457         Triangle t12=null, t23=null, t31=null;
 458         final Vertex v1, v2, v3;
 459         boolean in = false;
 460         boolean deleted = false;
 461         boolean painted = false;
 462         boolean special = false;
 463         final String source;
 464         final double ccx, ccy, r;
 465
 466         public String toString() { return "<<"+v1+""+v2+""+v3+">>"; }
 467         public boolean intersectsSegment(Vertex a, Vertex b) { return isect(v1,v2,a,b) || isect(v3,v2,a,b) || isect(v1,v3,a,b); }
 468         public double area() {
 469             double a = v1.distance(v2);
 470             double b = v3.distance(v2);
 471             double c = v1.distance(v3);
 472             double s = (a+b+c)/2;
 473             return Math.sqrt(s*(s-a)*(s-b)*(s-c));
 474         }
 475
 476         public boolean checkSkinny() {
 477             if (!(r / Math.min(Math.min(v1.distance(v2), v2.distance(v3)), v3.distance(v1)) > B)) return false;
 478             System.out.println("skinny triangle " + this);
 479             for (Iterator it = vertices.iterator(); it.hasNext();) {
 480                 Vertex v = (Vertex)it.next();
 481                 for (Iterator nit = v.next.iterator(); nit.hasNext();) {
 482                     Vertex v2 = (Vertex)nit.next();
 483                     double midx = (v.x+v2.x)/2;
 484                     double midy = (v.y+v2.y)/2;
 485                     if (distance(midx,midy,ccx,ccy) <= v.distance(midx,midy)) {
 486                         System.out.println("  but splitting it would encroach on a segment");
 487                         return false;
 488                     }
 489                 }
 490             }
 491             newVertex(ccx, ccy);
 492             return true;
 493         }
 494
 495         public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, int count, boolean strokeOnly) {
 496             if (painted) return;
 497             if (deleted) throw new Error("gargh!");
 498             if (!strokeOnly) {
 499                 if (special) {
 500                     buf.fillTriangle((int)a.multiply_px((float)v1.x, (float)v1.y),
 501                                      (int)a.multiply_py((float)v1.x, (float)v1.y),
 502                                      (int)a.multiply_px((float)v2.x, (float)v2.y),
 503                                      (int)a.multiply_py((float)v2.x, (float)v2.y),
 504                                      (int)a.multiply_px((float)v3.x, (float)v3.y),
 505                                      (int)a.multiply_py((float)v3.x, (float)v3.y),
 506                                      0xff0000ff);
 507                 } else if ((evenOdd && count%2!=0) || (!evenOdd && count!=0)) {
 508                     buf.fillTriangle((int)a.multiply_px((float)v1.x, (float)v1.y),
 509                                      (int)a.multiply_py((float)v1.x, (float)v1.y),
 510                                      (int)a.multiply_px((float)v2.x, (float)v2.y),
 511                                      (int)a.multiply_py((float)v2.x, (float)v2.y),
 512                                      (int)a.multiply_px((float)v3.x, (float)v3.y),
 513                                      (int)a.multiply_py((float)v3.x, (float)v3.y),
 514                                      color);
 515                 } else {
 516                     buf.fillTriangle((int)a.multiply_px((float)v1.x, (float)v1.y),
 517                                      (int)a.multiply_py((float)v1.x, (float)v1.y),
 518                                      (int)a.multiply_px((float)v2.x, (float)v2.y),
 519                                      (int)a.multiply_py((float)v2.x, (float)v2.y),
 520                                      (int)a.multiply_px((float)v3.x, (float)v3.y),
 521                                      (int)a.multiply_py((float)v3.x, (float)v3.y),
 522                                      0xff000000 | ((color & 0x00ffffff) >> 8));
 523                 }
 524             }
 525             painted = true;
 526             if (t12 != null && !t12.painted) {
 527                 t12.fill(buf, a, color, evenOdd, count + wind(v1, v2), strokeOnly);
 528                 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,
 529                          wind(v2,v1)==0?0xff000000:0xff0000ff);
 530             }
 531             if (t23 != null && !t23.painted) {
 532                 t23.fill(buf, a, color, evenOdd, count + wind(v2, v3), strokeOnly);
 533                 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,
 534                          wind(v3,v2)==0?0xff000000:0xff0000ff);
 535             }
 536             if (t31 != null && !t31.painted) {
 537                 t31.fill(buf, a, color, evenOdd, count + wind(v3, v1), strokeOnly);
 538                 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,
 539                          wind(v3,v1)==0?0xff000000:0xff0000ff);
 540             }
 541         }
 542         public int wind(Vertex a, Vertex b) { return a.wind(b); }
 543         public void clear() {
 544             if (!painted) return;
 545             painted = false;
 546             if (t12 != null) t12.clear();
 547             if (t23 != null) t23.clear();
 548             if (t31 != null) t31.clear();
 549         }
 550         public Triangle(String source, Vertex v1, Vertex v2, Vertex v3) { this(source, v1, v2, v3, false, false); }
 551         public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake) { this(source, v1,v2,v3,fake,false); }
 552         public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake, boolean ignoreProblems) {
 553             this.source = source;
 554             double a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
 555             if (a==0) {
 556                 Vertex t = v2; v2=v3; v3=v1; v1 = t;
 557                 a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
 558                 if (a==0) {
 559                     t = v2; v2=v3; v3=v1; v1 = t;
 560                     a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
 561                 }
 562                 if (a==0) {
 563                     t = v2; v2=v3; v3=v1; v1 = t;
 564                     a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
 565                 }
 566                 if (a==0) {
 567                     t = v1; v1=v3; v3=t;
 568                     a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
 569                 }
 570                 if (a==0) {
 571                     t = v2; v2=v3; v3=v1; v1 = t;
 572                     a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
 573                 }
 574                 if (a==0) {
 575                     t = v2; v2=v3; v3=v1; v1 = t;
 576                     a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
 577                 }
 578                 if (a==0) {
 579                     t = v2; v2=v3; v3=v1; v1 = t;
 580                     a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
 581                 }
 582             }
 583             if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
 584             this.v1 = v1; this.v2 = v2; this.v3 = v3;
 585             double a1=(v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
 586             double a2=(v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
 587             ccx=(a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2;
 588             ccy=(a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2;
 589             r = v1.distance(ccx, ccy);
 590             if (fake) return;
 591             for(int i=0; i<triangles.size(); i++) {
 592                 Triangle t = (Triangle)triangles.elementAt(i);
 593                 if ((t.v1==v1&&t.v2==v2)||(t.v1==v2&&t.v2==v1)) {
 594                     if (t.t12!=null && !ignoreProblems) {
 595                         System.out.println("v1=="+v1);
 596                         System.out.println("v2=="+v2);
 597                         System.out.println("t.v3=="+t.v3);
 598                         System.out.println("v3=="+v3);
 599                         special = true;
 600                         t.special = true;
 601                         triangles.add(this);
 602                         System.out.println(t.t12.source);
 603                         throw new Error();
 604                         //t.t12.delete(null);
 605                     }
 606                     t.t12=this;
 607                     t12=t;
 608                     //continue;
 609                 }
 610                 if ((t.v1==v2&&t.v2==v3)||(t.v1==v3&&t.v2==v2)) {
 611                     if (t.t12!=null && !ignoreProblems) {
 612                         special = true;
 613                         t.special = true;
 614                         System.out.println("v2=="+v2);
 615                         System.out.println("v3=="+v3);
 616                         System.out.println("t.v3=="+t.v3);
 617                         System.out.println("v1=="+v1);
 618                         System.out.println("t.t12.v1=="+t.t12.v1);
 619                         System.out.println("t.t12.v2=="+t.t12.v2);
 620                         System.out.println("t.t12.v3=="+t.t12.v3);
 621                         special = true;
 622                         t.special = true;
 623                         triangles.add(this);
 624                         throw new Error();
 625                         //t.t12.delete(null);
 626                     }
 627                     t.t12=this;
 628                     t23=t;
 629                     //continue;
 630                 }
 631                 if ((t.v1==v3&&t.v2==v1)||(t.v1==v1&&t.v2==v3)) {
 632                     if (t.t12!=null && !ignoreProblems) {
 633                         special = true;
 634                         t.special = true;
 635                         System.out.println("v1=="+v1);
 636                         System.out.println("v3=="+v3);
 637                         System.out.println("t.v3=="+t.v3);
 638                         System.out.println("v2=="+v2);
 639                         special = true;
 640                         t.special = true;
 641                         triangles.add(this);
 642                         throw new Error();
 643                         //t.t12.delete(null);
 644                     }
 645                     t.t12=this;
 646                     t31=t;
 647                     //continue;
 648                 }
 649                 if ((t.v2==v1&&t.v3==v2)||(t.v2==v2&&t.v3==v1)) {
 650                     if (t.t23!=null && !ignoreProblems) {
 651                         t = t.t23;
 652                         System.out.println("v1=="+v1);
 653                         System.out.println("v2=="+v2);
 654                         System.out.println("t.v1=="+t.v1);
 655                         System.out.println("v3=="+v3);
 656                         special = true;
 657                         t.special = true;
 658                         triangles.add(this);
 659                         System.out.println(t.source);
 660                         throw new Error();
 661                         //t.t23.delete(null);
 662                     }
 663                     t.t23=this;
 664                     t12=t;
 665                     //continue;
 666                 }
 667                 if ((t.v2==v2&&t.v3==v3)||(t.v2==v3&&t.v3==v2)) {
 668                     if (t.t23!=null && !ignoreProblems) {
 669                         special = true;
 670                         t=t.t23;
 671                         t.special = true;
 672                         triangles.add(this);
 673                         System.out.println(t.source);
 674                         throw new Error();
 675                         //t.t23.delete(null);
 676                     }
 677                     t.t23=this;
 678                     t23=t;
 679                     //continue;
 680                 }
 681                 if ((t.v2==v3&&t.v3==v1)||(t.v2==v1&&t.v3==v3)) {
 682                     if (t.t23!=null && !ignoreProblems) {
 683                         special = true;
 684                         t = t.t23;
 685                         t.special = true;
 686                         System.out.println("v1=="+v1);
 687                         System.out.println("v3=="+v3);
 688                         System.out.println("t.v3=="+t.v3);
 689                         System.out.println("v2=="+v2);
 690                         special = true;
 691                         t.special = true;
 692                         System.out.println(t.source);
 693                         triangles.add(this);
 694                         throw new Error();
 695                         //t.t23.delete(null);
 696                     }
 697                     t.t23=this;
 698                     t31=t;
 699                     //continue;
 700                 }
 701                 if ((t.v3==v1&&t.v1==v2)||(t.v3==v2&&t.v1==v1)) {
 702                     if (t.t31!=null && !ignoreProblems) {
 703                         t=t.t31;
 704                         special = true;
 705                         t.special = true;
 706                         System.out.println("v1=="+v1);
 707                         System.out.println("v2=="+v2);
 708                         System.out.println("t.v2=="+t.v2);
 709                         System.out.println("v3=="+v3);
 710                         triangles.add(this);
 711                         System.out.println(t.source);
 712                         throw new Error();
 713                         //t.t31.delete(null);
 714                     }
 715                     t.t31=this;
 716                     t12=t;
 717                     //continue;
 718                 }
 719                 if ((t.v3==v2&&t.v1==v3)||(t.v3==v3&&t.v1==v2)) {
 720                     if (t.t31!=null && !ignoreProblems) {
 721                         special = true;
 722                         t=t.t31;
 723                         t.special = true;
 724                         triangles.add(this);
 725                         System.out.println(t.source);
 726                         throw new Error();
 727                         //t.t31.delete(null);
 728                     }
 729                     t.t31=this;
 730                     t23=t;
 731                     //continue;
 732                 }
 733                 if ((t.v3==v3&&t.v1==v1)||(t.v3==v1&&t.v1==v3)) {
 734                     if (t.t31!=null && !ignoreProblems) {
 735                         t=t.t31;
 736                         System.out.println("t.v1="+t.v1);
 737                         System.out.println("t.v2="+t.v2);
 738                         System.out.println("t.v3="+t.v3);
 739                         System.out.println("v1="+v1);
 740                         System.out.println("v2="+v2);
 741                         System.out.println("v3="+v3);
 742                         special = true;
 743                         t.special = true;
 744                         triangles.add(this);
 745                         System.out.println("source=="+source);
 746                         System.out.println("t.source=="+t.source);
 747                         throw new Error();
 748                         //t.t31.delete(null);
 749                     }
 750                     t.t31=this;
 751                     t31=t;
 752                     //continue;
 753                 }
 754             }
 755             triangles.add(this);
 756         }
 757         public void delete(Triangle t, Vertex v, Vector vec) {
 758             if (deleted) return;
 759             if (t12==t) { t12 = null; if (vec != null) { vec.add(v1); vec.add(v2); } }
 760             if (t23==t) { t23 = null; if (vec != null) { vec.add(v2); vec.add(v3); } }
 761             if (t31==t) { t31 = null; if (vec != null) { vec.add(v3); vec.add(v1); } }
 762         }
 763         public void delete(Vector vec) {
 764             if (deleted) return;
 765             deleted = true;
 766             triangles.remove(this);
 767             if (t12 != null) t12.delete(this,null,vec); else if (vec != null) { vec.add(v1); vec.add(v2); }
 768             if (t23 != null) t23.delete(this,null,vec); else if (vec != null) { vec.add(v3); vec.add(v2); }
 769             if (t31 != null) t31.delete(this,null,vec); else if (vec != null) { vec.add(v1); vec.add(v3); }
 770         }
 771         public boolean contains(Vertex v) {
 772             double x = v.x;
 773             double y = v.y;
 774             if (v==v1) return false;
 775             if (v==v2) return false;
 776             if (v==v3) return false;
 777             if (v.intersectsSegment(v1,v2)) return false;
 778             if (v.intersectsSegment(v2,v3)) return false;
 779             if (v.intersectsSegment(v3,v1)) return false;
 780             int a = side(v1,v2,x,y);
 781             int b = side(v3,v2,x,y);
 782             int c = side(v1,v3,x,y);
 783             return (a==side(v1,v2,v3)) && (b==side(v3,v2,v1)) && (c==side(v1,v3,v2));
 784         }
 785     }
 786
 787     // Constructor //////////////////////////////////////////////////////////////////////////////
 788
 789     public Mesh(Polygon p) {
 790         p.sort();
 791         triangles.setSize(0);
 792         vertices.setSize(0);
 793
 794         newTriangle(newVertex(p.minx-10, p.miny-10),
 795                     newVertex(p.maxx+10, p.miny-10),
 796                     newVertex(p.maxx+10, p.maxy+10), "original0");
 797
 798         newTriangle(newVertex(p.minx-10, p.miny-10),
 799                     newVertex(p.minx-10, p.maxy+10),
 800                     newVertex(p.maxx+10, p.maxy+10), "original");
 801
 802         for(int i=0; i<p.numcontours-1; i++) {
 803             Vertex last = null, first = null;
 804             boolean good = false;
 805             for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
 806                 Vertex v = newVertex(p.x[j], p.y[j]);
 807                 if (v==last) continue;
 808                 if (v==first) continue;
 809                 if (last == null) { last = v; continue; }
 810                 if (first ==null) { first = v; continue; }
 811                 good = true;
 812                 break;
 813             }
 814             System.out.println("contour " + i + " is " + (good?"good":"bad"));
 815             if (!good) continue;
 816             last = null; first = null;
 817             for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
 818                 System.out.println("****************************************");
 819                 Vertex v = newVertex(p.x[j], p.y[j]);
 820                 if (v==last) continue;
 821                 if (first==null) first=v;
 822                 if (last != null) last.next.add(v);
 823                 last = v;
 824                 System.out.print(((int)v.x)+","+((int)v.y)+" ");
 825             }
 826             if (last!=first) last.next.add(first);
 827             System.out.println();
 828         }
 829
 830         while(true) {
 831             boolean redo = false;
 832             for(int k=0; k<vertices.size(); k++) {
 833                 Vector vec = new Vector();
 834                 Vertex vx = (Vertex)vertices.elementAt(k);
 835                 redo |= vx.makeNonDegenerate(vec);
 836             }
 837             if (!redo) break;
 838         }
 839
 840         /*
 841         redo = true;
 842         for(; redo;) {
 843             redo = false;
 844             for(int k=0; k<triangles.size(); k++) {
 845                 Triangle t = (Triangle)triangles.elementAt(k);
 846                 redo |= t.checkSkinny();
 847             }
 848             break;
 849         }
 850         System.out.println("I now have " + vertices.size() + " vertices");
 851         */
 852
 853         while(true) {
 854             boolean redo = false;
 855             for(int k=0; k<vertices.size(); k++) {
 856                 Vertex v = (Vertex)vertices.elementAt(k);
 857                 v.forced = false;
 858             }
 859             for(int k=0; k<vertices.size(); k++) {
 860                 Vertex v = (Vertex)vertices.elementAt(k);
 861                 redo |= v.force();
 862             }
 863             if (!redo) break;
 864         }
 865     }
 866 }
 867
 868