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