Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Edge.java

   1
   2 /**
   3  * A class that represents the quad edge data structure which implements
   4  * the edge algebra as described in the algorithm.
   5  * <p>
   6  * Each edge contains 4 parts, or other edges.  Any edge in the group may
   7  * be accessed using a series of rotate and flip operations.  The 0th
   8  * edge is the canonical representative of the group.
   9  * <p>
  10  * The quad edge class does not contain separate information for vertice
  11  * or faces; a vertex is implicitly defined as a ring of edges (the ring
  12  * is created using the next field).
  13  **/
  14 class Edge
  15 {
  16   /**
  17    * Group of edges that describe the quad edge
  18    **/
  19   Edge quadList[];
  20   /**
  21    * The position of this edge within the quad list
  22    **/
  23   int     listPos;
  24   /**
  25    * The vertex that this edge represents
  26    **/
  27   Vertex  vertex;
  28   /**
  29    * Contains a reference to a connected quad edge
  30    **/
  31   Edge    next;
  32
  33   public Edge(){
  34   }
  35
  36   /**
  37    * Create a new edge which.
  38    **/
  39   public Edge(Vertex v, Edge ql[], int pos)
  40   {
  41     vertex = v;
  42     quadList = ql;
  43     listPos = pos;
  44   }
  45
  46   /**
  47    * Create a new edge which.
  48    **/
  49   public Edge(Edge ql[], int pos)
  50   {
  51     this(null, ql, pos);
  52   }
  53
  54   /**
  55    * Create a string representation of the edge
  56    **/
  57   /*public String toString()
  58   {
  59     if (vertex != null)
  60       return vertex.toString();
  61     else
  62       return "None";
  63   }*/
  64
  65   public Edge makeEdge(Vertex o, Vertex d)
  66   {
  67     Edge ql[] = new Edge[4];
  68     ql[0] = new Edge(ql, 0);
  69     ql[1] = new Edge(ql, 1);
  70     ql[2] = new Edge(ql, 2);
  71     ql[3] = new Edge(ql, 3);
  72
  73     ql[0].next = ql[0];
  74     ql[1].next = ql[3];
  75     ql[2].next = ql[2];
  76     ql[3].next = ql[1];
  77
  78     Edge base = ql[0];
  79     base.setOrig(o);
  80     base.setDest(d);
  81     return base;
  82   }
  83
  84   public void setNext(Edge n)
  85   {
  86     next = n;
  87   }
  88
  89   /**
  90    * Initialize the data (vertex) for the edge's origin
  91    **/
  92   public void setOrig(Vertex o)
  93   {
  94     vertex = o;
  95   }
  96
  97   /**
  98    * Initialize the data (vertex) for the edge's destination
  99    **/
 100   public void setDest(Vertex d)
 101   {
 102     symmetric().setOrig(d);
 103   }
 104
 105   Edge oNext()
 106   {
 107     return next;
 108   }
 109
 110   Edge oPrev()
 111   {
 112     return this.rotate().oNext().rotate();
 113   }
 114
 115   Edge lNext()
 116   {
 117     return this.rotateInv().oNext().rotate();
 118   }
 119
 120   Edge lPrev()
 121   {
 122     return this.oNext().symmetric();
 123   }
 124
 125   Edge rNext()
 126   {
 127     return this.rotate().oNext().rotateInv();
 128   }
 129
 130   Edge rPrev()
 131   {
 132     return this.symmetric().oNext();
 133   }
 134
 135   Edge dNext()
 136   {
 137     return this.symmetric().oNext().symmetric();
 138   }
 139
 140   Edge dPrev()
 141   {
 142     return this.rotateInv().oNext().rotateInv();
 143   }
 144
 145   Vertex orig()
 146   {
 147     return vertex;
 148   }
 149
 150   Vertex dest()
 151   {
 152     return symmetric().orig();
 153   }
 154
 155   /**
 156    * Return the symmetric of the edge.  The symmetric is the same edge
 157    * with the opposite direction.
 158    * @return the symmetric of the edge
 159    **/
 160   Edge symmetric()
 161   {
 162     return quadList[(listPos+2)%4];
 163   }
 164
 165   /**
 166    * Return the rotated version of the edge.  The rotated version is a
 167    * 90 degree counterclockwise turn.
 168    * @return the rotated version of the edge
 169    **/
 170   Edge rotate()
 171   {
 172     return quadList[(listPos+1)%4];
 173   }
 174
 175   /**
 176    * Return the inverse rotated version of the edge.  The inverse
 177    * is a 90 degree clockwise turn.
 178    * @return the inverse rotated edge.
 179    **/
 180   Edge rotateInv()
 181   {
 182     return quadList[(listPos+3)%4];
 183   }
 184
 185   Edge nextQuadEdge()
 186   {
 187     return quadList[(listPos+1)%4];
 188   }
 189
 190   Edge connectLeft(Edge b)
 191   {
 192     Vertex t1,t2;
 193     Edge ans, lnexta;
 194
 195     t1 = dest();
 196     lnexta = lNext();
 197     t2 = b.orig();
 198     Edge e = new Edge();
 199     ans = e.makeEdge(t1, t2);
 200     ans.splice(lnexta);
 201     ans.symmetric().splice(b);
 202     return ans;
 203   }
 204
 205   Edge connectRight(Edge b)
 206   {
 207     Vertex t1,t2;
 208     Edge ans, oprevb,q1;
 209
 210     t1 = dest();
 211     t2 = b.orig();
 212     oprevb = b.oPrev();
 213
 214     Edge e = new Edge();
 215     ans = e.makeEdge(t1, t2);
 216     ans.splice(symmetric());
 217     ans.symmetric().splice(oprevb);
 218     return ans;
 219   }
 220
 221   /****************************************************************/
 222   /*    Quad-edge manipulation primitives
 223    ****************************************************************/
 224   void swapedge()
 225   {
 226     Edge a = oPrev();
 227     Edge syme = symmetric();
 228     Edge b = syme.oPrev();
 229     splice(a);
 230     syme.splice(b);
 231     Edge lnexttmp = a.lNext();
 232     splice(lnexttmp);
 233     lnexttmp = b.lNext();
 234     syme.splice(lnexttmp);
 235     Vertex a1 = a.dest();
 236     Vertex b1 = b.dest();
 237     setOrig(a1);
 238     setDest(b1);
 239   }
 240
 241   void splice(Edge b)
 242   {
 243     Edge alpha = oNext().rotate();
 244     Edge beta = b.oNext().rotate();
 245     Edge t1 = beta.oNext();
 246     Edge temp = alpha.oNext();
 247     alpha.setNext(t1);
 248     beta.setNext(temp);
 249     temp = oNext();
 250     t1 = b.oNext();
 251     b.setNext(temp);
 252     setNext(t1);
 253   }
 254
 255   boolean valid(Edge basel)
 256   {
 257     Vertex t1 = basel.orig();
 258     Vertex t3 = basel.dest();
 259     Vertex t2 = dest();
 260     return t1.ccw(t2, t3);
 261   }
 262
 263   void deleteEdge()
 264   {
 265     Edge f = oPrev();
 266     splice(f);
 267     f = symmetric().oPrev();
 268     symmetric().splice(f);
 269   }
 270
 271   EdgePair doMerge(Edge ldo, Edge ldi, Edge rdi, Edge rdo)
 272   {
 273     boolean torun = true;
 274     while (torun) {
 275       Vertex t3 = rdi.orig();
 276       Vertex t1 = ldi.orig();
 277       Vertex t2 = ldi.dest();
 278
 279       while (t1.ccw(t2, t3)) {
 280         ldi = ldi.lNext();
 281
 282         t1=ldi.orig();
 283         t2=ldi.dest();
 284       }
 285
 286       t2=rdi.dest();
 287
 288       if (t2.ccw(t3, t1)) {
 289         rdi = rdi.rPrev();
 290       } else {
 291         torun = false;
 292         // break;
 293       }
 294     }
 295
 296     Edge basel = rdi.symmetric().connectLeft(ldi);
 297
 298     Edge lcand = basel.rPrev();
 299     Edge rcand = basel.oPrev();
 300     Vertex t1 = basel.orig();
 301     Vertex t2 = basel.dest();
 302
 303     if (t1 == rdo.orig())
 304       rdo = basel;
 305     if (t2 == ldo.orig())
 306       ldo = basel.symmetric();
 307
 308     while (true) {
 309       Edge t = lcand.oNext();
 310       if (t.valid(basel)) {
 311         Vertex v4 = basel.orig();
 312
 313         Vertex v1 = lcand.dest();
 314         Vertex v3 = lcand.orig();
 315         Vertex v2 = t.dest();
 316         while (v1.incircle(v2,v3,v4)){
 317           lcand.deleteEdge();
 318           lcand = t;
 319
 320           t = lcand.oNext();
 321           v1 = lcand.dest();
 322           v3 = lcand.orig();
 323           v2 = t.dest();
 324         }
 325       }
 326
 327       t = rcand.oPrev();
 328       if (t.valid(basel)) {
 329         Vertex v4 = basel.dest();
 330         Vertex v1 = t.dest();
 331         Vertex v2 = rcand.dest();
 332         Vertex v3 = rcand.orig();
 333         while (v1.incircle(v2,v3,v4)) {
 334           rcand.deleteEdge();
 335           rcand = t;
 336           t = rcand.oPrev();
 337           v2 = rcand.dest();
 338           v3 = rcand.orig();
 339           v1 = t.dest();
 340         }
 341       }
 342
 343       boolean lvalid = lcand.valid(basel);
 344
 345       boolean rvalid = rcand.valid(basel);
 346       if ((!lvalid) && (!rvalid)) {
 347         return new EdgePair(ldo, rdo);
 348       }
 349
 350       Vertex v1 = lcand.dest();
 351       Vertex v2 = lcand.orig();
 352       Vertex v3 = rcand.orig();
 353       Vertex v4 = rcand.dest();
 354       if (!lvalid || (rvalid && v1.incircle(v2,v3,v4))) {
 355         basel = rcand.connectLeft(basel.symmetric());
 356         rcand = basel.symmetric().lNext();
 357       } else {
 358         basel = lcand.connectRight(basel).symmetric();
 359         lcand = basel.rPrev();
 360       }
 361     }
 362   }
 363 }
 364