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