package voronoi; import java.awt.Canvas; import java.awt.Color; import java.awt.Graphics; public class DelaunayTri { private static final boolean ONHULL = true; private static final boolean REMOVED = true; private static final boolean VISIBLE = true; private static final boolean PROCESSED = true; private static final int SAFE = 1000000; boolean toDraw; // for simulation boolean DeSim; Graphics g; Canvas c; int w; int h; private cVertexList list; private cEdgeList elist; private cFaceList flist; DelaunayTri(cVertexList list) { this.list = list; elist = new cEdgeList(); flist = new cFaceList(); toDraw = DeSim = false; g = null; c = null; w = 0; h = 0; } public void DeSim(boolean desim, Graphics Deg, int Dew, int Deh, Canvas Can) { DeSim = desim; c = Can; g = Deg; w = Dew; h = Deh; } public void Start(cVertexList listOld) { this.list = new cVertexList(); listOld.ListCopy(this.list); ReadVertices(); if (DoubleTriangle()) { toDraw = true; ConstructHull(); LowerFaces(); } } public void ClearDelaunay() { elist.ClearEdgeList(); flist.ClearFaceList(); toDraw = false; } public void ReadVertices() { int vnum = 0; cVertex v = list.head; do { v.ResetVertex3D(); v.vnum = vnum++; if ((Math.abs(v.v.x) > SAFE) || (Math.abs(v.v.y) > SAFE) || (Math.abs(v.v.z) > SAFE)) { System.out .println("Coordinate of vertex below might be too large..."); } v = v.next; } while (v != list.head); } private void LowerFaces() { cFace f = flist.head; int Flower = 0; do { if (Normz(f) < 0) { Flower++; f.lower = true; } else { if (DeSim) { g.setColor(Color.lightGray); DrawDelaunayTri(g, w, h); c.repaint(); } f.lower = false; if (DeSim) { g.setColor(Color.blue); DrawDelaunayTri(g, w, h); c.repaint(); try { Thread.sleep(1000); } catch (InterruptedException ee) { ; } } } f = f.next; } while (f != flist.head); } private boolean DoubleTriangle() { cVertex v0, v1, v2, v3; cFace f0, f1 = null; int vol; v0 = list.head; while (Collinear(v0, v0.next, v0.next.next)) if ((v0 = v0.next) == list.head) { System.out .println("DoubleTriangle: All points are Collinear!"); return false; } v1 = v0.next; v2 = v1.next; v0.mark = PROCESSED; v1.mark = PROCESSED; v2.mark = PROCESSED; f0 = MakeFace(v0, v1, v2, f1); f1 = MakeFace(v2, v1, v0, f0); f0.edge[0].adjface[1] = f1; f0.edge[1].adjface[1] = f1; f0.edge[2].adjface[1] = f1; f1.edge[0].adjface[1] = f0; f1.edge[1].adjface[1] = f0; f1.edge[2].adjface[1] = f0; v3 = v2.next; vol = VolumeSign(f0, v3); while (vol == 0) { if ((v3 = v3.next) == v0) { System.out.println("DoubleTriangle: All points are coplanar!"); return false; } vol = VolumeSign(f0, v3); } list.head = v3; return true; } private void ConstructHull() { cVertex v, vnext; v = list.head; do { vnext = v.next; if (!v.mark) { v.mark = PROCESSED; if (DeSim) { g.setColor(Color.lightGray); DrawRest(g, w, h); c.repaint(); } AddOne(v); if (DeSim) { g.setColor(Color.blue); DrawRest(g, w, h); c.repaint(); try { Thread.sleep(1000); } catch (InterruptedException ee) { ; } } if (DeSim) { g.setColor(Color.lightGray); DrawRest(g, w, h); c.repaint(); } CleanUp(); if (DeSim) { g.setColor(Color.blue); DrawRest(g, w, h); c.repaint(); try { Thread.sleep(1000); } catch (InterruptedException ee) { ; } } } v = vnext; } while (v != list.head); } private boolean AddOne(cVertex p) { cFace f; cEdge e; int vol; boolean vis = false; f = flist.head; do { vol = VolumeSign(f, p); if (vol < 0) { f.visible = VISIBLE; vis = true; } f = f.next; } while (f != flist.head); if (!vis) { p.onhull = !ONHULL; return false; } e = elist.head; do { cEdge temp; temp = e.next; if (e.adjface[0].visible && e.adjface[1].visible) { e.delete = REMOVED; } else if (e.adjface[0].visible || e.adjface[1].visible) { e.newface = MakeConeFace(e, p); } e = temp; } while (e != elist.head); return true; } private int VolumeSign(cFace f, cVertex p) { double vol; double ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz; double bxdx, bydy, bzdz, cxdx, cydy, czdz; ax = f.vertex[0].v.x; ay = f.vertex[0].v.y; az = f.vertex[0].v.z; bx = f.vertex[1].v.x; by = f.vertex[1].v.y; bz = f.vertex[1].v.z; cx = f.vertex[2].v.x; cy = f.vertex[2].v.y; cz = f.vertex[2].v.z; dx = p.v.x; dy = p.v.y; dz = p.v.z; bxdx = bx - dx; bydy = by - dy; bzdz = bz - dz; cxdx = cx - dx; cydy = cy - dy; czdz = cz - dz; vol = (az - dz) * (bxdx * cydy - bydy * cxdx) + (ay - dy) * (bzdz * cxdx - bxdx * czdz) + (ax - dx) * (bydy * czdz - bzdz * cydy); if (vol > 0.5) return 1; else if (vol < -0.5) return -1; else return 0; } private cFace MakeConeFace(cEdge e, cVertex p) { cEdge new_edge[] = new cEdge[2]; cFace new_face; int i, j; for (i = 0; i < 2; ++i) { new_edge[i] = e.endpts[i].duplicate; if (new_edge[i] == null) { new_edge[i] = elist.MakeNullEdge(); new_edge[i].endpts[0] = e.endpts[i]; new_edge[i].endpts[1] = p; e.endpts[i].duplicate = new_edge[i]; } } new_face = flist.MakeNullFace(); new_face.edge[0] = e; new_face.edge[1] = new_edge[0]; new_face.edge[2] = new_edge[1]; MakeCcw(new_face, e, p); for (i = 0; i < 2; ++i) for (j = 0; j < 2; ++j) if (new_edge[i].adjface[j] == null) { new_edge[i].adjface[j] = new_face; break; } return new_face; } private void MakeCcw(cFace f, cEdge e, cVertex p) { cFace fv; int i; cEdge s = new cEdge(); if (e.adjface[0].visible) fv = e.adjface[0]; else fv = e.adjface[1]; for (i = 0; fv.vertex[i] != e.endpts[0]; ++i) ; if (fv.vertex[(i + 1) % 3] != e.endpts[1]) { f.vertex[0] = e.endpts[1]; f.vertex[1] = e.endpts[0]; } else { f.vertex[0] = e.endpts[0]; f.vertex[1] = e.endpts[1]; Swap(s, f.edge[1], f.edge[2]); } f.vertex[2] = p; } private cFace MakeFace(cVertex v0, cVertex v1, cVertex v2, cFace fold) { cFace f; cEdge e0, e1, e2; if (fold == null) { e0 = elist.MakeNullEdge(); e1 = elist.MakeNullEdge(); e2 = elist.MakeNullEdge(); } else { e0 = fold.edge[2]; e1 = fold.edge[1]; e2 = fold.edge[0]; } e0.endpts[0] = v0; e0.endpts[1] = v1; e1.endpts[0] = v1; e1.endpts[1] = v2; e2.endpts[0] = v2; e2.endpts[1] = v0; f = flist.MakeNullFace(); f.edge[0] = e0; f.edge[1] = e1; f.edge[2] = e2; f.vertex[0] = v0; f.vertex[1] = v1; f.vertex[2] = v2; e0.adjface[0] = e1.adjface[0] = e2.adjface[0] = f; return f; } private void CleanUp() { CleanEdges(); CleanFaces(); CleanVertices(); } private void CleanEdges() { cEdge e; cEdge t; e = elist.head; do { if (e.newface != null) { if (e.adjface[0].visible) e.adjface[0] = e.newface; else e.adjface[1] = e.newface; e.newface = null; } e = e.next; } while (e != elist.head); while (elist.head != null && elist.head.delete) { e = elist.head; elist.Delete(e); } e = elist.head.next; do { if (e.delete) { t = e; e = e.next; elist.Delete(t); } else e = e.next; } while (e != elist.head); } private void CleanFaces() { cFace f; cFace t; while (flist.head != null && flist.head.visible) { f = flist.head; flist.Delete(f); } f = flist.head.next; do { if (f.visible) { t = f; f = f.next; flist.Delete(t); } else f = f.next; } while (f != flist.head); } private void CleanVertices() { cEdge e; cVertex v, t; e = elist.head; do { e.endpts[0].onhull = e.endpts[1].onhull = ONHULL; e = e.next; } while (e != elist.head); while (list.head != null && list.head.mark && !list.head.onhull) { v = list.head; list.Delete(v); } v = list.head.next; do { if (v.mark && !v.onhull) { t = v; v = v.next; list.Delete(t); } else v = v.next; } while (v != list.head); v = list.head; do { v.duplicate = null; v.onhull = !ONHULL; v = v.next; } while (v != list.head); } private boolean Collinear(cVertex a, cVertex b, cVertex c) { return (c.v.z - a.v.z) * (b.v.y - a.v.y) - (b.v.z - a.v.z) * (c.v.y - a.v.y) == 0 && (b.v.z - a.v.z) * (c.v.x - a.v.x) - (b.v.x - a.v.x) * (c.v.z - a.v.z) == 0 && (b.v.x - a.v.x) * (c.v.y - a.v.y) - (b.v.y - a.v.y) * (c.v.x - a.v.x) == 0; } private int Normz(cFace f) { cVertex a, b, c; a = f.vertex[0]; b = f.vertex[1]; c = f.vertex[2]; return (b.v.x - a.v.x) * (c.v.y - a.v.y) - (b.v.y - a.v.y) * (c.v.x - a.v.x); } private void Swap(cEdge t, cEdge x, cEdge y) { t = x; x = y; y = t; } public void DrawDelaunayTri(Graphics g, int w, int h) { cVertex v; cFace f; int V = 0, F = 0; v = list.head; do { if (v.mark) V++; v = v.next; } while (v != list.head); f = flist.head; do { ++F; f = f.next; } while (f != flist.head); do { if (f.lower) { if (flist.n >= 2) { g.drawLine(f.vertex[0].v.x, f.vertex[0].v.y, f.vertex[1].v.x, f.vertex[1].v.y); g.drawLine(f.vertex[1].v.x, f.vertex[1].v.y, f.vertex[2].v.x, f.vertex[2].v.y); g.drawLine(f.vertex[2].v.x, f.vertex[2].v.y, f.vertex[0].v.x, f.vertex[0].v.y); } } f = f.next; } while (f != flist.head); do { g.setColor(Color.black); g.fillOval(v.v.x - (int) (w / 2), v.v.y - (int) (h / 2), w, h); v = v.next; } while (v != list.head); } void out_triple(Graphics g, cVertex s1, cVertex s2, cVertex s3) { double P1X = s1.v.x; double P1Y = s1.v.y; double P2X = s2.v.x; double P2Y = s2.v.y; double P3X = s3.v.x; double P3Y = s3.v.y; double l1a = P2X - P1X; double l1b = P2Y - P1Y; double l1c = (P1Y * P1Y - P2Y * P2Y + P1X * P1X - P2X * P2X) * 0.5000; double l2a = P2X - P3X; double l2b = P2Y - P3Y; double l2c = (P3Y * P3Y - P2Y * P2Y + P3X * P3X - P2X * P2X) * 0.5000; if (l1a * l2b == l1b * l2a) return; double x = (l1c * l2b - l1b * l2c) / (l1b * l2a - l1a * l2b); double y = (l1a * l2c - l1c * l2a) / (l1b * l2a - l1a * l2b); double d = Math.sqrt(Math.pow(s1.v.x - x, 2) + Math.pow(s1.v.y - y, 2)); g.setColor(Color.blue); g.fillOval((int) P1X - (int) (w / 2), (int) P1Y - (int) (h / 2), w, h); g.fillOval((int) P2X - (int) (w / 2), (int) P2Y - (int) (h / 2), w, h); g.fillOval((int) P3X - (int) (w / 2), (int) P3Y - (int) (h / 2), w, h); g.setColor(Color.red); g.drawOval((int) (x - d), (int) (y - d), (int) (2 * d), (int) (2 * d)); } public void DrawCircle(Graphics g, int w, int h) { cVertex v; cFace f; int V = 0, F = 0; v = list.head; do { if (v.mark) V++; v = v.next; } while (v != list.head); f = flist.head; do { if(f.lower) out_triple( g, f.vertex[0],f.vertex[1],f.vertex[2]); ++F; f = f.next; } while (f != flist.head); } public void DrawRest(Graphics g, int w, int h) { cVertex v; cFace f; int V = 0, F = 0; v = list.head; do { if (v.mark) V++; v = v.next; } while (v != list.head); f = flist.head; do { ++F; f = f.next; } while (f != flist.head); do { if (flist.n >= 2) { g.drawLine(f.vertex[0].v.x, f.vertex[0].v.y, f.vertex[1].v.x, f.vertex[1].v.y); g.drawLine(f.vertex[1].v.x, f.vertex[1].v.y, f.vertex[2].v.x, f.vertex[2].v.y); g.drawLine(f.vertex[2].v.x, f.vertex[2].v.y, f.vertex[0].v.x, f.vertex[0].v.y); } f = f.next; } while (f != flist.head); do { g.setColor(Color.black); g.fillOval(v.v.x - (int) (w / 2), v.v.y - (int) (h / 2), w, h); v = v.next; } while (v != list.head); } }