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