| /* |
| * Copyright (c) 1998, 2006, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package sun.java2d.pipe; |
| |
| import java.awt.Rectangle; |
| import java.awt.Shape; |
| import java.awt.geom.AffineTransform; |
| import java.awt.geom.RectangularShape; |
| |
| /** |
| * This class encapsulates a definition of a two dimensional region which |
| * consists of a number of Y ranges each containing multiple X bands. |
| * <p> |
| * A rectangular Region is allowed to have a null band list in which |
| * case the rectangular shape is defined by the bounding box parameters |
| * (lox, loy, hix, hiy). |
| * <p> |
| * The band list, if present, consists of a list of rows in ascending Y |
| * order, ending at endIndex which is the index beyond the end of the |
| * last row. Each row consists of at least 3 + 2n entries (n >= 1) |
| * where the first 3 entries specify the Y range as start, end, and |
| * the number of X ranges in that Y range. These 3 entries are |
| * followed by pairs of X coordinates in ascending order: |
| * <pre> |
| * bands[rowstart+0] = Y0; // starting Y coordinate |
| * bands[rowstart+1] = Y1; // ending Y coordinate - endY > startY |
| * bands[rowstart+2] = N; // number of X bands - N >= 1 |
| * |
| * bands[rowstart+3] = X10; // starting X coordinate of first band |
| * bands[rowstart+4] = X11; // ending X coordinate of first band |
| * bands[rowstart+5] = X20; // starting X coordinate of second band |
| * bands[rowstart+6] = X21; // ending X coordinate of second band |
| * ... |
| * bands[rowstart+3+N*2-2] = XN0; // starting X coord of last band |
| * bands[rowstart+3+N*2-1] = XN1; // ending X coord of last band |
| * |
| * bands[rowstart+3+N*2] = ... // start of next Y row |
| * </pre> |
| */ |
| public class Region { |
| static final int INIT_SIZE = 50; |
| static final int GROW_SIZE = 50; |
| |
| /** |
| * Immutable Region. |
| */ |
| private static final class ImmutableRegion extends Region { |
| protected ImmutableRegion(int lox, int loy, int hix, int hiy) { |
| super(lox, loy, hix, hiy); |
| } |
| |
| // Override all the methods that mutate the object |
| public void appendSpans(sun.java2d.pipe.SpanIterator si) {} |
| public void setOutputArea(java.awt.Rectangle r) {} |
| public void setOutputAreaXYWH(int x, int y, int w, int h) {} |
| public void setOutputArea(int[] box) {} |
| public void setOutputAreaXYXY(int lox, int loy, int hix, int hiy) {} |
| } |
| |
| public static final Region EMPTY_REGION = new ImmutableRegion(0, 0, 0, 0); |
| public static final Region WHOLE_REGION = new ImmutableRegion( |
| Integer.MIN_VALUE, |
| Integer.MIN_VALUE, |
| Integer.MAX_VALUE, |
| Integer.MAX_VALUE); |
| |
| int lox; |
| int loy; |
| int hix; |
| int hiy; |
| |
| int endIndex; |
| int[] bands; |
| |
| private static native void initIDs(); |
| |
| static { |
| initIDs(); |
| } |
| |
| /** |
| * Adds the dimension <code>dim</code> to the coordinate |
| * <code>start</code> with appropriate clipping. If |
| * <code>dim</code> is non-positive then the method returns |
| * the start coordinate. If the sum overflows an integer |
| * data type then the method returns <code>Integer.MAX_VALUE</code>. |
| */ |
| public static int dimAdd(int start, int dim) { |
| if (dim <= 0) return start; |
| if ((dim += start) < start) return Integer.MAX_VALUE; |
| return dim; |
| } |
| |
| /** |
| * Adds the delta {@code dv} to the value {@code v} with |
| * appropriate clipping to the bounds of Integer resolution. |
| * If the answer would be greater than {@code Integer.MAX_VALUE} |
| * then {@code Integer.MAX_VALUE} is returned. |
| * If the answer would be less than {@code Integer.MIN_VALUE} |
| * then {@code Integer.MIN_VALUE} is returned. |
| * Otherwise the sum is returned. |
| */ |
| public static int clipAdd(int v, int dv) { |
| int newv = v + dv; |
| if ((newv > v) != (dv > 0)) { |
| newv = (dv < 0) ? Integer.MIN_VALUE : Integer.MAX_VALUE; |
| } |
| return newv; |
| } |
| |
| /** |
| * Multiply the scale factor {@code sv} and the value {@code v} with |
| * appropriate clipping to the bounds of Integer resolution. If the answer |
| * would be greater than {@code Integer.MAX_VALUE} then {@code |
| * Integer.MAX_VALUE} is returned. If the answer would be less than {@code |
| * Integer.MIN_VALUE} then {@code Integer.MIN_VALUE} is returned. Otherwise |
| * the multiplication is returned. |
| */ |
| public static int clipScale(final int v, final double sv) { |
| if (sv == 1.0) { |
| return v; |
| } |
| final double newv = v * sv; |
| if (newv < Integer.MIN_VALUE) { |
| return Integer.MIN_VALUE; |
| } |
| if (newv > Integer.MAX_VALUE) { |
| return Integer.MAX_VALUE; |
| } |
| return (int) Math.round(newv); |
| } |
| |
| protected Region(int lox, int loy, int hix, int hiy) { |
| this.lox = lox; |
| this.loy = loy; |
| this.hix = hix; |
| this.hiy = hiy; |
| } |
| |
| /** |
| * Returns a Region object covering the pixels which would be |
| * touched by a fill or clip operation on a Graphics implementation |
| * on the specified Shape object under the optionally specified |
| * AffineTransform object. |
| * |
| * @param s a non-null Shape object specifying the geometry enclosing |
| * the pixels of interest |
| * @param at an optional <code>AffineTransform</code> to be applied to the |
| * coordinates as they are returned in the iteration, or |
| * <code>null</code> if untransformed coordinates are desired |
| */ |
| public static Region getInstance(Shape s, AffineTransform at) { |
| return getInstance(WHOLE_REGION, false, s, at); |
| } |
| |
| /** |
| * Returns a Region object covering the pixels which would be |
| * touched by a fill or clip operation on a Graphics implementation |
| * on the specified Shape object under the optionally specified |
| * AffineTransform object further restricted by the specified |
| * device bounds. |
| * <p> |
| * Note that only the bounds of the specified Region are used to |
| * restrict the resulting Region. |
| * If devBounds is non-rectangular and clipping to the specific |
| * bands of devBounds is needed, then an intersection of the |
| * resulting Region with devBounds must be performed in a |
| * subsequent step. |
| * |
| * @param devBounds a non-null Region specifying some bounds to |
| * clip the geometry to |
| * @param s a non-null Shape object specifying the geometry enclosing |
| * the pixels of interest |
| * @param at an optional <code>AffineTransform</code> to be applied to the |
| * coordinates as they are returned in the iteration, or |
| * <code>null</code> if untransformed coordinates are desired |
| */ |
| public static Region getInstance(Region devBounds, |
| Shape s, AffineTransform at) |
| { |
| return getInstance(devBounds, false, s, at); |
| } |
| |
| /** |
| * Returns a Region object covering the pixels which would be |
| * touched by a fill or clip operation on a Graphics implementation |
| * on the specified Shape object under the optionally specified |
| * AffineTransform object further restricted by the specified |
| * device bounds. |
| * If the normalize parameter is true then coordinate normalization |
| * is performed as per the 2D Graphics non-antialiasing implementation |
| * of the VALUE_STROKE_NORMALIZE hint. |
| * <p> |
| * Note that only the bounds of the specified Region are used to |
| * restrict the resulting Region. |
| * If devBounds is non-rectangular and clipping to the specific |
| * bands of devBounds is needed, then an intersection of the |
| * resulting Region with devBounds must be performed in a |
| * subsequent step. |
| * |
| * @param devBounds a non-null Region specifying some bounds to |
| * clip the geometry to |
| * @param normalize a boolean indicating whether or not to apply |
| * normalization |
| * @param s a non-null Shape object specifying the geometry enclosing |
| * the pixels of interest |
| * @param at an optional <code>AffineTransform</code> to be applied to the |
| * coordinates as they are returned in the iteration, or |
| * <code>null</code> if untransformed coordinates are desired |
| */ |
| public static Region getInstance(Region devBounds, boolean normalize, |
| Shape s, AffineTransform at) |
| { |
| // Optimize for empty shapes to avoid involving the SpanIterator |
| if (s instanceof RectangularShape && |
| ((RectangularShape)s).isEmpty()) |
| { |
| return EMPTY_REGION; |
| } |
| |
| int box[] = new int[4]; |
| ShapeSpanIterator sr = new ShapeSpanIterator(normalize); |
| try { |
| sr.setOutputArea(devBounds); |
| sr.appendPath(s.getPathIterator(at)); |
| sr.getPathBox(box); |
| Region r = Region.getInstance(box); |
| r.appendSpans(sr); |
| return r; |
| } finally { |
| sr.dispose(); |
| } |
| } |
| |
| /** |
| * Returns a Region object with a rectangle of interest specified |
| * by the indicated Rectangle object. |
| * <p> |
| * This method can also be used to create a simple rectangular |
| * region. |
| */ |
| public static Region getInstance(Rectangle r) { |
| return Region.getInstanceXYWH(r.x, r.y, r.width, r.height); |
| } |
| |
| /** |
| * Returns a Region object with a rectangle of interest specified |
| * by the indicated rectangular area in x, y, width, height format. |
| * <p> |
| * This method can also be used to create a simple rectangular |
| * region. |
| */ |
| public static Region getInstanceXYWH(int x, int y, int w, int h) { |
| return Region.getInstanceXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); |
| } |
| |
| /** |
| * Returns a Region object with a rectangle of interest specified |
| * by the indicated span array. |
| * <p> |
| * This method can also be used to create a simple rectangular |
| * region. |
| */ |
| public static Region getInstance(int box[]) { |
| return new Region(box[0], box[1], box[2], box[3]); |
| } |
| |
| /** |
| * Returns a Region object with a rectangle of interest specified |
| * by the indicated rectangular area in lox, loy, hix, hiy format. |
| * <p> |
| * This method can also be used to create a simple rectangular |
| * region. |
| */ |
| public static Region getInstanceXYXY(int lox, int loy, int hix, int hiy) { |
| return new Region(lox, loy, hix, hiy); |
| } |
| |
| /** |
| * Sets the rectangle of interest for storing and returning |
| * region bands. |
| * <p> |
| * This method can also be used to initialize a simple rectangular |
| * region. |
| */ |
| public void setOutputArea(Rectangle r) { |
| setOutputAreaXYWH(r.x, r.y, r.width, r.height); |
| } |
| |
| /** |
| * Sets the rectangle of interest for storing and returning |
| * region bands. The rectangle is specified in x, y, width, height |
| * format and appropriate clipping is performed as per the method |
| * <code>dimAdd</code>. |
| * <p> |
| * This method can also be used to initialize a simple rectangular |
| * region. |
| */ |
| public void setOutputAreaXYWH(int x, int y, int w, int h) { |
| setOutputAreaXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); |
| } |
| |
| /** |
| * Sets the rectangle of interest for storing and returning |
| * region bands. The rectangle is specified as a span array. |
| * <p> |
| * This method can also be used to initialize a simple rectangular |
| * region. |
| */ |
| public void setOutputArea(int box[]) { |
| this.lox = box[0]; |
| this.loy = box[1]; |
| this.hix = box[2]; |
| this.hiy = box[3]; |
| } |
| |
| /** |
| * Sets the rectangle of interest for storing and returning |
| * region bands. The rectangle is specified in lox, loy, |
| * hix, hiy format. |
| * <p> |
| * This method can also be used to initialize a simple rectangular |
| * region. |
| */ |
| public void setOutputAreaXYXY(int lox, int loy, int hix, int hiy) { |
| this.lox = lox; |
| this.loy = loy; |
| this.hix = hix; |
| this.hiy = hiy; |
| } |
| |
| /** |
| * Appends the list of spans returned from the indicated |
| * SpanIterator. Each span must be at a higher starting |
| * Y coordinate than the previous data or it must have a |
| * Y range equal to the highest Y band in the region and a |
| * higher X coordinate than any of the spans in that band. |
| */ |
| public void appendSpans(SpanIterator si) { |
| int[] box = new int[6]; |
| |
| while (si.nextSpan(box)) { |
| appendSpan(box); |
| } |
| |
| endRow(box); |
| calcBBox(); |
| } |
| |
| /** |
| * Returns a Region object that represents the same list of rectangles as |
| * the current Region object, scaled by the specified sx, sy factors. |
| */ |
| public Region getScaledRegion(final double sx, final double sy) { |
| if (sx == 0 || sy == 0 || this == EMPTY_REGION) { |
| return EMPTY_REGION; |
| } |
| if ((sx == 1.0 && sy == 1.0) || (this == WHOLE_REGION)) { |
| return this; |
| } |
| |
| int tlox = clipScale(lox, sx); |
| int tloy = clipScale(loy, sy); |
| int thix = clipScale(hix, sx); |
| int thiy = clipScale(hiy, sy); |
| Region ret = new Region(tlox, tloy, thix, thiy); |
| int bands[] = this.bands; |
| if (bands != null) { |
| int end = endIndex; |
| int newbands[] = new int[end]; |
| int i = 0; // index for source bands |
| int j = 0; // index for translated newbands |
| int ncol; |
| while (i < end) { |
| int y1, y2; |
| newbands[j++] = y1 = clipScale(bands[i++], sy); |
| newbands[j++] = y2 = clipScale(bands[i++], sy); |
| newbands[j++] = ncol = bands[i++]; |
| int savej = j; |
| if (y1 < y2) { |
| while (--ncol >= 0) { |
| int x1 = clipScale(bands[i++], sx); |
| int x2 = clipScale(bands[i++], sx); |
| if (x1 < x2) { |
| newbands[j++] = x1; |
| newbands[j++] = x2; |
| } |
| } |
| } else { |
| i += ncol * 2; |
| } |
| // Did we get any non-empty bands in this row? |
| if (j > savej) { |
| newbands[savej-1] = (j - savej) / 2; |
| } else { |
| j = savej - 3; |
| } |
| } |
| if (j <= 5) { |
| if (j < 5) { |
| // No rows or bands were generated... |
| ret.lox = ret.loy = ret.hix = ret.hiy = 0; |
| } else { |
| // Only generated one single rect in the end... |
| ret.loy = newbands[0]; |
| ret.hiy = newbands[1]; |
| ret.lox = newbands[3]; |
| ret.hix = newbands[4]; |
| } |
| // ret.endIndex and ret.bands were never initialized... |
| // ret.endIndex = 0; |
| // ret.newbands = null; |
| } else { |
| // Generated multiple bands and/or multiple rows... |
| ret.endIndex = j; |
| ret.bands = newbands; |
| } |
| } |
| return ret; |
| } |
| |
| |
| /** |
| * Returns a Region object that represents the same list of |
| * rectangles as the current Region object, translated by |
| * the specified dx, dy translation factors. |
| */ |
| public Region getTranslatedRegion(int dx, int dy) { |
| if ((dx | dy) == 0) { |
| return this; |
| } |
| int tlox = lox + dx; |
| int tloy = loy + dy; |
| int thix = hix + dx; |
| int thiy = hiy + dy; |
| if ((tlox > lox) != (dx > 0) || |
| (tloy > loy) != (dy > 0) || |
| (thix > hix) != (dx > 0) || |
| (thiy > hiy) != (dy > 0)) |
| { |
| return getSafeTranslatedRegion(dx, dy); |
| } |
| Region ret = new Region(tlox, tloy, thix, thiy); |
| int bands[] = this.bands; |
| if (bands != null) { |
| int end = endIndex; |
| ret.endIndex = end; |
| int newbands[] = new int[end]; |
| ret.bands = newbands; |
| int i = 0; |
| int ncol; |
| while (i < end) { |
| newbands[i] = bands[i] + dy; i++; |
| newbands[i] = bands[i] + dy; i++; |
| newbands[i] = ncol = bands[i]; i++; |
| while (--ncol >= 0) { |
| newbands[i] = bands[i] + dx; i++; |
| newbands[i] = bands[i] + dx; i++; |
| } |
| } |
| } |
| return ret; |
| } |
| |
| private Region getSafeTranslatedRegion(int dx, int dy) { |
| int tlox = clipAdd(lox, dx); |
| int tloy = clipAdd(loy, dy); |
| int thix = clipAdd(hix, dx); |
| int thiy = clipAdd(hiy, dy); |
| Region ret = new Region(tlox, tloy, thix, thiy); |
| int bands[] = this.bands; |
| if (bands != null) { |
| int end = endIndex; |
| int newbands[] = new int[end]; |
| int i = 0; // index for source bands |
| int j = 0; // index for translated newbands |
| int ncol; |
| while (i < end) { |
| int y1, y2; |
| newbands[j++] = y1 = clipAdd(bands[i++], dy); |
| newbands[j++] = y2 = clipAdd(bands[i++], dy); |
| newbands[j++] = ncol = bands[i++]; |
| int savej = j; |
| if (y1 < y2) { |
| while (--ncol >= 0) { |
| int x1 = clipAdd(bands[i++], dx); |
| int x2 = clipAdd(bands[i++], dx); |
| if (x1 < x2) { |
| newbands[j++] = x1; |
| newbands[j++] = x2; |
| } |
| } |
| } else { |
| i += ncol * 2; |
| } |
| // Did we get any non-empty bands in this row? |
| if (j > savej) { |
| newbands[savej-1] = (j - savej) / 2; |
| } else { |
| j = savej - 3; |
| } |
| } |
| if (j <= 5) { |
| if (j < 5) { |
| // No rows or bands were generated... |
| ret.lox = ret.loy = ret.hix = ret.hiy = 0; |
| } else { |
| // Only generated one single rect in the end... |
| ret.loy = newbands[0]; |
| ret.hiy = newbands[1]; |
| ret.lox = newbands[3]; |
| ret.hix = newbands[4]; |
| } |
| // ret.endIndex and ret.bands were never initialized... |
| // ret.endIndex = 0; |
| // ret.newbands = null; |
| } else { |
| // Generated multiple bands and/or multiple rows... |
| ret.endIndex = j; |
| ret.bands = newbands; |
| } |
| } |
| return ret; |
| } |
| |
| /** |
| * Returns a Region object that represents the intersection of |
| * this object with the specified Rectangle. The return value |
| * may be this same object if no clipping occurs. |
| */ |
| public Region getIntersection(Rectangle r) { |
| return getIntersectionXYWH(r.x, r.y, r.width, r.height); |
| } |
| |
| /** |
| * Returns a Region object that represents the intersection of |
| * this object with the specified rectangular area. The return |
| * value may be this same object if no clipping occurs. |
| */ |
| public Region getIntersectionXYWH(int x, int y, int w, int h) { |
| return getIntersectionXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); |
| } |
| |
| /** |
| * Returns a Region object that represents the intersection of |
| * this object with the specified rectangular area. The return |
| * value may be this same object if no clipping occurs. |
| */ |
| public Region getIntersectionXYXY(int lox, int loy, int hix, int hiy) { |
| if (isInsideXYXY(lox, loy, hix, hiy)) { |
| return this; |
| } |
| Region ret = new Region((lox < this.lox) ? this.lox : lox, |
| (loy < this.loy) ? this.loy : loy, |
| (hix > this.hix) ? this.hix : hix, |
| (hiy > this.hiy) ? this.hiy : hiy); |
| if (bands != null) { |
| ret.appendSpans(this.getSpanIterator()); |
| } |
| return ret; |
| } |
| |
| /** |
| * Returns a Region object that represents the intersection of this |
| * object with the specified Region object. |
| * <p> |
| * If {@code A} and {@code B} are both Region Objects and |
| * <code>C = A.getIntersection(B);</code> then a point will |
| * be contained in {@code C} iff it is contained in both |
| * {@code A} and {@code B}. |
| * <p> |
| * The return value may be this same object or the argument |
| * Region object if no clipping occurs. |
| */ |
| public Region getIntersection(Region r) { |
| if (this.isInsideQuickCheck(r)) { |
| return this; |
| } |
| if (r.isInsideQuickCheck(this)) { |
| return r; |
| } |
| Region ret = new Region((r.lox < this.lox) ? this.lox : r.lox, |
| (r.loy < this.loy) ? this.loy : r.loy, |
| (r.hix > this.hix) ? this.hix : r.hix, |
| (r.hiy > this.hiy) ? this.hiy : r.hiy); |
| if (!ret.isEmpty()) { |
| ret.filterSpans(this, r, INCLUDE_COMMON); |
| } |
| return ret; |
| } |
| |
| /** |
| * Returns a Region object that represents the union of this |
| * object with the specified Region object. |
| * <p> |
| * If {@code A} and {@code B} are both Region Objects and |
| * <code>C = A.getUnion(B);</code> then a point will |
| * be contained in {@code C} iff it is contained in either |
| * {@code A} or {@code B}. |
| * <p> |
| * The return value may be this same object or the argument |
| * Region object if no augmentation occurs. |
| */ |
| public Region getUnion(Region r) { |
| if (r.isEmpty() || r.isInsideQuickCheck(this)) { |
| return this; |
| } |
| if (this.isEmpty() || this.isInsideQuickCheck(r)) { |
| return r; |
| } |
| Region ret = new Region((r.lox > this.lox) ? this.lox : r.lox, |
| (r.loy > this.loy) ? this.loy : r.loy, |
| (r.hix < this.hix) ? this.hix : r.hix, |
| (r.hiy < this.hiy) ? this.hiy : r.hiy); |
| ret.filterSpans(this, r, INCLUDE_A | INCLUDE_B | INCLUDE_COMMON); |
| return ret; |
| } |
| |
| /** |
| * Returns a Region object that represents the difference of the |
| * specified Region object subtracted from this object. |
| * <p> |
| * If {@code A} and {@code B} are both Region Objects and |
| * <code>C = A.getDifference(B);</code> then a point will |
| * be contained in {@code C} iff it is contained in |
| * {@code A} but not contained in {@code B}. |
| * <p> |
| * The return value may be this same object or the argument |
| * Region object if no clipping occurs. |
| */ |
| public Region getDifference(Region r) { |
| if (!r.intersectsQuickCheck(this)) { |
| return this; |
| } |
| if (this.isInsideQuickCheck(r)) { |
| return EMPTY_REGION; |
| } |
| Region ret = new Region(this.lox, this.loy, this.hix, this.hiy); |
| ret.filterSpans(this, r, INCLUDE_A); |
| return ret; |
| } |
| |
| /** |
| * Returns a Region object that represents the exclusive or of this |
| * object with the specified Region object. |
| * <p> |
| * If {@code A} and {@code B} are both Region Objects and |
| * <code>C = A.getExclusiveOr(B);</code> then a point will |
| * be contained in {@code C} iff it is contained in either |
| * {@code A} or {@code B}, but not if it is contained in both. |
| * <p> |
| * The return value may be this same object or the argument |
| * Region object if either is empty. |
| */ |
| public Region getExclusiveOr(Region r) { |
| if (r.isEmpty()) { |
| return this; |
| } |
| if (this.isEmpty()) { |
| return r; |
| } |
| Region ret = new Region((r.lox > this.lox) ? this.lox : r.lox, |
| (r.loy > this.loy) ? this.loy : r.loy, |
| (r.hix < this.hix) ? this.hix : r.hix, |
| (r.hiy < this.hiy) ? this.hiy : r.hiy); |
| ret.filterSpans(this, r, INCLUDE_A | INCLUDE_B); |
| return ret; |
| } |
| |
| static final int INCLUDE_A = 1; |
| static final int INCLUDE_B = 2; |
| static final int INCLUDE_COMMON = 4; |
| |
| private void filterSpans(Region ra, Region rb, int flags) { |
| int abands[] = ra.bands; |
| int bbands[] = rb.bands; |
| if (abands == null) { |
| abands = new int[] {ra.loy, ra.hiy, 1, ra.lox, ra.hix}; |
| } |
| if (bbands == null) { |
| bbands = new int[] {rb.loy, rb.hiy, 1, rb.lox, rb.hix}; |
| } |
| int box[] = new int[6]; |
| int acolstart = 0; |
| int ay1 = abands[acolstart++]; |
| int ay2 = abands[acolstart++]; |
| int acolend = abands[acolstart++]; |
| acolend = acolstart + 2 * acolend; |
| int bcolstart = 0; |
| int by1 = bbands[bcolstart++]; |
| int by2 = bbands[bcolstart++]; |
| int bcolend = bbands[bcolstart++]; |
| bcolend = bcolstart + 2 * bcolend; |
| int y = loy; |
| while (y < hiy) { |
| if (y >= ay2) { |
| if (acolend < ra.endIndex) { |
| acolstart = acolend; |
| ay1 = abands[acolstart++]; |
| ay2 = abands[acolstart++]; |
| acolend = abands[acolstart++]; |
| acolend = acolstart + 2 * acolend; |
| } else { |
| if ((flags & INCLUDE_B) == 0) break; |
| ay1 = ay2 = hiy; |
| } |
| continue; |
| } |
| if (y >= by2) { |
| if (bcolend < rb.endIndex) { |
| bcolstart = bcolend; |
| by1 = bbands[bcolstart++]; |
| by2 = bbands[bcolstart++]; |
| bcolend = bbands[bcolstart++]; |
| bcolend = bcolstart + 2 * bcolend; |
| } else { |
| if ((flags & INCLUDE_A) == 0) break; |
| by1 = by2 = hiy; |
| } |
| continue; |
| } |
| int yend; |
| if (y < by1) { |
| if (y < ay1) { |
| y = Math.min(ay1, by1); |
| continue; |
| } |
| // We are in a set of rows that belong only to A |
| yend = Math.min(ay2, by1); |
| if ((flags & INCLUDE_A) != 0) { |
| box[1] = y; |
| box[3] = yend; |
| int acol = acolstart; |
| while (acol < acolend) { |
| box[0] = abands[acol++]; |
| box[2] = abands[acol++]; |
| appendSpan(box); |
| } |
| } |
| } else if (y < ay1) { |
| // We are in a set of rows that belong only to B |
| yend = Math.min(by2, ay1); |
| if ((flags & INCLUDE_B) != 0) { |
| box[1] = y; |
| box[3] = yend; |
| int bcol = bcolstart; |
| while (bcol < bcolend) { |
| box[0] = bbands[bcol++]; |
| box[2] = bbands[bcol++]; |
| appendSpan(box); |
| } |
| } |
| } else { |
| // We are in a set of rows that belong to both A and B |
| yend = Math.min(ay2, by2); |
| box[1] = y; |
| box[3] = yend; |
| int acol = acolstart; |
| int bcol = bcolstart; |
| int ax1 = abands[acol++]; |
| int ax2 = abands[acol++]; |
| int bx1 = bbands[bcol++]; |
| int bx2 = bbands[bcol++]; |
| int x = Math.min(ax1, bx1); |
| if (x < lox) x = lox; |
| while (x < hix) { |
| if (x >= ax2) { |
| if (acol < acolend) { |
| ax1 = abands[acol++]; |
| ax2 = abands[acol++]; |
| } else { |
| if ((flags & INCLUDE_B) == 0) break; |
| ax1 = ax2 = hix; |
| } |
| continue; |
| } |
| if (x >= bx2) { |
| if (bcol < bcolend) { |
| bx1 = bbands[bcol++]; |
| bx2 = bbands[bcol++]; |
| } else { |
| if ((flags & INCLUDE_A) == 0) break; |
| bx1 = bx2 = hix; |
| } |
| continue; |
| } |
| int xend; |
| boolean appendit; |
| if (x < bx1) { |
| if (x < ax1) { |
| xend = Math.min(ax1, bx1); |
| appendit = false; |
| } else { |
| xend = Math.min(ax2, bx1); |
| appendit = ((flags & INCLUDE_A) != 0); |
| } |
| } else if (x < ax1) { |
| xend = Math.min(ax1, bx2); |
| appendit = ((flags & INCLUDE_B) != 0); |
| } else { |
| xend = Math.min(ax2, bx2); |
| appendit = ((flags & INCLUDE_COMMON) != 0); |
| } |
| if (appendit) { |
| box[0] = x; |
| box[2] = xend; |
| appendSpan(box); |
| } |
| x = xend; |
| } |
| } |
| y = yend; |
| } |
| endRow(box); |
| calcBBox(); |
| } |
| |
| /** |
| * Returns a Region object that represents the bounds of the |
| * intersection of this object with the bounds of the specified |
| * Region object. |
| * <p> |
| * The return value may be this same object if no clipping occurs |
| * and this Region is rectangular. |
| */ |
| public Region getBoundsIntersection(Rectangle r) { |
| return getBoundsIntersectionXYWH(r.x, r.y, r.width, r.height); |
| } |
| |
| /** |
| * Returns a Region object that represents the bounds of the |
| * intersection of this object with the bounds of the specified |
| * rectangular area in x, y, width, height format. |
| * <p> |
| * The return value may be this same object if no clipping occurs |
| * and this Region is rectangular. |
| */ |
| public Region getBoundsIntersectionXYWH(int x, int y, int w, int h) { |
| return getBoundsIntersectionXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); |
| } |
| |
| /** |
| * Returns a Region object that represents the bounds of the |
| * intersection of this object with the bounds of the specified |
| * rectangular area in lox, loy, hix, hiy format. |
| * <p> |
| * The return value may be this same object if no clipping occurs |
| * and this Region is rectangular. |
| */ |
| public Region getBoundsIntersectionXYXY(int lox, int loy, |
| int hix, int hiy) |
| { |
| if (this.bands == null && |
| this.lox >= lox && this.loy >= loy && |
| this.hix <= hix && this.hiy <= hiy) |
| { |
| return this; |
| } |
| return new Region((lox < this.lox) ? this.lox : lox, |
| (loy < this.loy) ? this.loy : loy, |
| (hix > this.hix) ? this.hix : hix, |
| (hiy > this.hiy) ? this.hiy : hiy); |
| } |
| |
| /** |
| * Returns a Region object that represents the intersection of |
| * this object with the bounds of the specified Region object. |
| * <p> |
| * The return value may be this same object or the argument |
| * Region object if no clipping occurs and the Regions are |
| * rectangular. |
| */ |
| public Region getBoundsIntersection(Region r) { |
| if (this.encompasses(r)) { |
| return r; |
| } |
| if (r.encompasses(this)) { |
| return this; |
| } |
| return new Region((r.lox < this.lox) ? this.lox : r.lox, |
| (r.loy < this.loy) ? this.loy : r.loy, |
| (r.hix > this.hix) ? this.hix : r.hix, |
| (r.hiy > this.hiy) ? this.hiy : r.hiy); |
| } |
| |
| /** |
| * Appends a single span defined by the 4 parameters |
| * spanlox, spanloy, spanhix, spanhiy. |
| * This span must be at a higher starting Y coordinate than |
| * the previous data or it must have a Y range equal to the |
| * highest Y band in the region and a higher X coordinate |
| * than any of the spans in that band. |
| */ |
| private void appendSpan(int box[]) { |
| int spanlox, spanloy, spanhix, spanhiy; |
| if ((spanlox = box[0]) < lox) spanlox = lox; |
| if ((spanloy = box[1]) < loy) spanloy = loy; |
| if ((spanhix = box[2]) > hix) spanhix = hix; |
| if ((spanhiy = box[3]) > hiy) spanhiy = hiy; |
| if (spanhix <= spanlox || spanhiy <= spanloy) { |
| return; |
| } |
| |
| int curYrow = box[4]; |
| if (endIndex == 0 || spanloy >= bands[curYrow + 1]) { |
| if (bands == null) { |
| bands = new int[INIT_SIZE]; |
| } else { |
| needSpace(5); |
| endRow(box); |
| curYrow = box[4]; |
| } |
| bands[endIndex++] = spanloy; |
| bands[endIndex++] = spanhiy; |
| bands[endIndex++] = 0; |
| } else if (spanloy == bands[curYrow] && |
| spanhiy == bands[curYrow + 1] && |
| spanlox >= bands[endIndex - 1]) { |
| if (spanlox == bands[endIndex - 1]) { |
| bands[endIndex - 1] = spanhix; |
| return; |
| } |
| needSpace(2); |
| } else { |
| throw new InternalError("bad span"); |
| } |
| bands[endIndex++] = spanlox; |
| bands[endIndex++] = spanhix; |
| bands[curYrow + 2]++; |
| } |
| |
| private void needSpace(int num) { |
| if (endIndex + num >= bands.length) { |
| int[] newbands = new int[bands.length + GROW_SIZE]; |
| System.arraycopy(bands, 0, newbands, 0, endIndex); |
| bands = newbands; |
| } |
| } |
| |
| private void endRow(int box[]) { |
| int cur = box[4]; |
| int prev = box[5]; |
| if (cur > prev) { |
| int[] bands = this.bands; |
| if (bands[prev + 1] == bands[cur] && |
| bands[prev + 2] == bands[cur + 2]) |
| { |
| int num = bands[cur + 2] * 2; |
| cur += 3; |
| prev += 3; |
| while (num > 0) { |
| if (bands[cur++] != bands[prev++]) { |
| break; |
| } |
| num--; |
| } |
| if (num == 0) { |
| // prev == box[4] |
| bands[box[5] + 1] = bands[prev + 1]; |
| endIndex = prev; |
| return; |
| } |
| } |
| } |
| box[5] = box[4]; |
| box[4] = endIndex; |
| } |
| |
| private void calcBBox() { |
| int[] bands = this.bands; |
| if (endIndex <= 5) { |
| if (endIndex == 0) { |
| lox = loy = hix = hiy = 0; |
| } else { |
| loy = bands[0]; |
| hiy = bands[1]; |
| lox = bands[3]; |
| hix = bands[4]; |
| endIndex = 0; |
| } |
| this.bands = null; |
| return; |
| } |
| int lox = this.hix; |
| int hix = this.lox; |
| int hiyindex = 0; |
| |
| int i = 0; |
| while (i < endIndex) { |
| hiyindex = i; |
| int numbands = bands[i + 2]; |
| i += 3; |
| if (lox > bands[i]) { |
| lox = bands[i]; |
| } |
| i += numbands * 2; |
| if (hix < bands[i - 1]) { |
| hix = bands[i - 1]; |
| } |
| } |
| |
| this.lox = lox; |
| this.loy = bands[0]; |
| this.hix = hix; |
| this.hiy = bands[hiyindex + 1]; |
| } |
| |
| /** |
| * Returns the lowest X coordinate in the Region. |
| */ |
| public final int getLoX() { |
| return lox; |
| } |
| |
| /** |
| * Returns the lowest Y coordinate in the Region. |
| */ |
| public final int getLoY() { |
| return loy; |
| } |
| |
| /** |
| * Returns the highest X coordinate in the Region. |
| */ |
| public final int getHiX() { |
| return hix; |
| } |
| |
| /** |
| * Returns the highest Y coordinate in the Region. |
| */ |
| public final int getHiY() { |
| return hiy; |
| } |
| |
| /** |
| * Returns the width of this Region clipped to the range (0 - MAX_INT). |
| */ |
| public final int getWidth() { |
| if (hix < lox) return 0; |
| int w; |
| if ((w = hix - lox) < 0) { |
| w = Integer.MAX_VALUE; |
| } |
| return w; |
| } |
| |
| /** |
| * Returns the height of this Region clipped to the range (0 - MAX_INT). |
| */ |
| public final int getHeight() { |
| if (hiy < loy) return 0; |
| int h; |
| if ((h = hiy - loy) < 0) { |
| h = Integer.MAX_VALUE; |
| } |
| return h; |
| } |
| |
| /** |
| * Returns true iff this Region encloses no area. |
| */ |
| public boolean isEmpty() { |
| return (hix <= lox || hiy <= loy); |
| } |
| |
| /** |
| * Returns true iff this Region represents a single simple |
| * rectangular area. |
| */ |
| public boolean isRectangular() { |
| return (bands == null); |
| } |
| |
| /** |
| * Returns true iff this Region contains the specified coordinate. |
| */ |
| public boolean contains(int x, int y) { |
| if (x < lox || x >= hix || y < loy || y >= hiy) return false; |
| if (bands == null) return true; |
| int i = 0; |
| while (i < endIndex) { |
| if (y < bands[i++]) { |
| return false; |
| } |
| if (y >= bands[i++]) { |
| int numspans = bands[i++]; |
| i += numspans * 2; |
| } else { |
| int end = bands[i++]; |
| end = i + end * 2; |
| while (i < end) { |
| if (x < bands[i++]) return false; |
| if (x < bands[i++]) return true; |
| } |
| return false; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Returns true iff this Region lies inside the indicated |
| * rectangular area specified in x, y, width, height format |
| * with appropriate clipping performed as per the dimAdd method. |
| */ |
| public boolean isInsideXYWH(int x, int y, int w, int h) { |
| return isInsideXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); |
| } |
| |
| /** |
| * Returns true iff this Region lies inside the indicated |
| * rectangular area specified in lox, loy, hix, hiy format. |
| */ |
| public boolean isInsideXYXY(int lox, int loy, int hix, int hiy) { |
| return (this.lox >= lox && this.loy >= loy && |
| this.hix <= hix && this.hiy <= hiy); |
| |
| } |
| |
| /** |
| * Quickly checks if this Region lies inside the specified |
| * Region object. |
| * <p> |
| * This method will return false if the specified Region |
| * object is not a simple rectangle. |
| */ |
| public boolean isInsideQuickCheck(Region r) { |
| return (r.bands == null && |
| r.lox <= this.lox && r.loy <= this.loy && |
| r.hix >= this.hix && r.hiy >= this.hiy); |
| } |
| |
| /** |
| * Quickly checks if this Region intersects the specified |
| * rectangular area specified in lox, loy, hix, hiy format. |
| * <p> |
| * This method tests only against the bounds of this region |
| * and does not bother to test if the rectangular region |
| * actually intersects any bands. |
| */ |
| public boolean intersectsQuickCheckXYXY(int lox, int loy, |
| int hix, int hiy) |
| { |
| return (hix > this.lox && lox < this.hix && |
| hiy > this.loy && loy < this.hiy); |
| } |
| |
| /** |
| * Quickly checks if this Region intersects the specified |
| * Region object. |
| * <p> |
| * This method tests only against the bounds of this region |
| * and does not bother to test if the rectangular region |
| * actually intersects any bands. |
| */ |
| public boolean intersectsQuickCheck(Region r) { |
| return (r.hix > this.lox && r.lox < this.hix && |
| r.hiy > this.loy && r.loy < this.hiy); |
| } |
| |
| /** |
| * Quickly checks if this Region surrounds the specified |
| * Region object. |
| * <p> |
| * This method will return false if this Region object is |
| * not a simple rectangle. |
| */ |
| public boolean encompasses(Region r) { |
| return (this.bands == null && |
| this.lox <= r.lox && this.loy <= r.loy && |
| this.hix >= r.hix && this.hiy >= r.hiy); |
| } |
| |
| /** |
| * Quickly checks if this Region surrounds the specified |
| * rectangular area specified in x, y, width, height format. |
| * <p> |
| * This method will return false if this Region object is |
| * not a simple rectangle. |
| */ |
| public boolean encompassesXYWH(int x, int y, int w, int h) { |
| return encompassesXYXY(x, y, dimAdd(x, w), dimAdd(y, h)); |
| } |
| |
| /** |
| * Quickly checks if this Region surrounds the specified |
| * rectangular area specified in lox, loy, hix, hiy format. |
| * <p> |
| * This method will return false if this Region object is |
| * not a simple rectangle. |
| */ |
| public boolean encompassesXYXY(int lox, int loy, int hix, int hiy) { |
| return (this.bands == null && |
| this.lox <= lox && this.loy <= loy && |
| this.hix >= hix && this.hiy >= hiy); |
| } |
| |
| /** |
| * Gets the bbox of the available spans, clipped to the OutputArea. |
| */ |
| public void getBounds(int pathbox[]) { |
| pathbox[0] = lox; |
| pathbox[1] = loy; |
| pathbox[2] = hix; |
| pathbox[3] = hiy; |
| } |
| |
| /** |
| * Clips the indicated bbox array to the bounds of this Region. |
| */ |
| public void clipBoxToBounds(int bbox[]) { |
| if (bbox[0] < lox) bbox[0] = lox; |
| if (bbox[1] < loy) bbox[1] = loy; |
| if (bbox[2] > hix) bbox[2] = hix; |
| if (bbox[3] > hiy) bbox[3] = hiy; |
| } |
| |
| /** |
| * Gets an iterator object to iterate over the spans in this region. |
| */ |
| public RegionIterator getIterator() { |
| return new RegionIterator(this); |
| } |
| |
| /** |
| * Gets a span iterator object that iterates over the spans in this region |
| */ |
| public SpanIterator getSpanIterator() { |
| return new RegionSpanIterator(this); |
| } |
| |
| /** |
| * Gets a span iterator object that iterates over the spans in this region |
| * but clipped to the bounds given in the argument (xlo, ylo, xhi, yhi). |
| */ |
| public SpanIterator getSpanIterator(int bbox[]) { |
| SpanIterator result = getSpanIterator(); |
| result.intersectClipBox(bbox[0], bbox[1], bbox[2], bbox[3]); |
| return result; |
| } |
| |
| /** |
| * Returns a SpanIterator that is the argument iterator filtered by |
| * this region. |
| */ |
| public SpanIterator filter(SpanIterator si) { |
| if (bands == null) { |
| si.intersectClipBox(lox, loy, hix, hiy); |
| } else { |
| si = new RegionClipSpanIterator(this, si); |
| } |
| return si; |
| } |
| |
| public String toString() { |
| StringBuffer sb = new StringBuffer(); |
| sb.append("Region[["); |
| sb.append(lox); |
| sb.append(", "); |
| sb.append(loy); |
| sb.append(" => "); |
| sb.append(hix); |
| sb.append(", "); |
| sb.append(hiy); |
| sb.append("]"); |
| if (bands != null) { |
| int col = 0; |
| while (col < endIndex) { |
| sb.append("y{"); |
| sb.append(bands[col++]); |
| sb.append(","); |
| sb.append(bands[col++]); |
| sb.append("}["); |
| int end = bands[col++]; |
| end = col + end * 2; |
| while (col < end) { |
| sb.append("x("); |
| sb.append(bands[col++]); |
| sb.append(", "); |
| sb.append(bands[col++]); |
| sb.append(")"); |
| } |
| sb.append("]"); |
| } |
| } |
| sb.append("]"); |
| return sb.toString(); |
| } |
| |
| public int hashCode() { |
| return (isEmpty() ? 0 : (lox * 3 + loy * 5 + hix * 7 + hiy * 9)); |
| } |
| |
| public boolean equals(Object o) { |
| if (!(o instanceof Region)) { |
| return false; |
| } |
| Region r = (Region) o; |
| if (this.isEmpty()) { |
| return r.isEmpty(); |
| } else if (r.isEmpty()) { |
| return false; |
| } |
| if (r.lox != this.lox || r.loy != this.loy || |
| r.hix != this.hix || r.hiy != this.hiy) |
| { |
| return false; |
| } |
| if (this.bands == null) { |
| return (r.bands == null); |
| } else if (r.bands == null) { |
| return false; |
| } |
| if (this.endIndex != r.endIndex) { |
| return false; |
| } |
| int abands[] = this.bands; |
| int bbands[] = r.bands; |
| for (int i = 0; i < endIndex; i++) { |
| if (abands[i] != bbands[i]) { |
| return false; |
| } |
| } |
| return true; |
| } |
| } |
