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