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