src/org/ibex/graphics/Polygon.java

   1 package org.ibex.graphics;\r
   2 import java.util.*;\r
   3 import org.ibex.util.*;\r
   4 \r
   5 //\r
   6 // This is a very heavily modified (nearly complete rewrite) version\r
   7 // of GPCJ, which is itself a Java port of the Generalized Polygon\r
   8 // Clipping Library\r
   9 // \r
  10 //   http://www.cs.man.ac.uk/aig/staff/alan/software/gpc.html\r
  11 //\r
  12 // Modifications by Adam Megacz\r
  13 //\r
  14 \r
  15 // Possible remaining optimizations:\r
  16 //   -- recycle EdgeNode instances\r
  17 //   -- evolve PolygonNode into the Polygon class?\r
  18 \r
  19 //\r
  20 // !! WARNING !!  !! WARNING !!  !! WARNING !!\r
  21 //\r
  22 // Unlike GPCJ, this code is NOT reentrant or thread-safe; static\r
  23 // arrays are used to avoid allocation penalties.  Also, the union(),\r
  24 // intersection(), and xor() methods destructively update the 'this'\r
  25 // object.\r
  26 //\r
  27 \r
  28 /*\r
  29  * The SEI Software Open Source License, Version 1.0\r
  30  *\r
  31  * Copyright (c) 2004, Solution Engineering, Inc.\r
  32  * All rights reserved.\r
  33  *\r
  34  * Redistribution and use in source and binary forms, with or without\r
  35  * modification, are permitted provided that the following conditions\r
  36  * are met:\r
  37  *\r
  38  * 1. Redistributions of source code must retain the above copyright\r
  39  *    notice, this list of conditions and the following disclaimer. \r
  40  *\r
  41  * 2. The end-user documentation included with the redistribution,\r
  42  *    if any, must include the following acknowledgment:\r
  43  *       "This product includes software developed by the\r
  44  *        Solution Engineering, Inc. (http://www.seisw.com/)."\r
  45  *    Alternately, this acknowledgment may appear in the software itself,\r
  46  *    if and wherever such third-party acknowledgments normally appear.\r
  47  *\r
  48  * 3. The name "Solution Engineering" must not be used to endorse or\r
  49  *    promote products derived from this software without prior\r
  50  *    written permission. For written permission, please contact\r
  51  *    admin@seisw.com.\r
  52  *\r
  53  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED\r
  54  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
  55  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE\r
  56  * DISCLAIMED.  IN NO EVENT SHALL SOLUTION ENGINEERING, INC. OR\r
  57  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\r
  58  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\r
  59  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF\r
  60  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND\r
  61  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,\r
  62  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT\r
  63  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF\r
  64  * SUCH DAMAGE.\r
  65  * ====================================================================\r
  66  */\r
  67 \r
  68 \r
  69 public final class Polygon {\r
  70 \r
  71     private static final int DEFAULT_PATHLEN  =  10;\r
  72     private static final int DEFAULT_CONTOURS =   4;\r
  73 \r
  74     private static final int BIGNUM = 65535;\r
  75 \r
  76     public boolean[] hole             = new boolean[DEFAULT_CONTOURS];\r
  77     public boolean[] contributing     = new boolean[DEFAULT_CONTOURS];\r
  78     public float[]   x                = new float[DEFAULT_PATHLEN];\r
  79     public float[]   y                = new float[DEFAULT_PATHLEN];\r
  80     public int       numvertices      = 0;\r
  81     public int[]     edges            = null;\r
  82     public int       numedges         = 0;\r
  83     public int[]     contours         = new int[DEFAULT_CONTOURS];\r
  84     public int       numcontours      = 0;\r
  85     public float[]   minx_            = new float[DEFAULT_CONTOURS];\r
  86     public float[]   miny_            = new float[DEFAULT_CONTOURS];\r
  87     public float[]   maxx_            = new float[DEFAULT_CONTOURS];\r
  88     public float[]   maxy_            = new float[DEFAULT_CONTOURS];\r
  89     public float     minx             = Float.MAX_VALUE;\r
  90     public float     miny             = Float.MAX_VALUE;\r
  91     public float     maxx             = Float.MIN_VALUE;\r
  92     public float     maxy             = Float.MIN_VALUE;\r
  93     public boolean   sealed           = false;\r
  94 \r
  95     public Polygon() { }\r
  96     public Polygon(Path p, Affine a) { p.addTo(this, a); }\r
  97     public void intersection(Polygon p2) { clip(GPC_INT, this, p2); }\r
  98     public void intersect(Polygon p2) { clip(GPC_INT, this, p2); }\r
  99     public void union(Polygon p2) { clip(GPC_UNION, this, p2); }\r
 100     public void xor(Polygon p2) { clip(GPC_XOR, this, p2); }\r
 101     public void subtract(Polygon p2) { clip(GPC_DIFF, this, p2); }\r
 102     private static Polygon rectclipper = new Polygon();\r
 103     public void addrect(float x1, float y1, float x2, float y2, Affine a) {\r
 104         add(a.multiply_px(x1, y1), a.multiply_py(x1, y1));\r
 105         add(a.multiply_px(x2, y1), a.multiply_py(x2, y1));\r
 106         add(a.multiply_px(x2, y2), a.multiply_py(x2, y2));\r
 107         add(a.multiply_px(x1, y2), a.multiply_py(x1, y2));\r
 108         closepath();\r
 109     }\r
 110     public void clipto(float x1, float y1, float x2, float y2, Affine a) {\r
 111         rectclipper.clear();\r
 112         rectclipper.addrect(x1, y1, x2, y2, a);\r
 113         intersection(rectclipper);\r
 114     }\r
 115     public void closepath() {\r
 116         if (numcontours > 0 && numvertices == 0) return;\r
 117         if (numcontours > 0 && (x[contours[numcontours-1]] != x[numvertices-1] || y[contours[numcontours-1]] != y[numvertices-1]))\r
 118             add(x[contours[numcontours-1]], y[contours[numcontours-1]]);\r
 119     }\r
 120     public void newcontour() {\r
 121         if (numcontours > 0 && numvertices == contours[numcontours-1]) return;\r
 122         closepath();\r
 123         maxx_[numcontours] = maxy_[numcontours] = Float.MIN_VALUE;\r
 124         minx_[numcontours] = miny_[numcontours] = Float.MAX_VALUE;\r
 125         contours[numcontours++] = numvertices;\r
 126         if (numcontours >= contours.length - 2) {\r
 127             int[] z = new int[contours.length * 4]; System.arraycopy(contours, 0, z, 0, contours.length); contours = z;\r
 128             boolean[] s = new boolean[hole.length * 4]; System.arraycopy(hole, 0, s, 0, hole.length); hole = s;\r
 129             s = new boolean[contributing.length * 4];System.arraycopy(contributing,0,s,0,contributing.length);contributing = s;\r
 130             float[] f = new float[minx_.length * 4]; System.arraycopy(minx_, 0, f, 0, minx_.length); minx_ = f;\r
 131             f = new float[maxx_.length * 4]; System.arraycopy(maxx_, 0, f, 0, maxx_.length); maxx_ = f;\r
 132             f = new float[miny_.length * 4]; System.arraycopy(miny_, 0, f, 0, miny_.length); miny_ = f;\r
 133             f = new float[maxy_.length * 4]; System.arraycopy(maxy_, 0, f, 0, maxy_.length); maxy_ = f;\r
 134             Log.debug(this, "growing contour list to " + contours.length);\r
 135         } \r
 136     }\r
 137     public void add(float x, float y) {\r
 138         if (sealed) { Log.error(this, "tried to add a vertex to a sealed polygon!"); return; }\r
 139         if (numcontours == 0) newcontour();\r
 140         this.x[numvertices] = x;\r
 141         this.y[numvertices] = y;\r
 142         numvertices++;\r
 143         if (x > maxx_[numcontours-1]) maxx_[numcontours-1] = x;\r
 144         if (x < minx_[numcontours-1]) minx_[numcontours-1] = x;\r
 145         if (y > maxy_[numcontours-1]) maxy_[numcontours-1] = y;\r
 146         if (y < miny_[numcontours-1]) miny_[numcontours-1] = y;\r
 147         if (x > maxx) maxx = x;\r
 148         if (x < minx) minx = x;\r
 149         if (y > maxy) maxy = y;\r
 150         if (y < miny) miny = y;\r
 151         if (numvertices >= this.x.length) {\r
 152             float[] new_x = new float[this.x.length * 4]; System.arraycopy(this.x, 0, new_x, 0, this.x.length); this.x = new_x;\r
 153             float[] new_y = new float[this.y.length * 4]; System.arraycopy(this.y, 0, new_y, 0, this.y.length); this.y = new_y;\r
 154             Log.debug(this, "growing vertex list to " + this.x.length);\r
 155         } \r
 156     }\r
 157     public void clear() {\r
 158         numvertices = 0; numedges = 0; numcontours = 0; sealed = false;\r
 159         maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE;\r
 160     }\r
 161     public boolean isEmpty() { return numvertices == 0; }\r
 162     public void add(Polygon p) { add(p, Affine.identity()); }\r
 163     public void add(Polygon p, Affine a) { for(int i=0; i<p.numcontours; i++) add(p, i, a); }\r
 164     public void add(Polygon p, int idx) { add(p, idx, Affine.identity()); }\r
 165     public void add(Polygon p, int idx, Affine a) {\r
 166         newcontour();\r
 167         for(int i=p.contours[idx]; i<p.contours[idx+1]; i++) {\r
 168             float x = p.x[p.contours[idx]+i];\r
 169             float y = p.y[p.contours[idx]+i];\r
 170             add(a.multiply_px(x, y), a.multiply_py(x, y));\r
 171         }\r
 172     }\r
 173     public void transform(Affine a) {\r
 174         maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE;\r
 175         int s = 0;\r
 176         for(int i=0; i<numvertices; i++) {\r
 177             while (i >= contours[s+1]) s++;\r
 178             float x = a.multiply_px(this.x[i], this.y[i]);\r
 179             float y = a.multiply_py(this.x[i], this.y[i]);\r
 180             this.x[i] = x; \r
 181             this.y[i] = y; \r
 182             if (x > maxx_[s]) maxx_[s] = x;\r
 183             if (x < minx_[s]) minx_[s] = x;\r
 184             if (y > maxy_[s]) maxy_[s] = y;\r
 185             if (y < miny_[s]) miny_[s] = y;\r
 186             if (x > maxx) maxx = x;\r
 187             if (x < minx) minx = x;\r
 188             if (y > maxy) maxy = y;\r
 189             if (y < miny) miny = y;\r
 190         }\r
 191     }\r
 192 \r
 193     public void stroke(PixelBuffer buf, int color) {\r
 194         Polygon p = this;\r
 195         if (!p.sealed) p.sort();\r
 196         for(int i=0; i<p.numedges; i++) {\r
 197             float x1 = p.x[p.edges[i]];\r
 198             float y1 = p.y[p.edges[i]];\r
 199             float x2 = p.x[p.edges[i]+1];\r
 200             float y2 = p.y[p.edges[i]+1];\r
 201             long start = System.currentTimeMillis(); try {\r
 202                 buf.drawLine((int)Math.floor(x1), (int)Math.floor(y1), (int)Math.ceil(x2), (int)Math.ceil(y2), color);\r
 203             } finally { Scheduler.drawing += System.currentTimeMillis() - start; }\r
 204         }\r
 205     }\r
 206 \r
 207     /** finds the x value at which the line intercepts the line y=_y */\r
 208     private int intercept(int i, float _y, boolean includeTop, boolean includeBottom) {\r
 209         Polygon p = this;\r
 210         if (includeTop ? (_y < Math.min(p.y[i], p.y[i+1])) : (_y <= Math.min(p.y[i], p.y[i+1])))\r
 211             return Integer.MIN_VALUE;\r
 212         if (includeBottom ? (_y > Math.max(p.y[i], p.y[i+1])) : (_y >= Math.max(p.y[i], p.y[i+1])))\r
 213             return Integer.MIN_VALUE;\r
 214         float f = (((float)(p.x[i + 1] - p.x[i])) / ((float)(p.y[i + 1] - p.y[i])) ) * ((float)(_y - p.y[i])) + p.x[i];\r
 215         return (int)Math.floor(f);\r
 216     }\r
 217 \r
 218     /** fill the interior of the path */\r
 219     public void fill(PixelBuffer buf, Paint paint) {\r
 220         Polygon p = this;\r
 221         if (!p.sealed) p.sort();\r
 222         if (p.numedges == 0) return;\r
 223         float y0 = p.y[p.edges[0]], y1 = y0;\r
 224         boolean useEvenOdd = false;\r
 225 \r
 226         // we iterate over all endpoints in increasing y-coordinate order\r
 227         OUTER: for(int index = 1; index<p.numedges; index++) {\r
 228             int count = 0;\r
 229 \r
 230             // we now examine the horizontal band between y=y0 and y=y1\r
 231             y0 = y1;\r
 232             y1 = p.y[p.edges[index]];\r
 233             if (y0 == y1) continue;\r
 234 \r
 235             // within this band, we iterate over all p.edges\r
 236             int x0 = Integer.MIN_VALUE;\r
 237             int leftSegment = -1;\r
 238             while(true) {\r
 239                 int x1 = Integer.MAX_VALUE;\r
 240                 int rightSegment = Integer.MAX_VALUE;\r
 241                 for(int i=0; i<p.numedges; i++) {\r
 242                     if (p.y[p.edges[i]] == p.y[p.edges[i]+1]) continue; // ignore horizontal lines; they are irrelevant.\r
 243                     // we order the segments by the x-coordinate of their midpoint;\r
 244                     // since segments cannot intersect, this is a well-ordering\r
 245                     int i0 = intercept(p.edges[i], y0, true, false);\r
 246                     int i1 = intercept(p.edges[i], y1, false, true);\r
 247                     if (i0 == Integer.MIN_VALUE || i1 == Integer.MIN_VALUE) continue;\r
 248                     int midpoint = i0 + i1;\r
 249                     if (midpoint < x0) continue;\r
 250                     if (midpoint == x0 && i <= leftSegment) continue;\r
 251                     if (midpoint > x1) continue;\r
 252                     if (midpoint == x1 && i >= rightSegment) continue;\r
 253                     rightSegment = i;\r
 254                     x1 = midpoint;\r
 255                 }\r
 256                 if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break;\r
 257                 if (leftSegment != -1)\r
 258                     if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0)) {\r
 259                         int tx1a = intercept(p.edges[leftSegment], y0, true, true);\r
 260                         int tx1b = intercept(p.edges[rightSegment], y0, true, true);\r
 261                         int tx2a = intercept(p.edges[leftSegment], y1, true, true);\r
 262                         int tx2b = intercept(p.edges[rightSegment], y1, true, true);\r
 263                         long start = System.currentTimeMillis(); try {\r
 264                             buf.fillTrapezoid(tx1a, tx1b, (int)y0, tx2a, tx2b, (int)y1, ((Paint.SingleColorPaint)paint).color);\r
 265                         } finally { Scheduler.drawing += System.currentTimeMillis() - start; }\r
 266                     }\r
 267                 if (useEvenOdd) count++;\r
 268                 else count += (p.y[p.edges[rightSegment]] < p.y[p.edges[rightSegment]+1]) ? -1 : 1;\r
 269                 leftSegment = rightSegment; x0 = x1;\r
 270             }\r
 271         }\r
 272     }\r
 273 \r
 274     //////////////////////////////////////////////////////////////////////////////\r
 275 \r
 276     public Polygon sort() {\r
 277         closepath();\r
 278         contours[numcontours] = numvertices;\r
 279         sealed = true;\r
 280         numedges = 0;\r
 281         edges = new int[numvertices];\r
 282         for(int i=0; i<numcontours; i++)\r
 283             for(int j=contours[i]; j<contours[i+1]-1; j++)\r
 284                 edges[numedges++] = j;\r
 285         sort(0, numedges - 1, false);\r
 286         return this;\r
 287     }\r
 288 \r
 289     /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */\r
 290     int sort(int left, int right, boolean partition) {\r
 291         if (partition) {\r
 292             int i, j, middle;\r
 293             middle = (left + right) / 2;\r
 294             int s = edges[right]; edges[right] = edges[middle]; edges[middle] = s;\r
 295             for (i = left - 1, j = right; ; ) {\r
 296                 while (y[edges[++i]] < y[edges[right]]);\r
 297                 while (j > left && y[edges[--j]] > y[edges[right]]);\r
 298                 if (i >= j) break;\r
 299                 s = edges[i]; edges[i] = edges[j]; edges[j] = s;\r
 300             }\r
 301             s = edges[right]; edges[right] = edges[i]; edges[i] = s;\r
 302             return i;\r
 303         } else {\r
 304             if (left >= right) return 0;\r
 305             int p = sort(left, right, true);\r
 306             sort(left, p - 1, false);\r
 307             sort(p + 1, right, false);\r
 308             return 0;\r
 309         }\r
 310     }\r
 311 \r
 312     // Rendering //////////////////////////////////////////////////////////////////////////////\r
 313 \r
 314        \r
 315     private static int bound(int min, int mid, int max) { return mid < min ? min : mid > max ? max : mid; }\r
 316 \r
 317     public String toString(int i) {\r
 318         String ret = "    ";\r
 319         for(int j=contours[i]; j<contours[i+1]; j++) ret += x[j]+","+y[j];\r
 320         return ret + "\n";\r
 321     }\r
 322     public String toString() {\r
 323         String ret = "Polygon\n";\r
 324         for(int i=0; i<numcontours; i++) ret += toString(i);\r
 325         return ret;\r
 326     }\r
 327 \r
 328 \r
 329     // GPC //////////////////////////////////////////////////////////////////////////////\r
 330 \r
 331     //private static final float GPC_EPSILON = 2.2204460492503131e-016 ;\r
 332     private static final float GPC_EPSILON = (float)1e-8;\r
 333     private static final String GPC_VERSION = "2.31" ;\r
 334     private static final int LEFT  = 0 ;\r
 335     private static final int RIGHT = 1 ;\r
 336     private static final int ABOVE = 0 ;\r
 337     private static final int BELOW = 1 ;\r
 338     private static final int CLIP = 0 ;\r
 339     private static final int SUBJ = 1 ;\r
 340     \r
 341     // evilbadnonthreadsafestuff\r
 342     private static ScanBeamList sbte       = new ScanBeamList();\r
 343     private static EdgeTable s_heap        = new EdgeTable();\r
 344     private static EdgeTable c_heap        = new EdgeTable();\r
 345     private static LmtTable lmt_table      = new LmtTable();\r
 346     private static TopPolygonNode out_poly = new TopPolygonNode();\r
 347     private static AetTree aet             = new AetTree();\r
 348     private static ItNodeTable it_table    = new ItNodeTable();\r
 349 \r
 350     private static Polygon clip(byte op, Polygon subj, Polygon clip) {\r
 351         try {\r
 352             long start = System.currentTimeMillis(); try {\r
 353             return clip_(op, subj, clip);\r
 354             } finally { Scheduler.clipping += System.currentTimeMillis() - start; }\r
 355         } catch (Exception npe) {\r
 356             npe.printStackTrace();\r
 357             return null;\r
 358         }\r
 359     }\r
 360     private static Polygon clip_(byte op, Polygon subj, Polygon clip) {\r
 361       int parity_CLIP = LEFT;\r
 362       int parity_SUBJ = LEFT;\r
 363       float[] sbt = null;\r
 364       int local_min = 0;\r
 365       int scanbeam = 0;\r
 366 \r
 367       numFreeEdgeNodes = numEdgeNodes;\r
 368 \r
 369         subj.closepath(); subj.contours[subj.numcontours] = subj.numvertices;\r
 370         clip.closepath(); clip.contours[clip.numcontours] = clip.numvertices;\r
 371         PolygonNode.clear();\r
 372 \r
 373       // Test for trivial NULL result cases \r
 374       if ((subj.isEmpty() && clip.isEmpty()) || (subj.isEmpty() && ((op == GPC_INT) || (op == GPC_DIFF))) ||\r
 375           (clip.isEmpty() &&  (op == GPC_INT)))\r
 376           { subj.clear(); return subj; }\r
 377       \r
 378       // Identify potentialy contributing contours \r
 379       if (((op == GPC_INT) || (op == GPC_DIFF)) && !subj.isEmpty() && !clip.isEmpty())\r
 380          minimax_test(subj, clip, op);\r
 381       \r
 382       // Build LMT \r
 383       lmt_table.clear();\r
 384       sbte.clear();\r
 385       s_heap.clear();\r
 386       c_heap.clear();\r
 387       if (!subj.isEmpty()) build_lmt(s_heap, lmt_table, sbte, subj, SUBJ, op);\r
 388       if (!clip.isEmpty()) build_lmt(c_heap, lmt_table, sbte, clip, CLIP, op);\r
 389       if (lmt_table.isEmpty()) { subj.clear(); return subj; }    // Return a NULL result if no contours contribute\r
 390 \r
 391       // Build scanbeam table from scanbeam tree \r
 392             sbt = sbte.sort();\r
 393       // Invert clip polygon for difference operation \r
 394       if (op == GPC_DIFF) parity_CLIP = RIGHT;\r
 395       out_poly.clear();\r
 396       aet.clear();\r
 397       \r
 398       // Process each scanbeam \r
 399       while(scanbeam < sbte.entries) {\r
 400          // Set yb and yt to the bottom and top of the scanbeam \r
 401          float yb = sbt[scanbeam++];\r
 402          float yt = (float)0.0;\r
 403          float dy = (float)0.0;\r
 404          if (scanbeam < sbte.entries) { yt = sbt[scanbeam]; dy = yt - yb; }\r
 405   \r
 406          // === SCANBEAM BOUNDARY PROCESSING ================================ \r
 407          // If LMT node corresponding to yb exists \r
 408          if (local_min < lmt_table.numentries && lmt_table.y[local_min] == yb) {\r
 409              // Add edges starting at this local minimum to the AET \r
 410              for(EdgeNode edge = lmt_table.first_bound[local_min]; (edge != null); edge= edge.next_bound)\r
 411                  add_edge_to_aet(aet, edge);\r
 412              local_min++;\r
 413          }\r
 414          \r
 415          float px = -Float.MAX_VALUE;    // Set dummy previous x value\r
 416          EdgeNode e0 = aet.top_node;       // Create bundles within AET\r
 417          EdgeNode e1 = aet.top_node;\r
 418          \r
 419          // Set up bundle fields of first edge \r
 420          if (aet.top_node.type == CLIP) aet.top_node.bundle_ABOVE_CLIP = (aet.top_node.top_y != yb) ? 1 : 0;\r
 421          else aet.top_node.bundle_ABOVE_SUBJ = (aet.top_node.top_y != yb) ? 1 : 0;\r
 422 \r
 423          if (((aet.top_node.type==0) ? 1 : 0) == CLIP) aet.top_node.bundle_ABOVE_CLIP = 0;\r
 424          else aet.top_node.bundle_ABOVE_SUBJ = 0;\r
 425          aet.top_node.bstate_ABOVE = UNBUNDLED;\r
 426 \r
 427          for (EdgeNode next_edge = aet.top_node.next; next_edge != null; next_edge = next_edge.next) {\r
 428             int ne_type = next_edge.type;\r
 429             int ne_type_opp = ((next_edge.type==0) ? 1 : 0);  // next edge type opposite\r
 430             \r
 431             // Set up bundle fields of next edge \r
 432             if (ne_type     == CLIP) next_edge.bundle_ABOVE_CLIP = (next_edge.top_y != yb) ? 1 : 0;\r
 433             else next_edge.bundle_ABOVE_SUBJ = (next_edge.top_y != yb) ? 1 : 0;                \r
 434             if (ne_type_opp == CLIP) next_edge.bundle_ABOVE_CLIP  = 0;\r
 435             else next_edge.bundle_ABOVE_SUBJ  = 0;                \r
 436             next_edge.bstate_ABOVE = UNBUNDLED;\r
 437             \r
 438             // Bundle edges above the scanbeam boundary if they coincide \r
 439             if ((ne_type == CLIP ? next_edge.bundle_ABOVE_CLIP : next_edge.bundle_ABOVE_SUBJ) == 1) {\r
 440                if (EQ(e0.xb, next_edge.xb) && EQ(e0.dx, next_edge.dx) && (e0.top_y != yb)) {\r
 441                    if (ne_type == CLIP)\r
 442                        next_edge.bundle_ABOVE_CLIP ^= ne_type == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;\r
 443                    else next_edge.bundle_ABOVE_SUBJ  ^= ne_type == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;\r
 444                    if (ne_type_opp == CLIP)\r
 445                        next_edge.bundle_ABOVE_CLIP = ne_type_opp == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;\r
 446                    else next_edge.bundle_ABOVE_SUBJ = ne_type_opp == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;\r
 447                   next_edge.bstate_ABOVE = BUNDLE_HEAD;\r
 448                   e0.bundle_ABOVE_CLIP = 0;\r
 449                   e0.bundle_ABOVE_SUBJ = 0;\r
 450                   e0.bstate_ABOVE = BUNDLE_TAIL;\r
 451                }\r
 452                e0 = next_edge;\r
 453             }\r
 454          }\r
 455          \r
 456          int horiz_CLIP = HState.NH;\r
 457          int horiz_SUBJ = HState.NH;\r
 458          int exists_CLIP = 0;\r
 459          int exists_SUBJ = 0;\r
 460          PolygonNode cf = null;\r
 461          \r
 462          // Process each edge at this scanbeam boundary \r
 463          for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {\r
 464              exists_CLIP = edge.bundle_ABOVE_CLIP + (edge.bundle_BELOW_CLIP << 1);\r
 465              exists_SUBJ = edge.bundle_ABOVE_SUBJ + (edge.bundle_BELOW_SUBJ << 1);\r
 466          \r
 467             if ((exists_CLIP != 0) || (exists_SUBJ != 0)) {   // Set bundle side \r
 468                edge.bside_CLIP = parity_CLIP;\r
 469                edge.bside_SUBJ = parity_SUBJ;\r
 470                boolean contributing = false;\r
 471                int br=0, bl=0, tr=0, tl=0;\r
 472                // Determine contributing status and quadrant occupancies \r
 473                switch(op) {\r
 474                    case GPC_DIFF:\r
 475                    case GPC_INT:\r
 476                        contributing= ((exists_CLIP!=0) && ((parity_SUBJ!=0) || (horiz_SUBJ!=0))) ||\r
 477                            ((exists_SUBJ!=0) && ((parity_CLIP!=0) || (horiz_CLIP!=0))) ||\r
 478                            ((exists_CLIP!=0) && (exists_SUBJ!=0) && (parity_CLIP == parity_SUBJ));\r
 479                        br = ((parity_CLIP!=0) && (parity_SUBJ!=0)) ? 1 : 0;\r
 480                        bl = (((parity_CLIP ^ edge.bundle_ABOVE_CLIP)!=0) &&\r
 481                              ((parity_SUBJ ^ edge.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;\r
 482                        tr = (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0)) !=0) && \r
 483                              ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0)) !=0)) ? 1 : 0;\r
 484                        tl = (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)!=0) &&\r
 485                              ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ)!=0))?1:0;\r
 486                        break;\r
 487 \r
 488                    case GPC_XOR:\r
 489                        contributing= (exists_CLIP!=0) || (exists_SUBJ!=0);\r
 490                        br= (parity_CLIP) ^ (parity_SUBJ);\r
 491                        bl= (parity_CLIP ^ edge.bundle_ABOVE_CLIP) ^ (parity_SUBJ ^ edge.bundle_ABOVE_SUBJ);\r
 492                        tr= (parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0)) ^ (parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0));\r
 493                        tl= (parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)\r
 494                            ^ (parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ);\r
 495                        break;\r
 496 \r
 497                    case GPC_UNION:\r
 498                        contributing= ((exists_CLIP!=0) && (!(parity_SUBJ!=0) || (horiz_SUBJ!=0))) ||\r
 499                            ((exists_SUBJ!=0) && (!(parity_CLIP!=0) || (horiz_CLIP!=0))) ||\r
 500                            ((exists_CLIP!=0) && (exists_SUBJ!=0) && (parity_CLIP == parity_SUBJ));\r
 501                        br= ((parity_CLIP!=0) || (parity_SUBJ!=0))?1:0;\r
 502                        bl= (((parity_CLIP ^ edge.bundle_ABOVE_CLIP)!=0) || ((parity_SUBJ ^ edge.bundle_ABOVE_SUBJ)!=0))?1:0;\r
 503                        tr= (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0))!=0) || \r
 504                             ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0))!=0)) ?1:0;\r
 505                        tl= (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)!=0) ||\r
 506                             ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ)!=0)) ? 1:0;\r
 507                        break;\r
 508                    default: throw new IllegalStateException("Unknown op");\r
 509                }\r
 510                \r
 511                // Update parity \r
 512                parity_CLIP ^= edge.bundle_ABOVE_CLIP;\r
 513                parity_SUBJ ^= edge.bundle_ABOVE_SUBJ;\r
 514                \r
 515                // Update horizontal state \r
 516                if (exists_CLIP!=0) horiz_CLIP = HState.next_h_state[horiz_CLIP][((exists_CLIP - 1) << 1) + parity_CLIP];\r
 517                if (exists_SUBJ!=0) horiz_SUBJ = HState.next_h_state[horiz_SUBJ][((exists_SUBJ - 1) << 1) + parity_SUBJ];\r
 518                \r
 519                if (contributing) {\r
 520                    float xb = edge.xb;\r
 521                    int vclass = VertexType.getType(tr, tl, br, bl);\r
 522                    switch (vclass) {\r
 523                      case VertexType.EMN:\r
 524                      case VertexType.IMN:\r
 525                         edge.outp_ABOVE = out_poly.add_local_min(xb, yb);\r
 526                         px = xb;\r
 527                         cf = edge.outp_ABOVE;\r
 528                         break;\r
 529                      case VertexType.ERI:\r
 530                         if (xb != px) { cf.add_right(xb, yb); px= xb; }\r
 531                         edge.outp_ABOVE= cf;\r
 532                         cf= null;\r
 533                         break;\r
 534                      case VertexType.ELI:\r
 535                         edge.outp_BELOW.add_left(xb, yb);\r
 536                         px= xb;\r
 537                         cf= edge.outp_BELOW;\r
 538                         break;\r
 539                      case VertexType.EMX:\r
 540                         if (xb != px) { cf.add_left(xb, yb); px= xb; }\r
 541                         out_poly.merge_right(cf, edge.outp_BELOW);\r
 542                         cf= null;\r
 543                         break;\r
 544                      case VertexType.ILI:\r
 545                         if (xb != px) { cf.add_left(xb, yb); px= xb; }\r
 546                         edge.outp_ABOVE= cf;\r
 547                         cf= null;\r
 548                         break;\r
 549                      case VertexType.IRI:\r
 550                         edge.outp_BELOW.add_right(xb, yb);\r
 551                         px= xb;\r
 552                         cf= edge.outp_BELOW;\r
 553                         edge.outp_BELOW= null;\r
 554                         break;\r
 555                      case VertexType.IMX:\r
 556                         if (xb != px) { cf.add_right(xb, yb); px= xb; }\r
 557                         out_poly.merge_left(cf, edge.outp_BELOW);\r
 558                         cf= null;\r
 559                         edge.outp_BELOW= null;\r
 560                         break;\r
 561                      case VertexType.IMM:\r
 562                         if (xb != px) { cf.add_right(xb, yb); px= xb; }\r
 563                         out_poly.merge_left(cf, edge.outp_BELOW);\r
 564                         edge.outp_BELOW= null;\r
 565                         edge.outp_ABOVE = out_poly.add_local_min(xb, yb);\r
 566                         cf= edge.outp_ABOVE;\r
 567                         break;\r
 568                      case VertexType.EMM:\r
 569                         if (xb != px) { cf.add_left(xb, yb); px= xb; }\r
 570                         out_poly.merge_right(cf, edge.outp_BELOW);\r
 571                         edge.outp_BELOW= null;\r
 572                         edge.outp_ABOVE = out_poly.add_local_min(xb, yb);\r
 573                         cf= edge.outp_ABOVE;\r
 574                         break;\r
 575                      case VertexType.LED:\r
 576                         if (edge.bot_y == yb) edge.outp_BELOW.add_left(xb, yb);\r
 577                         edge.outp_ABOVE= edge.outp_BELOW;\r
 578                         px= xb;\r
 579                         break;\r
 580                      case VertexType.RED:\r
 581                         if (edge.bot_y == yb) edge.outp_BELOW.add_right(xb, yb);\r
 582                         edge.outp_ABOVE= edge.outp_BELOW;\r
 583                         px= xb;\r
 584                         break;\r
 585                      default:\r
 586                         break;\r
 587                   } // End of switch \r
 588                } // End of contributing conditional \r
 589             } // End of edge exists conditional \r
 590          } // End of AET loop \r
 591          \r
 592          // Delete terminating edges from the AET, otherwise compute xt \r
 593          for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {\r
 594             if (edge.top_y == yb) {\r
 595                 EdgeNode prev_edge = edge.prev;\r
 596                 EdgeNode next_edge= edge.next;\r
 597                \r
 598                if (prev_edge != null) prev_edge.next = next_edge;\r
 599                else aet.top_node = next_edge;\r
 600                if (next_edge != null) next_edge.prev = prev_edge;\r
 601                \r
 602                // Copy bundle head state to the adjacent tail edge if required \r
 603                if ((edge.bstate_BELOW == BUNDLE_HEAD) && (prev_edge!=null)) {\r
 604                   if (prev_edge.bstate_BELOW == BUNDLE_TAIL) {\r
 605                      prev_edge.outp_BELOW= edge.outp_BELOW;\r
 606                      prev_edge.bstate_BELOW= UNBUNDLED;\r
 607                      if (prev_edge.prev != null) {\r
 608                         if (prev_edge.prev.bstate_BELOW == BUNDLE_TAIL)\r
 609                            prev_edge.bstate_BELOW = BUNDLE_HEAD;\r
 610                      }\r
 611                   }\r
 612                }\r
 613             } else {\r
 614                if (edge.top_y == yt) edge.xt = edge.top_x;\r
 615                else edge.xt= edge.bot_x + edge.dx * (yt - edge.bot_y);\r
 616             }\r
 617          }\r
 618                   \r
 619          if (scanbeam < sbte.entries) {\r
 620             // === SCANBEAM INTERIOR PROCESSING ============================== \r
 621             // Build intersection table for the current scanbeam \r
 622              it_table.clear();\r
 623              it_table.build_intersection_table(aet, dy);\r
 624          \r
 625             // Process each node in the intersection table \r
 626             for (int intersect = 0; intersect < it_table.num; intersect++) {\r
 627                e0 = it_table.ie_0[intersect];\r
 628                e1 = it_table.ie_1[intersect];\r
 629                \r
 630                // Only generate output for contributing intersections \r
 631                if (((e0.bundle_ABOVE_CLIP!=0) || (e0.bundle_ABOVE_SUBJ!=0)) &&\r
 632                    ((e1.bundle_ABOVE_CLIP!=0) || (e1.bundle_ABOVE_SUBJ!=0))) {\r
 633 \r
 634                   PolygonNode p = e0.outp_ABOVE;\r
 635                   PolygonNode q = e1.outp_ABOVE;\r
 636                   float ix = it_table.x[intersect];\r
 637                   float iy = it_table.y[intersect] + yb;\r
 638                \r
 639                   int in_clip = (((e0.bundle_ABOVE_CLIP!=0) && !(e0.bside_CLIP!=0)) ||\r
 640                                   ((e1.bundle_ABOVE_CLIP!=0) &&  (e1.bside_CLIP!=0)) ||\r
 641                                   (!(e0.bundle_ABOVE_CLIP!=0) && !(e1.bundle_ABOVE_CLIP!=0) &&\r
 642                                     (e0.bside_CLIP!=0) && (e1.bside_CLIP!=0))) ? 1 : 0;\r
 643                   \r
 644                   int in_subj = (((e0.bundle_ABOVE_SUBJ!=0) && !(e0.bside_SUBJ!=0)) ||\r
 645                                   ((e1.bundle_ABOVE_SUBJ!=0) &&  (e1.bside_SUBJ!=0)) ||\r
 646                                   (!(e0.bundle_ABOVE_SUBJ!=0) && !(e1.bundle_ABOVE_SUBJ!=0) &&\r
 647                                     (e0.bside_SUBJ!=0) && (e1.bside_SUBJ!=0))) ? 1 : 0;\r
 648         \r
 649                   int tr=0, tl=0, br=0, bl=0;\r
 650                   // Determine quadrant occupancies \r
 651                   switch(op) {\r
 652                       case GPC_DIFF:\r
 653                       case GPC_INT:\r
 654                           tr= ((in_clip!=0) && (in_subj!=0)) ? 1 : 0;\r
 655                           tl= (((in_clip ^ e1.bundle_ABOVE_CLIP)!=0) && ((in_subj ^ e1.bundle_ABOVE_SUBJ)!=0))?1:0;\r
 656                           br= (((in_clip ^ e0.bundle_ABOVE_CLIP)!=0) && ((in_subj ^ e0.bundle_ABOVE_SUBJ)!=0))?1:0;\r
 657                           bl= (((in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)!=0) &&\r
 658                                ((in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1:0;\r
 659                           break;\r
 660                       case GPC_XOR:\r
 661                           tr= (in_clip)^ (in_subj);\r
 662                           tl= (in_clip ^ e1.bundle_ABOVE_CLIP) ^ (in_subj ^ e1.bundle_ABOVE_SUBJ);\r
 663                           br= (in_clip ^ e0.bundle_ABOVE_CLIP) ^ (in_subj ^ e0.bundle_ABOVE_SUBJ);\r
 664                           bl= (in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)\r
 665                               ^ (in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ);\r
 666                           break;\r
 667                       case GPC_UNION:\r
 668                           tr= ((in_clip!=0) || (in_subj!=0)) ? 1 : 0;\r
 669                           tl= (((in_clip ^ e1.bundle_ABOVE_CLIP)!=0) || ((in_subj ^ e1.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;\r
 670                           br= (((in_clip ^ e0.bundle_ABOVE_CLIP)!=0) || ((in_subj ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;\r
 671                           bl= (((in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)!=0) ||\r
 672                                ((in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;\r
 673                           break;\r
 674                       default: throw new IllegalStateException("Unknown op type, "+op);\r
 675                   }\r
 676                   \r
 677                   int vclass = VertexType.getType(tr, tl, br, bl);\r
 678                   switch (vclass) {\r
 679                      case VertexType.EMN:\r
 680                         e0.outp_ABOVE = out_poly.add_local_min(ix, iy);\r
 681                         e1.outp_ABOVE = e0.outp_ABOVE;\r
 682                         break;\r
 683                      case VertexType.ERI:\r
 684                         if (p != null) { p.add_right(ix, iy); e1.outp_ABOVE= p; e0.outp_ABOVE= null; }\r
 685                         break;\r
 686                      case VertexType.ELI:\r
 687                         if (q != null) { q.add_left(ix, iy); e0.outp_ABOVE= q; e1.outp_ABOVE= null; }\r
 688                         break;\r
 689                      case VertexType.EMX:\r
 690                         if ((p!=null) && (q!=null)) {\r
 691                             p.add_left(ix, iy);\r
 692                             out_poly.merge_right(p, q);\r
 693                             e0.outp_ABOVE= null;\r
 694                            e1.outp_ABOVE= null;\r
 695                         }\r
 696                         break;\r
 697                      case VertexType.IMN:\r
 698                         e0.outp_ABOVE = out_poly.add_local_min(ix, iy);\r
 699                         e1.outp_ABOVE = e0.outp_ABOVE;\r
 700                         break;\r
 701                      case VertexType.ILI:\r
 702                         if (p != null) {\r
 703                            p.add_left(ix, iy);\r
 704                            e1.outp_ABOVE= p;\r
 705                            e0.outp_ABOVE= null;\r
 706                         }\r
 707                         break;\r
 708                      case VertexType.IRI:\r
 709                         if (q!=null) {\r
 710                            q.add_right(ix, iy);\r
 711                            e0.outp_ABOVE= q;\r
 712                            e1.outp_ABOVE= null;\r
 713                         }\r
 714                         break;\r
 715                      case VertexType.IMX:\r
 716                         if ((p!=null) && (q!=null)) {\r
 717                             p.add_right(ix, iy);\r
 718                             out_poly.merge_left(p, q);\r
 719                             e0.outp_ABOVE= null;\r
 720                             e1.outp_ABOVE= null;\r
 721                         }\r
 722                         break;\r
 723                      case VertexType.IMM:\r
 724                         if ((p!=null) && (q!=null)) {\r
 725                             p.add_right(ix, iy);\r
 726                             out_poly.merge_left(p, q);\r
 727                             e0.outp_ABOVE = out_poly.add_local_min(ix, iy);\r
 728                             e1.outp_ABOVE= e0.outp_ABOVE;\r
 729                         }\r
 730                         break;\r
 731                      case VertexType.EMM:\r
 732                         if ((p!=null) && (q!=null)) {\r
 733                             p.add_left(ix, iy);\r
 734                             out_poly.merge_right(p, q);\r
 735                             e0.outp_ABOVE = out_poly.add_local_min(ix, iy);\r
 736                             e1.outp_ABOVE = e0.outp_ABOVE;\r
 737                         }\r
 738                         break;\r
 739                      default: break;\r
 740                   } // End of switch \r
 741                } // End of contributing intersection conditional \r
 742                   \r
 743                // Swap bundle sides in response to edge crossing \r
 744                if (e0.bundle_ABOVE_CLIP!=0) e1.bside_CLIP = (e1.bside_CLIP==0)?1:0;\r
 745                if (e1.bundle_ABOVE_CLIP!=0) e0.bside_CLIP= (e0.bside_CLIP==0)?1:0;\r
 746                if (e0.bundle_ABOVE_SUBJ!=0) e1.bside_SUBJ= (e1.bside_SUBJ==0)?1:0;\r
 747                if (e1.bundle_ABOVE_SUBJ!=0) e0.bside_SUBJ= (e0.bside_SUBJ==0)?1:0;\r
 748 \r
 749                // Swap e0 and e1 bundles in the AET \r
 750                EdgeNode prev_edge = e0.prev;\r
 751                EdgeNode next_edge = e1.next;\r
 752                if (next_edge != null) next_edge.prev = e0;\r
 753    \r
 754                if (e0.bstate_ABOVE == BUNDLE_HEAD) {\r
 755                   boolean search = true;\r
 756                   while (search) {\r
 757                       prev_edge= prev_edge.prev;\r
 758                       if (prev_edge != null) {\r
 759                           if (prev_edge.bstate_ABOVE != BUNDLE_TAIL)\r
 760                               search= false;\r
 761                       } else {\r
 762                           search= false;\r
 763                       }\r
 764                   }\r
 765                }\r
 766                if (prev_edge == null) {\r
 767                   aet.top_node.prev = e1;\r
 768                   e1.next           = aet.top_node;\r
 769                   aet.top_node      = e0.next;\r
 770                } else {\r
 771                    prev_edge.next.prev = e1;\r
 772                    e1.next             = prev_edge.next;\r
 773                    prev_edge.next      = e0.next;\r
 774                }\r
 775                e0.next.prev = prev_edge;\r
 776                e1.next.prev = e1;\r
 777                e0.next      = next_edge;\r
 778             } // End of IT loop\r
 779                \r
 780             // Prepare for next scanbeam \r
 781             for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {\r
 782                EdgeNode next_edge = edge.next;\r
 783                EdgeNode succ_edge = edge.succ;\r
 784                if ((edge.top_y == yt) && (succ_edge!=null)) {\r
 785                   // Replace AET edge by its successor \r
 786                   succ_edge.outp_BELOW= edge.outp_ABOVE;\r
 787                   succ_edge.bstate_BELOW= edge.bstate_ABOVE;\r
 788                   succ_edge.bundle_BELOW_CLIP= edge.bundle_ABOVE_CLIP;\r
 789                   succ_edge.bundle_BELOW_SUBJ= edge.bundle_ABOVE_SUBJ;\r
 790                   EdgeNode prev_edge = edge.prev;\r
 791                   if (prev_edge != null) prev_edge.next = succ_edge;\r
 792                   else aet.top_node = succ_edge;\r
 793                   if (next_edge != null) next_edge.prev= succ_edge;\r
 794                   succ_edge.prev = prev_edge;\r
 795                   succ_edge.next = next_edge;\r
 796                } else {\r
 797                    // Update this edge \r
 798                    edge.outp_BELOW= edge.outp_ABOVE;\r
 799                    edge.bstate_BELOW= edge.bstate_ABOVE;\r
 800                    edge.bundle_BELOW_CLIP= edge.bundle_ABOVE_CLIP;\r
 801                    edge.bundle_BELOW_SUBJ= edge.bundle_ABOVE_SUBJ;\r
 802                    edge.xb= edge.xt;\r
 803                }\r
 804                edge.outp_ABOVE= null;\r
 805             }\r
 806          }\r
 807       } // === END OF SCANBEAM PROCESSING ================================== \r
 808 \r
 809       // Generate result polygon from out_poly \r
 810       subj.clear();\r
 811       return out_poly.getResult(subj);\r
 812    }\r
 813    \r
 814     private static boolean EQ(float a, float b) { return (Math.abs(a - b) <= GPC_EPSILON); }\r
 815     private static int PREV_INDEX(int i, int n) { return ((i - 1 + n) % n); }\r
 816     private static int NEXT_INDEX(int i, int n) { return ((i + 1   ) % n); }\r
 817     private static boolean OPTIMAL(Polygon p, int index, int i) {\r
 818         return (p.y[p.contours[index] + PREV_INDEX(i, p.contours[index+1]-p.contours[index])] != p.y[p.contours[index] + i]) ||\r
 819             (p.y[p.contours[index] + NEXT_INDEX(i, p.contours[index+1]-p.contours[index])] != p.y[p.contours[index] + i]);\r
 820     }\r
 821    \r
 822    private static void minimax_test(Polygon subj, Polygon clip, byte op) {\r
 823       // For each clip contour, search for any subject contour overlaps \r
 824       for(int c=0; c < clip.numcontours; c++) {\r
 825          boolean overlap = false;\r
 826          for(int s = 0; !overlap && (s < subj.numcontours); s++)\r
 827              overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) &&\r
 828                  (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c])));\r
 829          clip.contributing[c] = overlap;\r
 830       }  \r
 831       if (op != GPC_INT) return;\r
 832       // For each subject contour, search for any clip contour overlaps \r
 833       for (int s=0; s < subj.numcontours; s++) {\r
 834           boolean overlap = false;\r
 835           for (int c=0; !overlap && (c < clip.numcontours); c++)\r
 836               overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) &&\r
 837                   (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c])));\r
 838           subj.contributing[s] = overlap;\r
 839       }\r
 840    }\r
 841 \r
 842    private static void insert_bound(LmtTable lmt_table, float y, EdgeNode e) {\r
 843       int index = lmt_table.add(y, null);\r
 844       // Link node e to the tail of the list \r
 845       if (lmt_table.first_bound[index] == null) { lmt_table.first_bound[index] = e; return; }\r
 846       EdgeNode prev_bound = null;\r
 847       EdgeNode current_bound = lmt_table.first_bound[index];\r
 848       while(true)\r
 849           // Do primary sort on the x field \r
 850           if (e.bot_x <  current_bound.bot_x) {\r
 851               // Insert a new node mid-list \r
 852               if (prev_bound == null) lmt_table.first_bound[index] = e;\r
 853               else prev_bound.next_bound = e;\r
 854               e.next_bound = current_bound;\r
 855               break;\r
 856           } else if (e.bot_x == current_bound.bot_x) {\r
 857               // Do secondary sort on the dx field \r
 858               if (e.dx < current_bound.dx) {\r
 859                   // Insert a new node mid-list \r
 860                   if (prev_bound == null) lmt_table.first_bound[index] = e;\r
 861                   else prev_bound.next_bound = e;\r
 862                   e.next_bound = current_bound;\r
 863                   break;\r
 864               }\r
 865               // Head further down the list \r
 866               if (current_bound.next_bound == null) { current_bound.next_bound = e; break; }\r
 867               prev_bound = current_bound;\r
 868               current_bound = current_bound.next_bound;\r
 869           } else {\r
 870               // Head further down the list \r
 871               if (current_bound.next_bound == null) { current_bound.next_bound = e; break; }\r
 872               prev_bound = current_bound;\r
 873               current_bound = current_bound.next_bound;\r
 874           }\r
 875    }\r
 876    \r
 877    private static void add_edge_to_aet(AetTree aet, EdgeNode edge) {\r
 878       if (aet.top_node == null) {\r
 879          // Append edge onto the tail end of the AET \r
 880          aet.top_node = edge;\r
 881          edge.prev = null;\r
 882          edge.next= null;\r
 883          return;\r
 884       }\r
 885       EdgeNode current_edge = aet.top_node;\r
 886       EdgeNode prev = null;\r
 887       while(true)\r
 888           // Do primary sort on the xb field \r
 889           if (edge.xb < current_edge.xb) {\r
 890               // Insert edge here (before the AET edge) \r
 891               edge.prev= prev;\r
 892               edge.next= current_edge;\r
 893               current_edge.prev = edge;\r
 894               if (prev == null) aet.top_node = edge;\r
 895               else prev.next = edge;\r
 896               break;\r
 897           } else if (edge.xb == current_edge.xb) {\r
 898               // Do secondary sort on the dx field \r
 899               if (edge.dx < current_edge.dx) {\r
 900                   // Insert edge here (before the AET edge) \r
 901                   edge.prev= prev;\r
 902                   edge.next= current_edge;\r
 903                   current_edge.prev = edge;\r
 904                   if (prev == null) aet.top_node = edge;\r
 905                   else prev.next = edge;\r
 906                   break;\r
 907                }\r
 908               // Head further into the AET \r
 909               prev = current_edge;\r
 910               if (current_edge.next == null) {\r
 911                   current_edge.next = edge;\r
 912                   edge.prev = current_edge;\r
 913                   edge.next = null;\r
 914                   break;\r
 915               }\r
 916               current_edge = current_edge.next;\r
 917           } else {\r
 918               // Head further into the AET \r
 919               prev = current_edge;\r
 920               if (current_edge.next == null) {\r
 921                   current_edge.next = edge;\r
 922                   edge.prev = current_edge;\r
 923                   edge.next = null;\r
 924                   break;\r
 925                }\r
 926               current_edge = current_edge.next;\r
 927           }\r
 928    }\r
 929 \r
 930    private static void build_lmt(EdgeTable edge_table, LmtTable lmt_table, ScanBeamList sbte, Polygon p, int type, byte op) {\r
 931       for (int c=0; c < p.numcontours; c++) {\r
 932           if (!p.contributing[c]) { p.contributing[c] = true; continue; }\r
 933           // Perform contour optimisation \r
 934           int num_vertices= 0;\r
 935           int e_index = 0;\r
 936           edge_table.clear();\r
 937           for (int i= 0; i < p.contours[c+1] - p.contours[c]; i++)\r
 938               if (OPTIMAL(p, c, i)) {\r
 939                  edge_table.addNode(p.x[p.contours[c]+i], p.y[p.contours[c]+i]);\r
 940                  sbte.add(p.y[p.contours[c]+i]);  // Record vertex in the scanbeam table \r
 941                  num_vertices++;\r
 942               }\r
 943            \r
 944          // Do the contour forward pass \r
 945          for (int min= 0; min < num_vertices; min++) {\r
 946              // If a forward local minimum... \r
 947              if (edge_table.FWD_MIN(min)) {\r
 948                  // Search for the next local maximum... \r
 949                  int num_edges = 1;\r
 950                  int max = NEXT_INDEX(min, num_vertices);\r
 951                  while(edge_table.NOT_FMAX(max)) { num_edges++; max = NEXT_INDEX(max, num_vertices); }\r
 952 \r
 953                  // Build the next edge list \r
 954                  int v = min;\r
 955                  EdgeNode e = edge_table.getNode(e_index);\r
 956                  e.bstate_BELOW = UNBUNDLED;\r
 957                  e.bundle_BELOW_CLIP = 0;\r
 958                  e.bundle_BELOW_SUBJ = 0;\r
 959                   \r
 960                  for (int i= 0; i < num_edges; i++) {\r
 961                      EdgeNode ei = edge_table.getNode(e_index+i);\r
 962                      EdgeNode ev = edge_table.getNode(v);\r
 963                      ei.xb    = ev.vertex_x;\r
 964                      ei.bot_x = ev.vertex_x;\r
 965                      ei.bot_y = ev.vertex_y;\r
 966                      v = NEXT_INDEX(v, num_vertices);\r
 967                      ev = edge_table.getNode(v);\r
 968                      ei.top_x= ev.vertex_x;\r
 969                      ei.top_y= ev.vertex_y;\r
 970                      ei.dx= (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y);\r
 971                      ei.type = type;\r
 972                      ei.outp_ABOVE = null;\r
 973                      ei.outp_BELOW = null;\r
 974                      ei.next = null;\r
 975                      ei.prev = null;\r
 976                      ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;\r
 977                      ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null;\r
 978                      ei.next_bound = null;\r
 979                      ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT;\r
 980                      ei.bside_SUBJ = LEFT;\r
 981                  }\r
 982                  insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e);\r
 983                  e_index += num_edges;\r
 984              }\r
 985          }\r
 986 \r
 987          // Do the contour reverse pass \r
 988          for (int min= 0; min < num_vertices; min++) {\r
 989              // If a reverse local minimum... \r
 990              if (edge_table.REV_MIN(min)) {\r
 991                  // Search for the previous local maximum... \r
 992                  int num_edges= 1;\r
 993                  int max = PREV_INDEX(min, num_vertices);\r
 994                  while(edge_table.NOT_RMAX(max)) { num_edges++; max = PREV_INDEX(max, num_vertices); }\r
 995                  // Build the previous edge list \r
 996                  int v = min;\r
 997                  EdgeNode e = edge_table.getNode(e_index);\r
 998                  e.bstate_BELOW = UNBUNDLED;\r
 999                  e.bundle_BELOW_CLIP = 0;\r
1000                  e.bundle_BELOW_SUBJ = 0;\r
1001                  for (int i= 0; i < num_edges; i++) {\r
1002                      EdgeNode ei = edge_table.getNode(e_index+i);\r
1003                      EdgeNode ev = edge_table.getNode(v);\r
1004                      ei.xb    = ev.vertex_x;\r
1005                      ei.bot_x = ev.vertex_x;\r
1006                      ei.bot_y = ev.vertex_y;\r
1007                      v= PREV_INDEX(v, num_vertices);\r
1008                      ev = edge_table.getNode(v);\r
1009                      ei.top_x = ev.vertex_x;\r
1010                      ei.top_y = ev.vertex_y;\r
1011                      ei.dx = (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y);\r
1012                      ei.type = type;\r
1013                      ei.outp_ABOVE = null;\r
1014                      ei.outp_BELOW = null;\r
1015                      ei.next = null;\r
1016                      ei.prev = null;\r
1017                      ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;\r
1018                      ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null;\r
1019                      ei.next_bound = null;\r
1020                      ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT;\r
1021                      ei.bside_SUBJ = LEFT;\r
1022                  }\r
1023                  insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e);\r
1024                  e_index+= num_edges;\r
1025              }\r
1026          }\r
1027       }\r
1028    }\r
1029 \r
1030     public static final byte GPC_DIFF  = 0;\r
1031     public static final byte GPC_INT   = 1;\r
1032     public static final byte GPC_XOR   = 2;\r
1033     public static final byte GPC_UNION = 3;\r
1034 \r
1035     // Edge intersection classes\r
1036    private static class VertexType {\r
1037       public static final int NUL =  0; // Empty non-intersection            \r
1038       public static final int EMX =  1; // External maximum                  \r
1039       public static final int ELI =  2; // External left intermediate        \r
1040       public static final int TED =  3; // Top edge                          \r
1041       public static final int ERI =  4; // External right intermediate       \r
1042       public static final int RED =  5; // Right edge                        \r
1043       public static final int IMM =  6; // Internal maximum and minimum      \r
1044       public static final int IMN =  7; // Internal minimum                  \r
1045       public static final int EMN =  8; // External minimum                  \r
1046       public static final int EMM =  9; // External maximum and minimum      \r
1047       public static final int LED = 10; // Left edge                         \r
1048       public static final int ILI = 11; // Internal left intermediate        \r
1049       public static final int BED = 12; // Bottom edge                       \r
1050       public static final int IRI = 13; // Internal right intermediate       \r
1051       public static final int IMX = 14; // Internal maximum                  \r
1052       public static final int FUL = 15; // Full non-intersection             \r
1053       public static int getType(int tr, int tl, int br, int bl) { return tr + (tl << 1) + (br << 2) + (bl << 3); }\r
1054    }\r
1055    \r
1056    private static class HState {\r
1057       public static final int NH = 0; // No horizontal edge                \r
1058       public static final int BH = 1; // Bottom horizontal edge            \r
1059       public static final int TH = 2; // Top horizontal edge               \r
1060       // Horizontal edge state transitions within scanbeam boundary \r
1061       public static final int[][] next_h_state =\r
1062       {\r
1063       //        ABOVE     BELOW     CROSS \r
1064       //        L   R     L   R     L   R \r
1065       /* NH */ {BH, TH,   TH, BH,   NH, NH},\r
1066       /* BH */ {NH, NH,   NH, NH,   TH, TH},\r
1067       /* TH */ {NH, NH,   NH, NH,   BH, BH}\r
1068       };\r
1069    }\r
1070    \r
1071     public static final byte UNBUNDLED   = 0; // Isolated edge not within a bundle\r
1072     public static final byte BUNDLE_HEAD = 1; // Bundle head node\r
1073     public static final byte BUNDLE_TAIL = 2; // Passive bundle tail node\r
1074 \r
1075     private static class PolygonNode {\r
1076         public static void clear() { numvertices = 1; }\r
1077         private static final float[] x  = new float[BIGNUM];\r
1078         private static final float[] y  = new float[BIGNUM];\r
1079         private static final int[] nxt  = new int[BIGNUM];\r
1080         private static int numvertices = 1;\r
1081 \r
1082         int          active = 1;             // Active flag / vertex count        \r
1083         boolean      hole;                   // Hole / external contour flag      \r
1084         int          v_LEFT;                 // Left and right vertex list ptrs   \r
1085         int          v_RIGHT;                // Left and right vertex list ptrs   \r
1086         PolygonNode  next;                   // Pointer to next polygon contour   \r
1087         PolygonNode  proxy;                  // Pointer to actual structure used  \r
1088        \r
1089        public PolygonNode(PolygonNode next, float x0, float y0) {\r
1090            // Make v_LEFT and v_RIGHT point to new vertex \r
1091            x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;\r
1092            this.v_LEFT = numvertices;\r
1093            this.v_RIGHT = numvertices;\r
1094            numvertices++;\r
1095            this.proxy = this; // Initialise proxy to point to p itself \r
1096            this.next = next;\r
1097        }\r
1098        public void merge(PolygonNode q) { nxt[proxy.v_RIGHT] = q.proxy.v_LEFT; q.proxy.v_LEFT = proxy.v_LEFT; }\r
1099        public void mergeRight(PolygonNode p) { nxt[proxy.v_RIGHT] = p.proxy.v_LEFT; proxy.v_RIGHT = p.proxy.v_RIGHT; }\r
1100        public void addSelfTo(Polygon poly) {\r
1101            for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) poly.add(x[vtx], y[vtx]);\r
1102            poly.newcontour();\r
1103        }\r
1104        public int count() { int ret = 0; for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) ret++; return ret; }\r
1105        public void add_right(float x0, float y0) {\r
1106            x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;\r
1107            nxt[proxy.v_RIGHT] = numvertices;\r
1108            proxy.v_RIGHT = numvertices;\r
1109            numvertices++;\r
1110        }\r
1111        public void add_left(float x0, float y0) {\r
1112            x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;\r
1113            nxt[numvertices] = proxy.v_LEFT;\r
1114            proxy.v_LEFT = numvertices;\r
1115            numvertices++;\r
1116        }\r
1117    }\r
1118 \r
1119    private static class TopPolygonNode {\r
1120        PolygonNode top_node = null;\r
1121        public void clear() { top_node = null; }\r
1122        public PolygonNode add_local_min(float x, float y) {\r
1123            PolygonNode existing_min = top_node;\r
1124            top_node = new PolygonNode(existing_min, x, y);\r
1125            return top_node;\r
1126        }\r
1127        public void merge_left(PolygonNode p, PolygonNode q) {\r
1128          // Label contour as a hole \r
1129          q.proxy.hole = true;\r
1130          if (p.proxy == q.proxy) return;\r
1131          // Assign p's vertex list to the left end of q's list \r
1132          p.merge(q);\r
1133          // Redirect any p.proxy references to q.proxy \r
1134          PolygonNode target = p.proxy;\r
1135          for(PolygonNode node = top_node; (node != null); node = node.next)\r
1136              if (node.proxy == target) { node.active= 0; node.proxy= q.proxy; }\r
1137       }\r
1138 \r
1139       public void merge_right(PolygonNode p, PolygonNode q) {\r
1140          // Label contour as external \r
1141          q.proxy.hole = false;\r
1142          if (p.proxy == q.proxy) return;\r
1143          // Assign p's vertex list to the right end of q's list \r
1144          q.mergeRight(p);\r
1145          // Redirect any p->proxy references to q->proxy \r
1146          PolygonNode target = p.proxy;\r
1147          for (PolygonNode node = top_node; (node != null); node = node.next)\r
1148              if (node.proxy == target) { node.active = 0; node.proxy= q.proxy; }\r
1149       }\r
1150       \r
1151       public int count_contours() {\r
1152          int nc = 0;\r
1153          for (PolygonNode polygon = top_node; (polygon != null); polygon = polygon.next)\r
1154             if (polygon.active != 0) {\r
1155                // Count the vertices in the current contour \r
1156                int nv= polygon.proxy.count();\r
1157                // Record valid vertex counts in the active field \r
1158                if (nv > 2) { polygon.active = nv; nc++; }\r
1159                else polygon.active= 0;\r
1160             }\r
1161          return nc;\r
1162       }\r
1163       \r
1164       public Polygon getResult(Polygon result) {\r
1165          int num_contours = count_contours();\r
1166          if (num_contours <= 0) return result;\r
1167          int c= 0;\r
1168          PolygonNode npoly_node = null;\r
1169          for (PolygonNode poly_node = top_node; (poly_node != null); poly_node = npoly_node) {\r
1170              npoly_node = poly_node.next;\r
1171              if (poly_node.active == 0) continue;\r
1172              int prepoly = result.numcontours;\r
1173              // This algorithm puts the verticies into the poly in reverse order\r
1174              poly_node.proxy.addSelfTo(result);\r
1175              if (poly_node.proxy.hole) {\r
1176                  for(int i=prepoly; i<result.numcontours; i++)\r
1177                      result.hole[i] = poly_node.proxy.hole;\r
1178              }\r
1179              c++;\r
1180          }\r
1181          return result;\r
1182       }\r
1183    }\r
1184    \r
1185     private static EdgeNode[] allEdgeNodes = new EdgeNode[BIGNUM];\r
1186     private static int numEdgeNodes = 0;\r
1187     private static int numFreeEdgeNodes = 0;\r
1188     private static EdgeNode newEdgeNode(float x, float y) {\r
1189         if (numFreeEdgeNodes == 0) {\r
1190             return allEdgeNodes[numEdgeNodes++] = new EdgeNode(x, y);\r
1191         } else {\r
1192             EdgeNode ret = allEdgeNodes[--numFreeEdgeNodes];\r
1193             ret.vertex_x = x;\r
1194             ret.vertex_y = y;\r
1195             return ret;\r
1196         }\r
1197     }\r
1198    private static class EdgeNode {\r
1199        float vertex_x;\r
1200        float vertex_y;\r
1201        float top_x;\r
1202        float top_y;\r
1203        float bot_x;\r
1204        float bot_y;\r
1205        float         xb;           // Scanbeam bottom x coordinate      \r
1206        float         xt;           // Scanbeam top x coordinate         \r
1207        float         dx;           // Change in x for a unit y increase \r
1208        int           type;         // Clip / subject edge flag          \r
1209        int bundle_ABOVE_CLIP;\r
1210        int bundle_ABOVE_SUBJ;\r
1211        int bundle_BELOW_CLIP;\r
1212        int bundle_BELOW_SUBJ;\r
1213        int bside_CLIP;\r
1214        int bside_SUBJ;\r
1215        byte bstate_ABOVE;\r
1216        byte bstate_BELOW;\r
1217        PolygonNode  outp_ABOVE; // Output polygon / tristrip pointer \r
1218        PolygonNode  outp_BELOW; // Output polygon / tristrip pointer \r
1219        EdgeNode       prev;         // Previous edge in the AET          \r
1220        EdgeNode       next;         // Next edge in the AET              \r
1221        EdgeNode       pred;         // Edge connected at the lower end   \r
1222        EdgeNode       succ;         // Edge connected at the upper end   \r
1223        EdgeNode       next_bound;   // Pointer to next bound in LMT      \r
1224        public EdgeNode(float x, float y) { vertex_x = x; vertex_y = y; }\r
1225    }\r
1226    private static class AetTree { EdgeNode top_node; public void clear() { top_node = null; } }\r
1227 \r
1228    private static class EdgeTable {\r
1229        public EdgeNode[] edges = new EdgeNode[BIGNUM];\r
1230        public int entries;\r
1231        public void clear() { for(; entries >= 0; entries--) edges[entries] = null; entries = 0; }\r
1232        public void addNode(float x, float y) { edges[entries++] = newEdgeNode(x, y); }\r
1233        public EdgeNode getNode(int index) { return edges[index]; }\r
1234        public boolean NOT_RMAX(int i) { return (edges[PREV_INDEX(i, entries)].vertex_y > edges[i].vertex_y); }\r
1235        public boolean NOT_FMAX(int i) { return(edges[NEXT_INDEX(i, entries)].vertex_y > edges[i].vertex_y); }\r
1236        public boolean FWD_MIN(int i) {\r
1237            return ((edges[PREV_INDEX(i, entries)].vertex_y >= edges[i].vertex_y) &&\r
1238                    (edges[NEXT_INDEX(i, entries)].vertex_y >  edges[i].vertex_y));\r
1239        }\r
1240        public boolean REV_MIN(int i) {\r
1241            return ((edges[PREV_INDEX(i, entries)].vertex_y >  edges[i].vertex_y) &&\r
1242                    (edges[NEXT_INDEX(i, entries)].vertex_y >= edges[i].vertex_y));\r
1243        }\r
1244    }\r
1245 \r
1246    private static class LmtTable {\r
1247        float[] y = new float[BIGNUM];\r
1248        EdgeNode[] first_bound = new EdgeNode[BIGNUM];\r
1249        int numentries = 0;\r
1250        public void clear() { for(; numentries >= 0; numentries--) first_bound[numentries] = null; numentries = 0; }\r
1251        public int count() { return numentries; }\r
1252        public boolean isEmpty() { return numentries == 0; }\r
1253        public int add(float y0, EdgeNode e) {\r
1254            for(int i=0; i<numentries; i++)\r
1255                if (y[i] == y0) return i;\r
1256                else if (y[i] > y0) {\r
1257                    System.arraycopy(y, i, y, i+1, numentries-i);\r
1258                    System.arraycopy(first_bound, i, first_bound, i+1, numentries-i);\r
1259                    y[i] = y0;\r
1260                    first_bound[i] = e;\r
1261                    numentries++;\r
1262                    return i;\r
1263                }\r
1264            y[numentries] = y0;\r
1265            first_bound[numentries] = e;\r
1266            return numentries++;\r
1267        }\r
1268    }\r
1269 \r
1270    private static class ScanBeamList {\r
1271        public int entries = 0;\r
1272        public float[] floats = new float[BIGNUM];\r
1273        public void clear() { entries = 0; }\r
1274        public void add(float f) { floats[entries++] = f; }\r
1275        public float[] sort() {\r
1276            org.ibex.util.Vec.sortFloats(floats, 0, entries-1);\r
1277            int j = 0;\r
1278            for(int i=1; i<entries; i++) if (floats[j] != floats[i]) floats[++j] = floats[i];\r
1279            entries = j+1;\r
1280            return floats;\r
1281        }\r
1282    }\r
1283    \r
1284    private static class ItNodeTable {\r
1285        EdgeNode ie_0[] = new EdgeNode[BIGNUM];\r
1286        EdgeNode ie_1[] = new EdgeNode[BIGNUM];\r
1287        float x[] = new float[BIGNUM];\r
1288        float y[] = new float[BIGNUM];\r
1289        int num = 0;\r
1290        public void clear() { for(; num>=0; num--) { ie_0[num] = null; ie_1[num] = null; } num = 0; }\r
1291        public void build_intersection_table(AetTree aet, float dy) {\r
1292            int st = -1;\r
1293            // Process each AET edge \r
1294            for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next)\r
1295                if ((edge.bstate_ABOVE == BUNDLE_HEAD) ||\r
1296                    (edge.bundle_ABOVE_CLIP != 0) || (edge.bundle_ABOVE_SUBJ != 0))\r
1297                    st = add_st_edge(st, edge, dy);\r
1298            sort(0, num-1);\r
1299            for(;numst>=0; numst--) edge[numst] = null; numst = 0;\r
1300        }\r
1301        \r
1302        int numst = 0;\r
1303        EdgeNode edge[] = new EdgeNode[BIGNUM];    // Pointer to AET edge               \r
1304        float    xb[] = new float[BIGNUM];         // Scanbeam bottom x coordinate      \r
1305        float    xt[] = new float[BIGNUM];         // Scanbeam top x coordinate         \r
1306        float    dx[] = new float[BIGNUM];         // Change in x for a unit y increase \r
1307        int      prev[] = new int[BIGNUM];           // Previous edge in sorted list      \r
1308 \r
1309        private int add_st_edge(int st, EdgeNode e, float dy) {\r
1310            if (st == -1) { st = numst++; edge[st] = e; xb[st] = e.xb; xt[st] = e.xt; dx[st] = e.dx; prev[st] = -1; return st; }\r
1311            float den = (xt[st] - xb[st]) - (e.xt - e.xb);\r
1312 \r
1313            // If new edge and ST edge don't cross, No intersection - insert edge here (before the ST edge) \r
1314            if ((e.xt >= xt[st]) || (e.dx == dx[st]) || (Math.abs(den) <= GPC_EPSILON))\r
1315                { prev[numst] = st; st = numst++; edge[st] = e; xb[st] = e.xb; xt[st] = e.xt; dx[st] = e.dx; return st; }\r
1316 \r
1317            // Compute intersection between new edge and ST edge \r
1318            float r = (e.xb - xb[st]) / den;\r
1319            float x = xb[st] + r * (xt[st] - xb[st]);\r
1320            float y = r * dy;\r
1321            // Insert the edge pointers and the intersection point in the IT \r
1322            add_intersection(edge[st], e, x, y);\r
1323            prev[st] = add_st_edge(prev[st], e, dy);\r
1324            return st;\r
1325        }\r
1326        private void add_intersection(EdgeNode edge0, EdgeNode edge1, float x0, float y0) {\r
1327            ie_0[num] = edge0; ie_1[num] = edge1; x[num] = x0; y[num] = y0; num++; }\r
1328 \r
1329        public final void sort(int start, int end) {\r
1330            if(start >= end) return;\r
1331            if(end-start <= 6) {\r
1332                for(int i=start+1;i<=end;i++) {\r
1333                    float tmpa = y[i];\r
1334                    float tmpx = x[i];\r
1335                    EdgeNode tmpe0 = ie_0[i];\r
1336                    EdgeNode tmpe1 = ie_1[i];\r
1337                    int j;\r
1338                    for(j=i-1;j>=start;j--) {\r
1339                        if(y[j] <= tmpa) break;\r
1340                        y[j+1] = y[j];\r
1341                        x[j+1] = x[j];\r
1342                        ie_0[j+1] = ie_0[j];\r
1343                        ie_1[j+1] = ie_1[j];\r
1344                    }\r
1345                    y[j+1] = tmpa;\r
1346                    x[j+1] = tmpx;\r
1347                    ie_0[j+1] = tmpe0;\r
1348                    ie_1[j+1] = tmpe1;\r
1349                }\r
1350                return;\r
1351            }\r
1352            float pivot = y[end];\r
1353            int lo = start - 1;\r
1354            int hi = end;\r
1355            do {\r
1356                while(y[++lo] < pivot) { }\r
1357                while((hi > lo) && y[--hi] > pivot) { }\r
1358                swap(lo, hi);\r
1359            } while(lo < hi);\r
1360            swap(lo, end);\r
1361            sort(start, lo-1);\r
1362            sort(lo+1, end);\r
1363        }\r
1364        private final void swap(int a, int b) {\r
1365            if(a != b) {\r
1366                float tmp = x[a]; x[a] = x[b]; x[b] = tmp;\r
1367                tmp = y[a]; y[a] = y[b]; y[b] = tmp;\r
1368                EdgeNode tmpe = ie_0[a]; ie_0[a] = ie_0[b]; ie_0[b] = tmpe;\r
1369                tmpe = ie_1[a]; ie_1[a] = ie_1[b]; ie_1[b] = tmpe;\r
1370            }\r
1371        }\r
1372    }\r
1373 \r
1374 }\r