X-Git-Url: http://git.megacz.com/?p=org.ibex.core.git;a=blobdiff_plain;f=src%2Forg%2Fibex%2Fgraphics%2FPolygon.java;fp=src%2Forg%2Fibex%2Fgraphics%2FPolygon.java;h=c99797ce9d3ab6391a347dcb2be634f30c6048d2;hp=0000000000000000000000000000000000000000;hb=545a6bc7e6aff46ecb6012648fd9dd6f02588166;hpb=6eaf54fa906754ce35a7db0e8207fc6bbde5464d
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
= 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 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 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 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 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= 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 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=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;
+ }
+ }
+ }
+
+}