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