package memory.jolden.voronoi; import java.io.*; /** * A class that represents a voronoi diagram. The diagram is represnted * as a binary tree of points. **/ class Vertex extends Vec2 { /** * The left child of the tree that represents the voronoi diagram. **/ Vertex left; /** * The right child of the tree that represents the voronoi diagram. **/ Vertex right; /** * Seed value used during tree creation. **/ static int seed; public Vertex() { } public Vertex(double x, double y) { super(x, y); left = null; right = null; } public void setLeft(Vertex l) { left = l; } public void setRight(Vertex r) { right = r; } public Vertex getLeft() { return left; } public Vertex getRight() { return right; } /** * Generate a voronoi diagram **/ static Vertex createPoints(int n, MyDouble curmax, int i) { if (n < 1 ) { return null; } Vertex cur = new Vertex(); Vertex right = Vertex.createPoints(n/2, curmax, i); i -= n/2; cur.x = curmax.value * Math.exp(Math.log(Vertex.drand())/i); cur.y = Vertex.drand(); cur.norm = cur.x * cur.x + cur.y*cur.y; cur.right = right; curmax.value = cur.X(); Vertex left = Vertex.createPoints(n/2, curmax, i-1); cur.left = left; return null; } /** * Builds delaunay triangulation. **/ Edge buildDelaunayTriangulation(Vertex extra) { EdgePair retVal = buildDelaunay(extra); return retVal.getLeft(); } /** * Recursive delaunay triangulation procedure * Contains modifications for axis-switching division. **/ EdgePair buildDelaunay(Vertex extra) { EdgePair retval = null; if (getRight() != null && getLeft() != null) { // more than three elements; do recursion Vertex minx = getLow(); Vertex maxx = extra; EdgePair delright = getRight().buildDelaunay(extra); EdgePair delleft = getLeft().buildDelaunay(this); retval = Edge.doMerge(delleft.getLeft(), delleft.getRight(), delright.getLeft(), delright.getRight()); Edge ldo = retval.getLeft(); while (ldo.orig() != minx) { ldo = ldo.rPrev(); } Edge rdo = retval.getRight(); while (rdo.orig() != maxx) { rdo = rdo.lPrev(); } retval = new EdgePair(ldo, rdo); } else if (getLeft() == null) { // two points Edge a = Edge.makeEdge(this, extra); retval = new EdgePair(a, a.symmetric()); } else { // left, !right three points // 3 cases: triangles of 2 orientations, and 3 points on a line. */ Vertex s1 = getLeft(); Vertex s2 = this; Vertex s3 = extra; Edge a = Edge.makeEdge(s1, s2); Edge b = Edge.makeEdge(s2, s3); a.symmetric().splice(b); Edge c = b.connectLeft(a); if (s1.ccw(s3, s2)) { retval = new EdgePair(c.symmetric(), c); } else { retval = new EdgePair(a, b.symmetric()); if (s1.ccw(s2, s3)) c.deleteEdge(); } } return retval; } /** * Print the tree **/ void print() { Vertex tleft, tright; System.out.println("X=" + X() + " Y=" + Y()); if (left == null) System.out.println("NULL"); else left.print(); if (right == null) System.out.println("NULL"); else right.print(); } /** * Traverse down the left child to the end **/ Vertex getLow() { Vertex temp; Vertex tree = this; while ((temp=tree.getLeft()) != null) tree = temp; return tree; } /****************************************************************/ /* Geometric primitives ****************************************************************/ boolean incircle(Vertex b, Vertex c, Vertex d) /* incircle, as in the Guibas-Stolfi paper. */ { double adx, ady, bdx, bdy, cdx, cdy, dx, dy, anorm, bnorm, cnorm, dnorm; double dret ; Vertex loc_a,loc_b,loc_c,loc_d; int donedx,donedy,donednorm; loc_d = d; dx = loc_d.X(); dy = loc_d.Y(); dnorm = loc_d.Norm(); loc_a = this; adx = loc_a.X() - dx; ady = loc_a.Y() - dy; anorm = loc_a.Norm(); loc_b = b; bdx = loc_b.X() - dx; bdy = loc_b.Y() - dy; bnorm = loc_b.Norm(); loc_c = c; cdx = loc_c.X() - dx; cdy = loc_c.Y() - dy; cnorm = loc_c.Norm(); dret = (anorm - dnorm) * (bdx * cdy - bdy * cdx); dret += (bnorm - dnorm) * (cdx * ady - cdy * adx); dret += (cnorm - dnorm) * (adx * bdy - ady * bdx); return( (0.0 < dret) ? true : false ); } boolean ccw(Vertex b, Vertex c) /* TRUE iff this, B, C form a counterclockwise oriented triangle */ { double dret ; double xa,ya,xb,yb,xc,yc; Vertex loc_a,loc_b,loc_c; int donexa,doneya,donexb,doneyb,donexc,doneyc; loc_a = this; xa = loc_a.X(); ya = loc_a.Y(); loc_b = b; xb = loc_b.X(); yb = loc_b.Y(); loc_c = c; xc = loc_c.X(); yc = loc_c.Y(); dret = (xa-xc)*(yb-yc) - (xb-xc)*(ya-yc); return( (dret > 0.0)? true : false); } /** * A routine used by the random number generator **/ static int mult(int p,int q) { int p1, p0, q1, q0; int CONST_m1 = 10000; p1=p/CONST_m1; p0=p%CONST_m1; q1=q/CONST_m1; q0=q%CONST_m1; return (((p0*q1+p1*q0) % CONST_m1)*CONST_m1+p0*q0); } /** * Generate the nth random number **/ static int skiprand(int seed, int n) { for (; n != 0; n--) seed=random(seed); return seed; } static int random(int seed) { int CONST_b = 31415821; seed = mult(seed, CONST_b) + 1; return seed; } static double drand() { double retval = ((double)(Vertex.seed = Vertex.random(Vertex.seed))) / (double) 2147483647; return retval; } }