From 545a6bc7e6aff46ecb6012648fd9dd6f02588166 Mon Sep 17 00:00:00 2001
From: adam <adam@megacz.com>
Date: Mon, 3 May 2004 00:35:54 +0000
Subject: [PATCH] added Polygon.java

darcs-hash:20040503003554-5007d-399c7696ad7a8faf763d67614dc17c7d4c60fc83.gz
---
 src/org/ibex/graphics/Polygon.java | 1374 ++++++++++++++++++++++++++++++++++++
 1 file changed, 1374 insertions(+)
 create mode 100644 src/org/ibex/graphics/Polygon.java

diff --git a/src/org/ibex/graphics/Polygon.java b/src/org/ibex/graphics/Polygon.java
new file mode 100644
index 0000000..c99797c
--- /dev/null
+++ b/src/org/ibex/graphics/Polygon.java
@@ -0,0 +1,1374 @@
+package org.ibex.graphics;
+import java.util.*;
+import org.ibex.util.*;
+
+//
+// This is a very heavily modified (nearly complete rewrite) version
+// of GPCJ, which is itself a Java port of the Generalized Polygon
+// Clipping Library
+// 
+//   http://www.cs.man.ac.uk/aig/staff/alan/software/gpc.html
+//
+// Modifications by Adam Megacz
+//
+
+// Possible remaining optimizations:
+//   -- recycle EdgeNode instances
+//   -- evolve PolygonNode into the Polygon class?
+
+//
+// !! WARNING !!  !! WARNING !!  !! WARNING !!
+//
+// Unlike GPCJ, this code is NOT reentrant or thread-safe; static
+// arrays are used to avoid allocation penalties.  Also, the union(),
+// intersection(), and xor() methods destructively update the 'this'
+// object.
+//
+
+/*
+ * The SEI Software Open Source License, Version 1.0
+ *
+ * Copyright (c) 2004, Solution Engineering, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer. 
+ *
+ * 2. The end-user documentation included with the redistribution,
+ *    if any, must include the following acknowledgment:
+ *       "This product includes software developed by the
+ *        Solution Engineering, Inc. (http://www.seisw.com/)."
+ *    Alternately, this acknowledgment may appear in the software itself,
+ *    if and wherever such third-party acknowledgments normally appear.
+ *
+ * 3. The name "Solution Engineering" must not be used to endorse or
+ *    promote products derived from this software without prior
+ *    written permission. For written permission, please contact
+ *    admin@seisw.com.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED.  IN NO EVENT SHALL SOLUTION ENGINEERING, INC. OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * ====================================================================
+ */
+
+
+public final class Polygon {
+
+    private static final int DEFAULT_PATHLEN  =  10;
+    private static final int DEFAULT_CONTOURS =   4;
+
+    private static final int BIGNUM = 65535;
+
+    public boolean[] hole             = new boolean[DEFAULT_CONTOURS];
+    public boolean[] contributing     = new boolean[DEFAULT_CONTOURS];
+    public float[]   x                = new float[DEFAULT_PATHLEN];
+    public float[]   y                = new float[DEFAULT_PATHLEN];
+    public int       numvertices      = 0;
+    public int[]     edges            = null;
+    public int       numedges         = 0;
+    public int[]     contours         = new int[DEFAULT_CONTOURS];
+    public int       numcontours      = 0;
+    public float[]   minx_            = new float[DEFAULT_CONTOURS];
+    public float[]   miny_            = new float[DEFAULT_CONTOURS];
+    public float[]   maxx_            = new float[DEFAULT_CONTOURS];
+    public float[]   maxy_            = new float[DEFAULT_CONTOURS];
+    public float     minx             = Float.MAX_VALUE;
+    public float     miny             = Float.MAX_VALUE;
+    public float     maxx             = Float.MIN_VALUE;
+    public float     maxy             = Float.MIN_VALUE;
+    public boolean   sealed           = false;
+
+    public Polygon() { }
+    public Polygon(Path p, Affine a) { p.addTo(this, a); }
+    public void intersection(Polygon p2) { clip(GPC_INT, this, p2); }
+    public void intersect(Polygon p2) { clip(GPC_INT, this, p2); }
+    public void union(Polygon p2) { clip(GPC_UNION, this, p2); }
+    public void xor(Polygon p2) { clip(GPC_XOR, this, p2); }
+    public void subtract(Polygon p2) { clip(GPC_DIFF, this, p2); }
+    private static Polygon rectclipper = new Polygon();
+    public void addrect(float x1, float y1, float x2, float y2, Affine a) {
+        add(a.multiply_px(x1, y1), a.multiply_py(x1, y1));
+        add(a.multiply_px(x2, y1), a.multiply_py(x2, y1));
+        add(a.multiply_px(x2, y2), a.multiply_py(x2, y2));
+        add(a.multiply_px(x1, y2), a.multiply_py(x1, y2));
+        closepath();
+    }
+    public void clipto(float x1, float y1, float x2, float y2, Affine a) {
+        rectclipper.clear();
+        rectclipper.addrect(x1, y1, x2, y2, a);
+        intersection(rectclipper);
+    }
+    public void closepath() {
+        if (numcontours > 0 && numvertices == 0) return;
+        if (numcontours > 0 && (x[contours[numcontours-1]] != x[numvertices-1] || y[contours[numcontours-1]] != y[numvertices-1]))
+            add(x[contours[numcontours-1]], y[contours[numcontours-1]]);
+    }
+    public void newcontour() {
+        if (numcontours > 0 && numvertices == contours[numcontours-1]) return;
+        closepath();
+        maxx_[numcontours] = maxy_[numcontours] = Float.MIN_VALUE;
+        minx_[numcontours] = miny_[numcontours] = Float.MAX_VALUE;
+        contours[numcontours++] = numvertices;
+        if (numcontours >= contours.length - 2) {
+            int[] z = new int[contours.length * 4]; System.arraycopy(contours, 0, z, 0, contours.length); contours = z;
+            boolean[] s = new boolean[hole.length * 4]; System.arraycopy(hole, 0, s, 0, hole.length); hole = s;
+            s = new boolean[contributing.length * 4];System.arraycopy(contributing,0,s,0,contributing.length);contributing = s;
+            float[] f = new float[minx_.length * 4]; System.arraycopy(minx_, 0, f, 0, minx_.length); minx_ = f;
+            f = new float[maxx_.length * 4]; System.arraycopy(maxx_, 0, f, 0, maxx_.length); maxx_ = f;
+            f = new float[miny_.length * 4]; System.arraycopy(miny_, 0, f, 0, miny_.length); miny_ = f;
+            f = new float[maxy_.length * 4]; System.arraycopy(maxy_, 0, f, 0, maxy_.length); maxy_ = f;
+            Log.debug(this, "growing contour list to " + contours.length);
+        } 
+    }
+    public void add(float x, float y) {
+        if (sealed) { Log.error(this, "tried to add a vertex to a sealed polygon!"); return; }
+        if (numcontours == 0) newcontour();
+        this.x[numvertices] = x;
+        this.y[numvertices] = y;
+        numvertices++;
+        if (x > maxx_[numcontours-1]) maxx_[numcontours-1] = x;
+        if (x < minx_[numcontours-1]) minx_[numcontours-1] = x;
+        if (y > maxy_[numcontours-1]) maxy_[numcontours-1] = y;
+        if (y < miny_[numcontours-1]) miny_[numcontours-1] = y;
+        if (x > maxx) maxx = x;
+        if (x < minx) minx = x;
+        if (y > maxy) maxy = y;
+        if (y < miny) miny = y;
+        if (numvertices >= this.x.length) {
+            float[] new_x = new float[this.x.length * 4]; System.arraycopy(this.x, 0, new_x, 0, this.x.length); this.x = new_x;
+            float[] new_y = new float[this.y.length * 4]; System.arraycopy(this.y, 0, new_y, 0, this.y.length); this.y = new_y;
+            Log.debug(this, "growing vertex list to " + this.x.length);
+        } 
+    }
+    public void clear() {
+        numvertices = 0; numedges = 0; numcontours = 0; sealed = false;
+        maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE;
+    }
+    public boolean isEmpty() { return numvertices == 0; }
+    public void add(Polygon p) { add(p, Affine.identity()); }
+    public void add(Polygon p, Affine a) { for(int i=0; i<p.numcontours; i++) add(p, i, a); }
+    public void add(Polygon p, int idx) { add(p, idx, Affine.identity()); }
+    public void add(Polygon p, int idx, Affine a) {
+        newcontour();
+        for(int i=p.contours[idx]; i<p.contours[idx+1]; i++) {
+            float x = p.x[p.contours[idx]+i];
+            float y = p.y[p.contours[idx]+i];
+            add(a.multiply_px(x, y), a.multiply_py(x, y));
+        }
+    }
+    public void transform(Affine a) {
+        maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE;
+        int s = 0;
+        for(int i=0; i<numvertices; i++) {
+            while (i >= contours[s+1]) s++;
+            float x = a.multiply_px(this.x[i], this.y[i]);
+            float y = a.multiply_py(this.x[i], this.y[i]);
+            this.x[i] = x; 
+            this.y[i] = y; 
+            if (x > maxx_[s]) maxx_[s] = x;
+            if (x < minx_[s]) minx_[s] = x;
+            if (y > maxy_[s]) maxy_[s] = y;
+            if (y < miny_[s]) miny_[s] = y;
+            if (x > maxx) maxx = x;
+            if (x < minx) minx = x;
+            if (y > maxy) maxy = y;
+            if (y < miny) miny = y;
+        }
+    }
+
+    public void stroke(PixelBuffer buf, int color) {
+        Polygon p = this;
+        if (!p.sealed) p.sort();
+        for(int i=0; i<p.numedges; i++) {
+            float x1 = p.x[p.edges[i]];
+            float y1 = p.y[p.edges[i]];
+            float x2 = p.x[p.edges[i]+1];
+            float y2 = p.y[p.edges[i]+1];
+            long start = System.currentTimeMillis(); try {
+                buf.drawLine((int)Math.floor(x1), (int)Math.floor(y1), (int)Math.ceil(x2), (int)Math.ceil(y2), color);
+            } finally { Scheduler.drawing += System.currentTimeMillis() - start; }
+        }
+    }
+
+    /** finds the x value at which the line intercepts the line y=_y */
+    private int intercept(int i, float _y, boolean includeTop, boolean includeBottom) {
+        Polygon p = this;
+        if (includeTop ? (_y < Math.min(p.y[i], p.y[i+1])) : (_y <= Math.min(p.y[i], p.y[i+1])))
+            return Integer.MIN_VALUE;
+        if (includeBottom ? (_y > Math.max(p.y[i], p.y[i+1])) : (_y >= Math.max(p.y[i], p.y[i+1])))
+            return Integer.MIN_VALUE;
+        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];
+        return (int)Math.floor(f);
+    }
+
+    /** fill the interior of the path */
+    public void fill(PixelBuffer buf, Paint paint) {
+        Polygon p = this;
+        if (!p.sealed) p.sort();
+        if (p.numedges == 0) return;
+        float y0 = p.y[p.edges[0]], y1 = y0;
+        boolean useEvenOdd = false;
+
+        // we iterate over all endpoints in increasing y-coordinate order
+        OUTER: for(int index = 1; index<p.numedges; index++) {
+            int count = 0;
+
+            // we now examine the horizontal band between y=y0 and y=y1
+            y0 = y1;
+            y1 = p.y[p.edges[index]];
+            if (y0 == y1) continue;
+
+            // within this band, we iterate over all p.edges
+            int x0 = Integer.MIN_VALUE;
+            int leftSegment = -1;
+            while(true) {
+                int x1 = Integer.MAX_VALUE;
+                int rightSegment = Integer.MAX_VALUE;
+                for(int i=0; i<p.numedges; i++) {
+                    if (p.y[p.edges[i]] == p.y[p.edges[i]+1]) continue; // ignore horizontal lines; they are irrelevant.
+                    // we order the segments by the x-coordinate of their midpoint;
+                    // since segments cannot intersect, this is a well-ordering
+                    int i0 = intercept(p.edges[i], y0, true, false);
+                    int i1 = intercept(p.edges[i], y1, false, true);
+                    if (i0 == Integer.MIN_VALUE || i1 == Integer.MIN_VALUE) continue;
+                    int midpoint = i0 + i1;
+                    if (midpoint < x0) continue;
+                    if (midpoint == x0 && i <= leftSegment) continue;
+                    if (midpoint > x1) continue;
+                    if (midpoint == x1 && i >= rightSegment) continue;
+                    rightSegment = i;
+                    x1 = midpoint;
+                }
+                if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break;
+                if (leftSegment != -1)
+                    if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0)) {
+                        int tx1a = intercept(p.edges[leftSegment], y0, true, true);
+                        int tx1b = intercept(p.edges[rightSegment], y0, true, true);
+                        int tx2a = intercept(p.edges[leftSegment], y1, true, true);
+                        int tx2b = intercept(p.edges[rightSegment], y1, true, true);
+                        long start = System.currentTimeMillis(); try {
+                            buf.fillTrapezoid(tx1a, tx1b, (int)y0, tx2a, tx2b, (int)y1, ((Paint.SingleColorPaint)paint).color);
+                        } finally { Scheduler.drawing += System.currentTimeMillis() - start; }
+                    }
+                if (useEvenOdd) count++;
+                else count += (p.y[p.edges[rightSegment]] < p.y[p.edges[rightSegment]+1]) ? -1 : 1;
+                leftSegment = rightSegment; x0 = x1;
+            }
+        }
+    }
+
+    //////////////////////////////////////////////////////////////////////////////
+
+    public Polygon sort() {
+        closepath();
+        contours[numcontours] = numvertices;
+        sealed = true;
+        numedges = 0;
+        edges = new int[numvertices];
+        for(int i=0; i<numcontours; i++)
+            for(int j=contours[i]; j<contours[i+1]-1; j++)
+                edges[numedges++] = j;
+        sort(0, numedges - 1, false);
+        return this;
+    }
+
+    /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */
+    int sort(int left, int right, boolean partition) {
+        if (partition) {
+            int i, j, middle;
+            middle = (left + right) / 2;
+            int s = edges[right]; edges[right] = edges[middle]; edges[middle] = s;
+            for (i = left - 1, j = right; ; ) {
+                while (y[edges[++i]] < y[edges[right]]);
+                while (j > left && y[edges[--j]] > y[edges[right]]);
+                if (i >= j) break;
+                s = edges[i]; edges[i] = edges[j]; edges[j] = s;
+            }
+            s = edges[right]; edges[right] = edges[i]; edges[i] = s;
+            return i;
+        } else {
+            if (left >= right) return 0;
+            int p = sort(left, right, true);
+            sort(left, p - 1, false);
+            sort(p + 1, right, false);
+            return 0;
+        }
+    }
+
+    // Rendering //////////////////////////////////////////////////////////////////////////////
+
+       
+    private static int bound(int min, int mid, int max) { return mid < min ? min : mid > max ? max : mid; }
+
+    public String toString(int i) {
+        String ret = "    ";
+        for(int j=contours[i]; j<contours[i+1]; j++) ret += x[j]+","+y[j];
+        return ret + "\n";
+    }
+    public String toString() {
+        String ret = "Polygon\n";
+        for(int i=0; i<numcontours; i++) ret += toString(i);
+        return ret;
+    }
+
+
+    // GPC //////////////////////////////////////////////////////////////////////////////
+
+    //private static final float GPC_EPSILON = 2.2204460492503131e-016 ;
+    private static final float GPC_EPSILON = (float)1e-8;
+    private static final String GPC_VERSION = "2.31" ;
+    private static final int LEFT  = 0 ;
+    private static final int RIGHT = 1 ;
+    private static final int ABOVE = 0 ;
+    private static final int BELOW = 1 ;
+    private static final int CLIP = 0 ;
+    private static final int SUBJ = 1 ;
+    
+    // evilbadnonthreadsafestuff
+    private static ScanBeamList sbte       = new ScanBeamList();
+    private static EdgeTable s_heap        = new EdgeTable();
+    private static EdgeTable c_heap        = new EdgeTable();
+    private static LmtTable lmt_table      = new LmtTable();
+    private static TopPolygonNode out_poly = new TopPolygonNode();
+    private static AetTree aet             = new AetTree();
+    private static ItNodeTable it_table    = new ItNodeTable();
+
+    private static Polygon clip(byte op, Polygon subj, Polygon clip) {
+        try {
+            long start = System.currentTimeMillis(); try {
+            return clip_(op, subj, clip);
+            } finally { Scheduler.clipping += System.currentTimeMillis() - start; }
+        } catch (Exception npe) {
+            npe.printStackTrace();
+            return null;
+        }
+    }
+    private static Polygon clip_(byte op, Polygon subj, Polygon clip) {
+      int parity_CLIP = LEFT;
+      int parity_SUBJ = LEFT;
+      float[] sbt = null;
+      int local_min = 0;
+      int scanbeam = 0;
+
+      numFreeEdgeNodes = numEdgeNodes;
+
+        subj.closepath(); subj.contours[subj.numcontours] = subj.numvertices;
+        clip.closepath(); clip.contours[clip.numcontours] = clip.numvertices;
+        PolygonNode.clear();
+
+      // Test for trivial NULL result cases 
+      if ((subj.isEmpty() && clip.isEmpty()) || (subj.isEmpty() && ((op == GPC_INT) || (op == GPC_DIFF))) ||
+          (clip.isEmpty() &&  (op == GPC_INT)))
+          { subj.clear(); return subj; }
+      
+      // Identify potentialy contributing contours 
+      if (((op == GPC_INT) || (op == GPC_DIFF)) && !subj.isEmpty() && !clip.isEmpty())
+         minimax_test(subj, clip, op);
+      
+      // Build LMT 
+      lmt_table.clear();
+      sbte.clear();
+      s_heap.clear();
+      c_heap.clear();
+      if (!subj.isEmpty()) build_lmt(s_heap, lmt_table, sbte, subj, SUBJ, op);
+      if (!clip.isEmpty()) build_lmt(c_heap, lmt_table, sbte, clip, CLIP, op);
+      if (lmt_table.isEmpty()) { subj.clear(); return subj; }    // Return a NULL result if no contours contribute
+
+      // Build scanbeam table from scanbeam tree 
+            sbt = sbte.sort();
+      // Invert clip polygon for difference operation 
+      if (op == GPC_DIFF) parity_CLIP = RIGHT;
+      out_poly.clear();
+      aet.clear();
+      
+      // Process each scanbeam 
+      while(scanbeam < sbte.entries) {
+         // Set yb and yt to the bottom and top of the scanbeam 
+         float yb = sbt[scanbeam++];
+         float yt = (float)0.0;
+         float dy = (float)0.0;
+         if (scanbeam < sbte.entries) { yt = sbt[scanbeam]; dy = yt - yb; }
+  
+         // === SCANBEAM BOUNDARY PROCESSING ================================ 
+         // If LMT node corresponding to yb exists 
+         if (local_min < lmt_table.numentries && lmt_table.y[local_min] == yb) {
+             // Add edges starting at this local minimum to the AET 
+             for(EdgeNode edge = lmt_table.first_bound[local_min]; (edge != null); edge= edge.next_bound)
+                 add_edge_to_aet(aet, edge);
+             local_min++;
+         }
+         
+         float px = -Float.MAX_VALUE;    // Set dummy previous x value
+         EdgeNode e0 = aet.top_node;       // Create bundles within AET
+         EdgeNode e1 = aet.top_node;
+         
+         // Set up bundle fields of first edge 
+         if (aet.top_node.type == CLIP) aet.top_node.bundle_ABOVE_CLIP = (aet.top_node.top_y != yb) ? 1 : 0;
+         else aet.top_node.bundle_ABOVE_SUBJ = (aet.top_node.top_y != yb) ? 1 : 0;
+
+         if (((aet.top_node.type==0) ? 1 : 0) == CLIP) aet.top_node.bundle_ABOVE_CLIP = 0;
+         else aet.top_node.bundle_ABOVE_SUBJ = 0;
+         aet.top_node.bstate_ABOVE = UNBUNDLED;
+
+         for (EdgeNode next_edge = aet.top_node.next; next_edge != null; next_edge = next_edge.next) {
+            int ne_type = next_edge.type;
+            int ne_type_opp = ((next_edge.type==0) ? 1 : 0);  // next edge type opposite
+            
+            // Set up bundle fields of next edge 
+            if (ne_type     == CLIP) next_edge.bundle_ABOVE_CLIP = (next_edge.top_y != yb) ? 1 : 0;
+            else next_edge.bundle_ABOVE_SUBJ = (next_edge.top_y != yb) ? 1 : 0;                
+            if (ne_type_opp == CLIP) next_edge.bundle_ABOVE_CLIP  = 0;
+            else next_edge.bundle_ABOVE_SUBJ  = 0;                
+            next_edge.bstate_ABOVE = UNBUNDLED;
+            
+            // Bundle edges above the scanbeam boundary if they coincide 
+            if ((ne_type == CLIP ? next_edge.bundle_ABOVE_CLIP : next_edge.bundle_ABOVE_SUBJ) == 1) {
+               if (EQ(e0.xb, next_edge.xb) && EQ(e0.dx, next_edge.dx) && (e0.top_y != yb)) {
+                   if (ne_type == CLIP)
+                       next_edge.bundle_ABOVE_CLIP ^= ne_type == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;
+                   else next_edge.bundle_ABOVE_SUBJ  ^= ne_type == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;
+                   if (ne_type_opp == CLIP)
+                       next_edge.bundle_ABOVE_CLIP = ne_type_opp == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;
+                   else next_edge.bundle_ABOVE_SUBJ = ne_type_opp == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;
+                  next_edge.bstate_ABOVE = BUNDLE_HEAD;
+                  e0.bundle_ABOVE_CLIP = 0;
+                  e0.bundle_ABOVE_SUBJ = 0;
+                  e0.bstate_ABOVE = BUNDLE_TAIL;
+               }
+               e0 = next_edge;
+            }
+         }
+         
+         int horiz_CLIP = HState.NH;
+         int horiz_SUBJ = HState.NH;
+         int exists_CLIP = 0;
+         int exists_SUBJ = 0;
+         PolygonNode cf = null;
+         
+         // Process each edge at this scanbeam boundary 
+         for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {
+             exists_CLIP = edge.bundle_ABOVE_CLIP + (edge.bundle_BELOW_CLIP << 1);
+             exists_SUBJ = edge.bundle_ABOVE_SUBJ + (edge.bundle_BELOW_SUBJ << 1);
+         
+            if ((exists_CLIP != 0) || (exists_SUBJ != 0)) {   // Set bundle side 
+               edge.bside_CLIP = parity_CLIP;
+               edge.bside_SUBJ = parity_SUBJ;
+               boolean contributing = false;
+               int br=0, bl=0, tr=0, tl=0;
+               // Determine contributing status and quadrant occupancies 
+               switch(op) {
+                   case GPC_DIFF:
+                   case GPC_INT:
+                       contributing= ((exists_CLIP!=0) && ((parity_SUBJ!=0) || (horiz_SUBJ!=0))) ||
+                           ((exists_SUBJ!=0) && ((parity_CLIP!=0) || (horiz_CLIP!=0))) ||
+                           ((exists_CLIP!=0) && (exists_SUBJ!=0) && (parity_CLIP == parity_SUBJ));
+                       br = ((parity_CLIP!=0) && (parity_SUBJ!=0)) ? 1 : 0;
+                       bl = (((parity_CLIP ^ edge.bundle_ABOVE_CLIP)!=0) &&
+                             ((parity_SUBJ ^ edge.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;
+                       tr = (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0)) !=0) && 
+                             ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0)) !=0)) ? 1 : 0;
+                       tl = (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)!=0) &&
+                             ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ)!=0))?1:0;
+                       break;
+
+                   case GPC_XOR:
+                       contributing= (exists_CLIP!=0) || (exists_SUBJ!=0);
+                       br= (parity_CLIP) ^ (parity_SUBJ);
+                       bl= (parity_CLIP ^ edge.bundle_ABOVE_CLIP) ^ (parity_SUBJ ^ edge.bundle_ABOVE_SUBJ);
+                       tr= (parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0)) ^ (parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0));
+                       tl= (parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)
+                           ^ (parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ);
+                       break;
+
+                   case GPC_UNION:
+                       contributing= ((exists_CLIP!=0) && (!(parity_SUBJ!=0) || (horiz_SUBJ!=0))) ||
+                           ((exists_SUBJ!=0) && (!(parity_CLIP!=0) || (horiz_CLIP!=0))) ||
+                           ((exists_CLIP!=0) && (exists_SUBJ!=0) && (parity_CLIP == parity_SUBJ));
+                       br= ((parity_CLIP!=0) || (parity_SUBJ!=0))?1:0;
+                       bl= (((parity_CLIP ^ edge.bundle_ABOVE_CLIP)!=0) || ((parity_SUBJ ^ edge.bundle_ABOVE_SUBJ)!=0))?1:0;
+                       tr= (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0))!=0) || 
+                            ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0))!=0)) ?1:0;
+                       tl= (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)!=0) ||
+                            ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ)!=0)) ? 1:0;
+                       break;
+                   default: throw new IllegalStateException("Unknown op");
+               }
+               
+               // Update parity 
+               parity_CLIP ^= edge.bundle_ABOVE_CLIP;
+               parity_SUBJ ^= edge.bundle_ABOVE_SUBJ;
+               
+               // Update horizontal state 
+               if (exists_CLIP!=0) horiz_CLIP = HState.next_h_state[horiz_CLIP][((exists_CLIP - 1) << 1) + parity_CLIP];
+               if (exists_SUBJ!=0) horiz_SUBJ = HState.next_h_state[horiz_SUBJ][((exists_SUBJ - 1) << 1) + parity_SUBJ];
+               
+               if (contributing) {
+                   float xb = edge.xb;
+                   int vclass = VertexType.getType(tr, tl, br, bl);
+                   switch (vclass) {
+                     case VertexType.EMN:
+                     case VertexType.IMN:
+                        edge.outp_ABOVE = out_poly.add_local_min(xb, yb);
+                        px = xb;
+                        cf = edge.outp_ABOVE;
+                        break;
+                     case VertexType.ERI:
+                        if (xb != px) { cf.add_right(xb, yb); px= xb; }
+                        edge.outp_ABOVE= cf;
+                        cf= null;
+                        break;
+                     case VertexType.ELI:
+                        edge.outp_BELOW.add_left(xb, yb);
+                        px= xb;
+                        cf= edge.outp_BELOW;
+                        break;
+                     case VertexType.EMX:
+                        if (xb != px) { cf.add_left(xb, yb); px= xb; }
+                        out_poly.merge_right(cf, edge.outp_BELOW);
+                        cf= null;
+                        break;
+                     case VertexType.ILI:
+                        if (xb != px) { cf.add_left(xb, yb); px= xb; }
+                        edge.outp_ABOVE= cf;
+                        cf= null;
+                        break;
+                     case VertexType.IRI:
+                        edge.outp_BELOW.add_right(xb, yb);
+                        px= xb;
+                        cf= edge.outp_BELOW;
+                        edge.outp_BELOW= null;
+                        break;
+                     case VertexType.IMX:
+                        if (xb != px) { cf.add_right(xb, yb); px= xb; }
+                        out_poly.merge_left(cf, edge.outp_BELOW);
+                        cf= null;
+                        edge.outp_BELOW= null;
+                        break;
+                     case VertexType.IMM:
+                        if (xb != px) { cf.add_right(xb, yb); px= xb; }
+                        out_poly.merge_left(cf, edge.outp_BELOW);
+                        edge.outp_BELOW= null;
+                        edge.outp_ABOVE = out_poly.add_local_min(xb, yb);
+                        cf= edge.outp_ABOVE;
+                        break;
+                     case VertexType.EMM:
+                        if (xb != px) { cf.add_left(xb, yb); px= xb; }
+                        out_poly.merge_right(cf, edge.outp_BELOW);
+                        edge.outp_BELOW= null;
+                        edge.outp_ABOVE = out_poly.add_local_min(xb, yb);
+                        cf= edge.outp_ABOVE;
+                        break;
+                     case VertexType.LED:
+                        if (edge.bot_y == yb) edge.outp_BELOW.add_left(xb, yb);
+                        edge.outp_ABOVE= edge.outp_BELOW;
+                        px= xb;
+                        break;
+                     case VertexType.RED:
+                        if (edge.bot_y == yb) edge.outp_BELOW.add_right(xb, yb);
+                        edge.outp_ABOVE= edge.outp_BELOW;
+                        px= xb;
+                        break;
+                     default:
+                        break;
+                  } // End of switch 
+               } // End of contributing conditional 
+            } // End of edge exists conditional 
+         } // End of AET loop 
+         
+         // Delete terminating edges from the AET, otherwise compute xt 
+         for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {
+            if (edge.top_y == yb) {
+                EdgeNode prev_edge = edge.prev;
+                EdgeNode next_edge= edge.next;
+               
+               if (prev_edge != null) prev_edge.next = next_edge;
+               else aet.top_node = next_edge;
+               if (next_edge != null) next_edge.prev = prev_edge;
+               
+               // Copy bundle head state to the adjacent tail edge if required 
+               if ((edge.bstate_BELOW == BUNDLE_HEAD) && (prev_edge!=null)) {
+                  if (prev_edge.bstate_BELOW == BUNDLE_TAIL) {
+                     prev_edge.outp_BELOW= edge.outp_BELOW;
+                     prev_edge.bstate_BELOW= UNBUNDLED;
+                     if (prev_edge.prev != null) {
+                        if (prev_edge.prev.bstate_BELOW == BUNDLE_TAIL)
+                           prev_edge.bstate_BELOW = BUNDLE_HEAD;
+                     }
+                  }
+               }
+            } else {
+               if (edge.top_y == yt) edge.xt = edge.top_x;
+               else edge.xt= edge.bot_x + edge.dx * (yt - edge.bot_y);
+            }
+         }
+                  
+         if (scanbeam < sbte.entries) {
+            // === SCANBEAM INTERIOR PROCESSING ============================== 
+            // Build intersection table for the current scanbeam 
+             it_table.clear();
+             it_table.build_intersection_table(aet, dy);
+         
+            // Process each node in the intersection table 
+            for (int intersect = 0; intersect < it_table.num; intersect++) {
+               e0 = it_table.ie_0[intersect];
+               e1 = it_table.ie_1[intersect];
+               
+               // Only generate output for contributing intersections 
+               if (((e0.bundle_ABOVE_CLIP!=0) || (e0.bundle_ABOVE_SUBJ!=0)) &&
+                   ((e1.bundle_ABOVE_CLIP!=0) || (e1.bundle_ABOVE_SUBJ!=0))) {
+
+                  PolygonNode p = e0.outp_ABOVE;
+                  PolygonNode q = e1.outp_ABOVE;
+                  float ix = it_table.x[intersect];
+                  float iy = it_table.y[intersect] + yb;
+               
+                  int in_clip = (((e0.bundle_ABOVE_CLIP!=0) && !(e0.bside_CLIP!=0)) ||
+                                  ((e1.bundle_ABOVE_CLIP!=0) &&  (e1.bside_CLIP!=0)) ||
+                                  (!(e0.bundle_ABOVE_CLIP!=0) && !(e1.bundle_ABOVE_CLIP!=0) &&
+                                    (e0.bside_CLIP!=0) && (e1.bside_CLIP!=0))) ? 1 : 0;
+                  
+                  int in_subj = (((e0.bundle_ABOVE_SUBJ!=0) && !(e0.bside_SUBJ!=0)) ||
+                                  ((e1.bundle_ABOVE_SUBJ!=0) &&  (e1.bside_SUBJ!=0)) ||
+                                  (!(e0.bundle_ABOVE_SUBJ!=0) && !(e1.bundle_ABOVE_SUBJ!=0) &&
+                                    (e0.bside_SUBJ!=0) && (e1.bside_SUBJ!=0))) ? 1 : 0;
+        
+                  int tr=0, tl=0, br=0, bl=0;
+                  // Determine quadrant occupancies 
+                  switch(op) {
+                      case GPC_DIFF:
+                      case GPC_INT:
+                          tr= ((in_clip!=0) && (in_subj!=0)) ? 1 : 0;
+                          tl= (((in_clip ^ e1.bundle_ABOVE_CLIP)!=0) && ((in_subj ^ e1.bundle_ABOVE_SUBJ)!=0))?1:0;
+                          br= (((in_clip ^ e0.bundle_ABOVE_CLIP)!=0) && ((in_subj ^ e0.bundle_ABOVE_SUBJ)!=0))?1:0;
+                          bl= (((in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)!=0) &&
+                               ((in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1:0;
+                          break;
+                      case GPC_XOR:
+                          tr= (in_clip)^ (in_subj);
+                          tl= (in_clip ^ e1.bundle_ABOVE_CLIP) ^ (in_subj ^ e1.bundle_ABOVE_SUBJ);
+                          br= (in_clip ^ e0.bundle_ABOVE_CLIP) ^ (in_subj ^ e0.bundle_ABOVE_SUBJ);
+                          bl= (in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)
+                              ^ (in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ);
+                          break;
+                      case GPC_UNION:
+                          tr= ((in_clip!=0) || (in_subj!=0)) ? 1 : 0;
+                          tl= (((in_clip ^ e1.bundle_ABOVE_CLIP)!=0) || ((in_subj ^ e1.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;
+                          br= (((in_clip ^ e0.bundle_ABOVE_CLIP)!=0) || ((in_subj ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;
+                          bl= (((in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)!=0) ||
+                               ((in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;
+                          break;
+                      default: throw new IllegalStateException("Unknown op type, "+op);
+                  }
+                  
+                  int vclass = VertexType.getType(tr, tl, br, bl);
+                  switch (vclass) {
+                     case VertexType.EMN:
+                        e0.outp_ABOVE = out_poly.add_local_min(ix, iy);
+                        e1.outp_ABOVE = e0.outp_ABOVE;
+                        break;
+                     case VertexType.ERI:
+                        if (p != null) { p.add_right(ix, iy); e1.outp_ABOVE= p; e0.outp_ABOVE= null; }
+                        break;
+                     case VertexType.ELI:
+                        if (q != null) { q.add_left(ix, iy); e0.outp_ABOVE= q; e1.outp_ABOVE= null; }
+                        break;
+                     case VertexType.EMX:
+                        if ((p!=null) && (q!=null)) {
+                            p.add_left(ix, iy);
+                            out_poly.merge_right(p, q);
+                            e0.outp_ABOVE= null;
+                           e1.outp_ABOVE= null;
+                        }
+                        break;
+                     case VertexType.IMN:
+                        e0.outp_ABOVE = out_poly.add_local_min(ix, iy);
+                        e1.outp_ABOVE = e0.outp_ABOVE;
+                        break;
+                     case VertexType.ILI:
+                        if (p != null) {
+                           p.add_left(ix, iy);
+                           e1.outp_ABOVE= p;
+                           e0.outp_ABOVE= null;
+                        }
+                        break;
+                     case VertexType.IRI:
+                        if (q!=null) {
+                           q.add_right(ix, iy);
+                           e0.outp_ABOVE= q;
+                           e1.outp_ABOVE= null;
+                        }
+                        break;
+                     case VertexType.IMX:
+                        if ((p!=null) && (q!=null)) {
+                            p.add_right(ix, iy);
+                            out_poly.merge_left(p, q);
+                            e0.outp_ABOVE= null;
+                            e1.outp_ABOVE= null;
+                        }
+                        break;
+                     case VertexType.IMM:
+                        if ((p!=null) && (q!=null)) {
+                            p.add_right(ix, iy);
+                            out_poly.merge_left(p, q);
+                            e0.outp_ABOVE = out_poly.add_local_min(ix, iy);
+                            e1.outp_ABOVE= e0.outp_ABOVE;
+                        }
+                        break;
+                     case VertexType.EMM:
+                        if ((p!=null) && (q!=null)) {
+                            p.add_left(ix, iy);
+                            out_poly.merge_right(p, q);
+                            e0.outp_ABOVE = out_poly.add_local_min(ix, iy);
+                            e1.outp_ABOVE = e0.outp_ABOVE;
+                        }
+                        break;
+                     default: break;
+                  } // End of switch 
+               } // End of contributing intersection conditional 
+                  
+               // Swap bundle sides in response to edge crossing 
+               if (e0.bundle_ABOVE_CLIP!=0) e1.bside_CLIP = (e1.bside_CLIP==0)?1:0;
+               if (e1.bundle_ABOVE_CLIP!=0) e0.bside_CLIP= (e0.bside_CLIP==0)?1:0;
+               if (e0.bundle_ABOVE_SUBJ!=0) e1.bside_SUBJ= (e1.bside_SUBJ==0)?1:0;
+               if (e1.bundle_ABOVE_SUBJ!=0) e0.bside_SUBJ= (e0.bside_SUBJ==0)?1:0;
+
+               // Swap e0 and e1 bundles in the AET 
+               EdgeNode prev_edge = e0.prev;
+               EdgeNode next_edge = e1.next;
+               if (next_edge != null) next_edge.prev = e0;
+   
+               if (e0.bstate_ABOVE == BUNDLE_HEAD) {
+                  boolean search = true;
+                  while (search) {
+                      prev_edge= prev_edge.prev;
+                      if (prev_edge != null) {
+                          if (prev_edge.bstate_ABOVE != BUNDLE_TAIL)
+                              search= false;
+                      } else {
+                          search= false;
+                      }
+                  }
+               }
+               if (prev_edge == null) {
+                  aet.top_node.prev = e1;
+                  e1.next           = aet.top_node;
+                  aet.top_node      = e0.next;
+               } else {
+                   prev_edge.next.prev = e1;
+                   e1.next             = prev_edge.next;
+                   prev_edge.next      = e0.next;
+               }
+               e0.next.prev = prev_edge;
+               e1.next.prev = e1;
+               e0.next      = next_edge;
+            } // End of IT loop
+               
+            // Prepare for next scanbeam 
+            for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {
+               EdgeNode next_edge = edge.next;
+               EdgeNode succ_edge = edge.succ;
+               if ((edge.top_y == yt) && (succ_edge!=null)) {
+                  // Replace AET edge by its successor 
+                  succ_edge.outp_BELOW= edge.outp_ABOVE;
+                  succ_edge.bstate_BELOW= edge.bstate_ABOVE;
+                  succ_edge.bundle_BELOW_CLIP= edge.bundle_ABOVE_CLIP;
+                  succ_edge.bundle_BELOW_SUBJ= edge.bundle_ABOVE_SUBJ;
+                  EdgeNode prev_edge = edge.prev;
+                  if (prev_edge != null) prev_edge.next = succ_edge;
+                  else aet.top_node = succ_edge;
+                  if (next_edge != null) next_edge.prev= succ_edge;
+                  succ_edge.prev = prev_edge;
+                  succ_edge.next = next_edge;
+               } else {
+                   // Update this edge 
+                   edge.outp_BELOW= edge.outp_ABOVE;
+                   edge.bstate_BELOW= edge.bstate_ABOVE;
+                   edge.bundle_BELOW_CLIP= edge.bundle_ABOVE_CLIP;
+                   edge.bundle_BELOW_SUBJ= edge.bundle_ABOVE_SUBJ;
+                   edge.xb= edge.xt;
+               }
+               edge.outp_ABOVE= null;
+            }
+         }
+      } // === END OF SCANBEAM PROCESSING ================================== 
+
+      // Generate result polygon from out_poly 
+      subj.clear();
+      return out_poly.getResult(subj);
+   }
+   
+    private static boolean EQ(float a, float b) { return (Math.abs(a - b) <= GPC_EPSILON); }
+    private static int PREV_INDEX(int i, int n) { return ((i - 1 + n) % n); }
+    private static int NEXT_INDEX(int i, int n) { return ((i + 1   ) % n); }
+    private static boolean OPTIMAL(Polygon p, int index, int i) {
+        return (p.y[p.contours[index] + PREV_INDEX(i, p.contours[index+1]-p.contours[index])] != p.y[p.contours[index] + i]) ||
+            (p.y[p.contours[index] + NEXT_INDEX(i, p.contours[index+1]-p.contours[index])] != p.y[p.contours[index] + i]);
+    }
+   
+   private static void minimax_test(Polygon subj, Polygon clip, byte op) {
+      // For each clip contour, search for any subject contour overlaps 
+      for(int c=0; c < clip.numcontours; c++) {
+         boolean overlap = false;
+         for(int s = 0; !overlap && (s < subj.numcontours); s++)
+             overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) &&
+                 (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c])));
+         clip.contributing[c] = overlap;
+      }  
+      if (op != GPC_INT) return;
+      // For each subject contour, search for any clip contour overlaps 
+      for (int s=0; s < subj.numcontours; s++) {
+          boolean overlap = false;
+          for (int c=0; !overlap && (c < clip.numcontours); c++)
+              overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) &&
+                  (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c])));
+          subj.contributing[s] = overlap;
+      }
+   }
+
+   private static void insert_bound(LmtTable lmt_table, float y, EdgeNode e) {
+      int index = lmt_table.add(y, null);
+      // Link node e to the tail of the list 
+      if (lmt_table.first_bound[index] == null) { lmt_table.first_bound[index] = e; return; }
+      EdgeNode prev_bound = null;
+      EdgeNode current_bound = lmt_table.first_bound[index];
+      while(true)
+          // Do primary sort on the x field 
+          if (e.bot_x <  current_bound.bot_x) {
+              // Insert a new node mid-list 
+              if (prev_bound == null) lmt_table.first_bound[index] = e;
+              else prev_bound.next_bound = e;
+              e.next_bound = current_bound;
+              break;
+          } else if (e.bot_x == current_bound.bot_x) {
+              // Do secondary sort on the dx field 
+              if (e.dx < current_bound.dx) {
+                  // Insert a new node mid-list 
+                  if (prev_bound == null) lmt_table.first_bound[index] = e;
+                  else prev_bound.next_bound = e;
+                  e.next_bound = current_bound;
+                  break;
+              }
+              // Head further down the list 
+              if (current_bound.next_bound == null) { current_bound.next_bound = e; break; }
+              prev_bound = current_bound;
+              current_bound = current_bound.next_bound;
+          } else {
+              // Head further down the list 
+              if (current_bound.next_bound == null) { current_bound.next_bound = e; break; }
+              prev_bound = current_bound;
+              current_bound = current_bound.next_bound;
+          }
+   }
+   
+   private static void add_edge_to_aet(AetTree aet, EdgeNode edge) {
+      if (aet.top_node == null) {
+         // Append edge onto the tail end of the AET 
+         aet.top_node = edge;
+         edge.prev = null;
+         edge.next= null;
+         return;
+      }
+      EdgeNode current_edge = aet.top_node;
+      EdgeNode prev = null;
+      while(true)
+          // Do primary sort on the xb field 
+          if (edge.xb < current_edge.xb) {
+              // Insert edge here (before the AET edge) 
+              edge.prev= prev;
+              edge.next= current_edge;
+              current_edge.prev = edge;
+              if (prev == null) aet.top_node = edge;
+              else prev.next = edge;
+              break;
+          } else if (edge.xb == current_edge.xb) {
+              // Do secondary sort on the dx field 
+              if (edge.dx < current_edge.dx) {
+                  // Insert edge here (before the AET edge) 
+                  edge.prev= prev;
+                  edge.next= current_edge;
+                  current_edge.prev = edge;
+                  if (prev == null) aet.top_node = edge;
+                  else prev.next = edge;
+                  break;
+               }
+              // Head further into the AET 
+              prev = current_edge;
+              if (current_edge.next == null) {
+                  current_edge.next = edge;
+                  edge.prev = current_edge;
+                  edge.next = null;
+                  break;
+              }
+              current_edge = current_edge.next;
+          } else {
+              // Head further into the AET 
+              prev = current_edge;
+              if (current_edge.next == null) {
+                  current_edge.next = edge;
+                  edge.prev = current_edge;
+                  edge.next = null;
+                  break;
+               }
+              current_edge = current_edge.next;
+          }
+   }
+
+   private static void build_lmt(EdgeTable edge_table, LmtTable lmt_table, ScanBeamList sbte, Polygon p, int type, byte op) {
+      for (int c=0; c < p.numcontours; c++) {
+          if (!p.contributing[c]) { p.contributing[c] = true; continue; }
+          // Perform contour optimisation 
+          int num_vertices= 0;
+          int e_index = 0;
+          edge_table.clear();
+          for (int i= 0; i < p.contours[c+1] - p.contours[c]; i++)
+              if (OPTIMAL(p, c, i)) {
+                 edge_table.addNode(p.x[p.contours[c]+i], p.y[p.contours[c]+i]);
+                 sbte.add(p.y[p.contours[c]+i]);  // Record vertex in the scanbeam table 
+                 num_vertices++;
+              }
+           
+         // Do the contour forward pass 
+         for (int min= 0; min < num_vertices; min++) {
+             // If a forward local minimum... 
+             if (edge_table.FWD_MIN(min)) {
+                 // Search for the next local maximum... 
+                 int num_edges = 1;
+                 int max = NEXT_INDEX(min, num_vertices);
+                 while(edge_table.NOT_FMAX(max)) { num_edges++; max = NEXT_INDEX(max, num_vertices); }
+
+                 // Build the next edge list 
+                 int v = min;
+                 EdgeNode e = edge_table.getNode(e_index);
+                 e.bstate_BELOW = UNBUNDLED;
+                 e.bundle_BELOW_CLIP = 0;
+                 e.bundle_BELOW_SUBJ = 0;
+                  
+                 for (int i= 0; i < num_edges; i++) {
+                     EdgeNode ei = edge_table.getNode(e_index+i);
+                     EdgeNode ev = edge_table.getNode(v);
+                     ei.xb    = ev.vertex_x;
+                     ei.bot_x = ev.vertex_x;
+                     ei.bot_y = ev.vertex_y;
+                     v = NEXT_INDEX(v, num_vertices);
+                     ev = edge_table.getNode(v);
+                     ei.top_x= ev.vertex_x;
+                     ei.top_y= ev.vertex_y;
+                     ei.dx= (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y);
+                     ei.type = type;
+                     ei.outp_ABOVE = null;
+                     ei.outp_BELOW = null;
+                     ei.next = null;
+                     ei.prev = null;
+                     ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;
+                     ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null;
+                     ei.next_bound = null;
+                     ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT;
+                     ei.bside_SUBJ = LEFT;
+                 }
+                 insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e);
+                 e_index += num_edges;
+             }
+         }
+
+         // Do the contour reverse pass 
+         for (int min= 0; min < num_vertices; min++) {
+             // If a reverse local minimum... 
+             if (edge_table.REV_MIN(min)) {
+                 // Search for the previous local maximum... 
+                 int num_edges= 1;
+                 int max = PREV_INDEX(min, num_vertices);
+                 while(edge_table.NOT_RMAX(max)) { num_edges++; max = PREV_INDEX(max, num_vertices); }
+                 // Build the previous edge list 
+                 int v = min;
+                 EdgeNode e = edge_table.getNode(e_index);
+                 e.bstate_BELOW = UNBUNDLED;
+                 e.bundle_BELOW_CLIP = 0;
+                 e.bundle_BELOW_SUBJ = 0;
+                 for (int i= 0; i < num_edges; i++) {
+                     EdgeNode ei = edge_table.getNode(e_index+i);
+                     EdgeNode ev = edge_table.getNode(v);
+                     ei.xb    = ev.vertex_x;
+                     ei.bot_x = ev.vertex_x;
+                     ei.bot_y = ev.vertex_y;
+                     v= PREV_INDEX(v, num_vertices);
+                     ev = edge_table.getNode(v);
+                     ei.top_x = ev.vertex_x;
+                     ei.top_y = ev.vertex_y;
+                     ei.dx = (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y);
+                     ei.type = type;
+                     ei.outp_ABOVE = null;
+                     ei.outp_BELOW = null;
+                     ei.next = null;
+                     ei.prev = null;
+                     ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;
+                     ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null;
+                     ei.next_bound = null;
+                     ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT;
+                     ei.bside_SUBJ = LEFT;
+                 }
+                 insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e);
+                 e_index+= num_edges;
+             }
+         }
+      }
+   }
+
+    public static final byte GPC_DIFF  = 0;
+    public static final byte GPC_INT   = 1;
+    public static final byte GPC_XOR   = 2;
+    public static final byte GPC_UNION = 3;
+
+    // Edge intersection classes
+   private static class VertexType {
+      public static final int NUL =  0; // Empty non-intersection            
+      public static final int EMX =  1; // External maximum                  
+      public static final int ELI =  2; // External left intermediate        
+      public static final int TED =  3; // Top edge                          
+      public static final int ERI =  4; // External right intermediate       
+      public static final int RED =  5; // Right edge                        
+      public static final int IMM =  6; // Internal maximum and minimum      
+      public static final int IMN =  7; // Internal minimum                  
+      public static final int EMN =  8; // External minimum                  
+      public static final int EMM =  9; // External maximum and minimum      
+      public static final int LED = 10; // Left edge                         
+      public static final int ILI = 11; // Internal left intermediate        
+      public static final int BED = 12; // Bottom edge                       
+      public static final int IRI = 13; // Internal right intermediate       
+      public static final int IMX = 14; // Internal maximum                  
+      public static final int FUL = 15; // Full non-intersection             
+      public static int getType(int tr, int tl, int br, int bl) { return tr + (tl << 1) + (br << 2) + (bl << 3); }
+   }
+   
+   private static class HState {
+      public static final int NH = 0; // No horizontal edge                
+      public static final int BH = 1; // Bottom horizontal edge            
+      public static final int TH = 2; // Top horizontal edge               
+      // Horizontal edge state transitions within scanbeam boundary 
+      public static final int[][] next_h_state =
+      {
+      //        ABOVE     BELOW     CROSS 
+      //        L   R     L   R     L   R 
+      /* NH */ {BH, TH,   TH, BH,   NH, NH},
+      /* BH */ {NH, NH,   NH, NH,   TH, TH},
+      /* TH */ {NH, NH,   NH, NH,   BH, BH}
+      };
+   }
+   
+    public static final byte UNBUNDLED   = 0; // Isolated edge not within a bundle
+    public static final byte BUNDLE_HEAD = 1; // Bundle head node
+    public static final byte BUNDLE_TAIL = 2; // Passive bundle tail node
+
+    private static class PolygonNode {
+        public static void clear() { numvertices = 1; }
+        private static final float[] x  = new float[BIGNUM];
+        private static final float[] y  = new float[BIGNUM];
+        private static final int[] nxt  = new int[BIGNUM];
+        private static int numvertices = 1;
+
+        int          active = 1;             // Active flag / vertex count        
+        boolean      hole;                   // Hole / external contour flag      
+        int          v_LEFT;                 // Left and right vertex list ptrs   
+        int          v_RIGHT;                // Left and right vertex list ptrs   
+        PolygonNode  next;                   // Pointer to next polygon contour   
+        PolygonNode  proxy;                  // Pointer to actual structure used  
+       
+       public PolygonNode(PolygonNode next, float x0, float y0) {
+           // Make v_LEFT and v_RIGHT point to new vertex 
+           x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;
+           this.v_LEFT = numvertices;
+           this.v_RIGHT = numvertices;
+           numvertices++;
+           this.proxy = this; // Initialise proxy to point to p itself 
+           this.next = next;
+       }
+       public void merge(PolygonNode q) { nxt[proxy.v_RIGHT] = q.proxy.v_LEFT; q.proxy.v_LEFT = proxy.v_LEFT; }
+       public void mergeRight(PolygonNode p) { nxt[proxy.v_RIGHT] = p.proxy.v_LEFT; proxy.v_RIGHT = p.proxy.v_RIGHT; }
+       public void addSelfTo(Polygon poly) {
+           for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) poly.add(x[vtx], y[vtx]);
+           poly.newcontour();
+       }
+       public int count() { int ret = 0; for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) ret++; return ret; }
+       public void add_right(float x0, float y0) {
+           x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;
+           nxt[proxy.v_RIGHT] = numvertices;
+           proxy.v_RIGHT = numvertices;
+           numvertices++;
+       }
+       public void add_left(float x0, float y0) {
+           x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;
+           nxt[numvertices] = proxy.v_LEFT;
+           proxy.v_LEFT = numvertices;
+           numvertices++;
+       }
+   }
+
+   private static class TopPolygonNode {
+       PolygonNode top_node = null;
+       public void clear() { top_node = null; }
+       public PolygonNode add_local_min(float x, float y) {
+           PolygonNode existing_min = top_node;
+           top_node = new PolygonNode(existing_min, x, y);
+           return top_node;
+       }
+       public void merge_left(PolygonNode p, PolygonNode q) {
+         // Label contour as a hole 
+         q.proxy.hole = true;
+         if (p.proxy == q.proxy) return;
+         // Assign p's vertex list to the left end of q's list 
+         p.merge(q);
+         // Redirect any p.proxy references to q.proxy 
+         PolygonNode target = p.proxy;
+         for(PolygonNode node = top_node; (node != null); node = node.next)
+             if (node.proxy == target) { node.active= 0; node.proxy= q.proxy; }
+      }
+
+      public void merge_right(PolygonNode p, PolygonNode q) {
+         // Label contour as external 
+         q.proxy.hole = false;
+         if (p.proxy == q.proxy) return;
+         // Assign p's vertex list to the right end of q's list 
+         q.mergeRight(p);
+         // Redirect any p->proxy references to q->proxy 
+         PolygonNode target = p.proxy;
+         for (PolygonNode node = top_node; (node != null); node = node.next)
+             if (node.proxy == target) { node.active = 0; node.proxy= q.proxy; }
+      }
+      
+      public int count_contours() {
+         int nc = 0;
+         for (PolygonNode polygon = top_node; (polygon != null); polygon = polygon.next)
+            if (polygon.active != 0) {
+               // Count the vertices in the current contour 
+               int nv= polygon.proxy.count();
+               // Record valid vertex counts in the active field 
+               if (nv > 2) { polygon.active = nv; nc++; }
+               else polygon.active= 0;
+            }
+         return nc;
+      }
+      
+      public Polygon getResult(Polygon result) {
+         int num_contours = count_contours();
+         if (num_contours <= 0) return result;
+         int c= 0;
+         PolygonNode npoly_node = null;
+         for (PolygonNode poly_node = top_node; (poly_node != null); poly_node = npoly_node) {
+             npoly_node = poly_node.next;
+             if (poly_node.active == 0) continue;
+             int prepoly = result.numcontours;
+             // This algorithm puts the verticies into the poly in reverse order
+             poly_node.proxy.addSelfTo(result);
+             if (poly_node.proxy.hole) {
+                 for(int i=prepoly; i<result.numcontours; i++)
+                     result.hole[i] = poly_node.proxy.hole;
+             }
+             c++;
+         }
+         return result;
+      }
+   }
+   
+    private static EdgeNode[] allEdgeNodes = new EdgeNode[BIGNUM];
+    private static int numEdgeNodes = 0;
+    private static int numFreeEdgeNodes = 0;
+    private static EdgeNode newEdgeNode(float x, float y) {
+        if (numFreeEdgeNodes == 0) {
+            return allEdgeNodes[numEdgeNodes++] = new EdgeNode(x, y);
+        } else {
+            EdgeNode ret = allEdgeNodes[--numFreeEdgeNodes];
+            ret.vertex_x = x;
+            ret.vertex_y = y;
+            return ret;
+        }
+    }
+   private static class EdgeNode {
+       float vertex_x;
+       float vertex_y;
+       float top_x;
+       float top_y;
+       float bot_x;
+       float bot_y;
+       float         xb;           // Scanbeam bottom x coordinate      
+       float         xt;           // Scanbeam top x coordinate         
+       float         dx;           // Change in x for a unit y increase 
+       int           type;         // Clip / subject edge flag          
+       int bundle_ABOVE_CLIP;
+       int bundle_ABOVE_SUBJ;
+       int bundle_BELOW_CLIP;
+       int bundle_BELOW_SUBJ;
+       int bside_CLIP;
+       int bside_SUBJ;
+       byte bstate_ABOVE;
+       byte bstate_BELOW;
+       PolygonNode  outp_ABOVE; // Output polygon / tristrip pointer 
+       PolygonNode  outp_BELOW; // Output polygon / tristrip pointer 
+       EdgeNode       prev;         // Previous edge in the AET          
+       EdgeNode       next;         // Next edge in the AET              
+       EdgeNode       pred;         // Edge connected at the lower end   
+       EdgeNode       succ;         // Edge connected at the upper end   
+       EdgeNode       next_bound;   // Pointer to next bound in LMT      
+       public EdgeNode(float x, float y) { vertex_x = x; vertex_y = y; }
+   }
+   private static class AetTree { EdgeNode top_node; public void clear() { top_node = null; } }
+
+   private static class EdgeTable {
+       public EdgeNode[] edges = new EdgeNode[BIGNUM];
+       public int entries;
+       public void clear() { for(; entries >= 0; entries--) edges[entries] = null; entries = 0; }
+       public void addNode(float x, float y) { edges[entries++] = newEdgeNode(x, y); }
+       public EdgeNode getNode(int index) { return edges[index]; }
+       public boolean NOT_RMAX(int i) { return (edges[PREV_INDEX(i, entries)].vertex_y > edges[i].vertex_y); }
+       public boolean NOT_FMAX(int i) { return(edges[NEXT_INDEX(i, entries)].vertex_y > edges[i].vertex_y); }
+       public boolean FWD_MIN(int i) {
+           return ((edges[PREV_INDEX(i, entries)].vertex_y >= edges[i].vertex_y) &&
+                   (edges[NEXT_INDEX(i, entries)].vertex_y >  edges[i].vertex_y));
+       }
+       public boolean REV_MIN(int i) {
+           return ((edges[PREV_INDEX(i, entries)].vertex_y >  edges[i].vertex_y) &&
+                   (edges[NEXT_INDEX(i, entries)].vertex_y >= edges[i].vertex_y));
+       }
+   }
+
+   private static class LmtTable {
+       float[] y = new float[BIGNUM];
+       EdgeNode[] first_bound = new EdgeNode[BIGNUM];
+       int numentries = 0;
+       public void clear() { for(; numentries >= 0; numentries--) first_bound[numentries] = null; numentries = 0; }
+       public int count() { return numentries; }
+       public boolean isEmpty() { return numentries == 0; }
+       public int add(float y0, EdgeNode e) {
+           for(int i=0; i<numentries; i++)
+               if (y[i] == y0) return i;
+               else if (y[i] > y0) {
+                   System.arraycopy(y, i, y, i+1, numentries-i);
+                   System.arraycopy(first_bound, i, first_bound, i+1, numentries-i);
+                   y[i] = y0;
+                   first_bound[i] = e;
+                   numentries++;
+                   return i;
+               }
+           y[numentries] = y0;
+           first_bound[numentries] = e;
+           return numentries++;
+       }
+   }
+
+   private static class ScanBeamList {
+       public int entries = 0;
+       public float[] floats = new float[BIGNUM];
+       public void clear() { entries = 0; }
+       public void add(float f) { floats[entries++] = f; }
+       public float[] sort() {
+           org.ibex.util.Vec.sortFloats(floats, 0, entries-1);
+           int j = 0;
+           for(int i=1; i<entries; i++) if (floats[j] != floats[i]) floats[++j] = floats[i];
+           entries = j+1;
+           return floats;
+       }
+   }
+   
+   private static class ItNodeTable {
+       EdgeNode ie_0[] = new EdgeNode[BIGNUM];
+       EdgeNode ie_1[] = new EdgeNode[BIGNUM];
+       float x[] = new float[BIGNUM];
+       float y[] = new float[BIGNUM];
+       int num = 0;
+       public void clear() { for(; num>=0; num--) { ie_0[num] = null; ie_1[num] = null; } num = 0; }
+       public void build_intersection_table(AetTree aet, float dy) {
+           int st = -1;
+           // Process each AET edge 
+           for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next)
+               if ((edge.bstate_ABOVE == BUNDLE_HEAD) ||
+                   (edge.bundle_ABOVE_CLIP != 0) || (edge.bundle_ABOVE_SUBJ != 0))
+                   st = add_st_edge(st, edge, dy);
+           sort(0, num-1);
+           for(;numst>=0; numst--) edge[numst] = null; numst = 0;
+       }
+       
+       int numst = 0;
+       EdgeNode edge[] = new EdgeNode[BIGNUM];    // Pointer to AET edge               
+       float    xb[] = new float[BIGNUM];         // Scanbeam bottom x coordinate      
+       float    xt[] = new float[BIGNUM];         // Scanbeam top x coordinate         
+       float    dx[] = new float[BIGNUM];         // Change in x for a unit y increase 
+       int      prev[] = new int[BIGNUM];           // Previous edge in sorted list      
+
+       private int add_st_edge(int st, EdgeNode e, float dy) {
+           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; }
+           float den = (xt[st] - xb[st]) - (e.xt - e.xb);
+
+           // If new edge and ST edge don't cross, No intersection - insert edge here (before the ST edge) 
+           if ((e.xt >= xt[st]) || (e.dx == dx[st]) || (Math.abs(den) <= GPC_EPSILON))
+               { prev[numst] = st; st = numst++; edge[st] = e; xb[st] = e.xb; xt[st] = e.xt; dx[st] = e.dx; return st; }
+
+           // Compute intersection between new edge and ST edge 
+           float r = (e.xb - xb[st]) / den;
+           float x = xb[st] + r * (xt[st] - xb[st]);
+           float y = r * dy;
+           // Insert the edge pointers and the intersection point in the IT 
+           add_intersection(edge[st], e, x, y);
+           prev[st] = add_st_edge(prev[st], e, dy);
+           return st;
+       }
+       private void add_intersection(EdgeNode edge0, EdgeNode edge1, float x0, float y0) {
+           ie_0[num] = edge0; ie_1[num] = edge1; x[num] = x0; y[num] = y0; num++; }
+
+       public final void sort(int start, int end) {
+           if(start >= end) return;
+           if(end-start <= 6) {
+               for(int i=start+1;i<=end;i++) {
+                   float tmpa = y[i];
+                   float tmpx = x[i];
+                   EdgeNode tmpe0 = ie_0[i];
+                   EdgeNode tmpe1 = ie_1[i];
+                   int j;
+                   for(j=i-1;j>=start;j--) {
+                       if(y[j] <= tmpa) break;
+                       y[j+1] = y[j];
+                       x[j+1] = x[j];
+                       ie_0[j+1] = ie_0[j];
+                       ie_1[j+1] = ie_1[j];
+                   }
+                   y[j+1] = tmpa;
+                   x[j+1] = tmpx;
+                   ie_0[j+1] = tmpe0;
+                   ie_1[j+1] = tmpe1;
+               }
+               return;
+           }
+           float pivot = y[end];
+           int lo = start - 1;
+           int hi = end;
+           do {
+               while(y[++lo] < pivot) { }
+               while((hi > lo) && y[--hi] > pivot) { }
+               swap(lo, hi);
+           } while(lo < hi);
+           swap(lo, end);
+           sort(start, lo-1);
+           sort(lo+1, end);
+       }
+       private final void swap(int a, int b) {
+           if(a != b) {
+               float tmp = x[a]; x[a] = x[b]; x[b] = tmp;
+               tmp = y[a]; y[a] = y[b]; y[b] = tmp;
+               EdgeNode tmpe = ie_0[a]; ie_0[a] = ie_0[b]; ie_0[b] = tmpe;
+               tmpe = ie_1[a]; ie_1[a] = ie_1[b]; ie_1[b] = tmpe;
+           }
+       }
+   }
+
+}
-- 
1.7.10.4