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