1 /* 2 * Copyright (c) 1998, 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package sun.java2d.pipe; 27 28 import java.awt.Rectangle; 29 import java.awt.Shape; 30 import java.awt.geom.AffineTransform; 31 import java.awt.geom.RectangularShape; 32 33 import sun.java2d.loops.TransformHelper; 34 35 /** 36 * This class encapsulates a definition of a two dimensional region which 37 * consists of a number of Y ranges each containing multiple X bands. 38 * <p> 39 * A rectangular Region is allowed to have a null band list in which 40 * case the rectangular shape is defined by the bounding box parameters 41 * (lox, loy, hix, hiy). 42 * <p> 43 * The band list, if present, consists of a list of rows in ascending Y 44 * order, ending at endIndex which is the index beyond the end of the 45 * last row. Each row consists of at least 3 + 2n entries (n >= 1) 46 * where the first 3 entries specify the Y range as start, end, and 47 * the number of X ranges in that Y range. These 3 entries are 48 * followed by pairs of X coordinates in ascending order: 49 * <pre> 50 * bands[rowstart+0] = Y0; // starting Y coordinate 51 * bands[rowstart+1] = Y1; // ending Y coordinate - endY > startY 52 * bands[rowstart+2] = N; // number of X bands - N >= 1 53 * 54 * bands[rowstart+3] = X10; // starting X coordinate of first band 55 * bands[rowstart+4] = X11; // ending X coordinate of first band 56 * bands[rowstart+5] = X20; // starting X coordinate of second band 57 * bands[rowstart+6] = X21; // ending X coordinate of second band 58 * ... 59 * bands[rowstart+3+N*2-2] = XN0; // starting X coord of last band 60 * bands[rowstart+3+N*2-1] = XN1; // ending X coord of last band 61 * 62 * bands[rowstart+3+N*2] = ... // start of next Y row 63 * </pre> 64 */ 65 public final class Region { 66 private static final int INIT_SIZE = 50; 67 private static final int GROW_SIZE = 50; 68 69 public static final Region EMPTY_REGION = new Region(0, 0, 0, 0); 70 public static final Region WHOLE_REGION = new Region( 71 Integer.MIN_VALUE, 72 Integer.MIN_VALUE, 73 Integer.MAX_VALUE, 74 Integer.MAX_VALUE); 75 76 private int lox; 77 private int loy; 78 private int hix; 79 private int hiy; 80 81 int endIndex; 82 int[] bands; 83 84 private static native void initIDs(); 85 86 static { 87 initIDs(); 88 } 89 90 /** 91 * Adds the dimension {@code dim} to the coordinate 92 * {@code start} with appropriate clipping. If 93 * {@code dim} is non-positive then the method returns 94 * the start coordinate. If the sum overflows an integer 95 * data type then the method returns {@code Integer.MAX_VALUE}. 96 */ 97 public static int dimAdd(int start, int dim) { 98 if (dim <= 0) return start; 99 if ((dim += start) < start) return Integer.MAX_VALUE; 100 return dim; 101 } 102 103 /** 104 * Adds the delta {@code dv} to the value {@code v} with 105 * appropriate clipping to the bounds of Integer resolution. 106 * If the answer would be greater than {@code Integer.MAX_VALUE} 107 * then {@code Integer.MAX_VALUE} is returned. 108 * If the answer would be less than {@code Integer.MIN_VALUE} 109 * then {@code Integer.MIN_VALUE} is returned. 110 * Otherwise the sum is returned. 111 */ 112 public static int clipAdd(int v, int dv) { 113 int newv = v + dv; 114 if ((newv > v) != (dv > 0)) { 115 newv = (dv < 0) ? Integer.MIN_VALUE : Integer.MAX_VALUE; 116 } 117 return newv; 118 } 119 120 /** 121 * Multiply the scale factor {@code sv} and the value {@code v} with 122 * appropriate clipping to the bounds of Integer resolution. If the answer 123 * would be greater than {@code Integer.MAX_VALUE} then {@code 124 * Integer.MAX_VALUE} is returned. If the answer would be less than {@code 125 * Integer.MIN_VALUE} then {@code Integer.MIN_VALUE} is returned. Otherwise 126 * the multiplication is returned. 127 */ 128 public static int clipScale(final int v, final double sv) { 129 if (sv == 1.0) { 130 return v; 131 } 132 final double newv = v * sv; 133 if (newv < Integer.MIN_VALUE) { 134 return Integer.MIN_VALUE; 135 } 136 if (newv > Integer.MAX_VALUE) { 137 return Integer.MAX_VALUE; 138 } 139 return (int) Math.round(newv); 140 } 141 142 private Region(int lox, int loy, int hix, int hiy) { 143 this.lox = lox; 144 this.loy = loy; 145 this.hix = hix; 146 this.hiy = hiy; 147 } 148 149 private Region(int lox, int loy, int hix, int hiy, int[] bands, int end) { 150 this.lox = lox; 151 this.loy = loy; 152 this.hix = hix; 153 this.hiy = hiy; 154 this.bands = bands; 155 this.endIndex = end; 156 } 157 158 /** 159 * Returns a Region object covering the pixels which would be 160 * touched by a fill or clip operation on a Graphics implementation 161 * on the specified Shape object under the optionally specified 162 * AffineTransform object. 163 * 164 * @param s a non-null Shape object specifying the geometry enclosing 165 * the pixels of interest 166 * @param at an optional {@code AffineTransform} to be applied to the 167 * coordinates as they are returned in the iteration, or 168 * {@code null} if untransformed coordinates are desired 169 */ 170 public static Region getInstance(Shape s, AffineTransform at) { 171 return getInstance(WHOLE_REGION, false, s, at); 172 } 173 174 /** 175 * Returns a Region object covering the pixels which would be 176 * touched by a fill or clip operation on a Graphics implementation 177 * on the specified Shape object under the optionally specified 178 * AffineTransform object further restricted by the specified 179 * device bounds. 180 * <p> 181 * Note that only the bounds of the specified Region are used to 182 * restrict the resulting Region. 183 * If devBounds is non-rectangular and clipping to the specific 184 * bands of devBounds is needed, then an intersection of the 185 * resulting Region with devBounds must be performed in a 186 * subsequent step. 187 * 188 * @param devBounds a non-null Region specifying some bounds to 189 * clip the geometry to 190 * @param s a non-null Shape object specifying the geometry enclosing 191 * the pixels of interest 192 * @param at an optional {@code AffineTransform} to be applied to the 193 * coordinates as they are returned in the iteration, or 194 * {@code null} if untransformed coordinates are desired 195 */ 196 public static Region getInstance(Region devBounds, 197 Shape s, AffineTransform at) 198 { 199 return getInstance(devBounds, false, s, at); 200 } 201 202 /** 203 * Returns a Region object covering the pixels which would be 204 * touched by a fill or clip operation on a Graphics implementation 205 * on the specified Shape object under the optionally specified 206 * AffineTransform object further restricted by the specified 207 * device bounds. 208 * If the normalize parameter is true then coordinate normalization 209 * is performed as per the 2D Graphics non-antialiasing implementation 210 * of the VALUE_STROKE_NORMALIZE hint. 211 * <p> 212 * Note that only the bounds of the specified Region are used to 213 * restrict the resulting Region. 214 * If devBounds is non-rectangular and clipping to the specific 215 * bands of devBounds is needed, then an intersection of the 216 * resulting Region with devBounds must be performed in a 217 * subsequent step. 218 * 219 * @param devBounds a non-null Region specifying some bounds to 220 * clip the geometry to 221 * @param normalize a boolean indicating whether or not to apply 222 * normalization 223 * @param s a non-null Shape object specifying the geometry enclosing 224 * the pixels of interest 225 * @param at an optional {@code AffineTransform} to be applied to the 226 * coordinates as they are returned in the iteration, or 227 * {@code null} if untransformed coordinates are desired 228 */ 229 public static Region getInstance(Region devBounds, boolean normalize, 230 Shape s, AffineTransform at) 231 { 232 // Optimize for empty shapes to avoid involving the SpanIterator 233 if (s instanceof RectangularShape && 234 ((RectangularShape)s).isEmpty()) 235 { 236 return EMPTY_REGION; 237 } 238 239 int box[] = new int[4]; 240 ShapeSpanIterator sr = new ShapeSpanIterator(normalize); 241 try { 242 sr.setOutputArea(devBounds); 243 sr.appendPath(s.getPathIterator(at)); 244 sr.getPathBox(box); 245 return Region.getInstance(box, sr); 246 } finally { 247 sr.dispose(); 248 } 249 } 250 251 /** 252 * Returns a Region object with a rectangle of interest specified by the 253 * indicated rectangular area in lox, loy, hix, hiy and edges array, which 254 * is located relative to the rectangular area. Edges array - 0,1 are y 255 * range, 2N,2N+1 are x ranges, 1 per y range. 256 * 257 * @see TransformHelper 258 */ 259 static Region getInstance(final int lox, final int loy, final int hix, 260 final int hiy, final int[] edges) { 261 final int y1 = edges[0]; 262 final int y2 = edges[1]; 263 if (hiy <= loy || hix <= lox || y2 <= y1) { 264 return EMPTY_REGION; 265 } 266 // rowsNum * (3 + 1 * 2) 267 final int[] bands = new int[(y2 - y1) * 5]; 268 int end = 0; 269 int index = 2; 270 for (int y = y1; y < y2; ++y) { 271 final int spanlox = Math.max(clipAdd(lox, edges[index++]), lox); 272 final int spanhix = Math.min(clipAdd(lox, edges[index++]), hix); 273 if (spanlox < spanhix) { 274 final int spanloy = Math.max(clipAdd(loy, y), loy); 275 final int spanhiy = Math.min(clipAdd(spanloy, 1), hiy); 276 if (spanloy < spanhiy) { 277 bands[end++] = spanloy; 278 bands[end++] = spanhiy; 279 bands[end++] = 1; // 1 span per row 280 bands[end++] = spanlox; 281 bands[end++] = spanhix; 282 } 283 } 284 } 285 return end != 0 ? new Region(lox, loy, hix, hiy, bands, end) 286 : EMPTY_REGION; 287 } 288 289 /** 290 * Returns a Region object with a rectangle of interest specified 291 * by the indicated Rectangle object. 292 * <p> 293 * This method can also be used to create a simple rectangular 294 * region. 295 */ 296 public static Region getInstance(Rectangle r) { 297 return Region.getInstanceXYWH(r.x, r.y, r.width, r.height); 298 } 299 300 /** 301 * Returns a Region object with a rectangle of interest specified 302 * by the indicated rectangular area in x, y, width, height format. 303 * <p> 304 * This method can also be used to create a simple rectangular 305 * region. 306 */ 307 public static Region getInstanceXYWH(int x, int y, int w, int h) { 308 return Region.getInstanceXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); 309 } 310 311 /** 312 * Returns a Region object with a rectangle of interest specified 313 * by the indicated span array. 314 * <p> 315 * This method can also be used to create a simple rectangular 316 * region. 317 */ 318 public static Region getInstance(int box[]) { 319 return new Region(box[0], box[1], box[2], box[3]); 320 } 321 322 /** 323 * Returns a Region object with a rectangle of interest specified 324 * by the indicated rectangular area in lox, loy, hix, hiy format. 325 * <p> 326 * This method can also be used to create a simple rectangular 327 * region. 328 */ 329 public static Region getInstanceXYXY(int lox, int loy, int hix, int hiy) { 330 return new Region(lox, loy, hix, hiy); 331 } 332 333 /** 334 * Returns a Region object with a rectangle of interest specified by the 335 * indicated rectangular area in lox, loy, hix, hiy format. 336 * <p/> 337 * Appends the list of spans returned from the indicated SpanIterator. Each 338 * span must be at a higher starting Y coordinate than the previous data or 339 * it must have a Y range equal to the highest Y band in the region and a 340 * higher X coordinate than any of the spans in that band. 341 */ 342 public static Region getInstance(int box[], SpanIterator si) { 343 Region ret = new Region(box[0], box[1], box[2], box[3]); 344 ret.appendSpans(si); 345 return ret; 346 } 347 348 /** 349 * Appends the list of spans returned from the indicated 350 * SpanIterator. Each span must be at a higher starting 351 * Y coordinate than the previous data or it must have a 352 * Y range equal to the highest Y band in the region and a 353 * higher X coordinate than any of the spans in that band. 354 */ 355 private void appendSpans(SpanIterator si) { 356 int[] box = new int[6]; 357 358 while (si.nextSpan(box)) { 359 appendSpan(box); 360 } 361 362 endRow(box); 363 calcBBox(); 364 } 365 366 /** 367 * Returns a Region object that represents the same list of rectangles as 368 * the current Region object, scaled by the specified sx, sy factors. 369 */ 370 public Region getScaledRegion(final double sx, final double sy) { 371 if (sx == 0 || sy == 0 || this == EMPTY_REGION) { 372 return EMPTY_REGION; 373 } 374 if ((sx == 1.0 && sy == 1.0) || (this == WHOLE_REGION)) { 375 return this; 376 } 377 378 int tlox = clipScale(lox, sx); 379 int tloy = clipScale(loy, sy); 380 int thix = clipScale(hix, sx); 381 int thiy = clipScale(hiy, sy); 382 Region ret = new Region(tlox, tloy, thix, thiy); 383 int bands[] = this.bands; 384 if (bands != null) { 385 int end = endIndex; 386 int newbands[] = new int[end]; 387 int i = 0; // index for source bands 388 int j = 0; // index for translated newbands 389 int ncol; 390 while (i < end) { 391 int y1, y2; 392 newbands[j++] = y1 = clipScale(bands[i++], sy); 393 newbands[j++] = y2 = clipScale(bands[i++], sy); 394 newbands[j++] = ncol = bands[i++]; 395 int savej = j; 396 if (y1 < y2) { 397 while (--ncol >= 0) { 398 int x1 = clipScale(bands[i++], sx); 399 int x2 = clipScale(bands[i++], sx); 400 if (x1 < x2) { 401 newbands[j++] = x1; 402 newbands[j++] = x2; 403 } 404 } 405 } else { 406 i += ncol * 2; 407 } 408 // Did we get any non-empty bands in this row? 409 if (j > savej) { 410 newbands[savej-1] = (j - savej) / 2; 411 } else { 412 j = savej - 3; 413 } 414 } 415 if (j <= 5) { 416 if (j < 5) { 417 // No rows or bands were generated... 418 ret.lox = ret.loy = ret.hix = ret.hiy = 0; 419 } else { 420 // Only generated one single rect in the end... 421 ret.loy = newbands[0]; 422 ret.hiy = newbands[1]; 423 ret.lox = newbands[3]; 424 ret.hix = newbands[4]; 425 } 426 // ret.endIndex and ret.bands were never initialized... 427 // ret.endIndex = 0; 428 // ret.newbands = null; 429 } else { 430 // Generated multiple bands and/or multiple rows... 431 ret.endIndex = j; 432 ret.bands = newbands; 433 } 434 } 435 return ret; 436 } 437 438 439 /** 440 * Returns a Region object that represents the same list of 441 * rectangles as the current Region object, translated by 442 * the specified dx, dy translation factors. 443 */ 444 public Region getTranslatedRegion(int dx, int dy) { 445 if ((dx | dy) == 0) { 446 return this; 447 } 448 int tlox = lox + dx; 449 int tloy = loy + dy; 450 int thix = hix + dx; 451 int thiy = hiy + dy; 452 if ((tlox > lox) != (dx > 0) || 453 (tloy > loy) != (dy > 0) || 454 (thix > hix) != (dx > 0) || 455 (thiy > hiy) != (dy > 0)) 456 { 457 return getSafeTranslatedRegion(dx, dy); 458 } 459 Region ret = new Region(tlox, tloy, thix, thiy); 460 int bands[] = this.bands; 461 if (bands != null) { 462 int end = endIndex; 463 ret.endIndex = end; 464 int newbands[] = new int[end]; 465 ret.bands = newbands; 466 int i = 0; 467 int ncol; 468 while (i < end) { 469 newbands[i] = bands[i] + dy; i++; 470 newbands[i] = bands[i] + dy; i++; 471 newbands[i] = ncol = bands[i]; i++; 472 while (--ncol >= 0) { 473 newbands[i] = bands[i] + dx; i++; 474 newbands[i] = bands[i] + dx; i++; 475 } 476 } 477 } 478 return ret; 479 } 480 481 private Region getSafeTranslatedRegion(int dx, int dy) { 482 int tlox = clipAdd(lox, dx); 483 int tloy = clipAdd(loy, dy); 484 int thix = clipAdd(hix, dx); 485 int thiy = clipAdd(hiy, dy); 486 Region ret = new Region(tlox, tloy, thix, thiy); 487 int bands[] = this.bands; 488 if (bands != null) { 489 int end = endIndex; 490 int newbands[] = new int[end]; 491 int i = 0; // index for source bands 492 int j = 0; // index for translated newbands 493 int ncol; 494 while (i < end) { 495 int y1, y2; 496 newbands[j++] = y1 = clipAdd(bands[i++], dy); 497 newbands[j++] = y2 = clipAdd(bands[i++], dy); 498 newbands[j++] = ncol = bands[i++]; 499 int savej = j; 500 if (y1 < y2) { 501 while (--ncol >= 0) { 502 int x1 = clipAdd(bands[i++], dx); 503 int x2 = clipAdd(bands[i++], dx); 504 if (x1 < x2) { 505 newbands[j++] = x1; 506 newbands[j++] = x2; 507 } 508 } 509 } else { 510 i += ncol * 2; 511 } 512 // Did we get any non-empty bands in this row? 513 if (j > savej) { 514 newbands[savej-1] = (j - savej) / 2; 515 } else { 516 j = savej - 3; 517 } 518 } 519 if (j <= 5) { 520 if (j < 5) { 521 // No rows or bands were generated... 522 ret.lox = ret.loy = ret.hix = ret.hiy = 0; 523 } else { 524 // Only generated one single rect in the end... 525 ret.loy = newbands[0]; 526 ret.hiy = newbands[1]; 527 ret.lox = newbands[3]; 528 ret.hix = newbands[4]; 529 } 530 // ret.endIndex and ret.bands were never initialized... 531 // ret.endIndex = 0; 532 // ret.newbands = null; 533 } else { 534 // Generated multiple bands and/or multiple rows... 535 ret.endIndex = j; 536 ret.bands = newbands; 537 } 538 } 539 return ret; 540 } 541 542 /** 543 * Returns a Region object that represents the intersection of 544 * this object with the specified Rectangle. The return value 545 * may be this same object if no clipping occurs. 546 */ 547 public Region getIntersection(Rectangle r) { 548 return getIntersectionXYWH(r.x, r.y, r.width, r.height); 549 } 550 551 /** 552 * Returns a Region object that represents the intersection of 553 * this object with the specified rectangular area. The return 554 * value may be this same object if no clipping occurs. 555 */ 556 public Region getIntersectionXYWH(int x, int y, int w, int h) { 557 return getIntersectionXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); 558 } 559 560 /** 561 * Returns a Region object that represents the intersection of 562 * this object with the specified rectangular area. The return 563 * value may be this same object if no clipping occurs. 564 */ 565 public Region getIntersectionXYXY(int lox, int loy, int hix, int hiy) { 566 if (isInsideXYXY(lox, loy, hix, hiy)) { 567 return this; 568 } 569 Region ret = new Region((lox < this.lox) ? this.lox : lox, 570 (loy < this.loy) ? this.loy : loy, 571 (hix > this.hix) ? this.hix : hix, 572 (hiy > this.hiy) ? this.hiy : hiy); 573 if (bands != null) { 574 ret.appendSpans(this.getSpanIterator()); 575 } 576 return ret; 577 } 578 579 /** 580 * Returns a Region object that represents the intersection of this 581 * object with the specified Region object. 582 * <p> 583 * If {@code A} and {@code B} are both Region Objects and 584 * {@code C = A.getIntersection(B);} then a point will 585 * be contained in {@code C} iff it is contained in both 586 * {@code A} and {@code B}. 587 * <p> 588 * The return value may be this same object or the argument 589 * Region object if no clipping occurs. 590 */ 591 public Region getIntersection(Region r) { 592 if (this.isInsideQuickCheck(r)) { 593 return this; 594 } 595 if (r.isInsideQuickCheck(this)) { 596 return r; 597 } 598 Region ret = new Region((r.lox < this.lox) ? this.lox : r.lox, 599 (r.loy < this.loy) ? this.loy : r.loy, 600 (r.hix > this.hix) ? this.hix : r.hix, 601 (r.hiy > this.hiy) ? this.hiy : r.hiy); 602 if (!ret.isEmpty()) { 603 ret.filterSpans(this, r, INCLUDE_COMMON); 604 } 605 return ret; 606 } 607 608 /** 609 * Returns a Region object that represents the union of this 610 * object with the specified Region object. 611 * <p> 612 * If {@code A} and {@code B} are both Region Objects and 613 * {@code C = A.getUnion(B);} then a point will 614 * be contained in {@code C} iff it is contained in either 615 * {@code A} or {@code B}. 616 * <p> 617 * The return value may be this same object or the argument 618 * Region object if no augmentation occurs. 619 */ 620 public Region getUnion(Region r) { 621 if (r.isEmpty() || r.isInsideQuickCheck(this)) { 622 return this; 623 } 624 if (this.isEmpty() || this.isInsideQuickCheck(r)) { 625 return r; 626 } 627 Region ret = new Region((r.lox > this.lox) ? this.lox : r.lox, 628 (r.loy > this.loy) ? this.loy : r.loy, 629 (r.hix < this.hix) ? this.hix : r.hix, 630 (r.hiy < this.hiy) ? this.hiy : r.hiy); 631 ret.filterSpans(this, r, INCLUDE_A | INCLUDE_B | INCLUDE_COMMON); 632 return ret; 633 } 634 635 /** 636 * Returns a Region object that represents the difference of the 637 * specified Region object subtracted from this object. 638 * <p> 639 * If {@code A} and {@code B} are both Region Objects and 640 * {@code C = A.getDifference(B);} then a point will 641 * be contained in {@code C} iff it is contained in 642 * {@code A} but not contained in {@code B}. 643 * <p> 644 * The return value may be this same object or the argument 645 * Region object if no clipping occurs. 646 */ 647 public Region getDifference(Region r) { 648 if (!r.intersectsQuickCheck(this)) { 649 return this; 650 } 651 if (this.isInsideQuickCheck(r)) { 652 return EMPTY_REGION; 653 } 654 Region ret = new Region(this.lox, this.loy, this.hix, this.hiy); 655 ret.filterSpans(this, r, INCLUDE_A); 656 return ret; 657 } 658 659 /** 660 * Returns a Region object that represents the exclusive or of this 661 * object with the specified Region object. 662 * <p> 663 * If {@code A} and {@code B} are both Region Objects and 664 * {@code C = A.getExclusiveOr(B);} then a point will 665 * be contained in {@code C} iff it is contained in either 666 * {@code A} or {@code B}, but not if it is contained in both. 667 * <p> 668 * The return value may be this same object or the argument 669 * Region object if either is empty. 670 */ 671 public Region getExclusiveOr(Region r) { 672 if (r.isEmpty()) { 673 return this; 674 } 675 if (this.isEmpty()) { 676 return r; 677 } 678 Region ret = new Region((r.lox > this.lox) ? this.lox : r.lox, 679 (r.loy > this.loy) ? this.loy : r.loy, 680 (r.hix < this.hix) ? this.hix : r.hix, 681 (r.hiy < this.hiy) ? this.hiy : r.hiy); 682 ret.filterSpans(this, r, INCLUDE_A | INCLUDE_B); 683 return ret; 684 } 685 686 private static final int INCLUDE_A = 1; 687 private static final int INCLUDE_B = 2; 688 private static final int INCLUDE_COMMON = 4; 689 690 private void filterSpans(Region ra, Region rb, int flags) { 691 int abands[] = ra.bands; 692 int bbands[] = rb.bands; 693 if (abands == null) { 694 abands = new int[] {ra.loy, ra.hiy, 1, ra.lox, ra.hix}; 695 } 696 if (bbands == null) { 697 bbands = new int[] {rb.loy, rb.hiy, 1, rb.lox, rb.hix}; 698 } 699 int box[] = new int[6]; 700 int acolstart = 0; 701 int ay1 = abands[acolstart++]; 702 int ay2 = abands[acolstart++]; 703 int acolend = abands[acolstart++]; 704 acolend = acolstart + 2 * acolend; 705 int bcolstart = 0; 706 int by1 = bbands[bcolstart++]; 707 int by2 = bbands[bcolstart++]; 708 int bcolend = bbands[bcolstart++]; 709 bcolend = bcolstart + 2 * bcolend; 710 int y = loy; 711 while (y < hiy) { 712 if (y >= ay2) { 713 if (acolend < ra.endIndex) { 714 acolstart = acolend; 715 ay1 = abands[acolstart++]; 716 ay2 = abands[acolstart++]; 717 acolend = abands[acolstart++]; 718 acolend = acolstart + 2 * acolend; 719 } else { 720 if ((flags & INCLUDE_B) == 0) break; 721 ay1 = ay2 = hiy; 722 } 723 continue; 724 } 725 if (y >= by2) { 726 if (bcolend < rb.endIndex) { 727 bcolstart = bcolend; 728 by1 = bbands[bcolstart++]; 729 by2 = bbands[bcolstart++]; 730 bcolend = bbands[bcolstart++]; 731 bcolend = bcolstart + 2 * bcolend; 732 } else { 733 if ((flags & INCLUDE_A) == 0) break; 734 by1 = by2 = hiy; 735 } 736 continue; 737 } 738 int yend; 739 if (y < by1) { 740 if (y < ay1) { 741 y = Math.min(ay1, by1); 742 continue; 743 } 744 // We are in a set of rows that belong only to A 745 yend = Math.min(ay2, by1); 746 if ((flags & INCLUDE_A) != 0) { 747 box[1] = y; 748 box[3] = yend; 749 int acol = acolstart; 750 while (acol < acolend) { 751 box[0] = abands[acol++]; 752 box[2] = abands[acol++]; 753 appendSpan(box); 754 } 755 } 756 } else if (y < ay1) { 757 // We are in a set of rows that belong only to B 758 yend = Math.min(by2, ay1); 759 if ((flags & INCLUDE_B) != 0) { 760 box[1] = y; 761 box[3] = yend; 762 int bcol = bcolstart; 763 while (bcol < bcolend) { 764 box[0] = bbands[bcol++]; 765 box[2] = bbands[bcol++]; 766 appendSpan(box); 767 } 768 } 769 } else { 770 // We are in a set of rows that belong to both A and B 771 yend = Math.min(ay2, by2); 772 box[1] = y; 773 box[3] = yend; 774 int acol = acolstart; 775 int bcol = bcolstart; 776 int ax1 = abands[acol++]; 777 int ax2 = abands[acol++]; 778 int bx1 = bbands[bcol++]; 779 int bx2 = bbands[bcol++]; 780 int x = Math.min(ax1, bx1); 781 if (x < lox) x = lox; 782 while (x < hix) { 783 if (x >= ax2) { 784 if (acol < acolend) { 785 ax1 = abands[acol++]; 786 ax2 = abands[acol++]; 787 } else { 788 if ((flags & INCLUDE_B) == 0) break; 789 ax1 = ax2 = hix; 790 } 791 continue; 792 } 793 if (x >= bx2) { 794 if (bcol < bcolend) { 795 bx1 = bbands[bcol++]; 796 bx2 = bbands[bcol++]; 797 } else { 798 if ((flags & INCLUDE_A) == 0) break; 799 bx1 = bx2 = hix; 800 } 801 continue; 802 } 803 int xend; 804 boolean appendit; 805 if (x < bx1) { 806 if (x < ax1) { 807 xend = Math.min(ax1, bx1); 808 appendit = false; 809 } else { 810 xend = Math.min(ax2, bx1); 811 appendit = ((flags & INCLUDE_A) != 0); 812 } 813 } else if (x < ax1) { 814 xend = Math.min(ax1, bx2); 815 appendit = ((flags & INCLUDE_B) != 0); 816 } else { 817 xend = Math.min(ax2, bx2); 818 appendit = ((flags & INCLUDE_COMMON) != 0); 819 } 820 if (appendit) { 821 box[0] = x; 822 box[2] = xend; 823 appendSpan(box); 824 } 825 x = xend; 826 } 827 } 828 y = yend; 829 } 830 endRow(box); 831 calcBBox(); 832 } 833 834 /** 835 * Returns a Region object that represents the bounds of the 836 * intersection of this object with the bounds of the specified 837 * Region object. 838 * <p> 839 * The return value may be this same object if no clipping occurs 840 * and this Region is rectangular. 841 */ 842 public Region getBoundsIntersection(Rectangle r) { 843 return getBoundsIntersectionXYWH(r.x, r.y, r.width, r.height); 844 } 845 846 /** 847 * Returns a Region object that represents the bounds of the 848 * intersection of this object with the bounds of the specified 849 * rectangular area in x, y, width, height format. 850 * <p> 851 * The return value may be this same object if no clipping occurs 852 * and this Region is rectangular. 853 */ 854 public Region getBoundsIntersectionXYWH(int x, int y, int w, int h) { 855 return getBoundsIntersectionXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); 856 } 857 858 /** 859 * Returns a Region object that represents the bounds of the 860 * intersection of this object with the bounds of the specified 861 * rectangular area in lox, loy, hix, hiy format. 862 * <p> 863 * The return value may be this same object if no clipping occurs 864 * and this Region is rectangular. 865 */ 866 public Region getBoundsIntersectionXYXY(int lox, int loy, 867 int hix, int hiy) 868 { 869 if (this.bands == null && 870 this.lox >= lox && this.loy >= loy && 871 this.hix <= hix && this.hiy <= hiy) 872 { 873 return this; 874 } 875 return new Region((lox < this.lox) ? this.lox : lox, 876 (loy < this.loy) ? this.loy : loy, 877 (hix > this.hix) ? this.hix : hix, 878 (hiy > this.hiy) ? this.hiy : hiy); 879 } 880 881 /** 882 * Returns a Region object that represents the intersection of 883 * this object with the bounds of the specified Region object. 884 * <p> 885 * The return value may be this same object or the argument 886 * Region object if no clipping occurs and the Regions are 887 * rectangular. 888 */ 889 public Region getBoundsIntersection(Region r) { 890 if (this.encompasses(r)) { 891 return r; 892 } 893 if (r.encompasses(this)) { 894 return this; 895 } 896 return new Region((r.lox < this.lox) ? this.lox : r.lox, 897 (r.loy < this.loy) ? this.loy : r.loy, 898 (r.hix > this.hix) ? this.hix : r.hix, 899 (r.hiy > this.hiy) ? this.hiy : r.hiy); 900 } 901 902 /** 903 * Appends a single span defined by the 4 parameters 904 * spanlox, spanloy, spanhix, spanhiy. 905 * This span must be at a higher starting Y coordinate than 906 * the previous data or it must have a Y range equal to the 907 * highest Y band in the region and a higher X coordinate 908 * than any of the spans in that band. 909 */ 910 private void appendSpan(int box[]) { 911 int spanlox, spanloy, spanhix, spanhiy; 912 if ((spanlox = box[0]) < lox) spanlox = lox; 913 if ((spanloy = box[1]) < loy) spanloy = loy; 914 if ((spanhix = box[2]) > hix) spanhix = hix; 915 if ((spanhiy = box[3]) > hiy) spanhiy = hiy; 916 if (spanhix <= spanlox || spanhiy <= spanloy) { 917 return; 918 } 919 920 int curYrow = box[4]; 921 if (endIndex == 0 || spanloy >= bands[curYrow + 1]) { 922 if (bands == null) { 923 bands = new int[INIT_SIZE]; 924 } else { 925 needSpace(5); 926 endRow(box); 927 curYrow = box[4]; 928 } 929 bands[endIndex++] = spanloy; 930 bands[endIndex++] = spanhiy; 931 bands[endIndex++] = 0; 932 } else if (spanloy == bands[curYrow] && 933 spanhiy == bands[curYrow + 1] && 934 spanlox >= bands[endIndex - 1]) { 935 if (spanlox == bands[endIndex - 1]) { 936 bands[endIndex - 1] = spanhix; 937 return; 938 } 939 needSpace(2); 940 } else { 941 throw new InternalError("bad span"); 942 } 943 bands[endIndex++] = spanlox; 944 bands[endIndex++] = spanhix; 945 bands[curYrow + 2]++; 946 } 947 948 private void needSpace(int num) { 949 if (endIndex + num >= bands.length) { 950 int[] newbands = new int[bands.length + GROW_SIZE]; 951 System.arraycopy(bands, 0, newbands, 0, endIndex); 952 bands = newbands; 953 } 954 } 955 956 private void endRow(int box[]) { 957 int cur = box[4]; 958 int prev = box[5]; 959 if (cur > prev) { 960 int[] bands = this.bands; 961 if (bands[prev + 1] == bands[cur] && 962 bands[prev + 2] == bands[cur + 2]) 963 { 964 int num = bands[cur + 2] * 2; 965 cur += 3; 966 prev += 3; 967 while (num > 0) { 968 if (bands[cur++] != bands[prev++]) { 969 break; 970 } 971 num--; 972 } 973 if (num == 0) { 974 // prev == box[4] 975 bands[box[5] + 1] = bands[prev + 1]; 976 endIndex = prev; 977 return; 978 } 979 } 980 } 981 box[5] = box[4]; 982 box[4] = endIndex; 983 } 984 985 private void calcBBox() { 986 int[] bands = this.bands; 987 if (endIndex <= 5) { 988 if (endIndex == 0) { 989 lox = loy = hix = hiy = 0; 990 } else { 991 loy = bands[0]; 992 hiy = bands[1]; 993 lox = bands[3]; 994 hix = bands[4]; 995 endIndex = 0; 996 } 997 this.bands = null; 998 return; 999 } 1000 int lox = this.hix; 1001 int hix = this.lox; 1002 int hiyindex = 0; 1003 1004 int i = 0; 1005 while (i < endIndex) { 1006 hiyindex = i; 1007 int numbands = bands[i + 2]; 1008 i += 3; 1009 if (lox > bands[i]) { 1010 lox = bands[i]; 1011 } 1012 i += numbands * 2; 1013 if (hix < bands[i - 1]) { 1014 hix = bands[i - 1]; 1015 } 1016 } 1017 1018 this.lox = lox; 1019 this.loy = bands[0]; 1020 this.hix = hix; 1021 this.hiy = bands[hiyindex + 1]; 1022 } 1023 1024 /** 1025 * Returns the lowest X coordinate in the Region. 1026 */ 1027 public int getLoX() { 1028 return lox; 1029 } 1030 1031 /** 1032 * Returns the lowest Y coordinate in the Region. 1033 */ 1034 public int getLoY() { 1035 return loy; 1036 } 1037 1038 /** 1039 * Returns the highest X coordinate in the Region. 1040 */ 1041 public int getHiX() { 1042 return hix; 1043 } 1044 1045 /** 1046 * Returns the highest Y coordinate in the Region. 1047 */ 1048 public int getHiY() { 1049 return hiy; 1050 } 1051 1052 /** 1053 * Returns the width of this Region clipped to the range (0 - MAX_INT). 1054 */ 1055 public int getWidth() { 1056 if (hix < lox) return 0; 1057 int w; 1058 if ((w = hix - lox) < 0) { 1059 w = Integer.MAX_VALUE; 1060 } 1061 return w; 1062 } 1063 1064 /** 1065 * Returns the height of this Region clipped to the range (0 - MAX_INT). 1066 */ 1067 public int getHeight() { 1068 if (hiy < loy) return 0; 1069 int h; 1070 if ((h = hiy - loy) < 0) { 1071 h = Integer.MAX_VALUE; 1072 } 1073 return h; 1074 } 1075 1076 /** 1077 * Returns true iff this Region encloses no area. 1078 */ 1079 public boolean isEmpty() { 1080 return (hix <= lox || hiy <= loy); 1081 } 1082 1083 /** 1084 * Returns true iff this Region represents a single simple 1085 * rectangular area. 1086 */ 1087 public boolean isRectangular() { 1088 return (bands == null); 1089 } 1090 1091 /** 1092 * Returns true iff this Region contains the specified coordinate. 1093 */ 1094 public boolean contains(int x, int y) { 1095 if (x < lox || x >= hix || y < loy || y >= hiy) return false; 1096 if (bands == null) return true; 1097 int i = 0; 1098 while (i < endIndex) { 1099 if (y < bands[i++]) { 1100 return false; 1101 } 1102 if (y >= bands[i++]) { 1103 int numspans = bands[i++]; 1104 i += numspans * 2; 1105 } else { 1106 int end = bands[i++]; 1107 end = i + end * 2; 1108 while (i < end) { 1109 if (x < bands[i++]) return false; 1110 if (x < bands[i++]) return true; 1111 } 1112 return false; 1113 } 1114 } 1115 return false; 1116 } 1117 1118 /** 1119 * Returns true iff this Region lies inside the indicated 1120 * rectangular area specified in x, y, width, height format 1121 * with appropriate clipping performed as per the dimAdd method. 1122 */ 1123 public boolean isInsideXYWH(int x, int y, int w, int h) { 1124 return isInsideXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); 1125 } 1126 1127 /** 1128 * Returns true iff this Region lies inside the indicated 1129 * rectangular area specified in lox, loy, hix, hiy format. 1130 */ 1131 public boolean isInsideXYXY(int lox, int loy, int hix, int hiy) { 1132 return (this.lox >= lox && this.loy >= loy && 1133 this.hix <= hix && this.hiy <= hiy); 1134 1135 } 1136 1137 /** 1138 * Quickly checks if this Region lies inside the specified 1139 * Region object. 1140 * <p> 1141 * This method will return false if the specified Region 1142 * object is not a simple rectangle. 1143 */ 1144 public boolean isInsideQuickCheck(Region r) { 1145 return (r.bands == null && 1146 r.lox <= this.lox && r.loy <= this.loy && 1147 r.hix >= this.hix && r.hiy >= this.hiy); 1148 } 1149 1150 /** 1151 * Quickly checks if this Region intersects the specified 1152 * rectangular area specified in lox, loy, hix, hiy format. 1153 * <p> 1154 * This method tests only against the bounds of this region 1155 * and does not bother to test if the rectangular region 1156 * actually intersects any bands. 1157 */ 1158 public boolean intersectsQuickCheckXYXY(int lox, int loy, 1159 int hix, int hiy) 1160 { 1161 return (hix > this.lox && lox < this.hix && 1162 hiy > this.loy && loy < this.hiy); 1163 } 1164 1165 /** 1166 * Quickly checks if this Region intersects the specified 1167 * Region object. 1168 * <p> 1169 * This method tests only against the bounds of this region 1170 * and does not bother to test if the rectangular region 1171 * actually intersects any bands. 1172 */ 1173 public boolean intersectsQuickCheck(Region r) { 1174 return (r.hix > this.lox && r.lox < this.hix && 1175 r.hiy > this.loy && r.loy < this.hiy); 1176 } 1177 1178 /** 1179 * Quickly checks if this Region surrounds the specified 1180 * Region object. 1181 * <p> 1182 * This method will return false if this Region object is 1183 * not a simple rectangle. 1184 */ 1185 public boolean encompasses(Region r) { 1186 return (this.bands == null && 1187 this.lox <= r.lox && this.loy <= r.loy && 1188 this.hix >= r.hix && this.hiy >= r.hiy); 1189 } 1190 1191 /** 1192 * Quickly checks if this Region surrounds the specified 1193 * rectangular area specified in x, y, width, height format. 1194 * <p> 1195 * This method will return false if this Region object is 1196 * not a simple rectangle. 1197 */ 1198 public boolean encompassesXYWH(int x, int y, int w, int h) { 1199 return encompassesXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); 1200 } 1201 1202 /** 1203 * Quickly checks if this Region surrounds the specified 1204 * rectangular area specified in lox, loy, hix, hiy format. 1205 * <p> 1206 * This method will return false if this Region object is 1207 * not a simple rectangle. 1208 */ 1209 public boolean encompassesXYXY(int lox, int loy, int hix, int hiy) { 1210 return (this.bands == null && 1211 this.lox <= lox && this.loy <= loy && 1212 this.hix >= hix && this.hiy >= hiy); 1213 } 1214 1215 /** 1216 * Gets the bbox of the available spans, clipped to the OutputArea. 1217 */ 1218 public void getBounds(int pathbox[]) { 1219 pathbox[0] = lox; 1220 pathbox[1] = loy; 1221 pathbox[2] = hix; 1222 pathbox[3] = hiy; 1223 } 1224 1225 /** 1226 * Clips the indicated bbox array to the bounds of this Region. 1227 */ 1228 public void clipBoxToBounds(int bbox[]) { 1229 if (bbox[0] < lox) bbox[0] = lox; 1230 if (bbox[1] < loy) bbox[1] = loy; 1231 if (bbox[2] > hix) bbox[2] = hix; 1232 if (bbox[3] > hiy) bbox[3] = hiy; 1233 } 1234 1235 /** 1236 * Gets an iterator object to iterate over the spans in this region. 1237 */ 1238 public RegionIterator getIterator() { 1239 return new RegionIterator(this); 1240 } 1241 1242 /** 1243 * Gets a span iterator object that iterates over the spans in this region 1244 */ 1245 public SpanIterator getSpanIterator() { 1246 return new RegionSpanIterator(this); 1247 } 1248 1249 /** 1250 * Gets a span iterator object that iterates over the spans in this region 1251 * but clipped to the bounds given in the argument (xlo, ylo, xhi, yhi). 1252 */ 1253 public SpanIterator getSpanIterator(int bbox[]) { 1254 SpanIterator result = getSpanIterator(); 1255 result.intersectClipBox(bbox[0], bbox[1], bbox[2], bbox[3]); 1256 return result; 1257 } 1258 1259 /** 1260 * Returns a SpanIterator that is the argument iterator filtered by 1261 * this region. 1262 */ 1263 public SpanIterator filter(SpanIterator si) { 1264 if (bands == null) { 1265 si.intersectClipBox(lox, loy, hix, hiy); 1266 } else { 1267 si = new RegionClipSpanIterator(this, si); 1268 } 1269 return si; 1270 } 1271 1272 @Override 1273 public String toString() { 1274 StringBuilder sb = new StringBuilder(); 1275 sb.append("Region[["); 1276 sb.append(lox); 1277 sb.append(", "); 1278 sb.append(loy); 1279 sb.append(" => "); 1280 sb.append(hix); 1281 sb.append(", "); 1282 sb.append(hiy); 1283 sb.append(']'); 1284 if (bands != null) { 1285 int col = 0; 1286 while (col < endIndex) { 1287 sb.append("y{"); 1288 sb.append(bands[col++]); 1289 sb.append(','); 1290 sb.append(bands[col++]); 1291 sb.append("}["); 1292 int end = bands[col++]; 1293 end = col + end * 2; 1294 while (col < end) { 1295 sb.append("x("); 1296 sb.append(bands[col++]); 1297 sb.append(", "); 1298 sb.append(bands[col++]); 1299 sb.append(')'); 1300 } 1301 sb.append(']'); 1302 } 1303 } 1304 sb.append(']'); 1305 return sb.toString(); 1306 } 1307 1308 @Override 1309 public int hashCode() { 1310 return (isEmpty() ? 0 : (lox * 3 + loy * 5 + hix * 7 + hiy * 9)); 1311 } 1312 1313 @Override 1314 public boolean equals(Object o) { 1315 if (this == o) { 1316 return true; 1317 } 1318 if (!(o instanceof Region)) { 1319 return false; 1320 } 1321 Region r = (Region) o; 1322 if (this.isEmpty()) { 1323 return r.isEmpty(); 1324 } else if (r.isEmpty()) { 1325 return false; 1326 } 1327 if (r.lox != this.lox || r.loy != this.loy || 1328 r.hix != this.hix || r.hiy != this.hiy) 1329 { 1330 return false; 1331 } 1332 if (this.bands == null) { 1333 return (r.bands == null); 1334 } else if (r.bands == null) { 1335 return false; 1336 } 1337 if (this.endIndex != r.endIndex) { 1338 return false; 1339 } 1340 int abands[] = this.bands; 1341 int bbands[] = r.bands; 1342 for (int i = 0; i < endIndex; i++) { 1343 if (abands[i] != bbands[i]) { 1344 return false; 1345 } 1346 } 1347 return true; 1348 } 1349 }