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