/* * 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. * ==================================================================== */ package geomerative ; import java.util.ArrayList ; import java.util.List ; /** * Clip is a Java version of the General RPolygon Clipper algorithm * developed by Alan Murta (gpc@cs.man.ac.uk). The home page for the original source can be * found at * http://www.cs.man.ac.uk/aig/staff/alan/software/. *

* polyClass: Some of the public methods below take a polyClass * argument. This java.lang.Class object is assumed to implement the RPolygon * interface and have a no argument constructor. This was done so that the user of the algorithm * could create their own classes that implement the RPolygon interface and still uses * this algorithm. *

* Implementation Note: The converted algorithm does support the difference * operation, but a public method has not been provided and it has not been tested. To do so, * simply follow what has been done for intersection. * * @author Dan Bridenbecker, Solution Engineering, Inc. */ class RClip { // ----------------- // --- Constants --- // ----------------- private static final boolean DEBUG = false ; // Maximum precision for floats private static final double GPC_EPSILON = 2.2204460492503131e-016 ; //private static final float GPC_EPSILON = 1.192092896e-07F; 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 ; private static final boolean INVERT_TRISTRIPS = false ; // ------------------------ // --- Member Variables --- // ------------------------ // -------------------- // --- Constructors --- // -------------------- /** Creates a new instance of Clip */ private RClip() { } // ---------------------- // --- Static Methods --- // ---------------------- /** * Return the intersection of p1 and p2 where the * return type is of polyClass. See the note in the class description * for more on polyClass. * * @param p1 One of the polygons to performt he intersection with * @param p2 One of the polygons to performt he intersection with * @param polyClass The type of RPolygon to return */ static RPolygon intersection( RPolygon p1, RPolygon p2, Class polyClass ) { return clip( OperationType.GPC_INT, p1, p2, polyClass ); } /** * Return the union of p1 and p2 where the * return type is of polyClass. See the note in the class description * for more on polyClass. * * @param p1 One of the polygons to performt he union with * @param p2 One of the polygons to performt he union with * @param polyClass The type of RPolygon to return */ static RPolygon union( RPolygon p1, RPolygon p2, Class polyClass ) { return clip( OperationType.GPC_UNION, p1, p2, polyClass ); } /** * Return the xor of p1 and p2 where the * return type is of polyClass. See the note in the class description * for more on polyClass. * * @param p1 One of the polygons to performt he xor with * @param p2 One of the polygons to performt he xor with * @param polyClass The type of RPolygon to return */ static RPolygon xor( RPolygon p1, RPolygon p2, Class polyClass ) { return clip( OperationType.GPC_XOR, p1, p2, polyClass ); } /** * Return the diff of p1 and p2 where the * return type is of polyClass. See the note in the class description * for more on polyClass. * * @param p1 One of the polygons to performt he diff with * @param p2 One of the polygons to performt he diff with * @param polyClass The type of RPolygon to return */ static RPolygon diff( RPolygon p1, RPolygon p2, Class polyClass ) { return clip( OperationType.GPC_DIFF, p1, p2, polyClass ); } /** * Return the intersection of p1 and p2 where the * return type is of PolyDefault. * * @param p1 One of the polygons to performt he intersection with * @param p2 One of the polygons to performt he intersection with */ static RPolygon intersection( RPolygon p1, RPolygon p2 ) { return clip( OperationType.GPC_INT, p1, p2, RPolygon.class ); } /** * Return the union of p1 and p2 where the * return type is of PolyDefault. * * @param p1 One of the polygons to performt he union with * @param p2 One of the polygons to performt he union with */ static RPolygon union( RPolygon p1, RPolygon p2 ) { return clip( OperationType.GPC_UNION, p1, p2, RPolygon.class ); } /** * Return the xor of p1 and p2 where the * return type is of PolyDefault. * * @param p1 One of the polygons to performt he xor with * @param p2 One of the polygons to performt he xor with */ static RPolygon xor( RPolygon p1, RPolygon p2 ) { return clip( OperationType.GPC_XOR, p1, p2, RPolygon.class ); } /** * Return the diff of p1 and p2 where the * return type is of PolyDefault. * * @param p1 One of the polygons to performt he diff with * @param p2 One of the polygons to performt he diff with */ static RPolygon diff( RPolygon p1, RPolygon p2 ) { return clip( OperationType.GPC_DIFF, p1, p2, RPolygon.class ); } /** * Updates p1. * * @param p1 One of the polygons to performt he diff with */ static RPolygon update( RPolygon p1 ) { return clip( OperationType.GPC_DIFF, p1, new RPolygon(), RPolygon.class ); } // ----------------------- // --- Private Methods --- // ----------------------- /** * Create a new RPolygon type object using polyClass. */ private static RPolygon createNewPoly( Class polyClass ) { try { return (RPolygon)polyClass.newInstance(); } catch( InstantiationException | IllegalAccessException e ) { throw new RuntimeException(e); } } /** * clip() is the main method of the clipper algorithm. * This is where the conversion from really begins. */ private static RPolygon clip( OperationType op, RPolygon subj, RPolygon clip, Class polyClass ) { if(RG.useFastClip) { return FastRClip.clip(op, subj, clip, polyClass); } RPolygon result = createNewPoly( polyClass ) ; /* Test for trivial NULL result cases */ if( (subj.isEmpty() && clip.isEmpty()) || (subj.isEmpty() && ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF))) || (clip.isEmpty() && (op == OperationType.GPC_INT)) ) { return result ; } /* Identify potentialy contributing contours */ if( ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF)) && !subj.isEmpty() && !clip.isEmpty() ) { minimax_test(subj, clip, op); } /* Build LMT */ LmtTable lmt_table = new LmtTable(); ScanBeamTreeEntries sbte = new ScanBeamTreeEntries(); if (!subj.isEmpty()) { build_lmt(lmt_table, sbte, subj, SUBJ, op); } if( DEBUG ) { System.out.println(""); System.out.println(" ------------ After build_lmt for subj ---------"); lmt_table.print(); } if (!clip.isEmpty()) { build_lmt(lmt_table, sbte, clip, CLIP, op); } if( DEBUG ) { System.out.println(""); System.out.println(" ------------ After build_lmt for clip ---------"); lmt_table.print(); } /* Return a NULL result if no contours contribute */ if (lmt_table.top_node == null) { return result; } /* Build scanbeam table from scanbeam tree */ float[] sbt = sbte.build_sbt(); int[] parity = new int[2] ; parity[0] = LEFT ; parity[1] = LEFT ; /* Invert clip polygon for difference operation */ if (op == OperationType.GPC_DIFF) { parity[CLIP]= RIGHT; } if( DEBUG ) { print_sbt(sbt); } LmtNode local_min = lmt_table.top_node ; TopPolygonNode out_poly = new TopPolygonNode(); // used to create resulting RPolygon AetTree aet = new AetTree(); int scanbeam = 0 ; /* Process each scanbeam */ while( scanbeam < sbt.length ) { /* Set yb and yt to the bottom and top of the scanbeam */ float yb = sbt[scanbeam++]; float yt = 0.0F ; float dy = 0.0F ; if( scanbeam < sbt.length ) { yt = sbt[scanbeam]; dy = yt - yb; } /* === SCANBEAM BOUNDARY PROCESSING ================================ */ /* If LMT node corresponding to yb exists */ if (local_min != null ) { if (local_min.y == yb) { /* Add edges starting at this local minimum to the AET */ for( EdgeNode edge = local_min.first_bound; (edge != null) ; edge= edge.next_bound) { add_edge_to_aet( aet, edge ); } local_min = local_min.next; } } if( DEBUG ) { aet.print(); } /* Set dummy previous x value */ float px = -Float.MAX_VALUE ; /* Create bundles within AET */ EdgeNode e0 = aet.top_node ; EdgeNode e1 = aet.top_node ; /* Set up bundle fields of first edge */ aet.top_node.bundle[ABOVE][ aet.top_node.type ] = (aet.top_node.top.y != yb) ? 1 : 0; aet.top_node.bundle[ABOVE][ ((aet.top_node.type==0) ? 1 : 0) ] = 0; aet.top_node.bstate[ABOVE] = BundleState.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 */ next_edge.bundle[ABOVE][ ne_type ]= (next_edge.top.y != yb) ? 1 : 0; next_edge.bundle[ABOVE][ ne_type_opp ] = 0 ; next_edge.bstate[ABOVE] = BundleState.UNBUNDLED; /* Bundle edges above the scanbeam boundary if they coincide */ if ( next_edge.bundle[ABOVE][ne_type] == 1 ) { if (EQ(e0.xb, next_edge.xb) && EQ(e0.dx, next_edge.dx) && (e0.top.y != yb)) { next_edge.bundle[ABOVE][ ne_type ] ^= e0.bundle[ABOVE][ ne_type ]; next_edge.bundle[ABOVE][ ne_type_opp ] = e0.bundle[ABOVE][ ne_type_opp ]; next_edge.bstate[ABOVE] = BundleState.BUNDLE_HEAD; e0.bundle[ABOVE][CLIP] = 0; e0.bundle[ABOVE][SUBJ] = 0; e0.bstate[ABOVE] = BundleState.BUNDLE_TAIL; } e0 = next_edge; } } int[] horiz = new int[2] ; horiz[CLIP]= HState.NH; horiz[SUBJ]= HState.NH; int[] exists = new int[2] ; exists[CLIP] = 0 ; 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 */ if( (op == OperationType.GPC_DIFF) || (op == OperationType.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; } else if( op == OperationType.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]); } else if( op == OperationType.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; } else { 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 */ if( DEBUG ) { out_poly.print(); } } /* 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] == BundleState.BUNDLE_HEAD) && (prev_edge!=null)) { if (prev_edge.bstate[BELOW] == BundleState.BUNDLE_TAIL) { prev_edge.outp[BELOW]= edge.outp[BELOW]; prev_edge.bstate[BELOW]= BundleState.UNBUNDLED; if ( prev_edge.prev != null) { if (prev_edge.prev.bstate[BELOW] == BundleState.BUNDLE_TAIL) { prev_edge.bstate[BELOW] = BundleState.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.sbt_entries ) { /* === SCANBEAM INTERIOR PROCESSING ============================== */ /* Build intersection table for the current scanbeam */ ItNodeTable it_table = new ItNodeTable(); it_table.build_intersection_table(aet, dy); /* Process each node in the intersection table */ for (ItNode intersect = it_table.top_node ; (intersect != null); intersect = intersect.next) { e0= intersect.ie[0]; e1= intersect.ie[1]; /* 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 = intersect.point.x; float iy = intersect.point.y + 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 */ if( (op == OperationType.GPC_DIFF) || (op == OperationType.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; } else if( op == OperationType.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]); } else if( op == OperationType.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; } else { 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] == BundleState.BUNDLE_HEAD) { boolean search = true; while (search) { prev_edge= prev_edge.prev; if (prev_edge != null) { if (prev_edge.bstate[ABOVE] != BundleState.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; if( DEBUG ) { out_poly.print(); } } /* 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 */ result = out_poly.getResult(polyClass); return result ; } /** * Clipper to output tristrips */ private static RMesh clip( OperationType op, RPolygon subj, RPolygon clip ) { if(RG.useFastClip) { return FastRClip.clip(op, subj, clip); } PolygonNode tlist=null, tnn, tn; EdgeNode prev_edge, next_edge, edge, cf=null, succ_edge, e0, e1; VertexNode lt, ltn, rt, rtn; int cft=VertexType.LED; float []sbt; float xb, px, nx=0, yb, yt, dy, ix, iy; /* Test for trivial NULL result cases */ if( (subj.isEmpty() && clip.isEmpty()) || (subj.isEmpty() && ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF))) || (clip.isEmpty() && (op == OperationType.GPC_INT)) ) { return new RMesh() ; } /* Identify potentialy contributing contours */ if( ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF)) && !subj.isEmpty() && !clip.isEmpty() ) { minimax_test(subj, clip, op); } /* Build LMT */ LmtTable lmt_table = new LmtTable(); ScanBeamTreeEntries sbte = new ScanBeamTreeEntries(); if (!subj.isEmpty()) { build_lmt(lmt_table, sbte, subj, SUBJ, op); } if( DEBUG ) { System.out.println(""); System.out.println(" ------------ After build_lmt for subj ---------"); lmt_table.print(); } if (!clip.isEmpty()) { build_lmt(lmt_table, sbte, clip, CLIP, op); } if( DEBUG ) { System.out.println(""); System.out.println(" ------------ After build_lmt for clip ---------"); lmt_table.print(); } /* Return a NULL result if no contours contribute */ if (lmt_table.top_node == null) { return new RMesh(); } /* Build scanbeam table from scanbeam tree */ sbt = sbte.build_sbt(); int[] parity = new int[2] ; parity[0] = LEFT ; parity[1] = LEFT ; /* Invert clip polygon for difference operation */ if (op == OperationType.GPC_DIFF) { parity[CLIP]= RIGHT; } if( DEBUG ) { print_sbt(sbt); } LmtNode local_min = lmt_table.top_node ; AetTree aet = new AetTree(); int scanbeam = 0 ; /* Process each scanbeam */ while( scanbeam < sbt.length ) { /* Set yb and yt to the bottom and top of the scanbeam */ yb = sbt[scanbeam++]; yt = 0.0F ; dy = 0.0F ; if( scanbeam < sbt.length ) { yt = sbt[scanbeam]; dy = yt - yb; } /* === SCANBEAM BOUNDARY PROCESSING ================================ */ /* If LMT node corresponding to yb exists */ if (local_min != null ) { if (local_min.y == yb) { /* Add edges starting at this local minimum to the AET */ for( edge = local_min.first_bound; (edge != null) ; edge= edge.next_bound) { add_edge_to_aet( aet, edge ); } local_min = local_min.next; } } if( DEBUG ) { aet.print(); } /* Set dummy previous x value */ px = -Float.MAX_VALUE ; /* Create bundles within AET */ e0 = aet.top_node ; e1 = aet.top_node ; /* Set up bundle fields of first edge */ aet.top_node.bundle[ABOVE][ aet.top_node.type ] = (aet.top_node.top.y != yb) ? 1 : 0; aet.top_node.bundle[ABOVE][ ((aet.top_node.type==0) ? 1 : 0) ] = 0; aet.top_node.bstate[ABOVE] = BundleState.UNBUNDLED; for (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 */ next_edge.bundle[ABOVE][ ne_type ]= (next_edge.top.y != yb) ? 1 : 0; next_edge.bundle[ABOVE][ ne_type_opp ] = 0 ; next_edge.bstate[ABOVE] = BundleState.UNBUNDLED; /* Bundle edges above the scanbeam boundary if they coincide */ if ( next_edge.bundle[ABOVE][ne_type] == 1 ) { if (EQ(e0.xb, next_edge.xb) && EQ(e0.dx, next_edge.dx) && (e0.top.y != yb)) { next_edge.bundle[ABOVE][ ne_type ] ^= e0.bundle[ABOVE][ ne_type ]; next_edge.bundle[ABOVE][ ne_type_opp ] = e0.bundle[ABOVE][ ne_type_opp ]; next_edge.bstate[ABOVE] = BundleState.BUNDLE_HEAD; e0.bundle[ABOVE][CLIP] = 0; e0.bundle[ABOVE][SUBJ] = 0; e0.bstate[ABOVE] = BundleState.BUNDLE_TAIL; } e0 = next_edge; } } int[] horiz = new int[2] ; horiz[CLIP]= HState.NH; horiz[SUBJ]= HState.NH; int[] exists = new int[2] ; exists[CLIP] = 0 ; exists[SUBJ] = 0 ; /* Process each edge at this scanbeam boundary */ for (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 */ if( (op == OperationType.GPC_DIFF) || (op == OperationType.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; } else if( op == OperationType.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]); } else if( op == OperationType.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; } else { 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) { xb = edge.xb; int vclass = VertexType.getType( tr, tl, br, bl ); switch (vclass) { case VertexType.EMN: tlist=new_tristrip(tlist, edge, xb, yb); cf= edge; break; case VertexType.ERI: edge.outp[ABOVE]= cf.outp[ABOVE]; if (xb != cf.xb) { VERTEX(edge, ABOVE, RIGHT, xb, yb); } cf= null; break; case VertexType.ELI: VERTEX(edge, BELOW, LEFT, xb, yb); edge.outp[ABOVE]= null; cf= edge; break; case VertexType.EMX: if (xb != cf.xb) { VERTEX(edge, BELOW, RIGHT, xb, yb); } edge.outp[ABOVE] = null; cf= null; break; case VertexType.IMN: if (cft == VertexType.LED) { if (cf.bot.y != yb) { VERTEX(cf, BELOW, LEFT, cf.xb, yb); } tlist=new_tristrip(tlist, cf, cf.xb, yb); } edge.outp[ABOVE]= cf.outp[ABOVE]; VERTEX(edge, ABOVE, RIGHT, xb, yb); break; case VertexType.ILI: tlist=new_tristrip(tlist, edge, xb, yb); cf= edge; cft= VertexType.ILI; break; case VertexType.IRI: if (cft == VertexType.LED) { if (cf.bot.y != yb) { VERTEX(cf, BELOW, LEFT, cf.xb, yb); } tlist=new_tristrip(tlist, cf, cf.xb, yb); } VERTEX(edge, BELOW, RIGHT, xb, yb); edge.outp[ABOVE]= null; break; case VertexType.IMX: VERTEX(edge, BELOW, LEFT, xb, yb); edge.outp[ABOVE]= null; cft= VertexType.IMX; break; case VertexType.IMM: VERTEX(edge, BELOW, LEFT, xb, yb); edge.outp[ABOVE]= cf.outp[ABOVE]; if (xb != cf.xb) { VERTEX(cf, ABOVE, RIGHT, xb, yb); } cf= edge; break; case VertexType.EMM: VERTEX(edge, BELOW, RIGHT, xb, yb); edge.outp[ABOVE]= null; tlist=new_tristrip(tlist, edge, xb, yb); cf= edge; break; case VertexType.LED: if (edge.bot.y == yb) VERTEX(edge, BELOW, LEFT, xb, yb); edge.outp[ABOVE]= edge.outp[BELOW]; cf= edge; cft= VertexType.LED; break; case VertexType.RED: edge.outp[ABOVE]= cf.outp[ABOVE]; if (cft == VertexType.LED) { if (cf.bot.y == yb) { VERTEX(edge, BELOW, RIGHT, xb, yb); } else { if (edge.bot.y == yb) { VERTEX(cf, BELOW, LEFT, cf.xb, yb); VERTEX(edge, BELOW, RIGHT, xb, yb); } } } else { VERTEX(edge, BELOW, RIGHT, xb, yb); VERTEX(edge, ABOVE, RIGHT, xb, yb); } cf= null; 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 (edge = aet.top_node ; (edge != null); edge = edge.next) { if (edge.top.y == yb) { prev_edge = edge.prev; 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] == BundleState.BUNDLE_HEAD) && (prev_edge!=null)) { if (prev_edge.bstate[BELOW] == BundleState.BUNDLE_TAIL) { prev_edge.outp[BELOW]= edge.outp[BELOW]; prev_edge.bstate[BELOW]= BundleState.UNBUNDLED; if ( prev_edge.prev != null) { if (prev_edge.prev.bstate[BELOW] == BundleState.BUNDLE_TAIL) { prev_edge.bstate[BELOW] = BundleState.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.sbt_entries ) { /* === SCANBEAM INTERIOR PROCESSING ============================== */ /* Build intersection table for the current scanbeam */ ItNodeTable it_table = new ItNodeTable(); it_table.build_intersection_table(aet, dy); /* Process each node in the intersection table */ for (ItNode intersect = it_table.top_node ; (intersect != null); intersect = intersect.next) { e0= intersect.ie[0]; e1= intersect.ie[1]; /* 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]; ix = intersect.point.x; iy = intersect.point.y + 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 */ if( (op == OperationType.GPC_DIFF) || (op == OperationType.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; } else if( op == OperationType.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]); } else if( op == OperationType.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; } else { throw new IllegalStateException("Unknown op type, "+op); } next_edge = e1.next; prev_edge = e0.prev; int vclass = VertexType.getType( tr, tl, br, bl ); switch (vclass) { case VertexType.EMN: tlist=new_tristrip(tlist, e1, ix, iy); e1.outp[ABOVE] = e0.outp[ABOVE]; break; case VertexType.ERI: if (p != null) { px = P_EDGE(prev_edge, e0, ABOVE, px, iy); VERTEX(prev_edge, ABOVE, LEFT, px, iy); VERTEX(e0, ABOVE, RIGHT, ix, iy); e1.outp[ABOVE]= e0.outp[ABOVE]; e0.outp[ABOVE]= null; } break; case VertexType.ELI: if (q != null) { nx = N_EDGE(next_edge, e1, ABOVE, nx, iy); VERTEX(e1, ABOVE, LEFT, ix, iy); VERTEX(next_edge, ABOVE, RIGHT, nx, iy); e0.outp[ABOVE]= e1.outp[ABOVE]; e1.outp[ABOVE]= null; } break; case VertexType.EMX: if ((p!=null) && (q!=null)) { VERTEX(e0, ABOVE, LEFT, ix, iy); e0.outp[ABOVE]= null; e1.outp[ABOVE]= null; } break; case VertexType.IMN: px = P_EDGE(prev_edge, e0, ABOVE, px, iy); VERTEX(prev_edge, ABOVE, LEFT, px, iy); nx = N_EDGE(next_edge, e1, ABOVE, nx, iy); VERTEX(next_edge, ABOVE, RIGHT, nx, iy); tlist=new_tristrip(tlist, prev_edge, px, iy); e1.outp[ABOVE]= prev_edge.outp[ABOVE]; VERTEX(e1, ABOVE, RIGHT, ix, iy); tlist=new_tristrip(tlist, e0, ix, iy); next_edge.outp[ABOVE]= e0.outp[ABOVE]; VERTEX(next_edge, ABOVE, RIGHT, nx, iy); break; case VertexType.ILI: if (p != null) { VERTEX(e0, ABOVE, LEFT, ix, iy); nx = N_EDGE(next_edge, e1, ABOVE, nx, iy); VERTEX(next_edge, ABOVE, RIGHT, nx, iy); e1.outp[ABOVE]= e0.outp[ABOVE]; e0.outp[ABOVE]= null; } break; case VertexType.IRI: if (q!=null) { VERTEX(e1, ABOVE, RIGHT, ix, iy); px = P_EDGE(prev_edge, e0, ABOVE, px, iy); VERTEX(prev_edge, ABOVE, LEFT, px, iy); e0.outp[ABOVE]= e1.outp[ABOVE]; e1.outp[ABOVE]= null; } break; case VertexType.IMX: if ((p!=null) && (q!=null)) { VERTEX(e0, ABOVE, RIGHT, ix, iy); VERTEX(e1, ABOVE, LEFT, ix, iy); e0.outp[ABOVE]= null; e1.outp[ABOVE]= null; px = P_EDGE(prev_edge, e0, ABOVE, px, iy); VERTEX(prev_edge, ABOVE, LEFT, px, iy); tlist=new_tristrip(tlist, prev_edge, px, iy); nx = N_EDGE(next_edge, e1, ABOVE, nx, iy); VERTEX(next_edge, ABOVE, RIGHT, nx, iy); next_edge.outp[ABOVE]= prev_edge.outp[ABOVE]; VERTEX(next_edge, ABOVE, RIGHT, nx, iy); } break; case VertexType.IMM: if ((p!=null) && (q!=null)) { VERTEX(e0, ABOVE, RIGHT, ix, iy); VERTEX(e1, ABOVE, LEFT, ix, iy); px = P_EDGE(prev_edge, e0, ABOVE, px, iy); VERTEX(prev_edge, ABOVE, LEFT, px, iy); tlist=new_tristrip(tlist, prev_edge, px, iy); nx = N_EDGE(next_edge, e1, ABOVE, nx, iy); VERTEX(next_edge, ABOVE, RIGHT, nx, iy); e1.outp[ABOVE]= prev_edge.outp[ABOVE]; VERTEX(e1, ABOVE, RIGHT, ix, iy); tlist=new_tristrip(tlist, e0, ix, iy); next_edge.outp[ABOVE]= e0.outp[ABOVE]; VERTEX(next_edge, ABOVE, RIGHT, nx, iy); } break; case VertexType.EMM: if ((p!=null) && (q!=null)) { VERTEX(e0, ABOVE, LEFT, ix, iy); tlist=new_tristrip(tlist, e1, 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 */ prev_edge = e0.prev; next_edge = e1.next; if (next_edge != null) { next_edge.prev = e0; } if (e0.bstate[ABOVE] == BundleState.BUNDLE_HEAD) { boolean search = true; while (search) { prev_edge= prev_edge.prev; if (prev_edge != null) { if (prev_edge.bundle[ABOVE][CLIP]!=0 || prev_edge.bundle[ABOVE][SUBJ]!=0 || (prev_edge.bstate[ABOVE] == BundleState.BUNDLE_HEAD)) { search= false; } } else { search= false; } } } if (prev_edge == null) { e1.next = aet.top_node; aet.top_node = e0.next; } else { 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 ( edge = aet.top_node; (edge != null); edge = edge.next) { next_edge = edge.next; 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]; 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 tristrip from tlist */ RMesh result = new RMesh(); if (count_tristrips(tlist) > 0) { int s, v; s= 0; for (tn= tlist; tn!=null; tn= tnn) { tnn= tn.next; if (tn.active > 2) { /* Valid tristrip: copy the vertices and free the heap */ RStrip strip = new RStrip(); v= 0; if (INVERT_TRISTRIPS == true) { lt= tn.v[RIGHT]; rt= tn.v[LEFT]; } else { lt= tn.v[LEFT]; rt= tn.v[RIGHT]; } while (lt!=null || rt!=null) { if (lt!=null) { ltn= lt.next; strip.add(lt.x,lt.y); v++; lt= ltn; } if (rt!=null) { rtn= rt.next; strip.add(rt.x,rt.y); v++; rt= rtn; } } result.addStrip(strip); s++; } else { /* Invalid tristrip: just free the heap */ for (lt= tn.v[LEFT]; lt!=null; lt= ltn) { ltn= lt.next; } for (rt= tn.v[RIGHT]; rt!=null; rt= rtn) { rtn= rt.next; } } } } return result ; } public static RMesh polygonToMesh(RPolygon s) { RPolygon c = new RPolygon(); RPolygon s_clean = s.removeOpenContours(); /* for(int i=0; i c_bbox[c].getMaxX()))) && (!((s_bbox[s].getMaxY() < c_bbox[c].getMinY()) || (s_bbox[s].getMinY() > c_bbox[c].getMaxY()))); } } /* For each clip contour, search for any subject contour overlaps */ for( int c = 0; c < clip_num_poly; c++ ) { boolean overlap = false; for( int s = 0; !overlap && (s < subj_num_poly) ; s++) { overlap = o_table[s][c]; } if (!overlap) { clip.setContributing( c, false ); // Flag non contributing status } } if (op == OperationType.GPC_INT) { /* For each subject contour, search for any clip contour overlaps */ for ( int s= 0; s < subj_num_poly; s++) { boolean overlap = false; for ( int c= 0; !overlap && (c < clip_num_poly); c++) { overlap = o_table[s][c]; } if (!overlap) { subj.setContributing( s, false ); // Flag non contributing status } } } } private static LmtNode bound_list( LmtTable lmt_table, float y ) { if( lmt_table.top_node == null ) { lmt_table.top_node = new LmtNode(y); return lmt_table.top_node ; } else { LmtNode prev = null ; LmtNode node = lmt_table.top_node ; boolean done = false ; while( !done ) { if( y < node.y ) { /* Insert a new LMT node before the current node */ LmtNode existing_node = node ; node = new LmtNode(y); node.next = existing_node ; if( prev == null ) { lmt_table.top_node = node ; } else { prev.next = node ; } // if( existing_node == lmt_table.top_node ) // { // lmt_table.top_node = node ; // } done = true ; } else if ( y > node.y ) { /* Head further up the LMT */ if( node.next == null ) { node.next = new LmtNode(y); node = node.next ; done = true ; } else { prev = node ; node = node.next ; } } else { /* Use this existing LMT node */ done = true ; } } return node ; } } private static void insert_bound( LmtNode lmt_node, EdgeNode e) { if( lmt_node.first_bound == null ) { /* Link node e to the tail of the list */ lmt_node.first_bound = e ; } else { boolean done = false ; EdgeNode prev_bound = null ; EdgeNode current_bound = lmt_node.first_bound ; while( !done ) { /* 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_node.first_bound = e ; } else { prev_bound.next_bound = e ; } e.next_bound = current_bound ; // EdgeNode existing_bound = current_bound ; // current_bound = e ; // current_bound.next_bound = existing_bound ; // if( lmt_node.first_bound == existing_bound ) // { // lmt_node.first_bound = current_bound ; // } done = true ; } 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_node.first_bound = e ; } else { prev_bound.next_bound = e ; } e.next_bound = current_bound ; // EdgeNode existing_bound = current_bound ; // current_bound = e ; // current_bound.next_bound = existing_bound ; // if( lmt_node.first_bound == existing_bound ) // { // lmt_node.first_bound = current_bound ; // } done = true ; } else { /* Head further down the list */ if( current_bound.next_bound == null ) { current_bound.next_bound = e ; done = true ; } else { 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 ; done = true ; } else { 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; } else { EdgeNode current_edge = aet.top_node ; EdgeNode prev = null ; boolean done = false ; while( !done ) { /* 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 ; } // if( current_edge == aet.top_node ) // { // aet.top_node = edge ; // } // current_edge = edge ; done = true; } 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 ; } // if( current_edge == aet.top_node ) // { // aet.top_node = edge ; // } // current_edge = edge ; done = true; } 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 ; done = true ; } else { 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 ; done = true ; } else { current_edge = current_edge.next ; } } } } } private static void add_to_sbtree( ScanBeamTreeEntries sbte, float y ) { if( sbte.sb_tree == null ) { /* Add a new tree node here */ sbte.sb_tree = new ScanBeamTree( y ); sbte.sbt_entries++ ; return ; } ScanBeamTree tree_node = sbte.sb_tree ; boolean done = false ; while( !done ) { if ( tree_node.y > y) { if( tree_node.less == null ) { tree_node.less = new ScanBeamTree(y); sbte.sbt_entries++ ; done = true ; } else { tree_node = tree_node.less ; } } else if ( tree_node.y < y) { if( tree_node.more == null ) { tree_node.more = new ScanBeamTree(y); sbte.sbt_entries++ ; done = true ; } else { tree_node = tree_node.more ; } } else { done = true ; } } } private static EdgeTable build_lmt( LmtTable lmt_table, ScanBeamTreeEntries sbte, RPolygon p, int type, //poly type SUBJ/CLIP OperationType op) { /* Create the entire input polygon edge table in one go */ EdgeTable edge_table = new EdgeTable(); for ( int c= 0; c < p.getNumInnerPoly(); c++) { RPolygon ip = p.getInnerPoly(c); if( !ip.isContributing(0) ) { /* Ignore the non-contributing contour */ ip.setContributing(0, true); } else { /* Perform contour optimisation */ int num_vertices= 0; int e_index = 0 ; edge_table = new EdgeTable(); for ( int i= 0; i < ip.getNumPoints(); i++) { if( OPTIMAL(ip, i) ) { float x = ip.getX(i); float y = ip.getY(i); edge_table.addNode( x, y ); /* Record vertex in the scanbeam table */ add_to_sbtree( sbte, ip.getY(i) ); 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] = BundleState.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 == OperationType.GPC_DIFF) ? RIGHT : LEFT; ei.bside[SUBJ] = LEFT ; } insert_bound( bound_list(lmt_table, edge_table.getNode(min).vertex.y), e); if( DEBUG ) { System.out.println("fwd"); lmt_table.print(); } 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] = BundleState.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 == OperationType.GPC_DIFF) ? RIGHT : LEFT; ei.bside[SUBJ] = LEFT; } insert_bound( bound_list(lmt_table, edge_table.getNode(min).vertex.y), e); if( DEBUG ) { System.out.println("rev"); lmt_table.print(); } e_index+= num_edges; } } } } return edge_table; } private static StNode add_st_edge( StNode st, ItNodeTable it, EdgeNode edge, float dy) { if (st == null) { /* Append edge onto the tail end of the ST */ st = new StNode( edge, null ); } else { float den= (st.xt - st.xb) - (edge.xt - edge.xb); /* If new edge and ST edge don't cross */ if( (edge.xt >= st.xt) || (edge.dx == st.dx) || (Math.abs(den) <= GPC_EPSILON)) { /* No intersection - insert edge here (before the ST edge) */ StNode existing_node = st; st = new StNode( edge, existing_node ); } else { /* Compute intersection between new edge and ST edge */ float r= (edge.xb - st.xb) / den; float x= st.xb + r * (st.xt - st.xb); float y= r * dy; /* Insert the edge pointers and the intersection point in the IT */ it.top_node = add_intersection(it.top_node, st.edge, edge, x, y); /* Head further into the ST */ st.prev = add_st_edge(st.prev, it, edge, dy); } } return st ; } private static ItNode add_intersection( ItNode it_node, EdgeNode edge0, EdgeNode edge1, float x, float y) { if (it_node == null) { /* Append a new node to the tail of the list */ it_node = new ItNode( edge0, edge1, x, y, null ); } else { if ( it_node.point.y > y) { /* Insert a new node mid-list */ ItNode existing_node = it_node ; it_node = new ItNode( edge0, edge1, x, y, existing_node ); } else { /* Head further down the list */ it_node.next = add_intersection( it_node.next, edge0, edge1, x, y); } } return it_node ; } private static int count_tristrips(PolygonNode tn) { int total; for (total= 0; tn!=null; tn= tn.next) { if (tn.active > 2) { total++; } } return total; } private static VertexNode add_vertex(VertexNode ve_node, float x, float y) { if (ve_node == null) { /* Append a new node to the tail of the list */ ve_node = new VertexNode( x, y); } else { /* Head further down the list */ ve_node.next = add_vertex( ve_node.next, x, y); } return ve_node; } private static PolygonNode new_tristrip(PolygonNode po_node, EdgeNode edge, float x, float y) { if (po_node == null) { /* Append a new node to the tail of the list */ po_node = new PolygonNode(); po_node.v[LEFT]=add_vertex(po_node.v[LEFT], x, y); edge.outp[ABOVE]= po_node; } else { /* Head further down the list */ po_node.next = new_tristrip( po_node.next, edge, x, y); } return po_node; } // --------------------- // --- Inner Classes --- // --------------------- public static class OperationType { private String m_Type ; private OperationType( String type ) { m_Type = type; } public static final OperationType GPC_DIFF = new OperationType( "Difference" ); public static final OperationType GPC_INT = new OperationType( "Intersection" ); public static final OperationType GPC_XOR = new OperationType( "Exclusive or" ); public static final OperationType GPC_UNION = new OperationType( "Union" ); @Override public String toString() { return m_Type; } } /** * 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); } } /** * Horizontal edge states */ 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} }; } /** * Edge bundle state */ private static class BundleState { private String m_State ; private BundleState( String state ) { m_State = state ; } public static final BundleState UNBUNDLED = new BundleState( "UNBUNDLED" ); // Isolated edge not within a bundle public static final BundleState BUNDLE_HEAD = new BundleState( "BUNDLE_HEAD" ); // Bundle head node public static final BundleState BUNDLE_TAIL = new BundleState( "BUNDLE_TAIL" ); // Passive bundle tail node @Override public String toString() { return m_State; } } /** * Internal vertex list datatype */ private static class VertexNode { float x; // X coordinate component float y; // Y coordinate component VertexNode next; // Pointer to next vertex in list public VertexNode( float x, float y ) { this.x = x ; this.y = y ; this.next = null ; } } /** * Internal contour / tristrip type */ private static class PolygonNode { int active; /* Active flag / vertex count */ boolean hole; /* Hole / external contour flag */ VertexNode[] v = new VertexNode[2] ; /* Left and right vertex list ptrs */ PolygonNode next; /* Pointer to next polygon contour */ PolygonNode proxy; /* Pointer to actual structure used */ public PolygonNode() { /* Make v[LEFT] and v[RIGHT] point to new vertex */ this.v[LEFT ] = null ; this.v[RIGHT] = null ; this.next = null ; this.proxy = this ; /* Initialise proxy to point to p itself */ this.active = 1 ; //TRUE } public PolygonNode( PolygonNode next, float x, float y ) { /* Make v[LEFT] and v[RIGHT] point to new vertex */ VertexNode vn = new VertexNode( x, y ); this.v[LEFT ] = vn ; this.v[RIGHT] = vn ; this.next = next ; this.proxy = this ; /* Initialise proxy to point to p itself */ this.active = 1 ; //TRUE } public void add_right( float x, float y ) { VertexNode nv = new VertexNode( x, y ); /* Add vertex nv to the right end of the polygon's vertex list */ proxy.v[RIGHT].next= nv; /* Update proxy->v[RIGHT] to point to nv */ proxy.v[RIGHT]= nv; } public void add_left( float x, float y) { VertexNode nv = new VertexNode( x, y ); /* Add vertex nv to the left end of the polygon's vertex list */ nv.next= proxy.v[LEFT]; /* Update proxy->[LEFT] to point to nv */ proxy.v[LEFT]= nv; } } private static class TopPolygonNode { PolygonNode 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) { /* Assign p's vertex list to the left end of q's list */ p.proxy.v[RIGHT].next= q.proxy.v[LEFT]; q.proxy.v[LEFT]= p.proxy.v[LEFT]; /* 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) { /* Assign p's vertex list to the right end of q's list */ q.proxy.v[RIGHT].next= p.proxy.v[LEFT]; q.proxy.v[RIGHT]= p.proxy.v[RIGHT]; /* 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= 0; for (VertexNode v= polygon.proxy.v[LEFT]; (v != null); v = v.next) { nv++; } /* Record valid vertex counts in the active field */ if (nv > 2) { polygon.active = nv; nc++; } else { /* Invalid contour: just free the heap */ // VertexNode nextv = null ; // for (VertexNode v= polygon.proxy.v[LEFT]; (v != null); v = nextv) // { // nextv= v.next; // v = null ; // } polygon.active= 0; } } } return nc; } public RPolygon getResult( Class polyClass ) { //RPolygon result = createNewPoly( polyClass ); RPolygon result = new RPolygon(); int num_contours = count_contours(); if (num_contours > 0) { 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) { RContour contour; if(result.countContours()>0){ contour = result.contours[0]; }else{ contour = new RContour(); } //RPolygon poly = result ; if( num_contours > 0 ) { contour = new RContour(); //poly = createNewPoly( polyClass ); } if( poly_node.proxy.hole ) { contour.isHole = poly_node.proxy.hole; //poly.setIsHole( poly_node.proxy.hole ); } // ------------------------------------------------------------------------ // --- This algorithm puts the verticies into the poly in reverse order --- // ------------------------------------------------------------------------ for (VertexNode vtx = poly_node.proxy.v[LEFT]; (vtx != null) ; vtx = vtx.next ) { contour.addPoint(vtx.x, vtx.y); //poly.add( vtx.x, vtx.y ); } if( num_contours > 0 ) { result.addContour(contour); //result.add( poly ); } c++; } } // ----------------------------------------- // --- Sort holes to the end of the list --- // ----------------------------------------- RPolygon orig = new RPolygon(result) ; result = new RPolygon(); //result = createNewPoly( polyClass ); for( int i = 0 ; i < orig.countContours() ; i++ ) //for( int i = 0 ; i < orig.getNumInnerPoly() ; i++ ) { RContour inner = orig.contours[i]; //RPolygon inner = orig.getInnerPoly(i); if( !inner.isHole() ) { result.addContour(inner); //result.add(inner); } } for( int i = 0 ; i < orig.countContours() ; i++ ) //for( int i = 0 ; i < orig.getNumInnerPoly() ; i++ ) { RContour inner = orig.contours[i]; //RPolygon inner = orig.getInnerPoly(i); if( inner.isHole() ) { result.addContour(inner); } } } return result ; } public void print() { System.out.println("---- out_poly ----"); int c= 0; PolygonNode npoly_node = null ; for (PolygonNode poly_node= top_node; (poly_node != null); poly_node = npoly_node) { System.out.println("contour="+c+" active="+poly_node.active+" hole="+poly_node.proxy.hole); npoly_node = poly_node.next; if (poly_node.active != 0) { int v=0 ; for (VertexNode vtx = poly_node.proxy.v[LEFT]; (vtx != null) ; vtx = vtx.next ) { System.out.println("v="+v+" vtx.x="+vtx.x+" vtx.y="+vtx.y); } c++; } } } } private static class EdgeNode { RPoint vertex = new RPoint(); /* Piggy-backed contour vertex data */ RPoint bot = new RPoint(); /* Edge lower (x, y) coordinate */ RPoint top = new RPoint(); /* Edge upper (x, y) coordinate */ 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 = new int[2][2]; /* Bundle edge flags */ int[] bside = new int[2]; /* Bundle left / right indicators */ BundleState[] bstate = new BundleState[2]; /* Edge bundle state */ PolygonNode[] outp = new PolygonNode[2]; /* 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 */ } private static class AetTree { EdgeNode top_node ; public void print() { System.out.println(""); System.out.println("aet"); for( EdgeNode edge = top_node ; (edge != null) ; edge = edge.next ) { System.out.println("edge.vertex.x="+edge.vertex.x+" edge.vertex.y="+edge.vertex.y); } } } private static class EdgeTable { private List m_List = new ArrayList<>(); public void addNode( float x, float y ) { EdgeNode node = new EdgeNode(); node.vertex.x = x ; node.vertex.y = y ; m_List.add( node ); } public EdgeNode getNode( int index ) { return (EdgeNode)m_List.get(index); } public boolean FWD_MIN( int i ) { EdgeNode prev = (EdgeNode)m_List.get(PREV_INDEX(i, m_List.size())); EdgeNode next = (EdgeNode)m_List.get(NEXT_INDEX(i, m_List.size())); EdgeNode ith = (EdgeNode)m_List.get(i); return ((prev.vertex.getY() >= ith.vertex.getY()) && (next.vertex.getY() > ith.vertex.getY())); } public boolean NOT_FMAX( int i ) { EdgeNode next = (EdgeNode)m_List.get(NEXT_INDEX(i, m_List.size())); EdgeNode ith = (EdgeNode)m_List.get(i); return(next.vertex.getY() > ith.vertex.getY()); } public boolean REV_MIN( int i ) { EdgeNode prev = (EdgeNode)m_List.get(PREV_INDEX(i, m_List.size())); EdgeNode next = (EdgeNode)m_List.get(NEXT_INDEX(i, m_List.size())); EdgeNode ith = (EdgeNode)m_List.get(i); return ((prev.vertex.getY() > ith.vertex.getY()) && (next.vertex.getY() >= ith.vertex.getY())); } public boolean NOT_RMAX( int i ) { EdgeNode prev = (EdgeNode)m_List.get(PREV_INDEX(i, m_List.size())); EdgeNode ith = (EdgeNode)m_List.get(i); return (prev.vertex.getY() > ith.vertex.getY()) ; } } /** * Local minima table */ private static class LmtNode { float y; /* Y coordinate at local minimum */ EdgeNode first_bound; /* Pointer to bound list */ LmtNode next; /* Pointer to next local minimum */ public LmtNode( float yvalue ) { y = yvalue ; } } private static class LmtTable { LmtNode top_node ; public void print() { int n = 0 ; LmtNode lmt = top_node ; while( lmt != null ) { System.out.println("lmt("+n+")"); for( EdgeNode edge = lmt.first_bound ; (edge != null) ; edge = edge.next_bound ) { System.out.println("edge.vertex.x="+edge.vertex.x+" edge.vertex.y="+edge.vertex.y); } n++ ; lmt = lmt.next ; } } } /** * Scanbeam tree */ private static class ScanBeamTree { float y; /* Scanbeam node y value */ ScanBeamTree less; /* Pointer to nodes with lower y */ ScanBeamTree more; /* Pointer to nodes with higher y */ public ScanBeamTree( float yvalue ) { y = yvalue ; } } /** * */ private static class ScanBeamTreeEntries { int sbt_entries ; ScanBeamTree sb_tree ; public float[] build_sbt() { float[] sbt = new float[sbt_entries] ; int entries = 0 ; entries = inner_build_sbt( entries, sbt, sb_tree ); if( entries != sbt_entries ) { throw new IllegalStateException("Something went wrong buildign sbt from tree."); } return sbt ; } private int inner_build_sbt( int entries, float[] sbt, ScanBeamTree sbt_node ) { if( sbt_node.less != null ) { entries = inner_build_sbt(entries, sbt, sbt_node.less); } sbt[entries]= sbt_node.y; entries++; if( sbt_node.more != null ) { entries = inner_build_sbt(entries, sbt, sbt_node.more ); } return entries ; } } /** * Intersection table */ private static class ItNode { EdgeNode[] ie = new EdgeNode[2]; /* Intersecting edge (bundle) pair */ RPoint point = new RPoint(); /* Point of intersection */ ItNode next; /* The next intersection table node */ public ItNode( EdgeNode edge0, EdgeNode edge1, float x, float y, ItNode next ) { this.ie[0] = edge0 ; this.ie[1] = edge1 ; this.point.x = x ; this.point.y = y ; this.next = next ; } } private static class ItNodeTable { ItNode top_node ; public void build_intersection_table(AetTree aet, float dy) { StNode st = null ; /* Process each AET edge */ for (EdgeNode edge = aet.top_node ; (edge != null); edge = edge.next) { if( (edge.bstate[ABOVE] == BundleState.BUNDLE_HEAD) || (edge.bundle[ABOVE][CLIP] != 0) || (edge.bundle[ABOVE][SUBJ] != 0) ) { st = add_st_edge(st, this, edge, dy); } } } } /** * Sorted edge table */ private static class StNode { EdgeNode edge; /* Pointer to AET edge */ float xb; /* Scanbeam bottom x coordinate */ float xt; /* Scanbeam top x coordinate */ float dx; /* Change in x for a unit y increase */ StNode prev; /* Previous edge in sorted list */ public StNode( EdgeNode edge, StNode prev ) { this.edge = edge ; this.xb = edge.xb ; this.xt = edge.xt ; this.dx = edge.dx ; this.prev = prev ; } } // ------------- // --- DEBUG --- // ------------- private static void print_sbt( float[] sbt ) { System.out.println(""); System.out.println("sbt.length="+sbt.length); for( int i = 0 ; i < sbt.length ; i++ ) { System.out.println("sbt["+i+"]="+sbt[i]); } } }