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