Robust/src/Benchmarks/oooJava/voronoi/Vertex.java

   1 /**
   2  * A class that represents a voronoi diagram. The diagram is represnted as a
   3  * binary tree of points.
   4  **/
   5 class Vertex extends Vec2 {
   6   /**
   7    * The left child of the tree that represents the voronoi diagram.
   8    **/
   9   Vertex left;
  10   /**
  11    * The right child of the tree that represents the voronoi diagram.
  12    **/
  13   Vertex right;
  14
  15   /**
  16    * Seed value used during tree creation.
  17    **/
  18   static int seed;
  19
  20   public Vertex() {
  21   }
  22
  23   public Vertex(double x, double y) {
  24     super(x, y);
  25     left = null;
  26     right = null;
  27   }
  28
  29   public void setLeft(Vertex l) {
  30     left = l;
  31   }
  32
  33   public void setRight(Vertex r) {
  34     right = r;
  35   }
  36
  37   public Vertex getLeft() {
  38     return left;
  39   }
  40
  41   public Vertex getRight() {
  42     return right;
  43   }
  44
  45   /**
  46    * Generate a voronoi diagram
  47    **/
  48   static Vertex createPoints(int n, MyDouble curmax, int i) {
  49     if (n < 1) {
  50       return null;
  51     }
  52
  53     Vertex cur = new Vertex();
  54
  55     Vertex right = Vertex.createPoints(n / 2, curmax, i);
  56     i -= n / 2;
  57     cur.x = curmax.value * Math.exp(Math.log(Vertex.drand()) / i);
  58     cur.y = drand();
  59     // cur.y = Vertex.drand();
  60     cur.norm = cur.x * cur.x + cur.y * cur.y;
  61     cur.right = right;
  62     curmax.value = cur.X();
  63     Vertex left = Vertex.createPoints(n / 2, curmax, i - 1);
  64
  65     cur.left = left;
  66     return cur;
  67   }
  68
  69   /**
  70    * Builds delaunay triangulation.
  71    **/
  72   Edge buildDelaunayTriangulation(Vertex extra, int depth) {
  73     EdgePair retVal = buildDelaunay(extra, depth);
  74     return retVal.getLeft();
  75   }
  76
  77   EdgePair buildDelaunaySerial(Vertex extra) {
  78
  79     EdgePair retval = null;
  80     if (getRight() != null && getLeft() != null) {
  81       // more than three elements; do recursion
  82       Vertex minx = getLow();
  83       Vertex maxx = extra;
  84
  85       EdgePair delright = getRight().buildDelaunay(extra);
  86       EdgePair delleft = getLeft().buildDelaunay(this);
  87
  88       Edge e = new Edge();
  89       retval =
  90           e.doMerge(delleft.getLeft(), delleft.getRight(), delright.getLeft(), delright.getRight());
  91
  92       Edge ldo = retval.getLeft();
  93       while (ldo.orig() != minx) {
  94         ldo = ldo.rPrev();
  95       }
  96       Edge rdo = retval.getRight();
  97       while (rdo.orig() != maxx) {
  98         rdo = rdo.lPrev();
  99       }
 100
 101       retval = new EdgePair(ldo, rdo);
 102
 103     } else if (getLeft() == null) {
 104       // two points
 105       Edge a = makeEdge(this, extra);
 106       retval = new EdgePair(a, a.symmetric());
 107     } else {
 108       // left, !right three points
 109       // 3 cases: triangles of 2 orientations, and 3 points on a line. */
 110       Vertex s1 = getLeft();
 111       Vertex s2 = this;
 112       Vertex s3 = extra;
 113       Edge e = new Edge();
 114       Edge a = makeEdge(s1, s2);
 115       Edge b = makeEdge(s2, s3);
 116       a.symmetric().splice(b);
 117       Edge c = b.connectLeft(a);
 118       if (s1.ccw(s3, s2)) {
 119         retval = new EdgePair(c.symmetric(), c);
 120       } else {
 121         retval = new EdgePair(a, b.symmetric());
 122         if (s1.ccw(s2, s3))
 123           c.deleteEdge();
 124       }
 125     }
 126     return retval;
 127   }
 128
 129   EdgePair buildDelaunay(Vertex extra, int depth) {
 130
 131     EdgePair retval = null;
 132
 133     if(depth==5){
 134       return buildDelaunaySerial(extra);
 135     }else{
 136       depth++;
 137       if (getRight() != null && getLeft() != null) {
 138         // more than three elements; do recursion
 139         Vertex minx = getLow();
 140         Vertex maxx = extra;
 141
 142         sese p1{
 143           EdgePair delright = getRight().buildDelaunay(extra,depth);
 144         }
 145         EdgePair delleft = getLeft().buildDelaunay(this,depth);
 146
 147         Edge e = new Edge();
 148         retval =
 149             e.doMerge(delleft.getLeft(), delleft.getRight(), delright.getLeft(), delright.getRight());
 150
 151         Edge ldo = retval.getLeft();
 152         while (ldo.orig() != minx) {
 153           ldo = ldo.rPrev();
 154         }
 155         Edge rdo = retval.getRight();
 156         while (rdo.orig() != maxx) {
 157           rdo = rdo.lPrev();
 158         }
 159
 160         retval = new EdgePair(ldo, rdo);
 161
 162       } else if (getLeft() == null) {
 163         // two points
 164         Edge a = makeEdge(this, extra);
 165         retval = new EdgePair(a, a.symmetric());
 166       } else {
 167         // left, !right three points
 168         // 3 cases: triangles of 2 orientations, and 3 points on a line. */
 169         Vertex s1 = getLeft();
 170         Vertex s2 = this;
 171         Vertex s3 = extra;
 172         Edge a = makeEdge(s1, s2);
 173         Edge b = makeEdge(s2, s3);
 174         a.symmetric().splice(b);
 175         Edge c = b.connectLeft(a);
 176         if (s1.ccw(s3, s2)) {
 177           retval = new EdgePair(c.symmetric(), c);
 178         } else {
 179           retval = new EdgePair(a, b.symmetric());
 180           if (s1.ccw(s2, s3))
 181             c.deleteEdge();
 182         }
 183       }
 184       return retval;
 185     }
 186
 187   }
 188
 189   /**
 190    * Recursive delaunay triangulation procedure Contains modifications for
 191    * axis-switching division.
 192    **/
 193   EdgePair buildDelaunay(Vertex extra) {
 194     EdgePair retval = null;
 195     if (getRight() != null && getLeft() != null) {
 196       // more than three elements; do recursion
 197       Vertex minx = getLow();
 198       Vertex maxx = extra;
 199
 200       EdgePair delright = getRight().buildDelaunay(extra);
 201       EdgePair delleft = getLeft().buildDelaunay(this);
 202
 203       Edge e = new Edge();
 204       retval =
 205           e.doMerge(delleft.getLeft(), delleft.getRight(), delright.getLeft(), delright.getRight());
 206
 207       Edge ldo = retval.getLeft();
 208       while (ldo.orig() != minx) {
 209         ldo = ldo.rPrev();
 210       }
 211       Edge rdo = retval.getRight();
 212       while (rdo.orig() != maxx) {
 213         rdo = rdo.lPrev();
 214       }
 215
 216       retval = new EdgePair(ldo, rdo);
 217
 218     } else if (getLeft() == null) {
 219       // two points
 220       Edge a = makeEdge(this, extra);
 221       retval = new EdgePair(a, a.symmetric());
 222     } else {
 223       // left, !right three points
 224       // 3 cases: triangles of 2 orientations, and 3 points on a line. */
 225       Vertex s1 = getLeft();
 226       Vertex s2 = this;
 227       Vertex s3 = extra;
 228       Edge a = makeEdge(s1, s2);
 229       Edge b = makeEdge(s2, s3);
 230       a.symmetric().splice(b);
 231       Edge c = b.connectLeft(a);
 232       if (s1.ccw(s3, s2)) {
 233         retval = new EdgePair(c.symmetric(), c);
 234       } else {
 235         retval = new EdgePair(a, b.symmetric());
 236         if (s1.ccw(s2, s3))
 237           c.deleteEdge();
 238       }
 239     }
 240     return retval;
 241   }
 242
 243   /**
 244    * Print the tree
 245    **/
 246   void print() {
 247     Vertex tleft, tright;
 248
 249     System.out.println("X=" + X() + " Y=" + Y());
 250     if (left == null)
 251       System.out.println("NULL");
 252     else
 253       left.print();
 254     if (right == null)
 255       System.out.println("NULL");
 256     else
 257       right.print();
 258   }
 259
 260   /**
 261    * Traverse down the left child to the end
 262    **/
 263   Vertex getLow() {
 264     Vertex temp;
 265     Vertex tree = this;
 266
 267     while ((temp = tree.getLeft()) != null)
 268       tree = temp;
 269     return tree;
 270   }
 271
 272   /****************************************************************/
 273   /*
 274    * Geometric primitives
 275    * **************************************************************
 276    */
 277   boolean incircle(Vertex b, Vertex c, Vertex d)
 278   /* incircle, as in the Guibas-Stolfi paper. */
 279   {
 280     double adx, ady, bdx, bdy, cdx, cdy, dx, dy, anorm, bnorm, cnorm, dnorm;
 281     double dret;
 282     Vertex loc_a, loc_b, loc_c, loc_d;
 283
 284     int donedx, donedy, donednorm;
 285     loc_d = d;
 286     dx = loc_d.X();
 287     dy = loc_d.Y();
 288     dnorm = loc_d.Norm();
 289     loc_a = this;
 290     adx = loc_a.X() - dx;
 291     ady = loc_a.Y() - dy;
 292     anorm = loc_a.Norm();
 293     loc_b = b;
 294     bdx = loc_b.X() - dx;
 295     bdy = loc_b.Y() - dy;
 296     bnorm = loc_b.Norm();
 297     loc_c = c;
 298     cdx = loc_c.X() - dx;
 299     cdy = loc_c.Y() - dy;
 300     cnorm = loc_c.Norm();
 301     dret = (anorm - dnorm) * (bdx * cdy - bdy * cdx);
 302     dret += (bnorm - dnorm) * (cdx * ady - cdy * adx);
 303     dret += (cnorm - dnorm) * (adx * bdy - ady * bdx);
 304     return ((0.0 < dret) ? true : false);
 305   }
 306
 307   boolean ccw(Vertex b, Vertex c)
 308   /* TRUE iff this, B, C form a counterclockwise oriented triangle */
 309   {
 310     double dret;
 311     double xa, ya, xb, yb, xc, yc;
 312     Vertex loc_a, loc_b, loc_c;
 313
 314     int donexa, doneya, donexb, doneyb, donexc, doneyc;
 315
 316     loc_a = this;
 317     xa = loc_a.X();
 318     ya = loc_a.Y();
 319     loc_b = b;
 320     xb = loc_b.X();
 321     yb = loc_b.Y();
 322     loc_c = c;
 323     xc = loc_c.X();
 324     yc = loc_c.Y();
 325     dret = (xa - xc) * (yb - yc) - (xb - xc) * (ya - yc);
 326     return ((dret > 0.0) ? true : false);
 327   }
 328
 329   /**
 330    * A routine used by the random number generator
 331    **/
 332   static int mult(int p, int q) {
 333     int p1, p0, q1, q0;
 334     int CONST_m1 = 10000;
 335
 336     p1 = p / CONST_m1;
 337     p0 = p % CONST_m1;
 338     q1 = q / CONST_m1;
 339     q0 = q % CONST_m1;
 340     return (((p0 * q1 + p1 * q0) % CONST_m1) * CONST_m1 + p0 * q0);
 341   }
 342
 343   /**
 344    * Generate the nth random number
 345    **/
 346   static int skiprand(int seed, int n) {
 347     for (; n != 0; n--)
 348       seed = random(seed);
 349     return seed;
 350   }
 351
 352   static int random(int seed) {
 353     int CONST_b = 31415821;
 354
 355     seed = mult(seed, CONST_b) + 1;
 356     return seed;
 357   }
 358
 359   static double drand() {
 360     double retval = ((double) (Vertex.seed = Vertex.random(Vertex.seed))) / (double) 2147483647;
 361     return retval;
 362   }
 363
 364   public Edge makeEdge(Vertex o, Vertex d) {
 365     Edge ql[] = new Edge[4];
 366     ql[0] = new Edge(ql, 0);
 367     ql[1] = new Edge(ql, 1);
 368     ql[2] = new Edge(ql, 2);
 369     ql[3] = new Edge(ql, 3);
 370
 371     ql[0].next = ql[0];
 372     ql[1].next = ql[3];
 373     ql[2].next = ql[2];
 374     ql[3].next = ql[1];
 375
 376     Edge base = ql[0];
 377     base.setOrig(o);
 378     base.setDest(d);
 379     return base;
 380   }
 381
 382 }