From 8978602aee3dbe82b665e8ea57d185f7339a7ed3 Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 8 Apr 2011 22:31:08 +0000 Subject: [PATCH] having working version of both single and rcrpointer. currently it's working fine with original benchmark size 64k points which seems to be realllllllllly small for our env) --- .../src/Benchmarks/oooJava/voronoi/Edge.java | 362 ++++++++---------- .../Benchmarks/oooJava/voronoi/EdgePair.java | 18 +- .../Benchmarks/oooJava/voronoi/MyDouble.java | 21 +- .../oooJava/voronoi/TestRunner.java | 144 +++---- .../src/Benchmarks/oooJava/voronoi/Vec2.java | 112 +++--- .../Benchmarks/oooJava/voronoi/Vertex.java | 351 +++++++++-------- .../src/Benchmarks/oooJava/voronoi/makefile | 2 +- Robust/src/Benchmarks/oooJava/voronoi/runr | 1 + Robust/src/Benchmarks/oooJava/voronoi/runs | 1 + 9 files changed, 470 insertions(+), 542 deletions(-) create mode 100755 Robust/src/Benchmarks/oooJava/voronoi/runr create mode 100755 Robust/src/Benchmarks/oooJava/voronoi/runs diff --git a/Robust/src/Benchmarks/oooJava/voronoi/Edge.java b/Robust/src/Benchmarks/oooJava/voronoi/Edge.java index fb892b2f..4b891344 100644 --- a/Robust/src/Benchmarks/oooJava/voronoi/Edge.java +++ b/Robust/src/Benchmarks/oooJava/voronoi/Edge.java @@ -3,19 +3,18 @@ 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. + * 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. + * 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). + * 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 -{ +class Edge { /** * Group of edges that describe the quad edge **/ @@ -23,24 +22,23 @@ class Edge /** * The position of this edge within the quad list **/ - int listPos; + int listPos; /** * The vertex that this edge represents **/ - Vertex vertex; + Vertex vertex; /** * Contains a reference to a connected quad edge **/ - Edge next; - - public Edge(){ + Edge next; + + public Edge() { } /** * Create a new edge which. **/ - public Edge(Vertex v, Edge ql[], int pos) - { + public Edge(Vertex v, Edge ql[], int pos) { vertex = v; quadList = ql; listPos = pos; @@ -49,24 +47,19 @@ class Edge /** * Create a new edge which. **/ - public Edge(Edge ql[], int pos) - { + 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) - { + /* + * 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); @@ -77,158 +70,143 @@ class Edge 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) - { + public void setNext(Edge n) { next = n; } /** - * Initialize the data (vertex) for the edge's origin + * Initialize the data (vertex) for the edge's origin **/ - public void setOrig(Vertex o) - { + public void setOrig(Vertex o) { vertex = o; } /** * Initialize the data (vertex) for the edge's destination **/ - public void setDest(Vertex d) - { + public void setDest(Vertex d) { symmetric().setOrig(d); } - - Edge oNext() - { + + Edge oNext() { return next; } - Edge oPrev() - { + Edge oPrev() { return this.rotate().oNext().rotate(); } - - Edge lNext() - { + + Edge lNext() { return this.rotateInv().oNext().rotate(); } - Edge lPrev() - { - return this.oNext().symmetric(); + Edge lPrev() { + return this.oNext().symmetric(); } - Edge rNext() - { + Edge rNext() { return this.rotate().oNext().rotateInv(); } - Edge rPrev() - { - return this.symmetric().oNext(); + Edge rPrev() { + return this.symmetric().oNext(); } - Edge dNext() - { + Edge dNext() { return this.symmetric().oNext().symmetric(); } - Edge dPrev() - { - return this.rotateInv().oNext().rotateInv(); + Edge dPrev() { + return this.rotateInv().oNext().rotateInv(); } - - Vertex orig() - { + + Vertex orig() { return vertex; - } + } - Vertex dest() - { + 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. The symmetric is the same edge with the + * opposite direction. + * * @return the symmetric of the edge **/ - Edge symmetric() - { - return quadList[(listPos+2)%4]; + 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. The rotated version is a 90 degree + * counterclockwise turn. + * * @return the rotated version of the edge **/ - Edge rotate() - { - return quadList[(listPos+1)%4]; + 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 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 rotateInv() { + return quadList[(listPos + 3) % 4]; } - - Edge nextQuadEdge() - { - return quadList[(listPos+1)%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 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; + 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() - { + /* + * Quad-edge manipulation primitives + * ************************************************************** + */ + void swapedge() { Edge a = oPrev(); Edge syme = symmetric(); - Edge b = syme.oPrev(); + Edge b = syme.oPrev(); splice(a); syme.splice(b); Edge lnexttmp = a.lNext(); @@ -238,41 +216,37 @@ class Edge Vertex a1 = a.dest(); Vertex b1 = b.dest(); setOrig(a1); - setDest(b1); + setDest(b1); } - void splice(Edge b) - { + void splice(Edge b) { Edge alpha = oNext().rotate(); Edge beta = b.oNext().rotate(); Edge t1 = beta.oNext(); Edge temp = alpha.oNext(); - alpha.setNext(t1); + alpha.setNext(t1); beta.setNext(temp); - temp = oNext(); - t1 = b.oNext(); - b.setNext(temp); + temp = oNext(); + t1 = b.oNext(); + b.setNext(temp); setNext(t1); } - - boolean valid(Edge basel) - { + + boolean valid(Edge basel) { Vertex t1 = basel.orig(); Vertex t3 = basel.dest(); Vertex t2 = dest(); return t1.ccw(t2, t3); } - void deleteEdge() - { + void deleteEdge() { Edge f = oPrev(); splice(f); f = symmetric().oPrev(); symmetric().splice(f); - } + } - EdgePair doMerge(Edge ldo, Edge ldi, Edge rdi, Edge rdo) - { + EdgePair doMerge(Edge ldo, Edge ldi, Edge rdi, Edge rdo) { boolean torun = true; while (torun) { Vertex t3 = rdi.orig(); @@ -282,17 +256,17 @@ class Edge while (t1.ccw(t2, t3)) { ldi = ldi.lNext(); - t1=ldi.orig(); - t2=ldi.dest(); + t1 = ldi.orig(); + t2 = ldi.dest(); } - t2=rdi.dest(); + t2 = rdi.dest(); - if (t2.ccw(t3, t1)) { - rdi = rdi.rPrev(); + if (t2.ccw(t3, t1)) { + rdi = rdi.rPrev(); } else { torun = false; - // break; + // break; } } @@ -303,9 +277,9 @@ class Edge Vertex t1 = basel.orig(); Vertex t2 = basel.dest(); - if (t1 == rdo.orig()) + if (t1 == rdo.orig()) rdo = basel; - if (t2 == ldo.orig()) + if (t2 == ldo.orig()) ldo = basel.symmetric(); while (true) { @@ -316,7 +290,7 @@ class Edge Vertex v1 = lcand.dest(); Vertex v3 = lcand.orig(); Vertex v2 = t.dest(); - while (v1.incircle(v2,v3,v4)){ + while (v1.incircle(v2, v3, v4)) { lcand.deleteEdge(); lcand = t; @@ -333,7 +307,7 @@ class Edge Vertex v1 = t.dest(); Vertex v2 = rcand.dest(); Vertex v3 = rcand.orig(); - while (v1.incircle(v2,v3,v4)) { + while (v1.incircle(v2, v3, v4)) { rcand.deleteEdge(); rcand = t; t = rcand.oPrev(); @@ -354,7 +328,7 @@ class Edge Vertex v2 = lcand.orig(); Vertex v3 = rcand.orig(); Vertex v4 = rcand.dest(); - if (!lvalid || (rvalid && v1.incircle(v2,v3,v4))) { + if (!lvalid || (rvalid && v1.incircle(v2, v3, v4))) { basel = rcand.connectLeft(basel.symmetric()); rcand = basel.symmetric().lNext(); } else { @@ -364,104 +338,98 @@ class Edge } } - /** * Print the voronoi diagram and its dual, the delaunay triangle for the * diagram. **/ - void outputVoronoiDiagram() - { + void outputVoronoiDiagram() { Edge nex = this; - // Plot voronoi diagram edges with one endpoint at infinity. + // Plot voronoi diagram edges with one endpoint at infinity. do { - Vec2 v21 = (Vec2)nex.dest(); - Vec2 v22 = (Vec2)nex.orig(); + Vec2 v21 = (Vec2) nex.dest(); + Vec2 v22 = (Vec2) nex.orig(); Edge tmp = nex.oNext(); - Vec2 v23 = (Vec2)tmp.dest(); + 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(); + double d1 = ln / cvxvec.magn(); vv1 = cvxvec.cross(); - vv2 = vv1.times((float) d1) ; + 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. LinkedList edges = new LinkedList(); Hashtable seen = new Hashtable(); pushRing(edges, seen); System.out.println("no. of edges = " + edges.size()); - while (edges.size()!=0) { - Edge edge = (Edge)edges.pop(); - Integer b = (Integer)seen.get(edge); - if (b != null && b.intValue()==1) { - 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 Integer(0)); - prev = nex; - nex = nex.oNext(); - } while (prev != edge); + while (edges.size() != 0) { + Edge edge = (Edge) edges.pop(); + Integer b = (Integer) seen.get(edge); + if (b != null && b.intValue() == 1) { + 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 Integer(0)); + prev = nex; + nex = nex.oNext(); + } while (prev != edge); } edge.symmetric().pushRing(edges, seen); } } - - void pushRing(LinkedList stack, Hashtable seen) - { + void pushRing(LinkedList stack, Hashtable seen) { Edge nex = oNext(); while (nex != this) { if (!seen.containsKey(nex)) { - seen.put(nex, new Integer(1)); - stack.push(nex); + seen.put(nex, new Integer(1)); + stack.push(nex); } nex = nex.oNext(); } } - void pushNonezeroRing(LinkedList stack, Hashtable seen) - { + void pushNonezeroRing(LinkedList stack, Hashtable seen) { Edge nex = oNext(); while (nex != this) { if (seen.containsKey(nex)) { - seen.remove(nex); - stack.push(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 index b757284f..3d9aa267 100644 --- a/Robust/src/Benchmarks/oooJava/voronoi/EdgePair.java +++ b/Robust/src/Benchmarks/oooJava/voronoi/EdgePair.java @@ -1,27 +1,21 @@ -//import java.io.*; - /** * A class that represents an edge pair **/ -public class EdgePair -{ +public class EdgePair { Edge left; Edge right; - - public EdgePair(Edge l, Edge r) - { + + public EdgePair(Edge l, Edge r) { left = l; right = r; } - public Edge getLeft() - { + public Edge getLeft() { return left; } - public Edge getRight() - { + public Edge getRight() { return right; } -} +} diff --git a/Robust/src/Benchmarks/oooJava/voronoi/MyDouble.java b/Robust/src/Benchmarks/oooJava/voronoi/MyDouble.java index 68cad7fd..3c5c7f5f 100644 --- a/Robust/src/Benchmarks/oooJava/voronoi/MyDouble.java +++ b/Robust/src/Benchmarks/oooJava/voronoi/MyDouble.java @@ -1,18 +1,15 @@ - /** - * 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. + * 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) - { +public class MyDouble { + public double value; + + MyDouble(double d) { value = d; } - /*public String toString() - { + + 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 index 7e7d6459..51fea46e 100644 --- a/Robust/src/Benchmarks/oooJava/voronoi/TestRunner.java +++ b/Robust/src/Benchmarks/oooJava/voronoi/TestRunner.java @@ -1,25 +1,18 @@ -// 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. + * 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. - * + * 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. + * 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 -{ +public class TestRunner // Voronoi +{ /** * The number of points in the diagram **/ @@ -27,110 +20,67 @@ public class TestRunner //Voronoi /** * Set to true to print informative messages **/ - //private static boolean printMsgs; // = false; + // private static boolean printMsgs; // = false; /** - * Set to true to print the voronoi diagram and its dual, - * the delaunay diagram + * Set to true to print the voronoi diagram and its dual, the delaunay diagram **/ - private boolean printResults; // = false; - - public TestRunner(int npoints) { + private boolean printResults; // = false; + + public TestRunner(int npoints, boolean printResults) { this.points = npoints; - //this.printMsgs = false; - this.printResults = true; + this.printResults = printResults; } - + public static void main(String[] args) { - if(args.length < 2) { + if (args.length < 1) { System.out.println("Usage: "); System.out.println("Recommended values:"); System.out.println(" Num Points: 8000000"); - System.out.println(" Parallel_threshold: 3 for an 8 core, 6 for 24 core."); System.exit(-1); } - int npoints = Integer.parseInt(args[0]); - int parallelThreshold = Integer.parseInt(args[1]); - TestRunner tr = new TestRunner(npoints); - - tr.run(parallelThreshold); + int npoints = Integer.parseInt(args[0]); + + boolean printResults = false; + if (args.length > 1) { + if (args[1].equals("-p")) { + printResults = true; + } + } + + TestRunner tr = new TestRunner(npoints, printResults); + tr.run(); } /** - * The main routine which creates the points and then performs - * the delaunay triagulation. - * @param args the command line parameters + * 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[]) + public void run() // 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); + Vertex extra = Vertex.createPoints(1, new MyDouble(1.0), points); + Vertex point = Vertex.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) { + System.out.println("Doing voronoi on " + points + " points."); -// } - } - - /** - * 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++]; + long start1 = System.currentTimeMillis(); + Edge edge = point.buildDelaunayTriangulation(extra, 0); + 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 (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(); - }*/ + if (printResults) + edge.outputVoronoiDiagram(); - /** - * 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 index f137cc09..d5f627da 100644 --- a/Robust/src/Benchmarks/oooJava/voronoi/Vec2.java +++ b/Robust/src/Benchmarks/oooJava/voronoi/Vec2.java @@ -1,122 +1,100 @@ - -//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. + * 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) - { +class Vec2 { + double x, y; + double norm; + + public Vec2() { + } + + public Vec2(double xx, double yy) { x = xx; y = yy; - norm = (float)(x*x + y*y); + norm = (double) (x * x + y * y); } - public float X() - { + public double X() { return x; } - public float Y() - { + public double Y() { return y; } - public float Norm() - { + public double Norm() { return norm; } - - public void setNorm(float d) - { + + public void setNorm(double d) { norm = d; } - public String toString() - { + public String toString() { return x + " " + y; } - Vec2 circle_center(Vec2 b, Vec2 c) - { + Vec2 circle_center(Vec2 b, Vec2 c) { Vec2 vv1 = b.sub(c); - float d1 = vv1.magn(); + double 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); + 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 vv4 = c.sub(this); + double d3 = vv3.cprod(vv4); + double d2 = (double) (-2.0f * d3); Vec2 vv5 = c.sub(b); - float d4 = vv5.dot(vv4); + double d4 = vv5.dot(vv4); Vec2 vv6 = vv3.cross(); - Vec2 vv7 = vv6.times((float)(d4/d2)); + Vec2 vv7 = vv6.times((double) (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) + * 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)); + double cprod(Vec2 v) { + return ((double) (x * v.y - y * v.x)); } /* V2_dot: vector dot product */ - float dot(Vec2 v) - { - return((float)(x * v.x + y * v.y)); + double dot(Vec2 v) { + return ((double) (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))); + Vec2 times(double c) { + return (new Vec2((double) (c * x), (double) (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 sum(Vec2 v) { + return (new Vec2((double) (x + v.x), (double) (y + v.y))); } - Vec2 sub(Vec2 v) - { - return(new Vec2((float)(x - v.x), (float)(y - v.y))); + Vec2 sub(Vec2 v) { + return (new Vec2((double) (x - v.x), (double) (y - v.y))); } -/* V2_magn: magnitude of vector */ + /* V2_magn: magnitude of vector */ - float magn() - { - return(Math.sqrtf((float)(x*x+y*y))); + double magn() { + return (Math.sqrt((double) (x * x + y * y))); } - /* returns k X v (cross product). this is a vector perpendicular to v */ + /* returns k X v (cross product). this is a vector perpendicular to v */ - Vec2 cross() - { - return(new Vec2((float)y,(float)(-x))); + Vec2 cross() { + return (new Vec2((double) y, (double) (-x))); } } - - - diff --git a/Robust/src/Benchmarks/oooJava/voronoi/Vertex.java b/Robust/src/Benchmarks/oooJava/voronoi/Vertex.java index d65138a0..79bb20af 100644 --- a/Robust/src/Benchmarks/oooJava/voronoi/Vertex.java +++ b/Robust/src/Benchmarks/oooJava/voronoi/Vertex.java @@ -1,13 +1,8 @@ - -//import java.io.*; - /** - * A class that represents a voronoi diagram. The diagram is represnted - * as a binary tree of points. + * A class that represents a voronoi diagram. The diagram is represnted as a + * binary tree of points. **/ -class Vertex extends Vec2 -{ - +class Vertex extends Vec2 { /** * The left child of the tree that represents the voronoi diagram. **/ @@ -20,119 +15,158 @@ class Vertex extends Vec2 /** * Seed value used during tree creation. **/ - int seed; + static int seed; - public Vertex() { } + public Vertex() { + } - public Vertex(float x, float y) - { + public Vertex(double x, double y) { super(x, y); left = null; right = null; } - public void setLeft(Vertex l) - { + public void setLeft(Vertex l) { left = l; } - - public void setRight(Vertex r) - { + + public void setRight(Vertex r) { right = r; } - public Vertex getLeft() - { + public Vertex getLeft() { return left; } - - public Vertex getRight() - { + + public Vertex getRight() { return right; } /** * Generate a voronoi diagram **/ - Vertex createPoints(int n, MyDouble curmax, int i) - { - if (n < 1 ) { + static 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); + Vertex right = Vertex.createPoints(n / 2, curmax, i); + i -= n / 2; + cur.x = curmax.value * Math.exp(Math.log(Vertex.drand()) / i); + cur.y = drand(); + // cur.y = Vertex.drand(); + cur.norm = 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); - + curmax.value = cur.X(); + Vertex left = Vertex.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(); - } + Edge buildDelaunayTriangulation(Vertex extra, int depth) { + EdgePair retVal = buildDelaunay(extra, depth); + return retVal.getLeft(); + } - /** - * Recursive delaunay triangulation procedure - * Contains modifications for axis-switching division. - **/ - EdgePair buildDelaunay(Vertex extra, int depth, int threshold) - { - if(depth == threshold) { + 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().buildDelaunay(extra); + EdgePair delleft = getLeft().buildDelaunay(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; + } + + EdgePair buildDelaunay(Vertex extra, int depth) { + + EdgePair retval = null; + + if(depth==3){ return buildDelaunaySerial(extra); - } else - { - EdgePair retval = null; - if (getRight() != null && getLeft() != null) { + }else{ + depth++; + if (getRight() != null && getLeft() != null) { // more than three elements; do recursion - Vertex minx = getLow(); + Vertex minx = getLow(); Vertex maxx = extra; - - sese p1 { - EdgePair delright = getRight().buildDelaunay(extra,depth+1,threshold); + + sese p1{ + EdgePair delright = getRight().buildDelaunay(extra,depth); } - - EdgePair delleft = getLeft().buildDelaunay(this, depth+1,threshold); - + EdgePair delleft = getLeft().buildDelaunay(this,depth); + 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(); - } -// } - + retval = + e.doMerge(delleft.getLeft(), delleft.getRight(), delright.getLeft(), delright.getRight()); + Edge ldo = retval.getLeft(); - while (ldo.orig() != minx) { + 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 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 + // left, !right three points // 3 cases: triangles of 2 orientations, and 3 points on a line. */ Vertex s1 = getLeft(); Vertex s2 = this; @@ -146,48 +180,51 @@ class Vertex extends Vec2 retval = new EdgePair(c.symmetric(), c); } else { retval = new EdgePair(a, b.symmetric()); - if (s1.ccw(s2, s3)) + if (s1.ccw(s2, s3)) c.deleteEdge(); } } return retval; } + } - - EdgePair buildDelaunaySerial(Vertex extra) - { + + /** + * Recursive delaunay triangulation procedure Contains modifications for + * axis-switching division. + **/ + EdgePair buildDelaunay(Vertex extra) { EdgePair retval = null; - if (getRight() != null && getLeft() != null) { + if (getRight() != null && getLeft() != null) { // more than three elements; do recursion - Vertex minx = getLow(); + Vertex minx = getLow(); Vertex maxx = extra; - EdgePair delright = getRight().buildDelaunaySerial(extra); - - EdgePair delleft = getLeft().buildDelaunaySerial(this); + EdgePair delright = getRight().buildDelaunay(extra); + EdgePair delleft = getLeft().buildDelaunay(this); Edge e = new Edge(); - retval = e.doMerge(delleft.getLeft(), delleft.getRight(), - delright.getLeft(), delright.getRight()); + retval = + e.doMerge(delleft.getLeft(), delleft.getRight(), delright.getLeft(), delright.getRight()); Edge ldo = retval.getLeft(); - while (ldo.orig() != minx) { + 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 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 + // left, !right three points // 3 cases: triangles of 2 orientations, and 3 points on a line. */ Vertex s1 = getLeft(); Vertex s2 = this; @@ -201,7 +238,7 @@ class Vertex extends Vec2 retval = new EdgePair(c.symmetric(), c); } else { retval = new EdgePair(a, b.symmetric()); - if (s1.ccw(s2, s3)) + if (s1.ccw(s2, s3)) c.deleteEdge(); } } @@ -211,10 +248,9 @@ class Vertex extends Vec2 /** * Print the tree **/ - /*void print() - { + void print() { Vertex tleft, tright; - + System.out.println("X=" + X() + " Y=" + Y()); if (left == null) System.out.println("NULL"); @@ -222,109 +258,112 @@ class Vertex extends Vec2 left.print(); if (right == null) System.out.println("NULL"); - else + else right.print(); - }*/ + } /** * Traverse down the left child to the end **/ - Vertex getLow() - { + Vertex getLow() { Vertex temp; Vertex tree = this; - - while ((temp=tree.getLeft()) != null) + + while ((temp = tree.getLeft()) != null) tree = temp; return tree; - } - + } + /****************************************************************/ - /* Geometric primitives - ****************************************************************/ + /* + * Geometric primitives + * ************************************************************** + */ boolean incircle(Vertex b, Vertex c, Vertex d) - /* incircle, as in the Guibas-Stolfi paper. */ + /* 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; + 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(); + 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(); + 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(); + 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 ); + 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 */ { - float dret ; - float xa,ya,xb,yb,xc,yc; - Vertex loc_a,loc_b,loc_c; - - int donexa,doneya,donexb,doneyb,donexc,doneyc; + 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(); + xa = loc_a.X(); ya = loc_a.Y(); loc_b = b; - xb = loc_b.X(); + xb = loc_b.X(); yb = loc_b.Y(); loc_c = c; - xc = loc_c.X(); + 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); + dret = (xa - xc) * (yb - yc) - (xb - xc) * (ya - yc); + return ((dret > 0.0) ? true : false); } /** * A routine used by the random number generator **/ - int mult(int p,int q) - { + 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); + 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); + static int skiprand(int seed, int n) { + for (; n != 0; n--) + seed = random(seed); return seed; } - int random(int seed) - { + static 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; + static double drand() { + double retval = ((double) (Vertex.seed = Vertex.random(Vertex.seed))) / (double) 2147483647; return retval; } - -} - +} diff --git a/Robust/src/Benchmarks/oooJava/voronoi/makefile b/Robust/src/Benchmarks/oooJava/voronoi/makefile index c7d89b87c..7a003bc0 100644 --- a/Robust/src/Benchmarks/oooJava/voronoi/makefile +++ b/Robust/src/Benchmarks/oooJava/voronoi/makefile @@ -3,6 +3,6 @@ PROGRAM=TestRunner SOURCE_FILES=TestRunner.java NUM_OOO_WORKERS=24 -NUM_RCR_WORKERS=24 +NUM_RCR_WORKERS=27 include ../master-makefile diff --git a/Robust/src/Benchmarks/oooJava/voronoi/runr b/Robust/src/Benchmarks/oooJava/voronoi/runr new file mode 100755 index 00000000..a28ca050 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/runr @@ -0,0 +1 @@ +./TestRunnerr.bin 64000 \ No newline at end of file diff --git a/Robust/src/Benchmarks/oooJava/voronoi/runs b/Robust/src/Benchmarks/oooJava/voronoi/runs new file mode 100755 index 00000000..ab5b28a7 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/voronoi/runs @@ -0,0 +1 @@ +./TestRunners.bin 64000 \ No newline at end of file -- 2.34.1