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

   1 /*import java.io.*;
   2 import java.util.Stack;
   3 import java.util.Hashtable;*/
   4
   5 /**
   6  * A class that represents the quad edge data structure which implements
   7  * the edge algebra as described in the algorithm.
   8  * <p>
   9  * Each edge contains 4 parts, or other edges.  Any edge in the group may
  10  * be accessed using a series of rotate and flip operations.  The 0th
  11  * edge is the canonical representative of the group.
  12  * <p>
  13  * The quad edge class does not contain separate information for vertice
  14  * or faces; a vertex is implicitly defined as a ring of edges (the ring
  15  * is created using the next field).
  16  **/
  17 class Edge
  18 {
  19   /**
  20    * Group of edges that describe the quad edge
  21    **/
  22   Edge quadList[];
  23   /**
  24    * The position of this edge within the quad list
  25    **/
  26   int     listPos;
  27   /**
  28    * The vertex that this edge represents
  29    **/
  30   Vertex  vertex;
  31   /**
  32    * Contains a reference to a connected quad edge
  33    **/
  34   Edge    next;
  35
  36   public Edge(){
  37   }
  38
  39   /**
  40    * Create a new edge which.
  41    **/
  42   public Edge(Vertex v, Edge ql[], int pos)
  43   {
  44     vertex = v;
  45     quadList = ql;
  46     listPos = pos;
  47   }
  48
  49   /**
  50    * Create a new edge which.
  51    **/
  52   public Edge(Edge ql[], int pos)
  53   {
  54     this(null, ql, pos);
  55   }
  56
  57   /**
  58    * Create a string representation of the edge
  59    **/
  60   /*public String toString()
  61   {
  62     if (vertex != null)
  63       return vertex.toString();
  64     else
  65       return "None";
  66   }*/
  67
  68   public Edge makeEdge(Vertex o, Vertex d)
  69   {
  70     Edge ql[] = new Edge[4];
  71     ql[0] = new Edge(ql, 0);
  72     ql[1] = new Edge(ql, 1);
  73     ql[2] = new Edge(ql, 2);
  74     ql[3] = new Edge(ql, 3);
  75
  76     ql[0].next = ql[0];
  77     ql[1].next = ql[3];
  78     ql[2].next = ql[2];
  79     ql[3].next = ql[1];
  80
  81     Edge base = ql[0];
  82     base.setOrig(o);
  83     base.setDest(d);
  84     return base;
  85   }
  86
  87   public void setNext(Edge n)
  88   {
  89     next = n;
  90   }
  91
  92   /**
  93    * Initialize the data (vertex) for the edge's origin
  94    **/
  95   public void setOrig(Vertex o)
  96   {
  97     vertex = o;
  98   }
  99
 100   /**
 101    * Initialize the data (vertex) for the edge's destination
 102    **/
 103   public void setDest(Vertex d)
 104   {
 105     symmetric().setOrig(d);
 106   }
 107
 108   Edge oNext()
 109   {
 110     return next;
 111   }
 112
 113   Edge oPrev()
 114   {
 115     return this.rotate().oNext().rotate();
 116   }
 117
 118   Edge lNext()
 119   {
 120     return this.rotateInv().oNext().rotate();
 121   }
 122
 123   Edge lPrev()
 124   {
 125     return this.oNext().symmetric();
 126   }
 127
 128   Edge rNext()
 129   {
 130     return this.rotate().oNext().rotateInv();
 131   }
 132
 133   Edge rPrev()
 134   {
 135     return this.symmetric().oNext();
 136   }
 137
 138   Edge dNext()
 139   {
 140     return this.symmetric().oNext().symmetric();
 141   }
 142
 143   Edge dPrev()
 144   {
 145      return this.rotateInv().oNext().rotateInv();
 146   }
 147
 148   Vertex orig()
 149   {
 150     return vertex;
 151   }
 152
 153   Vertex dest()
 154   {
 155     return symmetric().orig();
 156   }
 157
 158   /**
 159    * Return the symmetric of the edge.  The symmetric is the same edge
 160    * with the opposite direction.
 161    * @return the symmetric of the edge
 162    **/
 163   Edge symmetric()
 164   {
 165     return quadList[(listPos+2)%4];
 166   }
 167
 168   /**
 169    * Return the rotated version of the edge.  The rotated version is a
 170    * 90 degree counterclockwise turn.
 171    * @return the rotated version of the edge
 172    **/
 173   Edge rotate()
 174   {
 175     return quadList[(listPos+1)%4];
 176   }
 177
 178   /**
 179    * Return the inverse rotated version of the edge.  The inverse
 180    * is a 90 degree clockwise turn.
 181    * @return the inverse rotated edge.
 182    **/
 183   Edge rotateInv()
 184   {
 185     return quadList[(listPos+3)%4];
 186   }
 187
 188   Edge nextQuadEdge()
 189   {
 190     return quadList[(listPos+1)%4];
 191   }
 192
 193   Edge connectLeft(Edge b)
 194   {
 195      Vertex t1,t2;
 196      Edge ans, lnexta;
 197
 198      t1 = dest();
 199      lnexta = lNext();
 200      t2 = b.orig();
 201      Edge e = new Edge();
 202      ans = e.makeEdge(t1, t2);
 203      ans.splice(lnexta);
 204      ans.symmetric().splice(b);
 205      return ans;
 206   }
 207
 208   Edge connectRight(Edge b)
 209   {
 210      Vertex t1,t2;
 211      Edge ans, oprevb,q1;
 212
 213      t1 = dest();
 214      t2 = b.orig();
 215      oprevb = b.oPrev();
 216
 217      Edge e = new Edge();
 218      ans = e.makeEdge(t1, t2);
 219      ans.splice(symmetric());
 220      ans.symmetric().splice(oprevb);
 221      return ans;
 222   }
 223
 224   /****************************************************************/
 225   /*    Quad-edge manipulation primitives
 226   ****************************************************************/
 227   void swapedge()
 228   {
 229     Edge a = oPrev();
 230     Edge syme = symmetric();
 231     Edge b = syme.oPrev();
 232     splice(a);
 233     syme.splice(b);
 234     Edge lnexttmp = a.lNext();
 235     splice(lnexttmp);
 236     lnexttmp = b.lNext();
 237     syme.splice(lnexttmp);
 238     Vertex a1 = a.dest();
 239     Vertex b1 = b.dest();
 240     setOrig(a1);
 241     setDest(b1);
 242   }
 243
 244   void splice(Edge b)
 245   {
 246     Edge alpha = oNext().rotate();
 247     Edge beta = b.oNext().rotate();
 248     Edge t1 = beta.oNext();
 249     Edge temp = alpha.oNext();
 250     alpha.setNext(t1);
 251     beta.setNext(temp);
 252     temp = oNext();
 253     t1 = b.oNext();
 254     b.setNext(temp);
 255     setNext(t1);
 256   }
 257
 258   boolean valid(Edge basel)
 259   {
 260     Vertex t1 = basel.orig();
 261     Vertex t3 = basel.dest();
 262     Vertex t2 = dest();
 263     return t1.ccw(t2, t3);
 264   }
 265
 266   void deleteEdge()
 267   {
 268     Edge f = oPrev();
 269     splice(f);
 270     f = symmetric().oPrev();
 271     symmetric().splice(f);
 272   }
 273
 274   EdgePair doMerge(Edge ldo, Edge ldi, Edge rdi, Edge rdo)
 275   {
 276     boolean torun = true;
 277     while (torun) {
 278       Vertex t3 = rdi.orig();
 279       Vertex t1 = ldi.orig();
 280       Vertex t2 = ldi.dest();
 281
 282       while (t1.ccw(t2, t3)) {
 283         ldi = ldi.lNext();
 284
 285         t1=ldi.orig();
 286         t2=ldi.dest();
 287       }
 288
 289       t2=rdi.dest();
 290
 291       if (t2.ccw(t3, t1)) {
 292         rdi = rdi.rPrev();
 293       } else {
 294         torun = false;
 295         // break;
 296       }
 297     }
 298
 299     Edge basel = rdi.symmetric().connectLeft(ldi);
 300
 301     Edge lcand = basel.rPrev();
 302     Edge rcand = basel.oPrev();
 303     Vertex t1 = basel.orig();
 304     Vertex t2 = basel.dest();
 305
 306     if (t1 == rdo.orig())
 307       rdo = basel;
 308     if (t2 == ldo.orig())
 309       ldo = basel.symmetric();
 310
 311     while (true) {
 312       Edge t = lcand.oNext();
 313       if (t.valid(basel)) {
 314         Vertex v4 = basel.orig();
 315
 316         Vertex v1 = lcand.dest();
 317         Vertex v3 = lcand.orig();
 318         Vertex v2 = t.dest();
 319         while (v1.incircle(v2,v3,v4)){
 320           lcand.deleteEdge();
 321           lcand = t;
 322
 323           t = lcand.oNext();
 324           v1 = lcand.dest();
 325           v3 = lcand.orig();
 326           v2 = t.dest();
 327         }
 328       }
 329
 330       t = rcand.oPrev();
 331       if (t.valid(basel)) {
 332         Vertex v4 = basel.dest();
 333         Vertex v1 = t.dest();
 334         Vertex v2 = rcand.dest();
 335         Vertex v3 = rcand.orig();
 336         while (v1.incircle(v2,v3,v4)) {
 337           rcand.deleteEdge();
 338           rcand = t;
 339           t = rcand.oPrev();
 340           v2 = rcand.dest();
 341           v3 = rcand.orig();
 342           v1 = t.dest();
 343         }
 344       }
 345
 346       boolean lvalid = lcand.valid(basel);
 347
 348       boolean rvalid = rcand.valid(basel);
 349       if ((!lvalid) && (!rvalid)) {
 350         return new EdgePair(ldo, rdo);
 351       }
 352
 353       Vertex v1 = lcand.dest();
 354       Vertex v2 = lcand.orig();
 355       Vertex v3 = rcand.orig();
 356       Vertex v4 = rcand.dest();
 357       if (!lvalid || (rvalid && v1.incircle(v2,v3,v4))) {
 358         basel = rcand.connectLeft(basel.symmetric());
 359         rcand = basel.symmetric().lNext();
 360       } else {
 361         basel = lcand.connectRight(basel).symmetric();
 362         lcand = basel.rPrev();
 363       }
 364     }
 365   }
 366
 367
 368   /**
 369    * Print the voronoi diagram and its dual, the delaunay triangle for the
 370    * diagram.
 371    **/
 372   void outputVoronoiDiagram()
 373   {
 374     Edge nex = this;
 375     //  Plot voronoi diagram edges with one endpoint at infinity.
 376     do {
 377       Vec2 v21 = (Vec2)nex.dest();
 378       Vec2 v22 = (Vec2)nex.orig();
 379       Edge tmp = nex.oNext();
 380       Vec2 v23 = (Vec2)tmp.dest();
 381       Vec2 cvxvec = v21.sub(v22);
 382       Vec2 center = v22.circle_center(v21, v23);
 383
 384       Vec2 vv1 = v22.sum(v22);
 385       Vec2 vv2 = vv1.times((float) 0.5);
 386       Vec2 vv3 = center.sub(vv2);
 387       double ln = 1.0 + vv3.magn();
 388       double d1 = ln/cvxvec.magn();
 389       vv1 = cvxvec.cross();
 390       vv2 = vv1.times((float) d1) ;
 391       vv3 = center.sum(vv2);
 392       System.out.println("Vedge " + center.toString() + " " + vv3.toString());
 393       nex = nex.rNext();
 394     } while (nex != this);
 395
 396     // plot delaunay triangle edges and finite VD edges.
 397     LinkedList edges = new LinkedList();
 398     Hashtable seen = new Hashtable();
 399     pushRing(edges, seen);
 400     System.out.println("no. of edges = " + edges.size());
 401     while (edges.size()!=0) {
 402       Edge edge = (Edge)edges.pop();
 403       Integer b = (Integer)seen.get(edge);
 404       if (b != null && b.intValue()==1) {
 405         Edge prev = edge;
 406         nex = edge.oNext();
 407         do {
 408           Vertex v1 = prev.orig();
 409           double d1 = v1.X();
 410           Vertex v2 = prev.dest();
 411           double d2 = v2.X();
 412           if (d1 >= d2) {
 413             System.out.println("Dedge " + v1 + " " + v2);
 414             Edge sprev = prev.symmetric();
 415             Edge snex = sprev.oNext();
 416             v1 = prev.orig();
 417             v2 = prev.dest();
 418             Vertex v3 = nex.dest();
 419             Vertex v4 = snex.dest();
 420             if (v1.ccw(v2, v3) != v1.ccw(v2, v4)) {
 421               Vec2 v21 = prev.orig();
 422               Vec2 v22 = prev.dest();
 423               Vec2 v23 = nex.dest();
 424               Vec2 vv1 = v21.circle_center(v22, v23);
 425               v21 = sprev.orig();
 426               v22 = sprev.dest();
 427               v23 = snex.dest();
 428               Vec2 vv2 = v21.circle_center(v22, v23);
 429               System.out.println("Vedge " + vv1.toString() + " " + vv2.toString());
 430             }
 431           }
 432           seen.put(prev, new Integer(0));
 433           prev = nex;
 434           nex = nex.oNext();
 435         } while (prev != edge);
 436       }
 437       edge.symmetric().pushRing(edges, seen);
 438     }
 439   }
 440
 441
 442   void pushRing(LinkedList stack, Hashtable seen)
 443   {
 444     Edge nex = oNext();
 445     while (nex != this) {
 446       if (!seen.containsKey(nex)) {
 447         seen.put(nex, new Integer(1));
 448         stack.push(nex);
 449       }
 450       nex = nex.oNext();
 451     }
 452   }
 453
 454   void pushNonezeroRing(LinkedList stack, Hashtable seen)
 455   {
 456     Edge nex = oNext();
 457     while (nex != this) {
 458       if (seen.containsKey(nex)) {
 459         seen.remove(nex);
 460         stack.push(nex);
 461       }
 462       nex = nex.oNext();
 463     }
 464   }
 465
 466 }
 467