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.
5 package org.ibex.graphics;
7 import java.util.collections.*;
8 import org.ibex.util.*;
11 * An incremental, adaptive, constrained Delaunay Triangulation.
12 * @see Kallmann, Bieri, and Thalmann: Fully Dynamic Constrained Delaunay Triangulations
14 public final class Mesh {
16 private static final double epsilon = (double)0.00000001;
17 private static final boolean debug = true;
19 private Vector vertices = new Vector();
20 private Vector triangles = new Vector();
22 public static double B = 5;
23 public static double Q = 0.4;
25 // Utilities //////////////////////////////////////////////////////////////////////////////
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));
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;
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;
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),
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);
58 public void stroke(PixelBuffer buf, Affine a, int color) {
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);
67 for (int i=0; i<triangles.size(); i++) {
68 Triangle t = ((Triangle)triangles.elementAt(i));
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);
78 // Static //////////////////////////////////////////////////////////////////////////////
80 public Vertex newVertex(double x, double y) {
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;
86 return ret==null ? new Vertex(x,y) : ret;
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;
100 Triangle t = new Triangle(source, v1, v2, v3, false, false);
101 if (debug) checktri();
105 public void checktri() {
106 for(int i=0; i<triangles.size(); i++) {
107 Triangle t = (Triangle)triangles.elementAt(i);
109 for(int j=0; j<vertices.size(); j++) {
110 Vertex v = (Vertex)vertices.elementAt(j);
113 throw new Error("triangle "+t+" contains vertex " + v);
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);
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");
133 // Vertex //////////////////////////////////////////////////////////////////////////////
135 private final class Vertex {
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) {
145 vertices.addElement(this);
146 Vector vec = new Vector();
147 Vector vec2 = new Vector();
148 boolean interior = false;
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;
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));
167 } else if (t.t23 != null && v.intersectsSegment(t.v2, t.v3)) {
168 System.out.println("on an edge");
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));
183 } else if (t.t31 != null && v.intersectsSegment(t.v1, t.v3)) {
185 System.out.println("on an edge");
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));
199 } else if (t.t12 != null && v.intersectsSegment(t.v1, t.v2)) {
200 System.out.println("on an edge");
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));
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");
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;
231 //if (t.v2.next.contains(t.v3)) continue;
232 //if (t.v3.next.contains(t.v2)) continue;
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;
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;
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;
250 vec.addElement(newTriangle(this, t.v1, v, "fixup"));
251 vec.addElement(newTriangle(this, t.v3, v, "fixup"));
253 } else if (t.v3==this) {
254 //if (t.v1.next.contains(t.v2)) continue;
255 //if (t.v2.next.contains(t.v1)) continue;
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;
262 vec.addElement(newTriangle(this, t.v2, v, "fixup"));
263 vec.addElement(newTriangle(this, t.v1, v, "fixup"));
265 throw new Error("this should not happen");
267 System.out.println("> made a swap");
271 public boolean makeNonDegenerate(Vector vec) {
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);
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);
313 public boolean force() {
314 if (forced) return false;
317 OUTER: for(Iterator it=next.iterator(); it.hasNext();) {
318 Vertex v = (Vertex)it.next();
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);
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; }
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();
355 orphans.remove(this);
361 orphans.remove(this);
363 triangulate(orphans, v);
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);
378 triangulate2(left, v, false);
379 v.triangulate2(right, this, false);
381 public boolean triangulate2(HashSet orphans, Vertex v, boolean skip) {
382 Vertex farthest = null;
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;
396 OUTER: for(Iterator it=orphans.iterator(); it.hasNext();) {
397 o = (Vertex)it.next();
399 Triangle t = new Triangle("temp", this, v, o, true);
400 for(Iterator it2=orphans.iterator(); it2.hasNext();) {
401 Vertex z = (Vertex)it2.next();
404 if (z==this) continue;
405 if (z.distance(t.ccx, t.ccy) < t.r || t.contains(z)) continue OUTER;
407 if (best==null || new Triangle("temp",this,v,best,true).area() > new Triangle("temp",this,v,o,true).area())
410 if (best==null) throw new Error("notgood, #orphans = " + orphans.size());
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);
425 doit &= o.triangulate2(left, v, false);
426 doit &= o.triangulate2(right, this, false);
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;
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;
444 public boolean intersectsSegment(Vertex v1, Vertex v2) {
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;
454 // Triangle //////////////////////////////////////////////////////////////////////////////
456 private final class Triangle {
457 Triangle t12=null, t23=null, t31=null;
458 final Vertex v1, v2, v3;
460 boolean deleted = false;
461 boolean painted = false;
462 boolean special = false;
464 final double ccx, ccy, r;
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));
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");
495 public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, int count, boolean strokeOnly) {
497 if (deleted) throw new Error("gargh!");
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),
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),
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));
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);
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);
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);
542 public int wind(Vertex a, Vertex b) { return a.wind(b); }
543 public void clear() {
544 if (!painted) return;
546 if (t12 != null) t12.clear();
547 if (t23 != null) t23.clear();
548 if (t31 != null) t31.clear();
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);
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);
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);
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);
568 a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x);
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);
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);
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);
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);
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);
602 System.out.println(t.t12.source);
604 //t.t12.delete(null);
610 if ((t.v1==v2&&t.v2==v3)||(t.v1==v3&&t.v2==v2)) {
611 if (t.t12!=null && !ignoreProblems) {
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);
625 //t.t12.delete(null);
631 if ((t.v1==v3&&t.v2==v1)||(t.v1==v1&&t.v2==v3)) {
632 if (t.t12!=null && !ignoreProblems) {
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);
643 //t.t12.delete(null);
649 if ((t.v2==v1&&t.v3==v2)||(t.v2==v2&&t.v3==v1)) {
650 if (t.t23!=null && !ignoreProblems) {
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);
659 System.out.println(t.source);
661 //t.t23.delete(null);
667 if ((t.v2==v2&&t.v3==v3)||(t.v2==v3&&t.v3==v2)) {
668 if (t.t23!=null && !ignoreProblems) {
673 System.out.println(t.source);
675 //t.t23.delete(null);
681 if ((t.v2==v3&&t.v3==v1)||(t.v2==v1&&t.v3==v3)) {
682 if (t.t23!=null && !ignoreProblems) {
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);
692 System.out.println(t.source);
695 //t.t23.delete(null);
701 if ((t.v3==v1&&t.v1==v2)||(t.v3==v2&&t.v1==v1)) {
702 if (t.t31!=null && !ignoreProblems) {
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);
711 System.out.println(t.source);
713 //t.t31.delete(null);
719 if ((t.v3==v2&&t.v1==v3)||(t.v3==v3&&t.v1==v2)) {
720 if (t.t31!=null && !ignoreProblems) {
725 System.out.println(t.source);
727 //t.t31.delete(null);
733 if ((t.v3==v3&&t.v1==v1)||(t.v3==v1&&t.v1==v3)) {
734 if (t.t31!=null && !ignoreProblems) {
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);
745 System.out.println("source=="+source);
746 System.out.println("t.source=="+t.source);
748 //t.t31.delete(null);
757 public void delete(Triangle t, Vertex v, Vector vec) {
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); } }
763 public void delete(Vector vec) {
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); }
771 public boolean contains(Vertex v) {
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));
787 // Constructor //////////////////////////////////////////////////////////////////////////////
789 public Mesh(Polygon p) {
791 triangles.setSize(0);
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");
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");
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; }
814 System.out.println("contour " + i + " is " + (good?"good":"bad"));
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);
824 System.out.print(((int)v.x)+","+((int)v.y)+" ");
826 if (last!=first) last.next.add(first);
827 System.out.println();
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);
844 for(int k=0; k<triangles.size(); k++) {
845 Triangle t = (Triangle)triangles.elementAt(k);
846 redo |= t.checkSkinny();
850 System.out.println("I now have " + vertices.size() + " vertices");
854 boolean redo = false;
855 for(int k=0; k<vertices.size(); k++) {
856 Vertex v = (Vertex)vertices.elementAt(k);
859 for(int k=0; k<vertices.size(); k++) {
860 Vertex v = (Vertex)vertices.elementAt(k);