- private final class Vertex {
- final double x, y;
- LinkedList next = new LinkedList();
- boolean forced = false;
- public String toString() { return "("+x+","+y+")"; }
- public double distance(Vertex v) { return distance(v.x, v.y); }
- public double distance(double x, double y) { return Mesh.distance(this.x,this.y,x,y); }
- public Vertex(double x, double y) {
- this.x = x;
- this.y = y;
- vertices.addElement(this);
- Vector vec = new Vector();
- Vector vec2 = new Vector();
- boolean interior = false;
- int edges = 0;
- Vertex v = this;
- boolean good = false;
- for(int i=0; i<triangles.size(); i++) {
- Triangle t = (Triangle)triangles.elementAt(i);
- if (good) throw new Error("impossible: Vertex() -> good twice");
- if (t.contains(this)) {
- System.out.println(t + " contains me");
- Triangle t12 = t.t12;
- Triangle t23 = t.t23;
- Triangle t31 = t.t31;
- t.delete(vec);
- vec2.addElement(newTriangle(this, t.v1, t.v2, "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v3, t.v2, "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v1, t.v3, "vertexinsertion " + this));
- fixup(vec2);
- good = true;
- break;
- } else if (t.t23 != null && v.intersectsSegment(t.v2, t.v3)) {
- System.out.println("on an edge");
- good = true;
- Triangle tt = t.t23;
- tt.delete(null);
- t.delete(null);
- Vertex va =
- ((tt.v1==t.v3&&tt.v2==t.v2)||(tt.v1==t.v2&&tt.v2==t.v3)) ? tt.v3 :
- ((tt.v2==t.v3&&tt.v3==t.v2)||(tt.v2==t.v2&&tt.v3==t.v3)) ? tt.v1 :
- ((tt.v1==t.v3&&tt.v3==t.v2)||(tt.v1==t.v2&&tt.v3==t.v3)) ? tt.v2 : null;
- vec2.addElement(newTriangle(this, t.v1, t.v3, "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v1, t.v2, "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v3, va , "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v2, va , "vertexinsertion " + this));
- fixup(vec2);
- break;
- } else if (t.t31 != null && v.intersectsSegment(t.v1, t.v3)) {
- good = true;
- System.out.println("on an edge");
- Triangle tt = t.t31;
- tt.delete(null);
- t.delete(null);
- Vertex va =
- ((tt.v1==t.v1&&tt.v2==t.v3)||(tt.v1==t.v3&&tt.v2==t.v1)) ? tt.v3 :
- ((tt.v2==t.v1&&tt.v3==t.v3)||(tt.v2==t.v3&&tt.v3==t.v1)) ? tt.v1 :
- ((tt.v1==t.v1&&tt.v3==t.v3)||(tt.v1==t.v3&&tt.v3==t.v1)) ? tt.v2 : null;
- vec2.addElement(newTriangle(this, t.v2, t.v1, "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v2, t.v3, "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v1, va , "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v3, va , "vertexinsertion " + this));
- fixup(vec2);
- break;
- } else if (t.t12 != null && v.intersectsSegment(t.v1, t.v2)) {
- System.out.println("on an edge");
- good = true;
- Triangle tt = t.t12;
- tt.delete(null);
- t.delete(null);
- Vertex va =
- ((tt.v1==t.v1&&tt.v2==t.v2)||(tt.v1==t.v2&&tt.v2==t.v1)) ? tt.v3 :
- ((tt.v2==t.v1&&tt.v3==t.v2)||(tt.v2==t.v2&&tt.v3==t.v1)) ? tt.v1 :
- ((tt.v1==t.v1&&tt.v3==t.v2)||(tt.v1==t.v2&&tt.v3==t.v1)) ? tt.v2 : null;
- vec2.addElement(newTriangle(this, t.v3, t.v1, "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v3, t.v2, "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v1, va , "vertexinsertion " + this));
- vec2.addElement(newTriangle(this, t.v2, va , "vertexinsertion " + this));
- fixup(vec2);
- break;
- }
- }
- if (triangles.size() > 2 && !good)
- throw new Error("vertex "+this+" did not fall within a triangle or on the edge of at least two");
- }
- public void fixup(Vector vec) {
- while(vec.size() > 0) {
- Triangle t = (Triangle)vec.lastElement();
- vec.setSize(vec.size() - 1);
- if (t.deleted) continue;
- Triangle to = t.v1==this ? t.t23 : t.v2==this ? t.t31 : t.v3==this ? t.t12 : null;
- if (to==null) continue;
- //throw new Error("fixup invoked with a triangle which does not have me as a vertex");
- if (to.deleted) throw new Error("this should not happen");
- if (to.r < this.distance(to.ccx, to.ccy)) continue;
- if (t.v1==this) {
- //if (t.v2.next.contains(t.v3)) continue;
- //if (t.v3.next.contains(t.v2)) continue;
- Vertex v =
- (to.v1!=t.v2 && to.v1!=t.v3) ? to.v1 :
- (to.v2!=t.v2 && to.v2!=t.v3) ? to.v2 :
- (to.v3!=t.v2 && to.v3!=t.v3) ? to.v3 : null;
- t.delete(null);
- to.delete(null);
- vec.addElement(newTriangle(this, t.v2, v, "fixup"));
- vec.addElement(newTriangle(this, t.v3, v, "fixup"));
- } else if (t.v2==this) {
- //if (t.v3.next.contains(t.v1)) continue;
- //if (t.v1.next.contains(t.v3)) continue;
- Vertex v =
- (to.v1!=t.v1 && to.v1!=t.v3) ? to.v1 :
- (to.v2!=t.v1 && to.v2!=t.v3) ? to.v2 :
- (to.v3!=t.v1 && to.v3!=t.v3) ? to.v3 : null;
- t.delete(null);
- to.delete(null);
- vec.addElement(newTriangle(this, t.v1, v, "fixup"));
- vec.addElement(newTriangle(this, t.v3, v, "fixup"));
-
- } else if (t.v3==this) {
- //if (t.v1.next.contains(t.v2)) continue;
- //if (t.v2.next.contains(t.v1)) continue;
- Vertex v =
- (to.v1!=t.v2 && to.v1!=t.v1) ? to.v1 :
- (to.v2!=t.v2 && to.v2!=t.v1) ? to.v2 :
- (to.v3!=t.v2 && to.v3!=t.v1) ? to.v3 : null;
- t.delete(null);
- to.delete(null);
- vec.addElement(newTriangle(this, t.v2, v, "fixup"));
- vec.addElement(newTriangle(this, t.v1, v, "fixup"));
- } else {
- throw new Error("this should not happen");
- }
- System.out.println("> made a swap");
- }
- }
-
- public boolean makeNonDegenerate(Vector vec) {
- Vertex v1 = this;
- for(int i2 = 0; i2<next.size(); i2++) {
- Vertex v2 = (Vertex)next.get(i2);
- for(int i3 = 0; i3<vertices.size(); i3++) {
- Vertex v3 = (Vertex)vertices.get(i3);
- for(int i4=0; i4<v3.next.size(); i4++) {
- Vertex v4 = (Vertex)v3.next.get(i4);
- if (v1==v3||v1==v4||v2==v3||v2==v4) continue;
- if (isect(v1,v2,v3,v4)) {
- double a1 = v2.y-v1.y;
- double a2 = v4.y-v3.y;
- double b1 = v1.x-v2.x;
- double b2 = v3.x-v4.x;
- double c1 = -1 * (a1*v1.x+b1*v1.y);
- double c2 = -1 * (a2*v3.x+b2*v3.y);
- // a1x+b1y+c1=0
- // y=-(a1x+c1)/b1
- // a2x-(a1x+c1)(b2/b1)+c2=0
- // a2b1x-b2(a1x+c1)+b1c2=0
- // a2b1x-a1b2x-b2c1+b1c2=0
- // x(a2b1-a1b2)-b2c1+b1c2=0
- // x(a2b1-a1b2)=b2c1-b1c2
- // x=(b2c1-b1c2)/(a2b1-a1b2)
- double xq = (b2*c1-c2*b1)/(b1*a2-b2*a1);
- Vertex v0 = newVertex(xq, -1 * (a1*xq+c1) / b1);
- //if (v0==v1||v0==v2||v0==v3||v0==v4) continue;
- System.out.println("inserting new vertex " + v0+" between " + v1+"-"+v2 +" and "+ v3+"-"+v4);
- v1.next.remove(v2);
- v1.next.add(v0);
- v0.next.add(v2);
- v3.next.remove(v4);
- v3.next.add(v0);
- v0.next.add(v4);
- return true;
- }
- }