0001: /*
0002: * Copyright 1998-2006 Sun Microsystems, Inc. All Rights Reserved.
0003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004: *
0005: * This code is free software; you can redistribute it and/or modify it
0006: * under the terms of the GNU General Public License version 2 only, as
0007: * published by the Free Software Foundation. Sun designates this
0008: * particular file as subject to the "Classpath" exception as provided
0009: * by Sun in the LICENSE file that accompanied this code.
0010: *
0011: * This code is distributed in the hope that it will be useful, but WITHOUT
0012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014: * version 2 for more details (a copy is included in the LICENSE file that
0015: * accompanied this code).
0016: *
0017: * You should have received a copy of the GNU General Public License version
0018: * 2 along with this work; if not, write to the Free Software Foundation,
0019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020: *
0021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022: * CA 95054 USA or visit www.sun.com if you need additional information or
0023: * have any questions.
0024: */
0025:
0026: package sun.java2d.pipe;
0027:
0028: import java.awt.Rectangle;
0029:
0030: /**
0031: * This class encapsulates a definition of a two dimensional region which
0032: * consists of a number of Y ranges each containing multiple X bands.
0033: * <p>
0034: * A rectangular Region is allowed to have a null band list in which
0035: * case the rectangular shape is defined by the bounding box parameters
0036: * (lox, loy, hix, hiy).
0037: * <p>
0038: * The band list, if present, consists of a list of rows in ascending Y
0039: * order, ending at endIndex which is the index beyond the end of the
0040: * last row. Each row consists of at least 3 + 2n entries (n >= 1)
0041: * where the first 3 entries specify the Y range as start, end, and
0042: * the number of X ranges in that Y range. These 3 entries are
0043: * followed by pairs of X coordinates in ascending order:
0044: * <pre>
0045: * bands[rowstart+0] = Y0; // starting Y coordinate
0046: * bands[rowstart+1] = Y1; // ending Y coordinate - endY > startY
0047: * bands[rowstart+2] = N; // number of X bands - N >= 1
0048: *
0049: * bands[rowstart+3] = X10; // starting X coordinate of first band
0050: * bands[rowstart+4] = X11; // ending X coordinate of first band
0051: * bands[rowstart+5] = X20; // starting X coordinate of second band
0052: * bands[rowstart+6] = X21; // ending X coordinate of second band
0053: * ...
0054: * bands[rowstart+3+N*2-2] = XN0; // starting X coord of last band
0055: * bands[rowstart+3+N*2-1] = XN1; // ending X coord of last band
0056: *
0057: * bands[rowstart+3+N*2] = ... // start of next Y row
0058: * </pre>
0059: */
0060: public class Region {
0061: static final int INIT_SIZE = 50;
0062: static final int GROW_SIZE = 50;
0063:
0064: static final Region EMPTY_REGION = new Region(0, 0, 0, 0);
0065:
0066: int lox;
0067: int loy;
0068: int hix;
0069: int hiy;
0070:
0071: int endIndex;
0072: int[] bands;
0073:
0074: private static native void initIDs();
0075:
0076: static {
0077: initIDs();
0078: }
0079:
0080: /**
0081: * Adds the dimension <code>dim</code> to the coordinate
0082: * <code>start</code> with appropriate clipping. If
0083: * <code>dim</code> is non-positive then the method returns
0084: * the start coordinate. If the sum overflows an integer
0085: * data type then the method returns <code>Integer.MAX_VALUE</code>.
0086: */
0087: public static int dimAdd(int start, int dim) {
0088: if (dim <= 0)
0089: return start;
0090: if ((dim += start) < start)
0091: return Integer.MAX_VALUE;
0092: return dim;
0093: }
0094:
0095: /**
0096: * Adds the delta {@code dv} to the value {@code v} with
0097: * appropriate clipping to the bounds of Integer resolution.
0098: * If the answer would be greater than {@code Integer.MAX_VALUE}
0099: * then {@code Integer.MAX_VALUE} is returned.
0100: * If the answer would be less than {@code Integer.MIN_VALUE}
0101: * then {@code Integer.MIN_VALUE} is returned.
0102: * Otherwise the sum is returned.
0103: */
0104: public static int clipAdd(int v, int dv) {
0105: int newv = v + dv;
0106: if ((newv > v) != (dv > 0)) {
0107: newv = (dv < 0) ? Integer.MIN_VALUE : Integer.MAX_VALUE;
0108: }
0109: return newv;
0110: }
0111:
0112: private Region(int lox, int loy, int hix, int hiy) {
0113: this .lox = lox;
0114: this .loy = loy;
0115: this .hix = hix;
0116: this .hiy = hiy;
0117: }
0118:
0119: /**
0120: * Returns a Region object with a rectangle of interest specified
0121: * by the indicated Rectangle object.
0122: * <p>
0123: * This method can also be used to create a simple rectangular
0124: * region.
0125: */
0126: public static Region getInstance(Rectangle r) {
0127: return Region.getInstanceXYWH(r.x, r.y, r.width, r.height);
0128: }
0129:
0130: /**
0131: * Returns a Region object with a rectangle of interest specified
0132: * by the indicated rectangular area in x, y, width, height format.
0133: * <p>
0134: * This method can also be used to create a simple rectangular
0135: * region.
0136: */
0137: public static Region getInstanceXYWH(int x, int y, int w, int h) {
0138: return Region.getInstanceXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
0139: }
0140:
0141: /**
0142: * Returns a Region object with a rectangle of interest specified
0143: * by the indicated span array.
0144: * <p>
0145: * This method can also be used to create a simple rectangular
0146: * region.
0147: */
0148: public static Region getInstance(int box[]) {
0149: return new Region(box[0], box[1], box[2], box[3]);
0150: }
0151:
0152: /**
0153: * Returns a Region object with a rectangle of interest specified
0154: * by the indicated rectangular area in lox, loy, hix, hiy format.
0155: * <p>
0156: * This method can also be used to create a simple rectangular
0157: * region.
0158: */
0159: public static Region getInstanceXYXY(int lox, int loy, int hix,
0160: int hiy) {
0161: return new Region(lox, loy, hix, hiy);
0162: }
0163:
0164: /**
0165: * Sets the rectangle of interest for storing and returning
0166: * region bands.
0167: * <p>
0168: * This method can also be used to initialize a simple rectangular
0169: * region.
0170: */
0171: public void setOutputArea(Rectangle r) {
0172: setOutputAreaXYWH(r.x, r.y, r.width, r.height);
0173: }
0174:
0175: /**
0176: * Sets the rectangle of interest for storing and returning
0177: * region bands. The rectangle is specified in x, y, width, height
0178: * format and appropriate clipping is performed as per the method
0179: * <code>dimAdd</code>.
0180: * <p>
0181: * This method can also be used to initialize a simple rectangular
0182: * region.
0183: */
0184: public void setOutputAreaXYWH(int x, int y, int w, int h) {
0185: setOutputAreaXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
0186: }
0187:
0188: /**
0189: * Sets the rectangle of interest for storing and returning
0190: * region bands. The rectangle is specified as a span array.
0191: * <p>
0192: * This method can also be used to initialize a simple rectangular
0193: * region.
0194: */
0195: public void setOutputArea(int box[]) {
0196: this .lox = box[0];
0197: this .loy = box[1];
0198: this .hix = box[2];
0199: this .hiy = box[3];
0200: }
0201:
0202: /**
0203: * Sets the rectangle of interest for storing and returning
0204: * region bands. The rectangle is specified in lox, loy,
0205: * hix, hiy format.
0206: * <p>
0207: * This method can also be used to initialize a simple rectangular
0208: * region.
0209: */
0210: public void setOutputAreaXYXY(int lox, int loy, int hix, int hiy) {
0211: this .lox = lox;
0212: this .loy = loy;
0213: this .hix = hix;
0214: this .hiy = hiy;
0215: }
0216:
0217: /**
0218: * Appends the list of spans returned from the indicated
0219: * SpanIterator. Each span must be at a higher starting
0220: * Y coordinate than the previous data or it must have a
0221: * Y range equal to the highest Y band in the region and a
0222: * higher X coordinate than any of the spans in that band.
0223: */
0224: public void appendSpans(SpanIterator si) {
0225: int[] box = new int[6];
0226:
0227: while (si.nextSpan(box)) {
0228: appendSpan(box);
0229: }
0230:
0231: endRow(box);
0232: calcBBox();
0233: }
0234:
0235: /**
0236: * Returns a Region object that represents the same list of
0237: * rectangles as the current Region object, translated by
0238: * the specified dx, dy translation factors.
0239: */
0240: public Region getTranslatedRegion(int dx, int dy) {
0241: if ((dx | dy) == 0) {
0242: return this ;
0243: }
0244: int tlox = lox + dx;
0245: int tloy = loy + dy;
0246: int thix = hix + dx;
0247: int thiy = hiy + dy;
0248: if ((tlox > lox) != (dx > 0) || (tloy > loy) != (dy > 0)
0249: || (thix > hix) != (dx > 0) || (thiy > hiy) != (dy > 0)) {
0250: return getSafeTranslatedRegion(dx, dy);
0251: }
0252: Region ret = new Region(tlox, tloy, thix, thiy);
0253: int bands[] = this .bands;
0254: if (bands != null) {
0255: int end = endIndex;
0256: ret.endIndex = end;
0257: int newbands[] = new int[end];
0258: ret.bands = newbands;
0259: int i = 0;
0260: int ncol;
0261: while (i < end) {
0262: newbands[i] = bands[i] + dy;
0263: i++;
0264: newbands[i] = bands[i] + dy;
0265: i++;
0266: newbands[i] = ncol = bands[i];
0267: i++;
0268: while (--ncol >= 0) {
0269: newbands[i] = bands[i] + dx;
0270: i++;
0271: newbands[i] = bands[i] + dx;
0272: i++;
0273: }
0274: }
0275: }
0276: return ret;
0277: }
0278:
0279: private Region getSafeTranslatedRegion(int dx, int dy) {
0280: int tlox = clipAdd(lox, dx);
0281: int tloy = clipAdd(loy, dy);
0282: int thix = clipAdd(hix, dx);
0283: int thiy = clipAdd(hiy, dy);
0284: Region ret = new Region(tlox, tloy, thix, thiy);
0285: int bands[] = this .bands;
0286: if (bands != null) {
0287: int end = endIndex;
0288: int newbands[] = new int[end];
0289: int i = 0; // index for source bands
0290: int j = 0; // index for translated newbands
0291: int ncol;
0292: while (i < end) {
0293: int y1, y2;
0294: newbands[j++] = y1 = clipAdd(bands[i++], dy);
0295: newbands[j++] = y2 = clipAdd(bands[i++], dy);
0296: newbands[j++] = ncol = bands[i++];
0297: int savej = j;
0298: if (y1 < y2) {
0299: while (--ncol >= 0) {
0300: int x1 = clipAdd(bands[i++], dx);
0301: int x2 = clipAdd(bands[i++], dx);
0302: if (x1 < x2) {
0303: newbands[j++] = x1;
0304: newbands[j++] = x2;
0305: }
0306: }
0307: } else {
0308: i += ncol * 2;
0309: }
0310: // Did we get any non-empty bands in this row?
0311: if (j > savej) {
0312: newbands[savej - 1] = (j - savej) / 2;
0313: } else {
0314: j = savej - 3;
0315: }
0316: }
0317: if (j <= 5) {
0318: if (j < 5) {
0319: // No rows or bands were generated...
0320: ret.lox = ret.loy = ret.hix = ret.hiy = 0;
0321: } else {
0322: // Only generated one single rect in the end...
0323: ret.loy = newbands[0];
0324: ret.hiy = newbands[1];
0325: ret.lox = newbands[3];
0326: ret.hix = newbands[4];
0327: }
0328: // ret.endIndex and ret.bands were never initialized...
0329: // ret.endIndex = 0;
0330: // ret.newbands = null;
0331: } else {
0332: // Generated multiple bands and/or multiple rows...
0333: ret.endIndex = j;
0334: ret.bands = newbands;
0335: }
0336: }
0337: return ret;
0338: }
0339:
0340: /**
0341: * Returns a Region object that represents the intersection of
0342: * this object with the specified Rectangle. The return value
0343: * may be this same object if no clipping occurs.
0344: */
0345: public Region getIntersection(Rectangle r) {
0346: return getIntersectionXYWH(r.x, r.y, r.width, r.height);
0347: }
0348:
0349: /**
0350: * Returns a Region object that represents the intersection of
0351: * this object with the specified rectangular area. The return
0352: * value may be this same object if no clipping occurs.
0353: */
0354: public Region getIntersectionXYWH(int x, int y, int w, int h) {
0355: return getIntersectionXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
0356: }
0357:
0358: /**
0359: * Returns a Region object that represents the intersection of
0360: * this object with the specified rectangular area. The return
0361: * value may be this same object if no clipping occurs.
0362: */
0363: public Region getIntersectionXYXY(int lox, int loy, int hix, int hiy) {
0364: if (isInsideXYXY(lox, loy, hix, hiy)) {
0365: return this ;
0366: }
0367: Region ret = new Region((lox < this .lox) ? this .lox : lox,
0368: (loy < this .loy) ? this .loy : loy,
0369: (hix > this .hix) ? this .hix : hix,
0370: (hiy > this .hiy) ? this .hiy : hiy);
0371: if (bands != null) {
0372: ret.appendSpans(this .getSpanIterator());
0373: }
0374: return ret;
0375: }
0376:
0377: /**
0378: * Returns a Region object that represents the intersection of this
0379: * object with the specified Region object.
0380: * <p>
0381: * If {@code A} and {@code B} are both Region Objects and
0382: * <code>C = A.getIntersection(B);</code> then a point will
0383: * be contained in {@code C} iff it is contained in both
0384: * {@code A} and {@code B}.
0385: * <p>
0386: * The return value may be this same object or the argument
0387: * Region object if no clipping occurs.
0388: */
0389: public Region getIntersection(Region r) {
0390: if (this .isInsideQuickCheck(r)) {
0391: return this ;
0392: }
0393: if (r.isInsideQuickCheck(this )) {
0394: return r;
0395: }
0396: Region ret = new Region((r.lox < this .lox) ? this .lox : r.lox,
0397: (r.loy < this .loy) ? this .loy : r.loy,
0398: (r.hix > this .hix) ? this .hix : r.hix,
0399: (r.hiy > this .hiy) ? this .hiy : r.hiy);
0400: if (!ret.isEmpty()) {
0401: ret.filterSpans(this , r, INCLUDE_COMMON);
0402: }
0403: return ret;
0404: }
0405:
0406: /**
0407: * Returns a Region object that represents the union of this
0408: * object with the specified Region object.
0409: * <p>
0410: * If {@code A} and {@code B} are both Region Objects and
0411: * <code>C = A.getUnion(B);</code> then a point will
0412: * be contained in {@code C} iff it is contained in either
0413: * {@code A} or {@code B}.
0414: * <p>
0415: * The return value may be this same object or the argument
0416: * Region object if no augmentation occurs.
0417: */
0418: public Region getUnion(Region r) {
0419: if (r.isEmpty() || r.isInsideQuickCheck(this )) {
0420: return this ;
0421: }
0422: if (this .isEmpty() || this .isInsideQuickCheck(r)) {
0423: return r;
0424: }
0425: Region ret = new Region((r.lox > this .lox) ? this .lox : r.lox,
0426: (r.loy > this .loy) ? this .loy : r.loy,
0427: (r.hix < this .hix) ? this .hix : r.hix,
0428: (r.hiy < this .hiy) ? this .hiy : r.hiy);
0429: ret
0430: .filterSpans(this , r, INCLUDE_A | INCLUDE_B
0431: | INCLUDE_COMMON);
0432: return ret;
0433: }
0434:
0435: /**
0436: * Returns a Region object that represents the difference of the
0437: * specified Region object subtracted from this object.
0438: * <p>
0439: * If {@code A} and {@code B} are both Region Objects and
0440: * <code>C = A.getDifference(B);</code> then a point will
0441: * be contained in {@code C} iff it is contained in
0442: * {@code A} but not contained in {@code B}.
0443: * <p>
0444: * The return value may be this same object or the argument
0445: * Region object if no clipping occurs.
0446: */
0447: public Region getDifference(Region r) {
0448: if (!r.intersectsQuickCheck(this )) {
0449: return this ;
0450: }
0451: if (this .isInsideQuickCheck(r)) {
0452: return EMPTY_REGION;
0453: }
0454: Region ret = new Region(this .lox, this .loy, this .hix, this .hiy);
0455: ret.filterSpans(this , r, INCLUDE_A);
0456: return ret;
0457: }
0458:
0459: /**
0460: * Returns a Region object that represents the exclusive or of this
0461: * object with the specified Region object.
0462: * <p>
0463: * If {@code A} and {@code B} are both Region Objects and
0464: * <code>C = A.getExclusiveOr(B);</code> then a point will
0465: * be contained in {@code C} iff it is contained in either
0466: * {@code A} or {@code B}, but not if it is contained in both.
0467: * <p>
0468: * The return value may be this same object or the argument
0469: * Region object if either is empty.
0470: */
0471: public Region getExclusiveOr(Region r) {
0472: if (r.isEmpty()) {
0473: return this ;
0474: }
0475: if (this .isEmpty()) {
0476: return r;
0477: }
0478: Region ret = new Region((r.lox > this .lox) ? this .lox : r.lox,
0479: (r.loy > this .loy) ? this .loy : r.loy,
0480: (r.hix < this .hix) ? this .hix : r.hix,
0481: (r.hiy < this .hiy) ? this .hiy : r.hiy);
0482: ret.filterSpans(this , r, INCLUDE_A | INCLUDE_B);
0483: return ret;
0484: }
0485:
0486: static final int INCLUDE_A = 1;
0487: static final int INCLUDE_B = 2;
0488: static final int INCLUDE_COMMON = 4;
0489:
0490: private void filterSpans(Region ra, Region rb, int flags) {
0491: int abands[] = ra.bands;
0492: int bbands[] = rb.bands;
0493: if (abands == null) {
0494: abands = new int[] { ra.loy, ra.hiy, 1, ra.lox, ra.hix };
0495: }
0496: if (bbands == null) {
0497: bbands = new int[] { rb.loy, rb.hiy, 1, rb.lox, rb.hix };
0498: }
0499: int box[] = new int[6];
0500: int acolstart = 0;
0501: int ay1 = abands[acolstart++];
0502: int ay2 = abands[acolstart++];
0503: int acolend = abands[acolstart++];
0504: acolend = acolstart + 2 * acolend;
0505: int bcolstart = 0;
0506: int by1 = bbands[bcolstart++];
0507: int by2 = bbands[bcolstart++];
0508: int bcolend = bbands[bcolstart++];
0509: bcolend = bcolstart + 2 * bcolend;
0510: int y = loy;
0511: while (y < hiy) {
0512: if (y >= ay2) {
0513: if (acolend < ra.endIndex) {
0514: acolstart = acolend;
0515: ay1 = abands[acolstart++];
0516: ay2 = abands[acolstart++];
0517: acolend = abands[acolstart++];
0518: acolend = acolstart + 2 * acolend;
0519: } else {
0520: if ((flags & INCLUDE_B) == 0)
0521: break;
0522: ay1 = ay2 = hiy;
0523: }
0524: continue;
0525: }
0526: if (y >= by2) {
0527: if (bcolend < rb.endIndex) {
0528: bcolstart = bcolend;
0529: by1 = bbands[bcolstart++];
0530: by2 = bbands[bcolstart++];
0531: bcolend = bbands[bcolstart++];
0532: bcolend = bcolstart + 2 * bcolend;
0533: } else {
0534: if ((flags & INCLUDE_A) == 0)
0535: break;
0536: by1 = by2 = hiy;
0537: }
0538: continue;
0539: }
0540: int yend;
0541: if (y < by1) {
0542: if (y < ay1) {
0543: y = Math.min(ay1, by1);
0544: continue;
0545: }
0546: // We are in a set of rows that belong only to A
0547: yend = Math.min(ay2, by1);
0548: if ((flags & INCLUDE_A) != 0) {
0549: box[1] = y;
0550: box[3] = yend;
0551: int acol = acolstart;
0552: while (acol < acolend) {
0553: box[0] = abands[acol++];
0554: box[2] = abands[acol++];
0555: appendSpan(box);
0556: }
0557: }
0558: } else if (y < ay1) {
0559: // We are in a set of rows that belong only to B
0560: yend = Math.min(by2, ay1);
0561: if ((flags & INCLUDE_B) != 0) {
0562: box[1] = y;
0563: box[3] = yend;
0564: int bcol = bcolstart;
0565: while (bcol < bcolend) {
0566: box[0] = bbands[bcol++];
0567: box[2] = bbands[bcol++];
0568: appendSpan(box);
0569: }
0570: }
0571: } else {
0572: // We are in a set of rows that belong to both A and B
0573: yend = Math.min(ay2, by2);
0574: box[1] = y;
0575: box[3] = yend;
0576: int acol = acolstart;
0577: int bcol = bcolstart;
0578: int ax1 = abands[acol++];
0579: int ax2 = abands[acol++];
0580: int bx1 = bbands[bcol++];
0581: int bx2 = bbands[bcol++];
0582: int x = Math.min(ax1, bx1);
0583: if (x < lox)
0584: x = lox;
0585: while (x < hix) {
0586: if (x >= ax2) {
0587: if (acol < acolend) {
0588: ax1 = abands[acol++];
0589: ax2 = abands[acol++];
0590: } else {
0591: if ((flags & INCLUDE_B) == 0)
0592: break;
0593: ax1 = ax2 = hix;
0594: }
0595: continue;
0596: }
0597: if (x >= bx2) {
0598: if (bcol < bcolend) {
0599: bx1 = bbands[bcol++];
0600: bx2 = bbands[bcol++];
0601: } else {
0602: if ((flags & INCLUDE_A) == 0)
0603: break;
0604: bx1 = bx2 = hix;
0605: }
0606: continue;
0607: }
0608: int xend;
0609: boolean appendit;
0610: if (x < bx1) {
0611: if (x < ax1) {
0612: xend = Math.min(ax1, bx1);
0613: appendit = false;
0614: } else {
0615: xend = Math.min(ax2, bx1);
0616: appendit = ((flags & INCLUDE_A) != 0);
0617: }
0618: } else if (x < ax1) {
0619: xend = Math.min(ax1, bx2);
0620: appendit = ((flags & INCLUDE_B) != 0);
0621: } else {
0622: xend = Math.min(ax2, bx2);
0623: appendit = ((flags & INCLUDE_COMMON) != 0);
0624: }
0625: if (appendit) {
0626: box[0] = x;
0627: box[2] = xend;
0628: appendSpan(box);
0629: }
0630: x = xend;
0631: }
0632: }
0633: y = yend;
0634: }
0635: endRow(box);
0636: calcBBox();
0637: }
0638:
0639: /**
0640: * Returns a Region object that represents the bounds of the
0641: * intersection of this object with the bounds of the specified
0642: * Region object.
0643: * <p>
0644: * The return value may be this same object if no clipping occurs
0645: * and this Region is rectangular.
0646: */
0647: public Region getBoundsIntersection(Rectangle r) {
0648: return getBoundsIntersectionXYWH(r.x, r.y, r.width, r.height);
0649: }
0650:
0651: /**
0652: * Returns a Region object that represents the bounds of the
0653: * intersection of this object with the bounds of the specified
0654: * rectangular area in x, y, width, height format.
0655: * <p>
0656: * The return value may be this same object if no clipping occurs
0657: * and this Region is rectangular.
0658: */
0659: public Region getBoundsIntersectionXYWH(int x, int y, int w, int h) {
0660: return getBoundsIntersectionXYXY(x, y, dimAdd(x, w), dimAdd(y,
0661: h));
0662: }
0663:
0664: /**
0665: * Returns a Region object that represents the bounds of the
0666: * intersection of this object with the bounds of the specified
0667: * rectangular area in lox, loy, hix, hiy format.
0668: * <p>
0669: * The return value may be this same object if no clipping occurs
0670: * and this Region is rectangular.
0671: */
0672: public Region getBoundsIntersectionXYXY(int lox, int loy, int hix,
0673: int hiy) {
0674: if (this .bands == null && this .lox >= lox && this .loy >= loy
0675: && this .hix <= hix && this .hiy <= hiy) {
0676: return this ;
0677: }
0678: return new Region((lox < this .lox) ? this .lox : lox,
0679: (loy < this .loy) ? this .loy : loy,
0680: (hix > this .hix) ? this .hix : hix,
0681: (hiy > this .hiy) ? this .hiy : hiy);
0682: }
0683:
0684: /**
0685: * Returns a Region object that represents the intersection of
0686: * this object with the bounds of the specified Region object.
0687: * <p>
0688: * The return value may be this same object or the argument
0689: * Region object if no clipping occurs and the Regions are
0690: * rectangular.
0691: */
0692: public Region getBoundsIntersection(Region r) {
0693: if (this .encompasses(r)) {
0694: return r;
0695: }
0696: if (r.encompasses(this )) {
0697: return this ;
0698: }
0699: return new Region((r.lox < this .lox) ? this .lox : r.lox,
0700: (r.loy < this .loy) ? this .loy : r.loy,
0701: (r.hix > this .hix) ? this .hix : r.hix,
0702: (r.hiy > this .hiy) ? this .hiy : r.hiy);
0703: }
0704:
0705: /**
0706: * Appends a single span defined by the 4 parameters
0707: * spanlox, spanloy, spanhix, spanhiy.
0708: * This span must be at a higher starting Y coordinate than
0709: * the previous data or it must have a Y range equal to the
0710: * highest Y band in the region and a higher X coordinate
0711: * than any of the spans in that band.
0712: */
0713: private void appendSpan(int box[]) {
0714: int spanlox, spanloy, spanhix, spanhiy;
0715: if ((spanlox = box[0]) < lox)
0716: spanlox = lox;
0717: if ((spanloy = box[1]) < loy)
0718: spanloy = loy;
0719: if ((spanhix = box[2]) > hix)
0720: spanhix = hix;
0721: if ((spanhiy = box[3]) > hiy)
0722: spanhiy = hiy;
0723: if (spanhix <= spanlox || spanhiy <= spanloy) {
0724: return;
0725: }
0726:
0727: int curYrow = box[4];
0728: if (endIndex == 0 || spanloy >= bands[curYrow + 1]) {
0729: if (bands == null) {
0730: bands = new int[INIT_SIZE];
0731: } else {
0732: needSpace(5);
0733: endRow(box);
0734: curYrow = box[4];
0735: }
0736: bands[endIndex++] = spanloy;
0737: bands[endIndex++] = spanhiy;
0738: bands[endIndex++] = 0;
0739: } else if (spanloy == bands[curYrow]
0740: && spanhiy == bands[curYrow + 1]
0741: && spanlox >= bands[endIndex - 1]) {
0742: if (spanlox == bands[endIndex - 1]) {
0743: bands[endIndex - 1] = spanhix;
0744: return;
0745: }
0746: needSpace(2);
0747: } else {
0748: throw new InternalError("bad span");
0749: }
0750: bands[endIndex++] = spanlox;
0751: bands[endIndex++] = spanhix;
0752: bands[curYrow + 2]++;
0753: }
0754:
0755: private void needSpace(int num) {
0756: if (endIndex + num >= bands.length) {
0757: int[] newbands = new int[bands.length + GROW_SIZE];
0758: System.arraycopy(bands, 0, newbands, 0, endIndex);
0759: bands = newbands;
0760: }
0761: }
0762:
0763: private void endRow(int box[]) {
0764: int cur = box[4];
0765: int prev = box[5];
0766: if (cur > prev) {
0767: int[] bands = this .bands;
0768: if (bands[prev + 1] == bands[cur]
0769: && bands[prev + 2] == bands[cur + 2]) {
0770: int num = bands[cur + 2] * 2;
0771: cur += 3;
0772: prev += 3;
0773: while (num > 0) {
0774: if (bands[cur++] != bands[prev++]) {
0775: break;
0776: }
0777: num--;
0778: }
0779: if (num == 0) {
0780: // prev == box[4]
0781: bands[box[5] + 1] = bands[prev + 1];
0782: endIndex = prev;
0783: return;
0784: }
0785: }
0786: }
0787: box[5] = box[4];
0788: box[4] = endIndex;
0789: }
0790:
0791: private void calcBBox() {
0792: int[] bands = this .bands;
0793: if (endIndex <= 5) {
0794: if (endIndex == 0) {
0795: lox = loy = hix = hiy = 0;
0796: } else {
0797: loy = bands[0];
0798: hiy = bands[1];
0799: lox = bands[3];
0800: hix = bands[4];
0801: endIndex = 0;
0802: }
0803: this .bands = null;
0804: return;
0805: }
0806: int lox = this .hix;
0807: int hix = this .lox;
0808: int hiyindex = 0;
0809:
0810: int i = 0;
0811: while (i < endIndex) {
0812: hiyindex = i;
0813: int numbands = bands[i + 2];
0814: i += 3;
0815: if (lox > bands[i]) {
0816: lox = bands[i];
0817: }
0818: i += numbands * 2;
0819: if (hix < bands[i - 1]) {
0820: hix = bands[i - 1];
0821: }
0822: }
0823:
0824: this .lox = lox;
0825: this .loy = bands[0];
0826: this .hix = hix;
0827: this .hiy = bands[hiyindex + 1];
0828: }
0829:
0830: /**
0831: * Returns the lowest X coordinate in the Region.
0832: */
0833: public final int getLoX() {
0834: return lox;
0835: }
0836:
0837: /**
0838: * Returns the lowest Y coordinate in the Region.
0839: */
0840: public final int getLoY() {
0841: return loy;
0842: }
0843:
0844: /**
0845: * Returns the highest X coordinate in the Region.
0846: */
0847: public final int getHiX() {
0848: return hix;
0849: }
0850:
0851: /**
0852: * Returns the highest Y coordinate in the Region.
0853: */
0854: public final int getHiY() {
0855: return hiy;
0856: }
0857:
0858: /**
0859: * Returns the width of this Region clipped to the range (0 - MAX_INT).
0860: */
0861: public final int getWidth() {
0862: if (hix < lox)
0863: return 0;
0864: int w;
0865: if ((w = hix - lox) < 0) {
0866: w = Integer.MAX_VALUE;
0867: }
0868: return w;
0869: }
0870:
0871: /**
0872: * Returns the height of this Region clipped to the range (0 - MAX_INT).
0873: */
0874: public final int getHeight() {
0875: if (hiy < loy)
0876: return 0;
0877: int h;
0878: if ((h = hiy - loy) < 0) {
0879: h = Integer.MAX_VALUE;
0880: }
0881: return h;
0882: }
0883:
0884: /**
0885: * Returns true iff this Region encloses no area.
0886: */
0887: public boolean isEmpty() {
0888: return (hix <= lox || hiy <= loy);
0889: }
0890:
0891: /**
0892: * Returns true iff this Region represents a single simple
0893: * rectangular area.
0894: */
0895: public boolean isRectangular() {
0896: return (bands == null);
0897: }
0898:
0899: /**
0900: * Returns true iff this Region contains the specified coordinate.
0901: */
0902: public boolean contains(int x, int y) {
0903: if (x < lox || x >= hix || y < loy || y >= hiy)
0904: return false;
0905: if (bands == null)
0906: return true;
0907: int i = 0;
0908: while (i < endIndex) {
0909: if (y < bands[i++]) {
0910: return false;
0911: }
0912: if (y >= bands[i++]) {
0913: int numspans = bands[i++];
0914: i += numspans * 2;
0915: } else {
0916: int end = bands[i++];
0917: end = i + end * 2;
0918: while (i < end) {
0919: if (x < bands[i++])
0920: return false;
0921: if (x < bands[i++])
0922: return true;
0923: }
0924: return false;
0925: }
0926: }
0927: return false;
0928: }
0929:
0930: /**
0931: * Returns true iff this Region lies inside the indicated
0932: * rectangular area specified in x, y, width, height format
0933: * with appropriate clipping performed as per the dimAdd method.
0934: */
0935: public boolean isInsideXYWH(int x, int y, int w, int h) {
0936: return isInsideXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
0937: }
0938:
0939: /**
0940: * Returns true iff this Region lies inside the indicated
0941: * rectangular area specified in lox, loy, hix, hiy format.
0942: */
0943: public boolean isInsideXYXY(int lox, int loy, int hix, int hiy) {
0944: return (this .lox >= lox && this .loy >= loy && this .hix <= hix && this .hiy <= hiy);
0945:
0946: }
0947:
0948: /**
0949: * Quickly checks if this Region lies inside the specified
0950: * Region object.
0951: * <p>
0952: * This method will return false if the specified Region
0953: * object is not a simple rectangle.
0954: */
0955: public boolean isInsideQuickCheck(Region r) {
0956: return (r.bands == null && r.lox <= this .lox
0957: && r.loy <= this .loy && r.hix >= this .hix && r.hiy >= this .hiy);
0958: }
0959:
0960: /**
0961: * Quickly checks if this Region intersects the specified
0962: * rectangular area specified in lox, loy, hix, hiy format.
0963: * <p>
0964: * This method tests only against the bounds of this region
0965: * and does not bother to test if the rectangular region
0966: * actually intersects any bands.
0967: */
0968: public boolean intersectsQuickCheckXYXY(int lox, int loy, int hix,
0969: int hiy) {
0970: return (hix > this .lox && lox < this .hix && hiy > this .loy && loy < this .hiy);
0971: }
0972:
0973: /**
0974: * Quickly checks if this Region intersects the specified
0975: * Region object.
0976: * <p>
0977: * This method tests only against the bounds of this region
0978: * and does not bother to test if the rectangular region
0979: * actually intersects any bands.
0980: */
0981: public boolean intersectsQuickCheck(Region r) {
0982: return (r.hix > this .lox && r.lox < this .hix
0983: && r.hiy > this .loy && r.loy < this .hiy);
0984: }
0985:
0986: /**
0987: * Quickly checks if this Region surrounds the specified
0988: * Region object.
0989: * <p>
0990: * This method will return false if this Region object is
0991: * not a simple rectangle.
0992: */
0993: public boolean encompasses(Region r) {
0994: return (this .bands == null && this .lox <= r.lox
0995: && this .loy <= r.loy && this .hix >= r.hix && this .hiy >= r.hiy);
0996: }
0997:
0998: /**
0999: * Quickly checks if this Region surrounds the specified
1000: * rectangular area specified in x, y, width, height format.
1001: * <p>
1002: * This method will return false if this Region object is
1003: * not a simple rectangle.
1004: */
1005: public boolean encompassesXYWH(int x, int y, int w, int h) {
1006: return encompassesXYXY(x, y, dimAdd(x, w), dimAdd(y, h));
1007: }
1008:
1009: /**
1010: * Quickly checks if this Region surrounds the specified
1011: * rectangular area specified in lox, loy, hix, hiy format.
1012: * <p>
1013: * This method will return false if this Region object is
1014: * not a simple rectangle.
1015: */
1016: public boolean encompassesXYXY(int lox, int loy, int hix, int hiy) {
1017: return (this .bands == null && this .lox <= lox
1018: && this .loy <= loy && this .hix >= hix && this .hiy >= hiy);
1019: }
1020:
1021: /**
1022: * Gets the bbox of the available spans, clipped to the OutputArea.
1023: */
1024: public void getBounds(int pathbox[]) {
1025: pathbox[0] = lox;
1026: pathbox[1] = loy;
1027: pathbox[2] = hix;
1028: pathbox[3] = hiy;
1029: }
1030:
1031: /**
1032: * Clips the indicated bbox array to the bounds of this Region.
1033: */
1034: public void clipBoxToBounds(int bbox[]) {
1035: if (bbox[0] < lox)
1036: bbox[0] = lox;
1037: if (bbox[1] < loy)
1038: bbox[1] = loy;
1039: if (bbox[2] > hix)
1040: bbox[2] = hix;
1041: if (bbox[3] > hiy)
1042: bbox[3] = hiy;
1043: }
1044:
1045: /**
1046: * Gets an iterator object to iterate over the spans in this region.
1047: */
1048: public RegionIterator getIterator() {
1049: return new RegionIterator(this );
1050: }
1051:
1052: /**
1053: * Gets a span iterator object that iterates over the spans in this region
1054: */
1055: public SpanIterator getSpanIterator() {
1056: return new RegionSpanIterator(this );
1057: }
1058:
1059: /**
1060: * Gets a span iterator object that iterates over the spans in this region
1061: * but clipped to the bounds given in the argument (xlo, ylo, xhi, yhi).
1062: */
1063: public SpanIterator getSpanIterator(int bbox[]) {
1064: SpanIterator result = getSpanIterator();
1065: result.intersectClipBox(bbox[0], bbox[1], bbox[2], bbox[3]);
1066: return result;
1067: }
1068:
1069: /**
1070: * Returns a SpanIterator that is the argument iterator filtered by
1071: * this region.
1072: */
1073: public SpanIterator filter(SpanIterator si) {
1074: if (bands == null) {
1075: si.intersectClipBox(lox, loy, hix, hiy);
1076: } else {
1077: si = new RegionClipSpanIterator(this , si);
1078: }
1079: return si;
1080: }
1081:
1082: public String toString() {
1083: StringBuffer sb = new StringBuffer();
1084: sb.append("Region[[");
1085: sb.append(lox);
1086: sb.append(", ");
1087: sb.append(loy);
1088: sb.append(" => ");
1089: sb.append(hix);
1090: sb.append(", ");
1091: sb.append(hiy);
1092: sb.append("]");
1093: if (bands != null) {
1094: int col = 0;
1095: while (col < endIndex) {
1096: sb.append("y{");
1097: sb.append(bands[col++]);
1098: sb.append(",");
1099: sb.append(bands[col++]);
1100: sb.append("}[");
1101: int end = bands[col++];
1102: end = col + end * 2;
1103: while (col < end) {
1104: sb.append("x(");
1105: sb.append(bands[col++]);
1106: sb.append(", ");
1107: sb.append(bands[col++]);
1108: sb.append(")");
1109: }
1110: sb.append("]");
1111: }
1112: }
1113: sb.append("]");
1114: return sb.toString();
1115: }
1116:
1117: public int hashCode() {
1118: return (isEmpty() ? 0 : (lox * 3 + loy * 5 + hix * 7 + hiy * 9));
1119: }
1120:
1121: public boolean equals(Object o) {
1122: if (!(o instanceof Region)) {
1123: return false;
1124: }
1125: Region r = (Region) o;
1126: if (this .isEmpty()) {
1127: return r.isEmpty();
1128: } else if (r.isEmpty()) {
1129: return false;
1130: }
1131: if (r.lox != this .lox || r.loy != this .loy || r.hiy != this .hiy
1132: || r.hiy != this .hiy) {
1133: return false;
1134: }
1135: if (this .bands == null) {
1136: return (r.bands == null);
1137: } else if (r.bands == null) {
1138: return false;
1139: }
1140: if (this .endIndex != r.endIndex) {
1141: return false;
1142: }
1143: int abands[] = this .bands;
1144: int bbands[] = r.bands;
1145: for (int i = 0; i < endIndex; i++) {
1146: if (abands[i] != bbands[i]) {
1147: return false;
1148: }
1149: }
1150: return true;
1151: }
1152: }
|