001/** 002 * Copyright (c) 2011, The University of Southampton and the individual contributors. 003 * All rights reserved. 004 * 005 * Redistribution and use in source and binary forms, with or without modification, 006 * are permitted provided that the following conditions are met: 007 * 008 * * Redistributions of source code must retain the above copyright notice, 009 * this list of conditions and the following disclaimer. 010 * 011 * * Redistributions in binary form must reproduce the above copyright notice, 012 * this list of conditions and the following disclaimer in the documentation 013 * and/or other materials provided with the distribution. 014 * 015 * * Neither the name of the University of Southampton nor the names of its 016 * contributors may be used to endorse or promote products derived from this 017 * software without specific prior written permission. 018 * 019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 029 */ 030package org.openimaj.math.geometry.shape.util; 031 032import java.util.Hashtable; 033 034import org.openimaj.math.geometry.shape.Polygon; 035import org.openimaj.math.geometry.shape.Rectangle; 036import org.openimaj.math.geometry.shape.util.polygon.AetTree; 037import org.openimaj.math.geometry.shape.util.polygon.BundleState; 038import org.openimaj.math.geometry.shape.util.polygon.EdgeNode; 039import org.openimaj.math.geometry.shape.util.polygon.EdgeTable; 040import org.openimaj.math.geometry.shape.util.polygon.HState; 041import org.openimaj.math.geometry.shape.util.polygon.ItNode; 042import org.openimaj.math.geometry.shape.util.polygon.LmtNode; 043import org.openimaj.math.geometry.shape.util.polygon.LmtTable; 044import org.openimaj.math.geometry.shape.util.polygon.OperationType; 045import org.openimaj.math.geometry.shape.util.polygon.PolygonNode; 046import org.openimaj.math.geometry.shape.util.polygon.ScanBeamTree; 047import org.openimaj.math.geometry.shape.util.polygon.ScanBeamTreeEntries; 048import org.openimaj.math.geometry.shape.util.polygon.StNode; 049import org.openimaj.math.geometry.shape.util.polygon.TopPolygonNode; 050import org.openimaj.math.geometry.shape.util.polygon.VertexType; 051 052/** 053 * <code>PolygonUtils</code> is a Java version of the <i>General Polygon Clipper</i> 054 * algorithm developed by Alan Murta (gpc@cs.man.ac.uk). The home page for the 055 * original source can be found at <a 056 * href="http://www.cs.man.ac.uk/aig/staff/alan/software/" target="_blank"> 057 * http://www.cs.man.ac.uk/aig/staff/alan/software/</a>. 058 * <p> 059 * <b><code>polyClass:</code></b> Some of the public methods below take a 060 * <code>polyClass</code> argument. This <code>java.lang.Class</code> object is 061 * assumed to implement the <code>Polygon</code> interface and have a no 062 * argument constructor. This was done so that the user of the algorithm could 063 * create their own classes that implement the <code>Polygon</code> interface 064 * and still uses this algorithm. 065 * <p> 066 * <strong>Implementation Note:</strong> The converted algorithm does support 067 * the <i>difference</i> operation, but a public method has not been provided 068 * and it has not been tested. To do so, simply follow what has been done for 069 * <i>intersection</i>. 070 * 071 * @author Dan Bridenbecker, Solution Engineering, Inc. 072 */ 073public class PolygonUtils 074{ 075 // ----------------- 076 // --- Constants --- 077 // ----------------- 078 private static final boolean DEBUG = false; 079 080 private static final double GPC_EPSILON = 2.2204460492503131e-016; 081 082 // private static final String GPC_VERSION = "2.31" ; 083 084 /** LEFT */ 085 public static final int LEFT = 0; 086 087 /** RIGHT */ 088 public static final int RIGHT = 1; 089 090 /** ABOVE */ 091 public static final int ABOVE = 0; 092 093 /** BELOW */ 094 public static final int BELOW = 1; 095 096 /** CLIP */ 097 public static final int CLIP = 0; 098 099 /** SUBJ */ 100 public static final int SUBJ = 1; 101 102 // ------------------------ 103 // --- Member Variables --- 104 // ------------------------ 105 private Hashtable<Polygon, Boolean> contributions = new Hashtable<Polygon, Boolean>(); 106 107 // -------------------- 108 // --- Constructors --- 109 // -------------------- 110 /** Creates a new instance of PolygonUtils */ 111 public PolygonUtils() 112 { 113 } 114 115 /** 116 * Return the intersection of <code>p1</code> and <code>p2</code> where the 117 * return type is of <code>polyClass</code>. See the note in the class 118 * description for more on <ocde>polyClass</code>. 119 * 120 * @param p1 One of the polygons to perform the intersection with 121 * @param p2 One of the polygons to perform the intersection with 122 * @param polyClass The type of <code>Polygon</code> to return 123 * @return the resultant polygon 124 */ 125 public Polygon intersection( Polygon p1, Polygon p2, 126 Class<Polygon> polyClass ) 127 { 128 return clip( OperationType.GPC_INT, p1, p2, polyClass ); 129 } 130 131 /** 132 * Return the union of <code>p1</code> and <code>p2</code> where the return 133 * type is of <code>polyClass</code>. See the note in the class description 134 * for more on <ocde>polyClass</code>. 135 * 136 * @param p1 One of the polygons to perform the union with 137 * @param p2 One of the polygons to perform the union with 138 * @param polyClass The type of <code>Polygon</code> to return 139 * @return the resultant polygon 140 */ 141 public Polygon union( Polygon p1, Polygon p2, Class<Polygon> polyClass ) 142 { 143 return clip( OperationType.GPC_UNION, p1, p2, polyClass ); 144 } 145 146 /** 147 * Return the xor of <code>p1</code> and <code>p2</code> where the return 148 * type is of <code>polyClass</code>. See the note in the class description 149 * for more on <code>polyClass</code>. 150 * 151 * @param p1 One of the polygons to perform the xor with 152 * @param p2 One of the polygons to perform the xor with 153 * @param polyClass The type of <code>Polygon</code> to return 154 * @return the resultant polygon 155 */ 156 public Polygon xor( Polygon p1, Polygon p2, Class<Polygon> polyClass ) 157 { 158 return clip( OperationType.GPC_XOR, p1, p2, polyClass ); 159 } 160 161 /** 162 * Return the intersection of <code>p1</code> and <code>p2</code> where the 163 * return type is of <code>PolyDefault</code>. 164 * 165 * @param p1 One of the polygons to perform the intersection with 166 * @param p2 One of the polygons to perform the intersection with 167 * @return the resultant polygon 168 */ 169 public Polygon intersection( Polygon p1, Polygon p2 ) 170 { 171 return clip( OperationType.GPC_INT, p1, p2, Polygon.class ); 172 } 173 174 /** 175 * Return the union of <code>p1</code> and <code>p2</code> where the return 176 * type is of <code>PolyDefault</code>. 177 * 178 * @param p1 One of the polygons to performt he union with 179 * @param p2 One of the polygons to performt he union with 180 * @return the resultant polygon 181 */ 182 public Polygon union( Polygon p1, Polygon p2 ) 183 { 184 return clip( OperationType.GPC_UNION, p1, p2, Polygon.class ); 185 } 186 187 /** 188 * Return the xor of <code>p1</code> and <code>p2</code> where the return 189 * type is of <code>PolyDefault</code>. 190 * 191 * @param p1 One of the polygons to perform the xor with 192 * @param p2 One of the polygons to perform the xor with 193 * @return the resultant polygon 194 */ 195 public Polygon xor( Polygon p1, Polygon p2 ) 196 { 197 return clip( OperationType.GPC_XOR, p1, p2, Polygon.class ); 198 } 199 200 // ----------------------- 201 // --- Private Methods --- 202 // ----------------------- 203 204 /** 205 * Create a new <code>Polygon</code> type object using 206 * <code>polyClass</code>. 207 */ 208 private Polygon createNewPoly( Class<Polygon> polyClass ) 209 { 210 try 211 { 212 return (Polygon) polyClass.newInstance(); 213 } 214 catch( Exception e ) 215 { 216 throw new RuntimeException( e ); 217 } 218 } 219 220 /** 221 * <code>clip()</code> is the main method of the clipper algorithm. This is 222 * where the conversion from really begins. 223 */ 224 private Polygon clip( OperationType op, Polygon subj, Polygon clip, 225 Class<Polygon> polyClass ) 226 { 227 HState hs = new HState(); 228 Polygon result = createNewPoly( polyClass ); 229 230 /* Test for trivial NULL result cases */ 231 if( (subj.isEmpty() && clip.isEmpty()) 232 || (subj.isEmpty() && ((op == OperationType.GPC_INT) || 233 (op == OperationType.GPC_DIFF))) 234 || (clip.isEmpty() && (op == OperationType.GPC_INT)) ) 235 { 236 System.err.println( "Subject or clip is empty" ); 237 return result; 238 } 239 240 /* Identify potentialy contributing contours */ 241 if( ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF)) 242 && !subj.isEmpty() && !clip.isEmpty() ) 243 { 244 minimax_test( subj, clip, op ); 245 } 246 247 /* Build LMT */ 248 LmtTable lmt_table = new LmtTable(); 249 ScanBeamTreeEntries sbte = new ScanBeamTreeEntries(); 250 // EdgeTable s_heap = null ; 251 // EdgeTable c_heap = null ; 252 if( !subj.isEmpty() ) 253 { 254 /* s_heap = */build_lmt( lmt_table, sbte, subj, SUBJ, op ); 255 } 256 if( DEBUG ) 257 { 258 System.out.println( "" ); 259 System.out.println( " ------------ After build_lmt for subj ---------" ); 260 lmt_table.print(); 261 } 262 if( !clip.isEmpty() ) 263 { 264 /* c_heap = */build_lmt( lmt_table, sbte, clip, CLIP, op ); 265 } 266 if( DEBUG ) 267 { 268 System.out.println( "" ); 269 System.out.println( " ------------ After build_lmt for clip ---------" ); 270 lmt_table.print(); 271 } 272 273 /* Return a NULL result if no contours contribute */ 274 if( lmt_table.top_node == null ) 275 { 276 return result; 277 } 278 279 /* Build scanbeam table from scanbeam tree */ 280 double[] sbt = sbte.build_sbt(); 281 282 int[] parity = new int[2]; 283 parity[0] = LEFT; 284 parity[1] = LEFT; 285 286 /* Invert clip polygon for difference operation */ 287 if( op == OperationType.GPC_DIFF ) 288 { 289 parity[CLIP] = RIGHT; 290 } 291 292 if( DEBUG ) 293 { 294 print_sbt( sbt ); 295 } 296 297 LmtNode local_min = lmt_table.top_node; 298 299 TopPolygonNode out_poly = new TopPolygonNode(); // used to create 300 // resulting Polygon 301 302 AetTree aet = new AetTree(); 303 int scanbeam = 0; 304 305 /* Process each scanbeam */ 306 while( scanbeam < sbt.length ) 307 { 308 /* Set yb and yt to the bottom and top of the scanbeam */ 309 double yb = sbt[scanbeam++]; 310 double yt = 0.0; 311 double dy = 0.0; 312 if( scanbeam < sbt.length ) 313 { 314 yt = sbt[scanbeam]; 315 dy = yt - yb; 316 } 317 318 /* === SCANBEAM BOUNDARY PROCESSING ================================ */ 319 320 /* If LMT node corresponding to yb exists */ 321 if( local_min != null ) 322 { 323 if( local_min.y == yb ) 324 { 325 /* Add edges starting at this local minimum to the AET */ 326 for( EdgeNode edge = local_min.first_bound; (edge != null); edge = edge.next_bound ) 327 { 328 add_edge_to_aet( aet, edge ); 329 } 330 331 local_min = local_min.next; 332 } 333 } 334 335 if( DEBUG ) 336 { 337 aet.print(); 338 } 339 /* Set dummy previous x value */ 340 double px = -Double.MAX_VALUE; 341 342 /* Create bundles within AET */ 343 EdgeNode e0 = aet.top_node; 344 EdgeNode e1 = aet.top_node; 345 346 /* Set up bundle fields of first edge */ 347 aet.top_node.bundle[ABOVE][aet.top_node.type] = (aet.top_node.top.y != yb) ? 1 348 : 0; 349 aet.top_node.bundle[ABOVE][((aet.top_node.type == 0) ? 1 : 0)] = 0; 350 aet.top_node.bstate[ABOVE] = BundleState.UNBUNDLED; 351 352 for( EdgeNode next_edge = aet.top_node.next; (next_edge != null); next_edge = next_edge.next ) 353 { 354 int ne_type = next_edge.type; 355 int ne_type_opp = ((next_edge.type == 0) ? 1 : 0); // next edge 356 // type 357 // opposite 358 359 /* Set up bundle fields of next edge */ 360 next_edge.bundle[ABOVE][ne_type] = (next_edge.top.y != yb) ? 1 361 : 0; 362 next_edge.bundle[ABOVE][ne_type_opp] = 0; 363 next_edge.bstate[ABOVE] = BundleState.UNBUNDLED; 364 365 /* Bundle edges above the scanbeam boundary if they coincide */ 366 if( next_edge.bundle[ABOVE][ne_type] == 1 ) 367 { 368 if( EQ( e0.xb, next_edge.xb ) && EQ( e0.dx, next_edge.dx ) 369 && (e0.top.y != yb) ) 370 { 371 next_edge.bundle[ABOVE][ne_type] ^= e0.bundle[ABOVE][ne_type]; 372 next_edge.bundle[ABOVE][ne_type_opp] = e0.bundle[ABOVE][ne_type_opp]; 373 next_edge.bstate[ABOVE] = BundleState.BUNDLE_HEAD; 374 e0.bundle[ABOVE][CLIP] = 0; 375 e0.bundle[ABOVE][SUBJ] = 0; 376 e0.bstate[ABOVE] = BundleState.BUNDLE_TAIL; 377 } 378 e0 = next_edge; 379 } 380 } 381 382 int[] horiz = new int[2]; 383 horiz[CLIP] = HState.NH; 384 horiz[SUBJ] = HState.NH; 385 386 int[] exists = new int[2]; 387 exists[CLIP] = 0; 388 exists[SUBJ] = 0; 389 390 PolygonNode cf = null; 391 392 /* Process each edge at this scanbeam boundary */ 393 for( EdgeNode edge = aet.top_node; (edge != null); edge = edge.next ) 394 { 395 exists[CLIP] = edge.bundle[ABOVE][CLIP] 396 + (edge.bundle[BELOW][CLIP] << 1); 397 exists[SUBJ] = edge.bundle[ABOVE][SUBJ] 398 + (edge.bundle[BELOW][SUBJ] << 1); 399 400 if( (exists[CLIP] != 0) || (exists[SUBJ] != 0) ) 401 { 402 /* Set bundle side */ 403 edge.bside[CLIP] = parity[CLIP]; 404 edge.bside[SUBJ] = parity[SUBJ]; 405 406 boolean contributing = false; 407 int br = 0, bl = 0, tr = 0, tl = 0; 408 /* Determine contributing status and quadrant occupancies */ 409 if( (op == OperationType.GPC_DIFF) 410 || (op == OperationType.GPC_INT) ) 411 { 412 contributing = ((exists[CLIP] != 0) && ((parity[SUBJ] != 0) || (horiz[SUBJ] != 0))) 413 || ((exists[SUBJ] != 0) && ((parity[CLIP] != 0) || (horiz[CLIP] != 0))) 414 || ((exists[CLIP] != 0) && (exists[SUBJ] != 0) && (parity[CLIP] == parity[SUBJ])); 415 br = ((parity[CLIP] != 0) && (parity[SUBJ] != 0)) ? 1 416 : 0; 417 bl = (((parity[CLIP] ^ edge.bundle[ABOVE][CLIP]) != 0) && ((parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ]) != 0)) ? 1 418 : 0; 419 tr = (((parity[CLIP] ^ ((horiz[CLIP] != HState.NH) ? 1 420 : 0)) != 0) && ((parity[SUBJ] ^ ((horiz[SUBJ] != HState.NH) ? 1 421 : 0)) != 0)) ? 1 : 0; 422 tl = (((parity[CLIP] 423 ^ ((horiz[CLIP] != HState.NH) ? 1 : 0) ^ edge.bundle[BELOW][CLIP]) != 0) && ((parity[SUBJ] 424 ^ ((horiz[SUBJ] != HState.NH) ? 1 : 0) ^ edge.bundle[BELOW][SUBJ]) != 0)) ? 1 425 : 0; 426 } 427 else if( op == OperationType.GPC_XOR ) 428 { 429 contributing = (exists[CLIP] != 0) 430 || (exists[SUBJ] != 0); 431 br = (parity[CLIP]) ^ (parity[SUBJ]); 432 bl = (parity[CLIP] ^ edge.bundle[ABOVE][CLIP]) 433 ^ (parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ]); 434 tr = (parity[CLIP] ^ ((horiz[CLIP] != HState.NH) ? 1 435 : 0)) 436 ^ (parity[SUBJ] ^ ((horiz[SUBJ] != HState.NH) ? 1 437 : 0)); 438 tl = (parity[CLIP] 439 ^ ((horiz[CLIP] != HState.NH) ? 1 : 0) ^ edge.bundle[BELOW][CLIP]) 440 ^ (parity[SUBJ] 441 ^ ((horiz[SUBJ] != HState.NH) ? 1 : 0) ^ edge.bundle[BELOW][SUBJ]); 442 } 443 else if( op == OperationType.GPC_UNION ) 444 { 445 contributing = ((exists[CLIP] != 0) && (!(parity[SUBJ] != 0) || (horiz[SUBJ] != 0))) 446 || ((exists[SUBJ] != 0) && (!(parity[CLIP] != 0) || (horiz[CLIP] != 0))) 447 || ((exists[CLIP] != 0) && (exists[SUBJ] != 0) && (parity[CLIP] == parity[SUBJ])); 448 br = ((parity[CLIP] != 0) || (parity[SUBJ] != 0)) ? 1 449 : 0; 450 bl = (((parity[CLIP] ^ edge.bundle[ABOVE][CLIP]) != 0) || ((parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ]) != 0)) ? 1 451 : 0; 452 tr = (((parity[CLIP] ^ ((horiz[CLIP] != HState.NH) ? 1 453 : 0)) != 0) || ((parity[SUBJ] ^ ((horiz[SUBJ] != HState.NH) ? 1 454 : 0)) != 0)) ? 1 : 0; 455 tl = (((parity[CLIP] 456 ^ ((horiz[CLIP] != HState.NH) ? 1 : 0) ^ edge.bundle[BELOW][CLIP]) != 0) || ((parity[SUBJ] 457 ^ ((horiz[SUBJ] != HState.NH) ? 1 : 0) ^ edge.bundle[BELOW][SUBJ]) != 0)) ? 1 458 : 0; 459 } 460 else 461 { 462 throw new IllegalStateException( "Unknown op" ); 463 } 464 465 /* Update parity */ 466 parity[CLIP] ^= edge.bundle[ABOVE][CLIP]; 467 parity[SUBJ] ^= edge.bundle[ABOVE][SUBJ]; 468 469 /* Update horizontal state */ 470 if( exists[CLIP] != 0 ) 471 { 472 horiz[CLIP] = hs.next_h_state[horiz[CLIP]][((exists[CLIP] - 1) << 1) 473 + parity[CLIP]]; 474 } 475 if( exists[SUBJ] != 0 ) 476 { 477 horiz[SUBJ] = hs.next_h_state[horiz[SUBJ]][((exists[SUBJ] - 1) << 1) 478 + parity[SUBJ]]; 479 } 480 481 if( contributing ) 482 { 483 double xb = edge.xb; 484 485 int vclass = VertexType.getType( tr, tl, br, bl ); 486 switch (vclass) 487 { 488 case VertexType.EMN: 489 case VertexType.IMN: 490 edge.outp[ABOVE] = out_poly.add_local_min( xb, 491 yb ); 492 px = xb; 493 cf = edge.outp[ABOVE]; 494 break; 495 case VertexType.ERI: 496 if( xb != px ) 497 { 498 cf.add_right( xb, yb ); 499 px = xb; 500 } 501 edge.outp[ABOVE] = cf; 502 cf = null; 503 break; 504 case VertexType.ELI: 505 edge.outp[BELOW].add_left( xb, yb ); 506 px = xb; 507 cf = edge.outp[BELOW]; 508 break; 509 case VertexType.EMX: 510 if( xb != px ) 511 { 512 cf.add_left( xb, yb ); 513 px = xb; 514 } 515 out_poly.merge_right( cf, edge.outp[BELOW] ); 516 cf = null; 517 break; 518 case VertexType.ILI: 519 if( xb != px ) 520 { 521 cf.add_left( xb, yb ); 522 px = xb; 523 } 524 edge.outp[ABOVE] = cf; 525 cf = null; 526 break; 527 case VertexType.IRI: 528 edge.outp[BELOW].add_right( xb, yb ); 529 px = xb; 530 cf = edge.outp[BELOW]; 531 edge.outp[BELOW] = null; 532 break; 533 case VertexType.IMX: 534 if( xb != px ) 535 { 536 cf.add_right( xb, yb ); 537 px = xb; 538 } 539 out_poly.merge_left( cf, edge.outp[BELOW] ); 540 cf = null; 541 edge.outp[BELOW] = null; 542 break; 543 case VertexType.IMM: 544 if( xb != px ) 545 { 546 cf.add_right( xb, yb ); 547 px = xb; 548 } 549 out_poly.merge_left( cf, edge.outp[BELOW] ); 550 edge.outp[BELOW] = null; 551 edge.outp[ABOVE] = out_poly.add_local_min( xb, 552 yb ); 553 cf = edge.outp[ABOVE]; 554 break; 555 case VertexType.EMM: 556 if( xb != px ) 557 { 558 cf.add_left( xb, yb ); 559 px = xb; 560 } 561 out_poly.merge_right( cf, edge.outp[BELOW] ); 562 edge.outp[BELOW] = null; 563 edge.outp[ABOVE] = out_poly.add_local_min( xb, 564 yb ); 565 cf = edge.outp[ABOVE]; 566 break; 567 case VertexType.LED: 568 if( edge.bot.y == yb ) 569 edge.outp[BELOW].add_left( xb, yb ); 570 edge.outp[ABOVE] = edge.outp[BELOW]; 571 px = xb; 572 break; 573 case VertexType.RED: 574 if( edge.bot.y == yb ) 575 edge.outp[BELOW].add_right( xb, yb ); 576 edge.outp[ABOVE] = edge.outp[BELOW]; 577 px = xb; 578 break; 579 default: 580 break; 581 } /* End of switch */ 582 } /* End of contributing conditional */ 583 } /* End of edge exists conditional */ 584 if( DEBUG ) 585 { 586 out_poly.print(); 587 } 588 } /* End of AET loop */ 589 590 /* Delete terminating edges from the AET, otherwise compute xt */ 591 for( EdgeNode edge = aet.top_node; (edge != null); edge = edge.next ) 592 { 593 if( edge.top.y == yb ) 594 { 595 EdgeNode prev_edge = edge.prev; 596 EdgeNode next_edge = edge.next; 597 598 if( prev_edge != null ) 599 prev_edge.next = next_edge; 600 else 601 aet.top_node = next_edge; 602 603 if( next_edge != null ) next_edge.prev = prev_edge; 604 605 /* 606 * Copy bundle head state to the adjacent tail edge if 607 * required 608 */ 609 if( (edge.bstate[BELOW] == BundleState.BUNDLE_HEAD) 610 && (prev_edge != null) ) 611 { 612 if( prev_edge.bstate[BELOW] == BundleState.BUNDLE_TAIL ) 613 { 614 prev_edge.outp[BELOW] = edge.outp[BELOW]; 615 prev_edge.bstate[BELOW] = BundleState.UNBUNDLED; 616 if( prev_edge.prev != null ) 617 { 618 if( prev_edge.prev.bstate[BELOW] == BundleState.BUNDLE_TAIL ) 619 { 620 prev_edge.bstate[BELOW] = BundleState.BUNDLE_HEAD; 621 } 622 } 623 } 624 } 625 } 626 else 627 { 628 if( edge.top.y == yt ) 629 edge.xt = edge.top.x; 630 else 631 edge.xt = edge.bot.x + edge.dx * (yt - edge.bot.y); 632 } 633 } 634 635 if( scanbeam < sbte.sbt_entries ) 636 { 637 /* 638 * === SCANBEAM INTERIOR PROCESSING 639 * ============================== 640 */ 641 642 /* Build intersection table for the current scanbeam */ 643 ItNodeTable it_table = new ItNodeTable(); 644 it_table.build_intersection_table( aet, dy ); 645 646 /* Process each node in the intersection table */ 647 for( ItNode intersect = it_table.top_node; (intersect != null); intersect = intersect.next ) 648 { 649 e0 = intersect.ie[0]; 650 e1 = intersect.ie[1]; 651 652 /* Only generate output for contributing intersections */ 653 if( ((e0.bundle[ABOVE][CLIP] != 0) || (e0.bundle[ABOVE][SUBJ] != 0)) 654 && ((e1.bundle[ABOVE][CLIP] != 0) || (e1.bundle[ABOVE][SUBJ] != 0)) ) 655 { 656 PolygonNode p = e0.outp[ABOVE]; 657 PolygonNode q = e1.outp[ABOVE]; 658 double ix = intersect.point.x; 659 double iy = intersect.point.y + yb; 660 661 int in_clip = (((e0.bundle[ABOVE][CLIP] != 0) && !(e0.bside[CLIP] != 0)) 662 || ((e1.bundle[ABOVE][CLIP] != 0) && (e1.bside[CLIP] != 0)) || (!(e0.bundle[ABOVE][CLIP] != 0) 663 && !(e1.bundle[ABOVE][CLIP] != 0) 664 && (e0.bside[CLIP] != 0) && (e1.bside[CLIP] != 0))) ? 1 665 : 0; 666 667 int in_subj = (((e0.bundle[ABOVE][SUBJ] != 0) && !(e0.bside[SUBJ] != 0)) 668 || ((e1.bundle[ABOVE][SUBJ] != 0) && (e1.bside[SUBJ] != 0)) || (!(e0.bundle[ABOVE][SUBJ] != 0) 669 && !(e1.bundle[ABOVE][SUBJ] != 0) 670 && (e0.bside[SUBJ] != 0) && (e1.bside[SUBJ] != 0))) ? 1 671 : 0; 672 673 int tr = 0, tl = 0, br = 0, bl = 0; 674 /* Determine quadrant occupancies */ 675 if( (op == OperationType.GPC_DIFF) 676 || (op == OperationType.GPC_INT) ) 677 { 678 tr = ((in_clip != 0) && (in_subj != 0)) ? 1 : 0; 679 tl = (((in_clip ^ e1.bundle[ABOVE][CLIP]) != 0) && ((in_subj ^ e1.bundle[ABOVE][SUBJ]) != 0)) ? 1 680 : 0; 681 br = (((in_clip ^ e0.bundle[ABOVE][CLIP]) != 0) && ((in_subj ^ e0.bundle[ABOVE][SUBJ]) != 0)) ? 1 682 : 0; 683 bl = (((in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP]) != 0) && ((in_subj 684 ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ]) != 0)) ? 1 685 : 0; 686 } 687 else if( op == OperationType.GPC_XOR ) 688 { 689 tr = (in_clip) ^ (in_subj); 690 tl = (in_clip ^ e1.bundle[ABOVE][CLIP]) 691 ^ (in_subj ^ e1.bundle[ABOVE][SUBJ]); 692 br = (in_clip ^ e0.bundle[ABOVE][CLIP]) 693 ^ (in_subj ^ e0.bundle[ABOVE][SUBJ]); 694 bl = (in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP]) 695 ^ (in_subj ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ]); 696 } 697 else if( op == OperationType.GPC_UNION ) 698 { 699 tr = ((in_clip != 0) || (in_subj != 0)) ? 1 : 0; 700 tl = (((in_clip ^ e1.bundle[ABOVE][CLIP]) != 0) || ((in_subj ^ e1.bundle[ABOVE][SUBJ]) != 0)) ? 1 701 : 0; 702 br = (((in_clip ^ e0.bundle[ABOVE][CLIP]) != 0) || ((in_subj ^ e0.bundle[ABOVE][SUBJ]) != 0)) ? 1 703 : 0; 704 bl = (((in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP]) != 0) || ((in_subj 705 ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ]) != 0)) ? 1 706 : 0; 707 } 708 else 709 { 710 throw new IllegalStateException( 711 "Unknown op type, " + op ); 712 } 713 714 int vclass = VertexType.getType( tr, tl, br, bl ); 715 switch (vclass) 716 { 717 case VertexType.EMN: 718 e0.outp[ABOVE] = out_poly 719 .add_local_min( ix, iy ); 720 e1.outp[ABOVE] = e0.outp[ABOVE]; 721 break; 722 case VertexType.ERI: 723 if( p != null ) 724 { 725 p.add_right( ix, iy ); 726 e1.outp[ABOVE] = p; 727 e0.outp[ABOVE] = null; 728 } 729 break; 730 case VertexType.ELI: 731 if( q != null ) 732 { 733 q.add_left( ix, iy ); 734 e0.outp[ABOVE] = q; 735 e1.outp[ABOVE] = null; 736 } 737 break; 738 case VertexType.EMX: 739 if( (p != null) && (q != null) ) 740 { 741 p.add_left( ix, iy ); 742 out_poly.merge_right( p, q ); 743 e0.outp[ABOVE] = null; 744 e1.outp[ABOVE] = null; 745 } 746 break; 747 case VertexType.IMN: 748 e0.outp[ABOVE] = out_poly 749 .add_local_min( ix, iy ); 750 e1.outp[ABOVE] = e0.outp[ABOVE]; 751 break; 752 case VertexType.ILI: 753 if( p != null ) 754 { 755 p.add_left( ix, iy ); 756 e1.outp[ABOVE] = p; 757 e0.outp[ABOVE] = null; 758 } 759 break; 760 case VertexType.IRI: 761 if( q != null ) 762 { 763 q.add_right( ix, iy ); 764 e0.outp[ABOVE] = q; 765 e1.outp[ABOVE] = null; 766 } 767 break; 768 case VertexType.IMX: 769 if( (p != null) && (q != null) ) 770 { 771 p.add_right( ix, iy ); 772 out_poly.merge_left( p, q ); 773 e0.outp[ABOVE] = null; 774 e1.outp[ABOVE] = null; 775 } 776 break; 777 case VertexType.IMM: 778 if( (p != null) && (q != null) ) 779 { 780 p.add_right( ix, iy ); 781 out_poly.merge_left( p, q ); 782 e0.outp[ABOVE] = out_poly.add_local_min( 783 ix, iy ); 784 e1.outp[ABOVE] = e0.outp[ABOVE]; 785 } 786 break; 787 case VertexType.EMM: 788 if( (p != null) && (q != null) ) 789 { 790 p.add_left( ix, iy ); 791 out_poly.merge_right( p, q ); 792 e0.outp[ABOVE] = out_poly.add_local_min( 793 ix, iy ); 794 e1.outp[ABOVE] = e0.outp[ABOVE]; 795 } 796 break; 797 default: 798 break; 799 } /* End of switch */ 800 } /* End of contributing intersection conditional */ 801 802 /* Swap bundle sides in response to edge crossing */ 803 if( e0.bundle[ABOVE][CLIP] != 0 ) 804 e1.bside[CLIP] = (e1.bside[CLIP] == 0) ? 1 : 0; 805 if( e1.bundle[ABOVE][CLIP] != 0 ) 806 e0.bside[CLIP] = (e0.bside[CLIP] == 0) ? 1 : 0; 807 if( e0.bundle[ABOVE][SUBJ] != 0 ) 808 e1.bside[SUBJ] = (e1.bside[SUBJ] == 0) ? 1 : 0; 809 if( e1.bundle[ABOVE][SUBJ] != 0 ) 810 e0.bside[SUBJ] = (e0.bside[SUBJ] == 0) ? 1 : 0; 811 812 /* Swap e0 and e1 bundles in the AET */ 813 EdgeNode prev_edge = e0.prev; 814 EdgeNode next_edge = e1.next; 815 if( next_edge != null ) 816 { 817 next_edge.prev = e0; 818 } 819 820 if( e0.bstate[ABOVE] == BundleState.BUNDLE_HEAD ) 821 { 822 boolean search = true; 823 while( search ) 824 { 825 prev_edge = prev_edge.prev; 826 if( prev_edge != null ) 827 { 828 if( prev_edge.bstate[ABOVE] != BundleState.BUNDLE_TAIL ) 829 { 830 search = false; 831 } 832 } 833 else 834 { 835 search = false; 836 } 837 } 838 } 839 if( prev_edge == null ) 840 { 841 aet.top_node.prev = e1; 842 e1.next = aet.top_node; 843 aet.top_node = e0.next; 844 } 845 else 846 { 847 prev_edge.next.prev = e1; 848 e1.next = prev_edge.next; 849 prev_edge.next = e0.next; 850 } 851 e0.next.prev = prev_edge; 852 e1.next.prev = e1; 853 e0.next = next_edge; 854 if( DEBUG ) 855 { 856 out_poly.print(); 857 } 858 } /* End of IT loop */ 859 860 /* Prepare for next scanbeam */ 861 for( EdgeNode edge = aet.top_node; (edge != null); edge = edge.next ) 862 { 863 EdgeNode next_edge = edge.next; 864 EdgeNode succ_edge = edge.succ; 865 if( (edge.top.y == yt) && (succ_edge != null) ) 866 { 867 /* Replace AET edge by its successor */ 868 succ_edge.outp[BELOW] = edge.outp[ABOVE]; 869 succ_edge.bstate[BELOW] = edge.bstate[ABOVE]; 870 succ_edge.bundle[BELOW][CLIP] = edge.bundle[ABOVE][CLIP]; 871 succ_edge.bundle[BELOW][SUBJ] = edge.bundle[ABOVE][SUBJ]; 872 EdgeNode prev_edge = edge.prev; 873 if( prev_edge != null ) 874 prev_edge.next = succ_edge; 875 else 876 aet.top_node = succ_edge; 877 if( next_edge != null ) next_edge.prev = succ_edge; 878 succ_edge.prev = prev_edge; 879 succ_edge.next = next_edge; 880 } 881 else 882 { 883 /* Update this edge */ 884 edge.outp[BELOW] = edge.outp[ABOVE]; 885 edge.bstate[BELOW] = edge.bstate[ABOVE]; 886 edge.bundle[BELOW][CLIP] = edge.bundle[ABOVE][CLIP]; 887 edge.bundle[BELOW][SUBJ] = edge.bundle[ABOVE][SUBJ]; 888 edge.xb = edge.xt; 889 } 890 edge.outp[ABOVE] = null; 891 } 892 } 893 } /* === END OF SCANBEAM PROCESSING ================================== */ 894 895 /* Generate result polygon from out_poly */ 896 result = out_poly.getResult( polyClass ); 897 898 return result; 899 } 900 901 private static boolean EQ( double a, double b ) 902 { 903 return (Math.abs( a - b ) <= GPC_EPSILON); 904 } 905 906 /** 907 * @param i 908 * @param n 909 * @return previous index 910 */ 911 public static int PREV_INDEX( int i, int n ) 912 { 913 return ((i - 1 + n) % n); 914 } 915 916 /** 917 * @param i 918 * @param n 919 * @return next index 920 */ 921 public static int NEXT_INDEX( int i, int n ) 922 { 923 return ((i + 1) % n); 924 } 925 926 private boolean OPTIMAL( Polygon p, int i ) 927 { 928 return (p.getInnerPoly( 0 ).points 929 .get( PREV_INDEX( i, p.nVertices() ) ).getY() != p 930 .getInnerPoly( 0 ).points.get( i ).getY()) 931 || (p.getInnerPoly( 0 ).points.get( 932 NEXT_INDEX( i, p.nVertices() ) ).getY() != p 933 .getInnerPoly( 0 ).points.get( i ).getY()); 934 } 935 936 private static Rectangle[] create_contour_bboxes( Polygon p ) 937 { 938 Rectangle[] box = new Rectangle[p.getNumInnerPoly()]; 939 940 /* Construct contour bounding boxes */ 941 for( int c = 0; c < p.getNumInnerPoly(); c++ ) 942 { 943 Polygon inner_poly = p.getInnerPoly( c ); 944 box[c] = inner_poly.calculateRegularBoundingBox(); 945 } 946 return box; 947 } 948 949 private void minimax_test( Polygon subj, Polygon clip, OperationType op ) 950 { 951 Rectangle[] s_bbox = create_contour_bboxes( subj ); 952 Rectangle[] c_bbox = create_contour_bboxes( clip ); 953 954 int subj_num_poly = subj.getNumInnerPoly(); 955 int clip_num_poly = clip.getNumInnerPoly(); 956 boolean[][] o_table = new boolean[subj_num_poly][clip_num_poly]; 957 958 /* Check all subject contour bounding boxes against clip boxes */ 959 for( int s = 0; s < subj_num_poly; s++ ) 960 { 961 for( int c = 0; c < clip_num_poly; c++ ) 962 { 963 o_table[s][c] = (!((s_bbox[s].maxX() < c_bbox[c].minX()) || (s_bbox[s] 964 .minX() > c_bbox[c].maxX()))) 965 && (!((s_bbox[s].maxY() < c_bbox[c].minY()) || (s_bbox[s] 966 .minY() > c_bbox[c].maxY()))); 967 } 968 } 969 970 /* For each clip contour, search for any subject contour overlaps */ 971 for( int c = 0; c < clip_num_poly; c++ ) 972 { 973 boolean overlap = false; 974 for( int s = 0; !overlap && (s < subj_num_poly); s++ ) 975 { 976 overlap = o_table[s][c]; 977 } 978 if( !overlap ) 979 { 980 contributions.put( clip, false ); 981 // clip.setContributing( c, false ); // Flag non contributing 982 // status 983 } 984 } 985 986 if( op == OperationType.GPC_INT ) 987 { 988 /* For each subject contour, search for any clip contour overlaps */ 989 for( int s = 0; s < subj_num_poly; s++ ) 990 { 991 boolean overlap = false; 992 for( int c = 0; !overlap && (c < clip_num_poly); c++ ) 993 { 994 overlap = o_table[s][c]; 995 } 996 if( !overlap ) 997 { 998 contributions.put( subj, false ); 999 // subj.setContributing( s, false ); // Flag non 1000 // contributing status 1001 } 1002 } 1003 } 1004 } 1005 1006 private static LmtNode bound_list( LmtTable lmt_table, double y ) 1007 { 1008 if( lmt_table.top_node == null ) 1009 { 1010 lmt_table.top_node = new LmtNode( y ); 1011 return lmt_table.top_node; 1012 } 1013 else 1014 { 1015 LmtNode prev = null; 1016 LmtNode node = lmt_table.top_node; 1017 boolean done = false; 1018 while( !done ) 1019 { 1020 if( y < node.y ) 1021 { 1022 /* Insert a new LMT node before the current node */ 1023 LmtNode existing_node = node; 1024 node = new LmtNode( y ); 1025 node.next = existing_node; 1026 if( prev == null ) 1027 { 1028 lmt_table.top_node = node; 1029 } 1030 else 1031 { 1032 prev.next = node; 1033 } 1034 if( existing_node == lmt_table.top_node ) 1035 { 1036 lmt_table.top_node = node; 1037 } 1038 done = true; 1039 } 1040 else if( y > node.y ) 1041 { 1042 /* Head further up the LMT */ 1043 if( node.next == null ) 1044 { 1045 node.next = new LmtNode( y ); 1046 node = node.next; 1047 done = true; 1048 } 1049 else 1050 { 1051 prev = node; 1052 node = node.next; 1053 } 1054 } 1055 else 1056 { 1057 /* Use this existing LMT node */ 1058 done = true; 1059 } 1060 } 1061 return node; 1062 } 1063 } 1064 1065 private static void insert_bound( LmtNode lmt_node, EdgeNode e ) 1066 { 1067 if( lmt_node.first_bound == null ) 1068 { 1069 /* Link node e to the tail of the list */ 1070 lmt_node.first_bound = e; 1071 } 1072 else 1073 { 1074 boolean done = false; 1075 EdgeNode prev_bound = null; 1076 EdgeNode current_bound = lmt_node.first_bound; 1077 while( !done ) 1078 { 1079 /* Do primary sort on the x field */ 1080 if( e.bot.x < current_bound.bot.x ) 1081 { 1082 /* Insert a new node mid-list */ 1083 if( prev_bound == null ) 1084 { 1085 lmt_node.first_bound = e; 1086 } 1087 else 1088 { 1089 prev_bound.next_bound = e; 1090 } 1091 e.next_bound = current_bound; 1092 1093 EdgeNode existing_bound = current_bound; 1094 current_bound = e; 1095 current_bound.next_bound = existing_bound; 1096 if( lmt_node.first_bound == existing_bound ) 1097 { 1098 lmt_node.first_bound = current_bound; 1099 } 1100 done = true; 1101 } 1102 else if( e.bot.x == current_bound.bot.x ) 1103 { 1104 /* Do secondary sort on the dx field */ 1105 if( e.dx < current_bound.dx ) 1106 { 1107 /* Insert a new node mid-list */ 1108 if( prev_bound == null ) 1109 { 1110 lmt_node.first_bound = e; 1111 } 1112 else 1113 { 1114 prev_bound.next_bound = e; 1115 } 1116 e.next_bound = current_bound; 1117 EdgeNode existing_bound = current_bound; 1118 current_bound = e; 1119 current_bound.next_bound = existing_bound; 1120 if( lmt_node.first_bound == existing_bound ) 1121 { 1122 lmt_node.first_bound = current_bound; 1123 } 1124 done = true; 1125 } 1126 else 1127 { 1128 /* Head further down the list */ 1129 if( current_bound.next_bound == null ) 1130 { 1131 current_bound.next_bound = e; 1132 done = true; 1133 } 1134 else 1135 { 1136 prev_bound = current_bound; 1137 current_bound = current_bound.next_bound; 1138 } 1139 } 1140 } 1141 else 1142 { 1143 /* Head further down the list */ 1144 if( current_bound.next_bound == null ) 1145 { 1146 current_bound.next_bound = e; 1147 done = true; 1148 } 1149 else 1150 { 1151 prev_bound = current_bound; 1152 current_bound = current_bound.next_bound; 1153 } 1154 } 1155 } 1156 } 1157 } 1158 1159 private void add_edge_to_aet( AetTree aet, EdgeNode edge ) 1160 { 1161 if( aet.top_node == null ) 1162 { 1163 /* Append edge onto the tail end of the AET */ 1164 aet.top_node = edge; 1165 edge.prev = null; 1166 edge.next = null; 1167 } 1168 else 1169 { 1170 EdgeNode current_edge = aet.top_node; 1171 EdgeNode prev = null; 1172 boolean done = false; 1173 while( !done ) 1174 { 1175 /* Do primary sort on the xb field */ 1176 if( edge.xb < current_edge.xb ) 1177 { 1178 /* Insert edge here (before the AET edge) */ 1179 edge.prev = prev; 1180 edge.next = current_edge; 1181 current_edge.prev = edge; 1182 if( prev == null ) 1183 { 1184 aet.top_node = edge; 1185 } 1186 else 1187 { 1188 prev.next = edge; 1189 } 1190 if( current_edge == aet.top_node ) 1191 { 1192 aet.top_node = edge; 1193 } 1194 current_edge = edge; 1195 done = true; 1196 } 1197 else if( edge.xb == current_edge.xb ) 1198 { 1199 /* Do secondary sort on the dx field */ 1200 if( edge.dx < current_edge.dx ) 1201 { 1202 /* Insert edge here (before the AET edge) */ 1203 edge.prev = prev; 1204 edge.next = current_edge; 1205 current_edge.prev = edge; 1206 if( prev == null ) 1207 { 1208 aet.top_node = edge; 1209 } 1210 else 1211 { 1212 prev.next = edge; 1213 } 1214 // if( current_edge == aet.top_node ) 1215 // { 1216 // aet.top_node = edge ; 1217 // } 1218 // current_edge = edge ; 1219 done = true; 1220 } 1221 else 1222 { 1223 /* Head further into the AET */ 1224 prev = current_edge; 1225 if( current_edge.next == null ) 1226 { 1227 current_edge.next = edge; 1228 edge.prev = current_edge; 1229 edge.next = null; 1230 done = true; 1231 } 1232 else 1233 { 1234 current_edge = current_edge.next; 1235 } 1236 } 1237 } 1238 else 1239 { 1240 /* Head further into the AET */ 1241 prev = current_edge; 1242 if( current_edge.next == null ) 1243 { 1244 current_edge.next = edge; 1245 edge.prev = current_edge; 1246 edge.next = null; 1247 done = true; 1248 } 1249 else 1250 { 1251 current_edge = current_edge.next; 1252 } 1253 } 1254 } 1255 } 1256 } 1257 1258 private static void add_to_sbtree( ScanBeamTreeEntries sbte, double y ) 1259 { 1260 if( sbte.sb_tree == null ) 1261 { 1262 /* Add a new tree node here */ 1263 sbte.sb_tree = new ScanBeamTree( y ); 1264 sbte.sbt_entries++; 1265 return; 1266 } 1267 ScanBeamTree tree_node = sbte.sb_tree; 1268 boolean done = false; 1269 while( !done ) 1270 { 1271 if( tree_node.y > y ) 1272 { 1273 if( tree_node.less == null ) 1274 { 1275 tree_node.less = new ScanBeamTree( y ); 1276 sbte.sbt_entries++; 1277 done = true; 1278 } 1279 else 1280 { 1281 tree_node = tree_node.less; 1282 } 1283 } 1284 else if( tree_node.y < y ) 1285 { 1286 if( tree_node.more == null ) 1287 { 1288 tree_node.more = new ScanBeamTree( y ); 1289 sbte.sbt_entries++; 1290 done = true; 1291 } 1292 else 1293 { 1294 tree_node = tree_node.more; 1295 } 1296 } 1297 else 1298 { 1299 done = true; 1300 } 1301 } 1302 } 1303 1304 private EdgeTable build_lmt( LmtTable lmt_table, ScanBeamTreeEntries sbte, 1305 Polygon p, int type, // Polygon 1306 // type 1307 // SUBJ/CLIP 1308 OperationType op ) 1309 { 1310 /* Create the entire input polygon edge table in one go */ 1311 EdgeTable edge_table = new EdgeTable(); 1312 1313 for( int c = 0; c < p.getNumInnerPoly(); c++ ) 1314 { 1315 Polygon ip = p.getInnerPoly( c ); 1316 Boolean cc; 1317 if( (cc = contributions.get( ip )) != null && !cc ) 1318 { 1319 /* Ignore the non-contributing contour */ 1320 contributions.put( ip, true ); 1321 // ip.setContributing(0, true); 1322 } 1323 else 1324 { 1325 /* Perform contour optimisation */ 1326 int num_vertices = 0; 1327 int e_index = 0; 1328 edge_table = new EdgeTable(); 1329 for( int i = 0; i < ip.nVertices(); i++ ) 1330 { 1331 if( OPTIMAL( ip, i ) ) 1332 { 1333 double x = ip.getInnerPoly( 0 ).points.get( i ) 1334 .getX(); 1335 double y = ip.getInnerPoly( 0 ).points.get( i ) 1336 .getY(); 1337 edge_table.addNode( x, y ); 1338 1339 /* Record vertex in the scanbeam table */ 1340 add_to_sbtree( sbte, y ); 1341 1342 num_vertices++; 1343 } 1344 } 1345 1346 /* Do the contour forward pass */ 1347 for( int min = 0; min < num_vertices; min++ ) 1348 { 1349 /* If a forward local minimum... */ 1350 if( edge_table.FWD_MIN( min ) ) 1351 { 1352 /* Search for the next local maximum... */ 1353 int num_edges = 1; 1354 int max = NEXT_INDEX( min, num_vertices ); 1355 while( edge_table.NOT_FMAX( max ) ) 1356 { 1357 num_edges++; 1358 max = NEXT_INDEX( max, num_vertices ); 1359 } 1360 1361 /* Build the next edge list */ 1362 int v = min; 1363 EdgeNode e = edge_table.getNode( e_index ); 1364 e.bstate[BELOW] = BundleState.UNBUNDLED; 1365 e.bundle[BELOW][CLIP] = 0; 1366 e.bundle[BELOW][SUBJ] = 0; 1367 1368 for( int i = 0; i < num_edges; i++ ) 1369 { 1370 EdgeNode ei = edge_table.getNode( e_index + i ); 1371 EdgeNode ev = edge_table.getNode( v ); 1372 1373 ei.xb = ev.vertex.x; 1374 ei.bot.x = ev.vertex.x; 1375 ei.bot.y = ev.vertex.y; 1376 1377 v = NEXT_INDEX( v, num_vertices ); 1378 ev = edge_table.getNode( v ); 1379 1380 ei.top.x = ev.vertex.x; 1381 ei.top.y = ev.vertex.y; 1382 ei.dx = (ev.vertex.x - ei.bot.x) 1383 / (ei.top.y - ei.bot.y); 1384 ei.type = type; 1385 ei.outp[ABOVE] = null; 1386 ei.outp[BELOW] = null; 1387 ei.next = null; 1388 ei.prev = null; 1389 ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table 1390 .getNode( e_index + i + 1 ) : null; 1391 // ei.pred = ((num_edges > 1) && (i > 0)) ? 1392 // edge_table.getNode(e_index+i-1) : null ; 1393 ei.next_bound = null; 1394 ei.bside[CLIP] = (op == OperationType.GPC_DIFF) ? RIGHT 1395 : LEFT; 1396 ei.bside[SUBJ] = LEFT; 1397 } 1398 insert_bound( 1399 bound_list( lmt_table, 1400 edge_table.getNode( min ).vertex.y ), e ); 1401 if( DEBUG ) 1402 { 1403 System.out.println( "fwd" ); 1404 lmt_table.print(); 1405 } 1406 e_index += num_edges; 1407 } 1408 } 1409 1410 /* Do the contour reverse pass */ 1411 for( int min = 0; min < num_vertices; min++ ) 1412 { 1413 /* If a reverse local minimum... */ 1414 if( edge_table.REV_MIN( min ) ) 1415 { 1416 /* Search for the previous local maximum... */ 1417 int num_edges = 1; 1418 int max = PREV_INDEX( min, num_vertices ); 1419 while( edge_table.NOT_RMAX( max ) ) 1420 { 1421 num_edges++; 1422 max = PREV_INDEX( max, num_vertices ); 1423 } 1424 1425 /* Build the previous edge list */ 1426 int v = min; 1427 EdgeNode e = edge_table.getNode( e_index ); 1428 e.bstate[BELOW] = BundleState.UNBUNDLED; 1429 e.bundle[BELOW][CLIP] = 0; 1430 e.bundle[BELOW][SUBJ] = 0; 1431 1432 for( int i = 0; i < num_edges; i++ ) 1433 { 1434 EdgeNode ei = edge_table.getNode( e_index + i ); 1435 EdgeNode ev = edge_table.getNode( v ); 1436 1437 ei.xb = ev.vertex.x; 1438 ei.bot.x = ev.vertex.x; 1439 ei.bot.y = ev.vertex.y; 1440 1441 v = PREV_INDEX( v, num_vertices ); 1442 ev = edge_table.getNode( v ); 1443 1444 ei.top.x = ev.vertex.x; 1445 ei.top.y = ev.vertex.y; 1446 ei.dx = (ev.vertex.x - ei.bot.x) 1447 / (ei.top.y - ei.bot.y); 1448 ei.type = type; 1449 ei.outp[ABOVE] = null; 1450 ei.outp[BELOW] = null; 1451 ei.next = null; 1452 ei.prev = null; 1453 ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table 1454 .getNode( e_index + i + 1 ) : null; 1455 // ei.pred = ((num_edges > 1) && (i > 0)) ? 1456 // edge_table.getNode(e_index+i-1) : null ; 1457 ei.next_bound = null; 1458 ei.bside[CLIP] = (op == OperationType.GPC_DIFF) ? RIGHT 1459 : LEFT; 1460 ei.bside[SUBJ] = LEFT; 1461 } 1462 insert_bound( 1463 bound_list( lmt_table, 1464 edge_table.getNode( min ).vertex.y ), e ); 1465 if( DEBUG ) 1466 { 1467 System.out.println( "rev" ); 1468 lmt_table.print(); 1469 } 1470 e_index += num_edges; 1471 } 1472 } 1473 } 1474 } 1475 return edge_table; 1476 } 1477 1478 private StNode add_st_edge( StNode st, ItNodeTable it, EdgeNode edge, 1479 double dy ) 1480 { 1481 if( st == null ) 1482 { 1483 /* Append edge onto the tail end of the ST */ 1484 st = new StNode( edge, null ); 1485 } 1486 else 1487 { 1488 double den = (st.xt - st.xb) - (edge.xt - edge.xb); 1489 1490 /* If new edge and ST edge don't cross */ 1491 if( (edge.xt >= st.xt) || (edge.dx == st.dx) 1492 || (Math.abs( den ) <= GPC_EPSILON) ) 1493 { 1494 /* No intersection - insert edge here (before the ST edge) */ 1495 StNode existing_node = st; 1496 st = new StNode( edge, existing_node ); 1497 } 1498 else 1499 { 1500 /* Compute intersection between new edge and ST edge */ 1501 double r = (edge.xb - st.xb) / den; 1502 double x = st.xb + r * (st.xt - st.xb); 1503 double y = r * dy; 1504 1505 /* Insert the edge pointers and the intersection point in the IT */ 1506 it.top_node = add_intersection( it.top_node, st.edge, edge, x, 1507 y ); 1508 1509 /* Head further into the ST */ 1510 st.prev = add_st_edge( st.prev, it, edge, dy ); 1511 } 1512 } 1513 return st; 1514 } 1515 1516 private ItNode add_intersection( ItNode it_node, EdgeNode edge0, 1517 EdgeNode edge1, double x, double y ) 1518 { 1519 if( it_node == null ) 1520 { 1521 /* Append a new node to the tail of the list */ 1522 it_node = new ItNode( edge0, edge1, x, y, null ); 1523 } 1524 else 1525 { 1526 if( it_node.point.y > y ) 1527 { 1528 /* Insert a new node mid-list */ 1529 ItNode existing_node = it_node; 1530 it_node = new ItNode( edge0, edge1, x, y, existing_node ); 1531 } 1532 else 1533 { 1534 /* Head further down the list */ 1535 it_node.next = add_intersection( it_node.next, edge0, edge1, x, 1536 y ); 1537 } 1538 } 1539 return it_node; 1540 } 1541 1542 class ItNodeTable 1543 { 1544 ItNode top_node; 1545 1546 public void build_intersection_table( AetTree aet, double dy ) 1547 { 1548 StNode st = null; 1549 1550 /* Process each AET edge */ 1551 for( EdgeNode edge = aet.top_node; (edge != null); edge = edge.next ) 1552 { 1553 if( (edge.bstate[PolygonUtils.ABOVE] == BundleState.BUNDLE_HEAD) 1554 || (edge.bundle[PolygonUtils.ABOVE][PolygonUtils.CLIP] != 0) 1555 || (edge.bundle[PolygonUtils.ABOVE][PolygonUtils.SUBJ] != 0) ) 1556 { 1557 st = add_st_edge( st, this, edge, dy ); 1558 } 1559 } 1560 } 1561 } 1562 1563 // ------------- 1564 // --- DEBUG --- 1565 // ------------- 1566 private static void print_sbt( double[] sbt ) 1567 { 1568 System.out.println( "" ); 1569 System.out.println( "sbt.length=" + sbt.length ); 1570 for( int i = 0; i < sbt.length; i++ ) 1571 { 1572 System.out.println( "sbt[" + i + "]=" + sbt[i] ); 1573 } 1574 } 1575}