From d1ceae8cf7e0222d15f1b1c80aba6d93e59b2dfb Mon Sep 17 00:00:00 2001 From: stephey Date: Fri, 8 Apr 2011 05:39:01 +0000 Subject: [PATCH] voronoi benchmark. On dc-11, the computation part runs 3x faster with a computation depth of 3. It could probably do better but for some reason, when I add another sese (see Vertex.java line 115 where it's commented out), RuntimeConflictResolver.java crashes on line 506 (cannot find a conflict graph for a given sese). --- .../src/Benchmarks/oooJava/voronoi/Edge.java | 468 ++++++++++++++++++ .../Benchmarks/oooJava/voronoi/EdgePair.java | 27 + .../Benchmarks/oooJava/voronoi/MyDouble.java | 18 + .../oooJava/voronoi/TestRunner.java | 136 +++++ .../src/Benchmarks/oooJava/voronoi/Vec2.java | 122 +++++ .../Benchmarks/oooJava/voronoi/Vertex.java | 330 ++++++++++++ .../src/Benchmarks/oooJava/voronoi/makefile | 8 + 7 files changed, 1109 insertions(+) create mode 100644 Robust/src/Benchmarks/oooJava/voronoi/Edge.java create mode 100644 Robust/src/Benchmarks/oooJava/voronoi/EdgePair.java create mode 100644 Robust/src/Benchmarks/oooJava/voronoi/MyDouble.java create mode 100644 Robust/src/Benchmarks/oooJava/voronoi/TestRunner.java create mode 100644 Robust/src/Benchmarks/oooJava/voronoi/Vec2.java create mode 100644 Robust/src/Benchmarks/oooJava/voronoi/Vertex.java create mode 100644 Robust/src/Benchmarks/oooJava/voronoi/makefile diff --git a/Robust/src/Benchmarks/oooJava/voronoi/Edge.java b/Robust/src/Benchmarks/oooJava/voronoi/Edge.java new file mode 100644 index 00000000..bd16aaad --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/Edge.java @@ -0,0 +1,468 @@ + +/*import java.io.*; +import java.util.Stack; +import java.util.Hashtable;*/ + +/** + * A class that represents the quad edge data structure which implements + * the edge algebra as described in the algorithm. + *

+ * Each edge contains 4 parts, or other edges. Any edge in the group may + * be accessed using a series of rotate and flip operations. The 0th + * edge is the canonical representative of the group. + *

+ * The quad edge class does not contain separate information for vertice + * or faces; a vertex is implicitly defined as a ring of edges (the ring + * is created using the next field). + **/ +class Edge +{ + /** + * Group of edges that describe the quad edge + **/ + Edge quadList[]; + /** + * The position of this edge within the quad list + **/ + int listPos; + /** + * The vertex that this edge represents + **/ + Vertex vertex; + /** + * Contains a reference to a connected quad edge + **/ + Edge next; + + public Edge(){ + } + + /** + * Create a new edge which. + **/ + public Edge(Vertex v, Edge ql[], int pos) + { + vertex = v; + quadList = ql; + listPos = pos; + } + + /** + * Create a new edge which. + **/ + public Edge(Edge ql[], int pos) + { + this(null, ql, pos); + } + + /** + * Create a string representation of the edge + **/ + /*public String toString() + { + if (vertex != null) + return vertex.toString(); + else + return "None"; + }*/ + + public Edge makeEdge(Vertex o, Vertex d) + { + Edge ql[] = new Edge[4]; + ql[0] = new Edge(ql, 0); + ql[1] = new Edge(ql, 1); + ql[2] = new Edge(ql, 2); + ql[3] = new Edge(ql, 3); + + ql[0].next = ql[0]; + ql[1].next = ql[3]; + ql[2].next = ql[2]; + ql[3].next = ql[1]; + + Edge base = ql[0]; + base.setOrig(o); + base.setDest(d); + return base; + } + + public void setNext(Edge n) + { + next = n; + } + + /** + * Initialize the data (vertex) for the edge's origin + **/ + public void setOrig(Vertex o) + { + vertex = o; + } + + /** + * Initialize the data (vertex) for the edge's destination + **/ + public void setDest(Vertex d) + { + symmetric().setOrig(d); + } + + Edge oNext() + { + return next; + } + + Edge oPrev() + { + return this.rotate().oNext().rotate(); + } + + Edge lNext() + { + return this.rotateInv().oNext().rotate(); + } + + Edge lPrev() + { + return this.oNext().symmetric(); + } + + Edge rNext() + { + return this.rotate().oNext().rotateInv(); + } + + Edge rPrev() + { + return this.symmetric().oNext(); + } + + Edge dNext() + { + return this.symmetric().oNext().symmetric(); + } + + Edge dPrev() + { + return this.rotateInv().oNext().rotateInv(); + } + + Vertex orig() + { + return vertex; + } + + Vertex dest() + { + return symmetric().orig(); + } + + /** + * Return the symmetric of the edge. The symmetric is the same edge + * with the opposite direction. + * @return the symmetric of the edge + **/ + Edge symmetric() + { + return quadList[(listPos+2)%4]; + } + + /** + * Return the rotated version of the edge. The rotated version is a + * 90 degree counterclockwise turn. + * @return the rotated version of the edge + **/ + Edge rotate() + { + return quadList[(listPos+1)%4]; + } + + /** + * Return the inverse rotated version of the edge. The inverse + * is a 90 degree clockwise turn. + * @return the inverse rotated edge. + **/ + Edge rotateInv() + { + return quadList[(listPos+3)%4]; + } + + Edge nextQuadEdge() + { + return quadList[(listPos+1)%4]; + } + + Edge connectLeft(Edge b) + { + Vertex t1,t2; + Edge ans, lnexta; + + t1 = dest(); + lnexta = lNext(); + t2 = b.orig(); + Edge e = new Edge(); + ans = e.makeEdge(t1, t2); + ans.splice(lnexta); + ans.symmetric().splice(b); + return ans; + } + + Edge connectRight(Edge b) + { + Vertex t1,t2; + Edge ans, oprevb,q1; + + t1 = dest(); + t2 = b.orig(); + oprevb = b.oPrev(); + + Edge e = new Edge(); + ans = e.makeEdge(t1, t2); + ans.splice(symmetric()); + ans.symmetric().splice(oprevb); + return ans; + } + + /****************************************************************/ + /* Quad-edge manipulation primitives + ****************************************************************/ + void swapedge() + { + Edge a = oPrev(); + Edge syme = symmetric(); + Edge b = syme.oPrev(); + splice(a); + syme.splice(b); + Edge lnexttmp = a.lNext(); + splice(lnexttmp); + lnexttmp = b.lNext(); + syme.splice(lnexttmp); + Vertex a1 = a.dest(); + Vertex b1 = b.dest(); + setOrig(a1); + setDest(b1); + } + + void splice(Edge b) + { + Edge alpha = oNext().rotate(); + Edge beta = b.oNext().rotate(); + Edge t1 = beta.oNext(); + Edge temp = alpha.oNext(); + alpha.setNext(t1); + beta.setNext(temp); + temp = oNext(); + t1 = b.oNext(); + b.setNext(temp); + setNext(t1); + } + + boolean valid(Edge basel) + { + Vertex t1 = basel.orig(); + Vertex t3 = basel.dest(); + Vertex t2 = dest(); + return t1.ccw(t2, t3); + } + + void deleteEdge() + { + Edge f = oPrev(); + splice(f); + f = symmetric().oPrev(); + symmetric().splice(f); + } + + EdgePair doMerge(Edge ldo, Edge ldi, Edge rdi, Edge rdo) + { + boolean torun = true; + while (torun) { + Vertex t3 = rdi.orig(); + Vertex t1 = ldi.orig(); + Vertex t2 = ldi.dest(); + + while (t1.ccw(t2, t3)) { + ldi = ldi.lNext(); + + t1=ldi.orig(); + t2=ldi.dest(); + } + + t2=rdi.dest(); + + if (t2.ccw(t3, t1)) { + rdi = rdi.rPrev(); + } else { + torun = false; + // break; + } + } + + Edge basel = rdi.symmetric().connectLeft(ldi); + + Edge lcand = basel.rPrev(); + Edge rcand = basel.oPrev(); + Vertex t1 = basel.orig(); + Vertex t2 = basel.dest(); + + if (t1 == rdo.orig()) + rdo = basel; + if (t2 == ldo.orig()) + ldo = basel.symmetric(); + + while (true) { + Edge t = lcand.oNext(); + if (t.valid(basel)) { + Vertex v4 = basel.orig(); + + Vertex v1 = lcand.dest(); + Vertex v3 = lcand.orig(); + Vertex v2 = t.dest(); + while (v1.incircle(v2,v3,v4)){ + lcand.deleteEdge(); + lcand = t; + + t = lcand.oNext(); + v1 = lcand.dest(); + v3 = lcand.orig(); + v2 = t.dest(); + } + } + + t = rcand.oPrev(); + if (t.valid(basel)) { + Vertex v4 = basel.dest(); + Vertex v1 = t.dest(); + Vertex v2 = rcand.dest(); + Vertex v3 = rcand.orig(); + while (v1.incircle(v2,v3,v4)) { + rcand.deleteEdge(); + rcand = t; + t = rcand.oPrev(); + v2 = rcand.dest(); + v3 = rcand.orig(); + v1 = t.dest(); + } + } + + boolean lvalid = lcand.valid(basel); + + boolean rvalid = rcand.valid(basel); + if ((!lvalid) && (!rvalid)) { + return new EdgePair(ldo, rdo); + } + + Vertex v1 = lcand.dest(); + Vertex v2 = lcand.orig(); + Vertex v3 = rcand.orig(); + Vertex v4 = rcand.dest(); + if (!lvalid || (rvalid && v1.incircle(v2,v3,v4))) { + basel = rcand.connectLeft(basel.symmetric()); + rcand = basel.symmetric().lNext(); + } else { + basel = lcand.connectRight(basel).symmetric(); + lcand = basel.rPrev(); + } + } + } + + + /** + * Print the voronoi diagram and its dual, the delaunay triangle for the + * diagram. + **/ + /*void outputVoronoiDiagram() + { + Edge nex = this; + // Plot voronoi diagram edges with one endpoint at infinity. + do { + Vec2 v21 = (Vec2)nex.dest(); + Vec2 v22 = (Vec2)nex.orig(); + Edge tmp = nex.oNext(); + Vec2 v23 = (Vec2)tmp.dest(); + Vec2 cvxvec = v21.sub(v22); + Vec2 center = v22.circle_center(v21, v23); + + Vec2 vv1 = v22.sum(v22); + Vec2 vv2 = vv1.times((float) 0.5); + Vec2 vv3 = center.sub(vv2); + double ln = 1.0 + vv3.magn(); + double d1 = ln/cvxvec.magn(); + vv1 = cvxvec.cross(); + vv2 = vv1.times((float) d1) ; + vv3 = center.sum(vv2); + System.out.println("Vedge " + center.toString() + " " + vv3.toString()); + nex = nex.rNext(); + } while (nex != this); + + // plot delaunay triangle edges and finite VD edges. + Stack edges = new Stack(); + Hashtable seen = new Hashtable(); + pushRing(edges, seen); + System.out.println("no. of edges = " + edges.size()); + while (!edges.empty()) { + Edge edge = (Edge)edges.pop(); + Boolean b = (Boolean)seen.get(edge); + if (b != null && b.booleanValue()) { + Edge prev = edge; + nex = edge.oNext(); + do { + Vertex v1 = prev.orig(); + double d1 = v1.X(); + Vertex v2 = prev.dest(); + double d2 = v2.X(); + if (d1 >= d2) { + System.out.println("Dedge " + v1 + " " + v2); + Edge sprev = prev.symmetric(); + Edge snex = sprev.oNext(); + v1 = prev.orig(); + v2 = prev.dest(); + Vertex v3 = nex.dest(); + Vertex v4 = snex.dest(); + if (v1.ccw(v2, v3) != v1.ccw(v2, v4)) { + Vec2 v21 = prev.orig(); + Vec2 v22 = prev.dest(); + Vec2 v23 = nex.dest(); + Vec2 vv1 = v21.circle_center(v22, v23); + v21 = sprev.orig(); + v22 = sprev.dest(); + v23 = snex.dest(); + Vec2 vv2 = v21.circle_center(v22, v23); + System.out.println("Vedge " + vv1.toString() + " " + vv2.toString()); + } + } + seen.put(prev, new Boolean(false)); + prev = nex; + nex = nex.oNext(); + } while (prev != edge); + } + edge.symmetric().pushRing(edges, seen); + } + } + + /* + void pushRing(Stack stack, Hashtable seen) + { + Edge nex = oNext(); + while (nex != this) { + if (!seen.containsKey(nex)) { + seen.put(nex, new Boolean(true)); + stack.push(nex); + } + nex = nex.oNext(); + } + } + + void pushNonezeroRing(Stack stack, Hashtable seen) + { + Edge nex = oNext(); + while (nex != this) { + if (seen.containsKey(nex)) { + seen.remove(nex); + stack.push(nex); + } + nex = nex.oNext(); + } + }*/ + +} + diff --git a/Robust/src/Benchmarks/oooJava/voronoi/EdgePair.java b/Robust/src/Benchmarks/oooJava/voronoi/EdgePair.java new file mode 100644 index 00000000..b757284f --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/EdgePair.java @@ -0,0 +1,27 @@ +//import java.io.*; + +/** + * A class that represents an edge pair + **/ +public class EdgePair +{ + Edge left; + Edge right; + + public EdgePair(Edge l, Edge r) + { + left = l; + right = r; + } + + public Edge getLeft() + { + return left; + } + + public Edge getRight() + { + return right; + } + +} diff --git a/Robust/src/Benchmarks/oooJava/voronoi/MyDouble.java b/Robust/src/Benchmarks/oooJava/voronoi/MyDouble.java new file mode 100644 index 00000000..68cad7fd --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/MyDouble.java @@ -0,0 +1,18 @@ + +/** + * A class that represents a wrapper around a double value so + * that we can use it as an 'out' parameter. The java.lang.Double + * class is immutable. + **/ +public class MyDouble +{ + public float value; + MyDouble(float d) + { + value = d; + } + /*public String toString() + { + return Double.toString(value); + }*/ +} diff --git a/Robust/src/Benchmarks/oooJava/voronoi/TestRunner.java b/Robust/src/Benchmarks/oooJava/voronoi/TestRunner.java new file mode 100644 index 00000000..33805743 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/TestRunner.java @@ -0,0 +1,136 @@ +// Bamboo version +/*import java.io.*; +import java.util.Stack;*/ + +/** + * A Java implementation of the voronoi Olden benchmark. Voronoi + * generates a random set of points and computes a Voronoi diagram for + * the points. + *

+ * + * L. Guibas and J. Stolfi. "General Subdivisions and Voronoi Diagrams" + * ACM Trans. on Graphics 4(2):74-123, 1985. + * + *

+ * The Java version of voronoi (slightly) differs from the C version + * in several ways. The C version allocates an array of 4 edges and + * uses pointer addition to implement quick rotate operations. The + * Java version does not use pointer addition to implement these + * operations. + **/ +public class TestRunner //Voronoi +{ + /** + * The number of points in the diagram + **/ + private int points; // = 0; + /** + * Set to true to print informative messages + **/ + //private static boolean printMsgs; // = false; + /** + * Set to true to print the voronoi diagram and its dual, + * the delaunay diagram + **/ + //private static boolean printResults; // = false; + + public TestRunner(int npoints) { + this.points = npoints; + //this.printMsgs = false; + //this.printResults = false; + } + + public static void main(String[] args) { + if(args.length < 2) { + System.out.println("Usage: "); + System.out.println("Recommended values:"); + System.out.println(" Num Points: 6400000"); + System.out.println(" Parallel_threshold: 3 for an 8 core machine."); + System.exit(-1); + } + int npoints = Integer.parseInt(args[0]); + int parallelThreshold = Integer.parseInt(args[1]); + TestRunner tr = new TestRunner(npoints); + + tr.run(parallelThreshold); + } + + /** + * The main routine which creates the points and then performs + * the delaunay triagulation. + * @param args the command line parameters + **/ + public void run(int parallelThreshold) //main(String args[]) + { +// parseCmdLine(args); + + /*if (printMsgs) + System.out.println("Getting " + points + " points");*/ + + long start0 = System.currentTimeMillis(); + Vertex v = new Vertex(); + v.seed = 1023; + Vertex extra = v.createPoints(1, new MyDouble(1.0f), points); + Vertex point = v.createPoints(points-1, new MyDouble(extra.X()), points-1); + long end0 = System.currentTimeMillis(); + + /*if (printMsgs)*/ + System.out.println("Doing voronoi on " + points + " points with threshold " + parallelThreshold); + + long start1 = System.currentTimeMillis(); + Edge edge = point.buildDelaunayTriangulation(extra, parallelThreshold); + long end1 = System.currentTimeMillis(); + System.out.println("Build time " + (end0-start0)/1000.0); + System.out.println("Compute time " + (end1-start1)/1000.0); + System.out.println("Total time " + (end1-start0)/1000.0); + System.out.println("Done!"); + + /*if (printResults) + edge.outputVoronoiDiagram(); */ + +// if (printMsgs) { + +// } + } + + /** + * Parse the command line options. + * @param args the command line options. + **/ + /*private static final void parseCmdLine(String args[]) + { + int i = 0; + String arg; + + while (i < args.length && args[i].startsWith("-")) { + arg = args[i++]; + + if (arg.equals("-n")) { + if (i < args.length) { + points = new Integer(args[i++]).intValue(); + } else throw new RuntimeException("-n requires the number of points"); + } else if (arg.equals("-p")) { + printResults = true; + } else if (arg.equals("-m")) { + printMsgs = true; + } else if (arg.equals("-h")) { + usage(); + } + } + if (points == 0) usage(); + }*/ + + /** + * The usage routine which describes the program options. + **/ + private static final void usage() + { + /*System.err.println("usage: java Voronoi -n [-p] [-m] [-h]"); + System.err.println(" -n the number of points in the diagram"); + System.err.println(" -p (print detailed results/messages - the voronoi diagram>)"); + System.err.println(" -v (print informative message)"); + System.err.println(" -h (this message)"); + System.exit(0);*/ + } + +} diff --git a/Robust/src/Benchmarks/oooJava/voronoi/Vec2.java b/Robust/src/Benchmarks/oooJava/voronoi/Vec2.java new file mode 100644 index 00000000..9802e69a --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/Vec2.java @@ -0,0 +1,122 @@ + +//import java.io.*; + +/** + * Vector Routines from CMU vision library. + * They are used only for the Voronoi Diagram, not the Delaunay Triagulation. + * They are slow because of large call-by-value parameters. + **/ +class Vec2 +{ + float x,y; + float norm; + + public Vec2() {} + + public Vec2(float xx, float yy) + { + x = xx; + y = yy; + norm = (float)(x*x + y*y); + } + + public float X() + { + return x; + } + + public float Y() + { + return y; + } + + public float Norm() + { + return norm; + } + + public void setNorm(float d) + { + norm = d; + } + + /*public String toString() + { + return x + " " + y; + }*/ + + Vec2 circle_center(Vec2 b, Vec2 c) + { + Vec2 vv1 = b.sub(c); + float d1 = vv1.magn(); + vv1 = sum(b); + Vec2 vv2 = vv1.times(0.5f); + if (d1 < 0.0) /*there is no intersection point, the bisectors coincide. */ + return(vv2); + else { + Vec2 vv3 = b.sub(this); + Vec2 vv4 = c.sub(this); + float d3 = vv3.cprod(vv4) ; + float d2 = (float)(-2.0f * d3) ; + Vec2 vv5 = c.sub(b); + float d4 = vv5.dot(vv4); + Vec2 vv6 = vv3.cross(); + Vec2 vv7 = vv6.times((float)(d4/d2)); + return vv2.sum(vv7); + } + } + + + + /** + * cprod: forms triple scalar product of [u,v,k], where k = u cross v + * (returns the magnitude of u cross v in space) + **/ + float cprod(Vec2 v) + { + return((float)(x * v.y - y * v.x)); + } + + /* V2_dot: vector dot product */ + + float dot(Vec2 v) + { + return((float)(x * v.x + y * v.y)); + } + + /* V2_times: multiply a vector by a scalar */ + + Vec2 times(float c) + { + return (new Vec2((float)(c*x), (float)(c*y))); + } + + /* V2_sum, V2_sub: Vector addition and subtraction */ + + Vec2 sum(Vec2 v) + { + return (new Vec2((float)(x + v.x), (float)(y + v.y))); + } + + Vec2 sub(Vec2 v) + { + return(new Vec2((float)(x - v.x), (float)(y - v.y))); + } + +/* V2_magn: magnitude of vector */ + + float magn() + { + return(Math.sqrtf((float)(x*x+y*y))); + } + + /* returns k X v (cross product). this is a vector perpendicular to v */ + + Vec2 cross() + { + return(new Vec2((float)y,(float)(-x))); + } +} + + + diff --git a/Robust/src/Benchmarks/oooJava/voronoi/Vertex.java b/Robust/src/Benchmarks/oooJava/voronoi/Vertex.java new file mode 100644 index 00000000..d65138a0 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/Vertex.java @@ -0,0 +1,330 @@ + +//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. + **/ + int seed; + + public Vertex() { } + + public Vertex(float x, float 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 + **/ + Vertex createPoints(int n, MyDouble curmax, int i) + { + if (n < 1 ) { + return null; + } + + Vertex cur = new Vertex(); + + Vertex right = cur.createPoints(n/2, curmax, i); + i -= n/2; + cur.x = (float)(curmax.value * Math.expf(Math.logf((float)this.drand())/i)); + cur.y = (float)this.drand(); + cur.norm = (float)(cur.x * cur.x + cur.y*cur.y); + cur.right = right; + curmax.value = (float)cur.X(); + Vertex left = cur.createPoints(n/2, curmax, i-1); + + cur.left = left; + return cur; + } + + + /** + * Builds delaunay triangulation. + **/ + Edge buildDelaunayTriangulation(Vertex extra, int parallelThreshold) + { + EdgePair retVal = buildDelaunay(extra, 0, parallelThreshold); + return retVal.getLeft(); + } + + /** + * Recursive delaunay triangulation procedure + * Contains modifications for axis-switching division. + **/ + EdgePair buildDelaunay(Vertex extra, int depth, int threshold) + { + if(depth == threshold) { + return buildDelaunaySerial(extra); + } else + { + EdgePair retval = null; + if (getRight() != null && getLeft() != null) { + // more than three elements; do recursion + Vertex minx = getLow(); + Vertex maxx = extra; + + sese p1 { + EdgePair delright = getRight().buildDelaunay(extra,depth+1,threshold); + } + + EdgePair delleft = getLeft().buildDelaunay(this, depth+1,threshold); + + Edge e = new Edge(); + retval = e.doMerge(delleft.getLeft(), delleft.getRight(), + delright.getLeft(), delright.getRight()); + + +// sese findRight { + Edge rdo = retval.getRight(); + while (rdo.orig() != maxx) { + rdo = rdo.lPrev(); + } +// } + + Edge ldo = retval.getLeft(); + while (ldo.orig() != minx) { + ldo = ldo.rPrev(); + } + + retval = new EdgePair(ldo, rdo); + + } else if (getLeft() == null) { + // two points + Edge e = new Edge(); + Edge a = e.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 e = new Edge(); + Edge a = e.makeEdge(s1, s2); + Edge b = e.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; + } + } + + EdgePair buildDelaunaySerial(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().buildDelaunaySerial(extra); + + EdgePair delleft = getLeft().buildDelaunaySerial(this); + + Edge e = new Edge(); + retval = e.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 e = new Edge(); + Edge a = e.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 e = new Edge(); + Edge a = e.makeEdge(s1, s2); + Edge b = e.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. */ + { + float adx, ady, bdx, bdy, cdx, cdy, dx, dy, anorm, bnorm, cnorm, dnorm; + float 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 = (float)((anorm - dnorm) * (bdx * cdy - bdy * cdx)); + dret += (float)((bnorm - dnorm) * (cdx * ady - cdy * adx)); + dret += (float)((cnorm - dnorm) * (adx * bdy - ady * bdx)); + return( (0.0f < dret) ? true : false ); + } + + boolean ccw(Vertex b, Vertex c) + /* TRUE iff this, B, C form a counterclockwise oriented triangle */ + { + float dret ; + float 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 = (float)((float)(xa-xc)*(float)(yb-yc) - (float)(xb-xc)*(float)(ya-yc)); + return( (dret > 0.0f)? true : false); + } + + /** + * A routine used by the random number generator + **/ + 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 + **/ + int skiprand(int seed, int n) + { + for (; n != 0; n--) + seed=random(seed); + return seed; + } + + int random(int seed) + { + int CONST_b = 31415821; + + seed = mult(seed, CONST_b) + 1; + return seed; + } + + float drand() + { + this.seed = this.random(this.seed); + float retval = ((float)this.seed) / + (float) 2147483647; + return retval; + } + +} + + diff --git a/Robust/src/Benchmarks/oooJava/voronoi/makefile b/Robust/src/Benchmarks/oooJava/voronoi/makefile new file mode 100644 index 00000000..cbd92578 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/makefile @@ -0,0 +1,8 @@ +PROGRAM=TestRunner + +SOURCE_FILES=TestRunner.java + +NUM_OOO_WORKERS=24 +NUM_RCR_WORKERS=7 + +include ../master-makefile -- 2.34.1