0001: /*
0002: * $RCSfile: ROIShape.java,v $
0003: *
0004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
0005: *
0006: * Use is subject to license terms.
0007: *
0008: * $Revision: 1.2 $
0009: * $Date: 2005/11/24 00:04:04 $
0010: * $State: Exp $
0011: */
0012: package javax.media.jai;
0013:
0014: import java.awt.Graphics2D;
0015: import java.awt.Point;
0016: import java.awt.Polygon;
0017: import java.awt.Rectangle;
0018: import java.awt.RenderingHints;
0019: import java.awt.Shape;
0020: import java.awt.Transparency;
0021: import java.awt.color.ColorSpace;
0022: import java.awt.geom.AffineTransform;
0023: import java.awt.geom.Area;
0024: import java.awt.geom.GeneralPath;
0025: import java.awt.geom.Line2D;
0026: import java.awt.geom.PathIterator;
0027: import java.awt.geom.Point2D;
0028: import java.awt.geom.Rectangle2D;
0029: import java.awt.image.BufferedImage;
0030: import java.awt.image.ColorModel;
0031: import java.awt.image.ComponentColorModel;
0032: import java.awt.image.DataBuffer;
0033: import java.awt.image.MultiPixelPackedSampleModel;
0034: import java.awt.image.RenderedImage;
0035: import java.awt.image.SampleModel;
0036: import java.awt.image.WritableRaster;
0037: import java.io.IOException;
0038: import java.io.ObjectInputStream;
0039: import java.io.ObjectOutputStream;
0040: import java.util.Arrays;
0041: import java.util.Comparator;
0042: import java.util.LinkedList;
0043: import java.util.ListIterator;
0044: import java.util.Vector;
0045:
0046: /**
0047: * A class representing a region of interest within an image as a
0048: * <code>Shape</code>. Such regions are binary by definition. Using
0049: * a <code>Shape</code> representation allows boolean operations to be
0050: * performed quickly and with compact storage. If a
0051: * <code>PropertyGenerator</code> responsible for generating the
0052: * <code>ROI</code> property of a particular
0053: * <code>OperationDescriptor</code> (e.g., a warp) cannot reasonably
0054: * produce an <code>ROIShape</code> representing the region, it should
0055: * call <code>getAsImage()</code> on its sources and produce its
0056: * output <code>ROI</code> in image form.
0057: *
0058: */
0059: public class ROIShape extends ROI {
0060: /** The internal Shape that defines this mask. */
0061: transient Shape theShape = null;
0062:
0063: /**
0064: * Calculate the point of intersection of two line segments.
0065: * This method assumes that the line segments do in fact intersect.
0066: *
0067: * @param x1 The abscissa of the first end point of the first segment.
0068: * @param y1 The ordinate of the first end point of the first segment.
0069: * @param x2 The abscissa of the second end point of the first segment.
0070: * @param y2 The ordinate of the second end point of the first segment.
0071: * @param u1 The abscissa of the first end point of the second segment.
0072: * @param v1 The ordinate of the first end point of the second segment.
0073: * @param u2 The abscissa of the second end point of the second segment.
0074: * @param v2 The ordinate of the second end point of the second segment.
0075: *
0076: * @return The point of intersection.
0077: */
0078: private static Point2D.Double getIntersection(double x1, double y1,
0079: double x2, double y2, double u1, double v1, double u2,
0080: double v2) {
0081: double[][] a = new double[2][2];
0082: a[0][0] = y2 - y1;
0083: a[0][1] = x1 - x2;
0084: a[1][0] = v2 - v1;
0085: a[1][1] = u1 - u2;
0086:
0087: double[] c = new double[2];
0088: c[0] = y1 * (x1 - x2) + x1 * (y2 - y1);
0089: c[1] = v1 * (u1 - u2) + u1 * (v2 - v1);
0090:
0091: double det = a[0][0] * a[1][1] - a[0][1] * a[1][0];
0092: double tmp = a[0][0];
0093: a[0][0] = a[1][1] / det;
0094: a[0][1] = -a[0][1] / det;
0095: a[1][0] = -a[1][0] / det;
0096: a[1][1] = tmp / det;
0097:
0098: double x = a[0][0] * c[0] + a[0][1] * c[1];
0099: double y = a[1][0] * c[0] + a[1][1] * c[1];
0100:
0101: return new Point2D.Double(x, y);
0102: }
0103:
0104: /**
0105: * Convert a <code>Polygon</code> into a <code>LinkedList</code> of
0106: * <code>Rectangle</code>s representing run lengths of pixels contained
0107: * within the <code>Polygon</code>.
0108: *
0109: * @param clip The clipping <code>Rectangle</code>.
0110: * @param poly The <code>Polygon</code> to examine.
0111: * @return The <code>LinkedList</code> of run length
0112: * <code>Rectangle</code>s.
0113: */
0114: private LinkedList polygonToRunLengthList(Rectangle clip,
0115: Polygon poly) {
0116: PolyShape ps = new PolyShape(poly, clip);
0117: return ps.getAsRectList();
0118: }
0119:
0120: /**
0121: * Converts a <code>LinkedList</code> of <code>Rectangle</code>s into an
0122: * array of integers representing a bit mask.
0123: *
0124: * @param rectangleList The list of <code>Rectangle</code>s.
0125: * @param clip The clipping <code>Rectangle</code>.
0126: * @param mask A two-dimensional array of ints at least
0127: * (width + 31)/32 entries wide and (height) entries tall,
0128: * or null.
0129: *
0130: * @return An integer array representing a bit mask.
0131: */
0132: private static int[][] rectangleListToBitmask(
0133: LinkedList rectangleList, Rectangle clip, int[][] mask) {
0134: int bitField = 0x80000000;
0135:
0136: // Determine the minimum required width of the bitmask in integers.
0137: int bitmaskIntWidth = (clip.width + 31) / 32;
0138:
0139: // Construct bitmask array if argument is null.
0140: if (mask == null) {
0141: mask = new int[clip.height][bitmaskIntWidth];
0142: } else if (mask.length < clip.height
0143: || mask[0].length < bitmaskIntWidth) {
0144: throw new RuntimeException(JaiI18N.getString("ROIShape0"));
0145: }
0146:
0147: // Iterate over the list of Rectangles.
0148: ListIterator rectangleIter = rectangleList.listIterator(0);
0149: while (rectangleIter.hasNext()) {
0150: // Only set bits corresponding to pixels in the clip Rectangle.
0151: Rectangle rect;
0152: if (clip
0153: .intersects(rect = (Rectangle) rectangleIter.next())) {
0154: rect = clip.intersection(rect);
0155:
0156: // Set the extremal indexes for the current Rectangle.
0157: int yMin = rect.y - clip.y;
0158: int xMin = rect.x - clip.x;
0159: int yMax = yMin + rect.height - 1;
0160: int xMax = xMin + rect.width - 1;
0161:
0162: // Set all bits within the current Rectangle.
0163: for (int y = yMin; y <= yMax; y++) {
0164: int[] bitrow = mask[y];
0165: for (int x = xMin; x <= xMax; x++) {
0166: int index = x / 32;
0167: int shift = x % 32;
0168: bitrow[index] |= (bitField >>> shift);
0169: }
0170: }
0171: }
0172: }
0173:
0174: return mask;
0175: }
0176:
0177: /**
0178: * Constructs an ROIShape from a Shape.
0179: *
0180: * @param s A Shape.
0181: *
0182: * @throws IllegalArgumentException if s is null.
0183: */
0184: public ROIShape(Shape s) {
0185: if (s == null) {
0186: throw new IllegalArgumentException(JaiI18N
0187: .getString("ROIShape2"));
0188: }
0189: theShape = s;
0190: }
0191:
0192: /**
0193: * Constructs an ROIShape from an Area.
0194: *
0195: * @param a An Area.
0196: */
0197: public ROIShape(Area a) {
0198: AffineTransform at = new AffineTransform(); // Identity
0199: PathIterator pi = a.getPathIterator(at);
0200: GeneralPath gp = new GeneralPath(pi.getWindingRule());
0201: gp.append(pi, false);
0202:
0203: theShape = gp;
0204: }
0205:
0206: /**
0207: * Instance inner class used for scan conversion of a polygonal
0208: * <code>Shape</code>.
0209: */
0210: private class PolyShape {
0211: /** A polygon which has yet to be classified as one
0212: * of the following types. */
0213: private static final int POLYGON_UNCLASSIFIED = 0;
0214:
0215: /** A degenerate polygon, i.e., all vertices equal or
0216: on the same line. */
0217: private static final int POLYGON_DEGENERATE = POLYGON_UNCLASSIFIED + 1;
0218:
0219: /** A convex polygon. */
0220: private static final int POLYGON_CONVEX = POLYGON_DEGENERATE + 1;
0221:
0222: /** A concave polygon (simple or non-simple). */
0223: private static final int POLYGON_CONCAVE = POLYGON_CONVEX + 1;
0224:
0225: /** The internal polygon. */
0226: private Polygon poly;
0227:
0228: /** The clipping <code>Rectangle</code>. */
0229: private Rectangle clip;
0230:
0231: /** The type of polygon. */
0232: private int type = POLYGON_UNCLASSIFIED;
0233:
0234: /** Flag indicating whether the supplied clipping <code>Rectangle</code>
0235: * is inside the <code>Polygon</code>.
0236: */
0237: private boolean insidePolygon = false;
0238:
0239: /**
0240: * Constructs a new PolyShape. The <code>Polygon</code> argument is
0241: * clipped against the supplied <code>Rectangle</code>.
0242: *
0243: * @param polygon The <code>Polygon</code>.
0244: * @param clipRect The clipping <code>Rectangle</code>.
0245: */
0246: PolyShape(Polygon polygon, Rectangle clipRect) {
0247: // Cache the arguments.
0248: poly = polygon;
0249: clip = clipRect;
0250:
0251: // Determine whether the clipping Rectangle is inside the Polygon.
0252: insidePolygon = poly.contains(clipRect);
0253: type = POLYGON_UNCLASSIFIED;
0254: }
0255:
0256: /**
0257: * Inner class representing a polygon edge.
0258: */
0259: private class PolyEdge implements Comparator {
0260: /** X coordinate of intersection of edge with current scanline. */
0261: public double x;
0262:
0263: /** Change in X with respect to Y. */
0264: public double dx;
0265:
0266: /** The edge number: edge i goes from vertex i to vertex i+1. */
0267: public int i;
0268:
0269: /**
0270: * Construct a <code>PolyEdge</code> object.
0271: *
0272: * @param x X coordinate of edge intersection with scanline.
0273: * @param dx The change in X with respect to Y.
0274: * @param i The edge number.
0275: */
0276: PolyEdge(double x, double dx, int i) {
0277: this .x = x;
0278: this .dx = dx;
0279: this .i = i;
0280: }
0281:
0282: /**
0283: * Implementation of java.util.Comparator.compare. The argument
0284: * <code>Object</code>s are assumed to be <code>PolyEdge</code>s
0285: * and are sorted on the basis of their respective x components.
0286: *
0287: * @param o1 The first <code>PolyEdge</code> object.
0288: * @param o2 The second <code>PolyEdge</code> object.
0289: *
0290: * @return -1 if o1 < o2, 1 if o1 > o2, 0 if o1 == o2.
0291: */
0292: public int compare(Object o1, Object o2) {
0293: double x1 = ((PolyEdge) o1).x;
0294: double x2 = ((PolyEdge) o2).x;
0295:
0296: int returnValue;
0297: if (x1 < x2) {
0298: returnValue = -1;
0299: } else if (x1 > x2) {
0300: returnValue = 1;
0301: } else {
0302: returnValue = 0;
0303: }
0304:
0305: return returnValue;
0306: }
0307: }
0308:
0309: /**
0310: * Perform scan conversion of the <code>PolyShape</code> to generate
0311: * a <code>LinkedList</code> of <code>Rectangle</code>s.
0312: *
0313: * @return A <code>LinkedList</code> of <code>Rectangle</code>s
0314: * representing the scan conversion of the <code>PolyShape</code>.
0315: */
0316: public LinkedList getAsRectList() {
0317: LinkedList rectList = new LinkedList();
0318:
0319: if (insidePolygon) {
0320: rectList.addLast((Object) poly.getBounds());
0321: } else {
0322: // Classify the polygon as one of the pre-defined types.
0323: classifyPolygon();
0324:
0325: // Perform scan conversion according to polygon type.
0326: switch (type) {
0327: case POLYGON_DEGENERATE:
0328: rectList = null;
0329: break;
0330: case POLYGON_CONVEX:
0331: rectList = scanConvex(rectList);
0332: break;
0333: case POLYGON_CONCAVE:
0334: rectList = scanConcave(rectList);
0335: break;
0336: default:
0337: throw new RuntimeException(JaiI18N
0338: .getString("ROIShape1"));
0339: }
0340: }
0341:
0342: return rectList;
0343: }
0344:
0345: /**
0346: * Classify a <code>Polygon</code> as one of the pre-defined types
0347: * for this class.
0348: */
0349: private int classifyPolygon() {
0350: if (type != POLYGON_UNCLASSIFIED) {
0351: return type;
0352: }
0353:
0354: int n = poly.npoints;
0355: if (n < 3) {
0356: type = POLYGON_DEGENERATE;
0357: return type;
0358:
0359: } else if (poly.getBounds().contains(clip)) {
0360: type = POLYGON_CONVEX;
0361: return type;
0362: }
0363:
0364: // Cache references to Polygon vertices.
0365: int[] x = poly.xpoints;
0366: int[] y = poly.ypoints;
0367:
0368: // Calculate the sign of the angle between the first and
0369: // second directed segments.
0370: int previousSign = sgn((x[0] - x[1]) * (y[1] - y[2])
0371: - (x[1] - x[2]) * (y[0] - y[1]));
0372: boolean allZero = (previousSign == 0);
0373:
0374: // Calculate the initial lexicographic direction.
0375: int previousDirection;
0376: if (x[0] < x[1]) {
0377: previousDirection = -1;
0378: } else if (x[0] > x[1]) {
0379: previousDirection = 1;
0380: } else if (y[0] < y[1]) {
0381: previousDirection = -1;
0382: } else if (y[0] > y[1]) {
0383: previousDirection = 1;
0384: } else {
0385: previousDirection = 0;
0386: }
0387:
0388: // Calculate signs of all angles between segments. If all angles
0389: // are zero then the vertices all lie on a line. If all non-zero
0390: // angles have the same sign then the polygon is convex. Otherwise
0391: // the polygon is concave unless the lexicographic direction
0392: // changes sign more than twice.
0393: int numDirectionChanges = 0;
0394: for (int i = 1; i < n; i++) {
0395: // Set the indices of the next two vertices.
0396: int j = (i + 1) % n;
0397: int k = (i + 2) % n;
0398:
0399: // Calculate the initial lexicographic direction.
0400: int currentDirection;
0401: if (x[i] < x[j]) {
0402: currentDirection = -1;
0403: } else if (x[i] > x[j]) {
0404: currentDirection = 1;
0405: } else if (y[i] < y[j]) {
0406: currentDirection = -1;
0407: } else if (y[i] > y[j]) {
0408: currentDirection = 1;
0409: } else {
0410: currentDirection = 0;
0411: }
0412:
0413: // Increment the direction change counter if necessary.
0414: if (currentDirection != 0
0415: && currentDirection == -previousDirection) {
0416: numDirectionChanges++;
0417: }
0418: previousDirection = currentDirection;
0419:
0420: // Calculate the sign of the angle between the current and
0421: // next directed segments.
0422: int sign = sgn((x[i] - x[j]) * (y[j] - y[k])
0423: - (x[j] - x[k]) * (y[i] - y[j]));
0424: allZero = (allZero && sign == 0);
0425: if (!allZero) {
0426: if (sign != 0 && sign == -previousSign) {
0427: type = POLYGON_CONCAVE;
0428: break;
0429: } else if (sign != 0) { // Only cache non-zero signs.
0430: previousSign = sign;
0431: }
0432: }
0433: }
0434:
0435: if (type == POLYGON_UNCLASSIFIED) {
0436: if (allZero) { // All points on a line.
0437: type = POLYGON_DEGENERATE;
0438: } else if (numDirectionChanges > 2) {
0439: type = POLYGON_CONCAVE;
0440: } else {
0441: type = POLYGON_CONVEX;
0442: }
0443: }
0444:
0445: return type;
0446: }
0447:
0448: /**
0449: * Calculate the sign of the argument.
0450: *
0451: * @param i The integer the sign of which is to be determined.
0452: *
0453: * @return 1 for positive, -1 for negative, and 0 for zero arguments.
0454: */
0455: private final int sgn(int i) {
0456: int sign;
0457: if (i > 0) {
0458: sign = 1;
0459: } else if (i < 0) {
0460: sign = -1;
0461: } else { // zero
0462: sign = 0;
0463: }
0464: return sign;
0465: }
0466:
0467: /**
0468: * Perform scan conversion of a convex polygon.
0469: *
0470: * @param rectList A <code>LinkedList</code>; may be null.
0471: *
0472: * @return A <code>LinkedList</code> of <code>Rectangle</code>s
0473: * representing the scan conversion of the convex polygon.
0474: */
0475: private LinkedList scanConvex(LinkedList rectList) {
0476:
0477: if (rectList == null) {
0478: rectList = new LinkedList();
0479: }
0480:
0481: // Find the index of the top vertex.
0482: int yMin = poly.ypoints[0];
0483: int topVertex = 0;
0484: int n = poly.npoints;
0485: for (int i = 1; i < n; i++) {
0486: if (poly.ypoints[i] < yMin) {
0487: yMin = poly.ypoints[i];
0488: topVertex = i;
0489: }
0490: }
0491:
0492: // Left and right vertex indices.
0493: int leftIndex = topVertex;
0494: int rightIndex = topVertex;
0495:
0496: // Number of vertices remaining.
0497: int numRemaining = n;
0498:
0499: // Current scan line.
0500: int y = yMin;
0501:
0502: // Lower end of left & right edges.
0503: int intYLeft = y - 1;
0504: int intYRight = intYLeft;
0505:
0506: // Copy points to double precision arrays where necessary.
0507: double[] px = intArrayToDoubleArray(poly.xpoints);
0508: int[] py = poly.ypoints;
0509:
0510: double[] leftX = new double[1];
0511: double[] leftDX = new double[1];
0512: double[] rightX = new double[1];
0513: double[] rightDX = new double[1];
0514:
0515: // Scan along lines using new edges along the left and right sides
0516: // as the line crosses new vertices.
0517: while (numRemaining > 0) {
0518: int i;
0519:
0520: // Advance the left edge.
0521: while (intYLeft <= y && numRemaining > 0) {
0522: numRemaining--;
0523: i = leftIndex - 1;
0524: if (i < 0)
0525: i = n - 1;
0526: intersectX(px[leftIndex], py[leftIndex], px[i],
0527: py[i], y, leftX, leftDX);
0528: intYLeft = py[i];
0529: leftIndex = i;
0530: }
0531:
0532: // Advance the right edge.
0533: while (intYRight <= y && numRemaining > 0) {
0534: numRemaining--;
0535: i = rightIndex + 1;
0536: if (i >= n)
0537: i = 0;
0538: intersectX(px[rightIndex], py[rightIndex], px[i],
0539: py[i], y, rightX, rightDX);
0540: intYRight = py[i];
0541: rightIndex = i;
0542: }
0543:
0544: // Process until end of left or right edge.
0545: while (y < intYLeft && y < intYRight) {
0546: if (y >= clip.y && y < clip.getMaxY()) {
0547: Rectangle rect;
0548: if (leftX[0] <= rightX[0]) {
0549: rect = scanSegment(y, leftX[0], rightX[0]);
0550: } else {
0551: rect = scanSegment(y, rightX[0], leftX[0]);
0552: }
0553: if (rect != null) {
0554: rectList.addLast((Object) rect);
0555: }
0556: }
0557: y++;
0558: leftX[0] += leftDX[0];
0559: rightX[0] += rightDX[0];
0560: }
0561: }
0562:
0563: return rectList;
0564: }
0565:
0566: /**
0567: * Return a <code>Rectangle</code> for the supplied line and
0568: * abscissa end points.
0569: *
0570: * @param y The line number.
0571: * @param leftX The left end point of the segment.
0572: * @param rightX The right end point of the segment.
0573: *
0574: * @return The run length <code>Rectangle</code> for the segment.
0575: */
0576: private Rectangle scanSegment(int y, double leftX, double rightX) {
0577: double x = leftX - 0.5;
0578: int xl = (x < clip.x) ? clip.x : (int) Math.ceil(x);
0579: int xr = (int) Math.floor(rightX - 0.5);
0580: if (xr >= clip.x + clip.width)
0581: xr = clip.x + clip.width - 1;
0582: if (xl > xr)
0583: return null;
0584:
0585: return new Rectangle(xl, y, xr - xl + 1, 1);
0586: }
0587:
0588: /**
0589: * For the line y + 0.5 calculate the intersection with the segment
0590: * (x1, y1) to (x2, y2) as well as the slope dx/dy at the point of
0591: * intersection.
0592: *
0593: * @param x1 Abscissa of first segment end point.
0594: * @param y1 Ordinate of first segment end point.
0595: * @param x2 Abscissa of second segment end point.
0596: * @param y2 Ordinate of second segment end point.
0597: * @param y The image line to intersect.
0598: * @param x The abscissa of the point of intersection.
0599: * @param dx The slope dx/dy of the point of intersection.
0600: */
0601: private void intersectX(double x1, int y1, double x2, int y2,
0602: int y, double[] x, double[] dx) {
0603: int dy = y2 - y1;
0604: if (dy == 0)
0605: dy = 1;
0606: double frac = y - y1 + 0.5;
0607:
0608: dx[0] = (x2 - x1) / dy;
0609: x[0] = x1 + dx[0] * frac;
0610: }
0611:
0612: /**
0613: * Perform scan conversion of a concave polygon.
0614: *
0615: * @param rectList A <code>LinkedList</code>; may be null.
0616: *
0617: * @return A <code>LinkedList</code> of <code>Rectangle</code>s
0618: * representing the scan conversion of the concave polygon.
0619: */
0620: private LinkedList scanConcave(LinkedList rectList) {
0621:
0622: if (rectList == null) {
0623: rectList = new LinkedList();
0624: }
0625:
0626: int numVertices = poly.npoints;
0627: if (numVertices <= 0)
0628: return null;
0629:
0630: // Create y-sorted Vector of indices into vertex arrays.
0631: Vector indVector = new Vector();
0632: indVector.add(new Integer(0));
0633: for (int count = 1; count < numVertices; count++) {
0634: // Search entire array until
0635: // vertexY[index] >= vertexY[count] or index == count.
0636: int index = 0;
0637: int value = poly.ypoints[count];
0638: while (index < count) {
0639: int elt = ((Integer) (indVector.get(index)))
0640: .intValue();
0641: if (value <= poly.ypoints[elt])
0642: break;
0643: index++;
0644: }
0645: indVector.insertElementAt((Object) new Integer(count),
0646: index);
0647: }
0648:
0649: // Convert the Vector of indices to an array of same.
0650: int[] ind = vectorToIntArray(indVector);
0651:
0652: // Create a Vector of active edges.
0653: Vector activeEdges = new Vector(numVertices);
0654:
0655: // Initialize the range of lines to examine.
0656: int y0 = Math.max((int) clip.getMinY(), (int) Math
0657: .ceil(poly.ypoints[ind[0]] - 0.5F));
0658: int y1 = Math.min((int) clip.getMaxY(), (int) Math
0659: .floor(poly.ypoints[ind[numVertices - 1]] - 0.5F));
0660:
0661: // Loop over lines. The current line is at y + 0.5 in
0662: // continuous coordinates.
0663: int nextVertex = 0;
0664: for (int y = y0; y <= y1; y++) {
0665: // Check vertices between previous and current line.
0666: while (nextVertex < numVertices
0667: && poly.ypoints[ind[nextVertex]] <= y + 0.5F) {
0668: int i = ind[nextVertex];
0669:
0670: // Delete old (previous) edges and insert new
0671: // (subsequent) edges if they cross current line.
0672: int j = i > 0 ? i - 1 : numVertices - 1; // Previous vertex
0673: if (poly.ypoints[j] <= y - 0.5F) {
0674: deleteEdge(activeEdges, j);
0675: } else if (poly.ypoints[j] > y + 0.5F) {
0676: appendEdge(activeEdges, j, y);
0677: }
0678:
0679: j = i < numVertices - 1 ? i + 1 : 0; // Next vertex.
0680: if (poly.ypoints[j] <= y - 0.5F) {
0681: deleteEdge(activeEdges, i);
0682: } else if (poly.ypoints[j] > y + 0.5F) {
0683: appendEdge(activeEdges, i, y);
0684: }
0685:
0686: nextVertex++;
0687: }
0688:
0689: // Sort active edges by the edge X coordinate.
0690: Object[] edges = activeEdges.toArray();
0691: Arrays.sort(edges, (PolyEdge) edges[0]);
0692:
0693: // Extract run length Rectangles for current line.
0694: int numActive = activeEdges.size();
0695: for (int k = 0; k < numActive; k += 2) {
0696: // Get left and right edges.
0697: PolyEdge edge1 = (PolyEdge) edges[k];
0698: PolyEdge edge2 = (PolyEdge) edges[k + 1];
0699:
0700: // Clip left end point.
0701: int xl = (int) Math.ceil(edge1.x - 0.5);
0702: if (xl < clip.getMinX()) {
0703: xl = (int) clip.getMinX();
0704: }
0705:
0706: // Clip right end point.
0707: int xr = (int) Math.floor(edge2.x - 0.5);
0708: if (xr > clip.getMaxX()) {
0709: xr = (int) clip.getMaxX();
0710: }
0711:
0712: // Create run length Rectangle.
0713: if (xl <= xr) {
0714: Rectangle r = new Rectangle(xl, y, xr - xl + 1,
0715: 1);
0716: rectList.addLast((Object) r);
0717: }
0718:
0719: // Increment edge coordinates.
0720: edge1.x += edge1.dx;
0721: activeEdges.setElementAt((Object) edge1, k);
0722: edge2.x += edge2.dx;
0723: activeEdges.setElementAt((Object) edge2, k + 1);
0724: }
0725: }
0726:
0727: return rectList;
0728: }
0729:
0730: /**
0731: * Delete a <code>PolyEdge</code> from the Vector of active edges.
0732: *
0733: * @param edges The <code>Vector</code> of <code>PolyEdge</code>s.
0734: * @param i The number of the edge to be deleted.
0735: */
0736: private void deleteEdge(Vector edges, int i) {
0737: int numActive = edges.size();
0738: int j;
0739: for (j = 0; j < numActive; j++) {
0740: PolyEdge edge = (PolyEdge) edges.get(j);
0741: if (edge.i == i)
0742: break;
0743: }
0744: if (j < numActive) {
0745: edges.removeElementAt(j);
0746: }
0747: }
0748:
0749: /**
0750: * Append a <code>PolyEdge</code> to the Vector of active edges.
0751: *
0752: * @param edges The <code>Vector</code> of <code>PolyEdge</code>s.
0753: * @param i The number of the edge to be appended.
0754: * @param y The y coordinate of the current scanline.
0755: */
0756: private void appendEdge(Vector edges, int i, int y) {
0757: int j = (i + 1) % poly.npoints;
0758: int ip;
0759: int iq;
0760: if (poly.ypoints[i] < poly.ypoints[j]) {
0761: ip = i;
0762: iq = j;
0763: } else {
0764: ip = j;
0765: iq = i;
0766: }
0767: double dx = (double) (poly.xpoints[iq] - poly.xpoints[ip])
0768: / (double) (poly.ypoints[iq] - poly.ypoints[ip]);
0769: double x = dx * (y + 0.5F - poly.ypoints[ip])
0770: + poly.xpoints[ip];
0771: edges.add(new PolyEdge(x, dx, i));
0772: }
0773:
0774: /**
0775: * Convert an array of <code>int</code>s to an array of
0776: * <code>double</code>s.
0777: */
0778: private double[] intArrayToDoubleArray(int[] intArray) {
0779: int length = intArray.length;
0780: double[] doubleArray = new double[length];
0781: for (int i = 0; i < length; i++) {
0782: doubleArray[i] = intArray[i];
0783: }
0784: return doubleArray;
0785: }
0786:
0787: /**
0788: * Convert a <code>Vector</code> of <code>Integer</code>s to an array
0789: * of <code>int</code>s.
0790: *
0791: * @param vector A <code>Vector</code> of <code>Integer</code>s.
0792: *
0793: * @return The array of <code>int</code>s.
0794: */
0795: private int[] vectorToIntArray(Vector vector) {
0796: int size = vector.size();
0797: int[] array = new int[size];
0798: Object[] objects = vector.toArray();
0799: for (int i = 0; i < size; i++) {
0800: array[i] = ((Integer) objects[i]).intValue();
0801: }
0802: return array;
0803: }
0804: }
0805:
0806: /** Returns the bounds of the mask as a <code>Rectangle</code>. */
0807: public Rectangle getBounds() {
0808: return theShape.getBounds();
0809: }
0810:
0811: /** Returns the bounds of the mask as a <code>Rectangle2D</code>. */
0812: public Rectangle2D getBounds2D() {
0813: return theShape.getBounds2D();
0814: }
0815:
0816: /**
0817: * Returns <code>true</code> if the mask contains a given Point.
0818: *
0819: * @param p a Point specifying the coordinates of the pixel to be queried.
0820: * @return <code>true</code> if the pixel lies within the mask.
0821: *
0822: * @throws IllegalArgumentException is p is null.
0823: */
0824: public boolean contains(Point p) {
0825: if (p == null) {
0826: throw new IllegalArgumentException(JaiI18N
0827: .getString("Generic0"));
0828: }
0829:
0830: return contains(p.x, p.y);
0831: }
0832:
0833: /**
0834: * Returns <code>true</code> if the mask contains a given Point2D.
0835: *
0836: * @param p A Point2D specifying the coordinates of the pixel
0837: * to be queried.
0838: * @throws IllegalArgumentException is p is null.
0839: * @return <code>true</code> if the pixel lies within the mask.
0840: */
0841: public boolean contains(Point2D p) {
0842: if (p == null) {
0843: throw new IllegalArgumentException(JaiI18N
0844: .getString("Generic0"));
0845: }
0846:
0847: return contains((int) p.getX(), (int) p.getY());
0848: }
0849:
0850: /**
0851: * Returns <code>true</code> if the mask contains the point (x, y).
0852: *
0853: * @param x An int specifying the X coordinate of the pixel to be queried.
0854: * @param y An int specifying the Y coordinate of the pixel to be queried.
0855: * @return <code>true</code> if the pixel lies within the mask.
0856: */
0857: public boolean contains(int x, int y) {
0858: return theShape.contains(x, y);
0859: }
0860:
0861: /**
0862: * Returns <code>true</code> if the mask contains the point (x, y).
0863: *
0864: * @param x A double specifying the X coordinate of the pixel
0865: * to be queried.
0866: * @param y A double specifying the Y coordinate of the pixel
0867: * to be queried.
0868: * @return <code>true</code> if the pixel lies within the mask.
0869: */
0870: public boolean contains(double x, double y) {
0871: return contains((int) x, (int) y);
0872: }
0873:
0874: /**
0875: * Returns <code>true</code> if a given <code>Rectangle</code> is
0876: * entirely included within the mask.
0877: *
0878: * @param rect A <code>Rectangle</code> specifying the region to
0879: * be tested for inclusion.
0880: * @return <code>true</code> if the rectangle is
0881: * entirely contained within the mask.
0882: * @throws IllegalArgumentException is rect is null.
0883: */
0884: public boolean contains(Rectangle rect) {
0885: if (rect == null) {
0886: throw new IllegalArgumentException(JaiI18N
0887: .getString("Generic0"));
0888: }
0889:
0890: return contains(new Rectangle2D.Float((float) rect.x,
0891: (float) rect.y, (float) rect.width, (float) rect.height));
0892: }
0893:
0894: /**
0895: * Returns <code>true</code> if a given <code>Rectangle2D</code>
0896: * is entirely included within the mask.
0897: *
0898: * @param rect A <code>Rectangle2D</code> specifying the region to
0899: * be tested for inclusion.
0900: * @return <code>true</code> if the rectangle is entirely
0901: * contained within the mask.
0902: * @throws IllegalArgumentException is rect is null.
0903: */
0904: public boolean contains(Rectangle2D rect) {
0905: if (rect == null) {
0906: throw new IllegalArgumentException(JaiI18N
0907: .getString("Generic0"));
0908: }
0909:
0910: return theShape.contains(rect);
0911: }
0912:
0913: /**
0914: * Returns <code>true</code> if a given rectangle (x, y, w, h) is entirely
0915: * included within the mask.
0916: *
0917: * @param x The int X coordinate of the upper left corner of the region.
0918: * @param y The int Y coordinate of the upper left corner of the region.
0919: * @param w The int width of the region.
0920: * @param h The int height of the region.
0921: * @return <code>true</code> if the rectangle is entirely
0922: * contained within the mask.
0923: */
0924: public boolean contains(int x, int y, int w, int h) {
0925: return contains(new Rectangle2D.Float((float) x, (float) y,
0926: (float) w, (float) h));
0927: }
0928:
0929: /**
0930: * Returns <code>true</code> if a given rectangle (x, y, w, h) is entirely
0931: * included within the mask.
0932: *
0933: * @param x The double X coordinate of the upper left corner of the region.
0934: * @param y The double Y coordinate of the upper left corner of the region.
0935: * @param w The double width of the region.
0936: * @param h The double height of the region.
0937: * @return <code>true</code> if the rectangle is entirely contained
0938: * within the mask.
0939: */
0940: public boolean contains(double x, double y, double w, double h) {
0941: return theShape.contains(x, y, w, h);
0942: }
0943:
0944: /**
0945: * Returns <code>true</code> if a given <code>Rectangle</code>
0946: * intersects the mask.
0947: *
0948: * @param r A <code>Rectangle</code> specifying the region to be tested for
0949: * inclusion.
0950: * @return <code>true</code> if the rectangle intersects the mask.
0951: * @throws IllegalArgumentException is r is null.
0952: */
0953: public boolean intersects(Rectangle r) {
0954: if (r == null) {
0955: throw new IllegalArgumentException(JaiI18N
0956: .getString("Generic0"));
0957: }
0958:
0959: return intersects(new Rectangle2D.Float((float) r.x,
0960: (float) r.y, (float) r.width, (float) r.height));
0961: }
0962:
0963: /**
0964: * Returns <code>true</code> if a given <code>Rectangle2D</code>
0965: * intersects the mask.
0966: *
0967: * @param r A <code>Rectangle2D</code> specifying the region to be
0968: * tested for inclusion.
0969: * @return <code>true</code> if the rectangle intersects the mask.
0970: * @throws IllegalArgumentException is r is null.
0971: */
0972: public boolean intersects(Rectangle2D r) {
0973: if (r == null) {
0974: throw new IllegalArgumentException(JaiI18N
0975: .getString("Generic0"));
0976: }
0977:
0978: return theShape.intersects(r);
0979: }
0980:
0981: /**
0982: * Returns <code>true</code> if a given rectangle (x, y, w, h)
0983: * intersects the mask.
0984: *
0985: * @param x The int X coordinate of the upper left corner of the region.
0986: * @param y The int Y coordinate of the upper left corner of the region.
0987: * @param w The int width of the region.
0988: * @param h The int height of the region.
0989: * @return <code>true</code> if the rectangle intersects the mask.
0990: */
0991: public boolean intersects(int x, int y, int w, int h) {
0992: return intersects(new Rectangle2D.Float((float) x, (float) y,
0993: (float) w, (float) h));
0994: }
0995:
0996: /**
0997: * Returns <code>true</code> if a given rectangle (x, y, w, h)
0998: * intersects the mask.
0999: *
1000: * @param x The double X coordinate of the upper left corner of the region.
1001: * @param y The double Y coordinate of the upper left corner of the region.
1002: * @param w The double width of the region.
1003: * @param h The double height of the region.
1004: * @return <code>true</code> if the rectangle intersects the mask.
1005: */
1006: public boolean intersects(double x, double y, double w, double h) {
1007: return theShape.intersects(x, y, w, h);
1008: }
1009:
1010: /**
1011: * Adds another mask to this one.
1012: * This operation may force this mask to be rendered.
1013: *
1014: * @param roi A ROI.
1015: * @throws IllegalArgumentException is roi is null.
1016: */
1017: public ROI add(ROI roi) {
1018:
1019: if (roi == null) {
1020: throw new IllegalArgumentException(JaiI18N
1021: .getString("ROIShape3"));
1022: }
1023:
1024: if (!(roi instanceof ROIShape)) {
1025: return super .add(roi);
1026: } else {
1027: ROIShape rois = (ROIShape) roi;
1028: Area a1 = new Area(theShape);
1029: Area a2 = new Area(rois.theShape);
1030: a1.add(a2);
1031: return new ROIShape(a1);
1032: }
1033: }
1034:
1035: /**
1036: * Subtracts another mask from this one.
1037: * This operation may force this mask to be rendered.
1038: *
1039: * @param roi A ROI.
1040: * @throws IllegalArgumentException is roi is null.
1041: */
1042: public ROI subtract(ROI roi) {
1043:
1044: if (roi == null) {
1045: throw new IllegalArgumentException(JaiI18N
1046: .getString("ROIShape3"));
1047: }
1048:
1049: if (!(roi instanceof ROIShape)) {
1050: return super .subtract(roi);
1051: } else {
1052: ROIShape rois = (ROIShape) roi;
1053: Area a1 = new Area(theShape);
1054: Area a2 = new Area(rois.theShape);
1055: a1.subtract(a2);
1056: return new ROIShape(a1);
1057: }
1058: }
1059:
1060: /**
1061: * Sets the mask to its intersection with another mask.
1062: * This operation may force this mask to be rendered.
1063: *
1064: * @param roi A ROI.
1065: * @throws IllegalArgumentException is roi is null.
1066: */
1067: public ROI intersect(ROI roi) {
1068:
1069: if (roi == null) {
1070: throw new IllegalArgumentException(JaiI18N
1071: .getString("ROIShape3"));
1072: }
1073:
1074: if (!(roi instanceof ROIShape)) {
1075: return super .intersect(roi);
1076: } else {
1077: ROIShape rois = (ROIShape) roi;
1078: Area a1 = new Area(theShape);
1079: Area a2 = new Area(rois.theShape);
1080: a1.intersect(a2);
1081: return new ROIShape(a1);
1082: }
1083: }
1084:
1085: /**
1086: * Sets the mask to its exclusive-or with another mask.
1087: * This operation may force this mask to be rendered.
1088: *
1089: * @param roi A ROI.
1090: * @throws IllegalArgumentException is roi is null.
1091: */
1092: public ROI exclusiveOr(ROI roi) {
1093:
1094: if (roi == null) {
1095: throw new IllegalArgumentException(JaiI18N
1096: .getString("ROIShape3"));
1097: }
1098:
1099: if (!(roi instanceof ROIShape)) {
1100: return super .exclusiveOr(roi);
1101: } else {
1102: ROIShape rois = (ROIShape) roi;
1103: Area a1 = new Area(theShape);
1104: Area a2 = new Area(rois.theShape);
1105: a1.exclusiveOr(a2);
1106: return new ROIShape(a1);
1107: }
1108: }
1109:
1110: /**
1111: * Returns the internal Shape representation or null if a shape
1112: * representation is not possible.
1113: */
1114: public Shape getAsShape() {
1115: return theShape;
1116: }
1117:
1118: /**
1119: * Returns the shape as a <code>PlanarImage</code>. This requires
1120: * performing an antialiased rendering of the internal Shape.
1121: *
1122: * @return If the upper-left corner of the bounds of this
1123: * <code>ROIShape</code> is (0, 0), the returned image is a
1124: * <code>BufferedImage</code> of type TYPE_BYTE_BINARY wrapped as
1125: * a <code>PlanarImage</code>. Otherwise, the returned image is a
1126: * (bilevel) <code>TiledImage</code> whose <code>SampleModel</code>
1127: * is an instance of <code>MultiPixelPackedSampleModel</code>.
1128: */
1129: public PlanarImage getAsImage() {
1130:
1131: if (theImage != null)
1132: return theImage;
1133:
1134: Rectangle r = theShape.getBounds();
1135:
1136: PlanarImage pi;
1137: Graphics2D g2d;
1138:
1139: if ((r.x == 0) && (r.y == 0)) {
1140:
1141: BufferedImage bi = new BufferedImage(r.width, r.height,
1142: BufferedImage.TYPE_BYTE_BINARY);
1143:
1144: pi = PlanarImage.wrapRenderedImage(bi);
1145: g2d = bi.createGraphics();
1146: } else {
1147:
1148: SampleModel sm = new MultiPixelPackedSampleModel(
1149: DataBuffer.TYPE_BYTE, r.width, r.height, 1);
1150:
1151: // Create a TiledImage into which to write.
1152: TiledImage ti = new TiledImage(r.x, r.y, r.width, r.height,
1153: r.x, r.y, sm, PlanarImage.createColorModel(sm));
1154:
1155: // Create the associated TiledImageGraphics.
1156: pi = ti;
1157: g2d = ti.createGraphics();
1158: }
1159:
1160: // Write the Shape into the TiledImageGraphics.
1161: g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
1162: RenderingHints.VALUE_ANTIALIAS_ON);
1163: g2d.fill(theShape);
1164:
1165: theImage = pi; // Cache the output
1166:
1167: return theImage;
1168: }
1169:
1170: /**
1171: * Transforms the current contents of the <code>ROI</code> by a
1172: * given <code>AffineTransform</code>.
1173: *
1174: * @param at An <code>AffineTransform</code> object.
1175: * @throws IllegalArgumentException if at is null.
1176: */
1177: public ROI transform(AffineTransform at) {
1178: if (at == null) {
1179: throw new IllegalArgumentException(JaiI18N
1180: .getString("Generic0"));
1181: }
1182:
1183: return new ROIShape(at.createTransformedShape(theShape));
1184: }
1185:
1186: /**
1187: * Returns a bitmask for a given rectangular region of the ROI
1188: * indicating whether the pixel is included in the region of
1189: * interest. The results are packed into 32-bit integers, with
1190: * the MSB considered to lie on the left. The last entry in each
1191: * row of the result may have bits that lie outside of the
1192: * requested rectangle. These bits are guaranteed to be zeroed.
1193: *
1194: * <p> The <code>mask</code> array, if supplied, must be of length
1195: * equal to or greater than <code>height</code> and each of its
1196: * subarrays must have length equal to or greater than (width +
1197: * 31)/32. If <code>null</code> is passed in, a suitable array
1198: * will be constructed. If the mask is non-null but has
1199: * insufficient size, an exception will be thrown.
1200: *
1201: * @param x The X coordinate of the upper left corner of the rectangle.
1202: * @param y The Y coordinate of the upper left corner of the rectangle.
1203: * @param width The width of the rectangle.
1204: * @param height The height of the rectangle.
1205: * @param mask A two-dimensional array of ints at least
1206: * (width + 31)/32 entries wide and (height) entries tall,
1207: * or null.
1208: * @return A reference to the <code>mask</code> parameter, or
1209: * to a newly constructed array if <code>mask</code> is
1210: * <code>null</code>.
1211: */
1212: public int[][] getAsBitmask(int x, int y, int width, int height,
1213: int[][] mask) {
1214: // Get the un-merged Rectangle list (run length Rectangles only).
1215: LinkedList rectList = getAsRectangleList(x, y, width, height,
1216: false);
1217:
1218: if (rectList == null) {
1219: return null;
1220: }
1221:
1222: // Convert the Rectangle list to a bit mask.
1223: return rectangleListToBitmask(rectList, new Rectangle(x, y,
1224: width, height), mask);
1225: }
1226:
1227: /**
1228: * Returns a <code>LinkedList</code> of <code>Rectangle</code>s
1229: * for a given rectangular region of the ROI. The
1230: * <code>Rectangle</code>s in the list are merged into a minimal
1231: * set.
1232: *
1233: * @param x The X coordinate of the upper left corner of the rectangle.
1234: * @param y The Y coordinate of the upper left corner of the rectangle.
1235: * @param width The width of the rectangle.
1236: * @param height The height of the rectangle.
1237: * @return A <code>LinkedList</code> of <code>Rectangle</code>s.
1238: */
1239: public LinkedList getAsRectangleList(int x, int y, int width,
1240: int height) {
1241: return getAsRectangleList(x, y, width, height, true);
1242: }
1243:
1244: /**
1245: * Returns a <code>LinkedList</code> of <code>Rectangle</code>s for
1246: * a given rectangular region of the ROI.
1247: *
1248: * @param x The X coordinate of the upper left corner of the rectangle.
1249: * @param y The Y coordinate of the upper left corner of the rectangle.
1250: * @param width The width of the rectangle.
1251: * @param height The height of the rectangle.
1252: * @param mergeRectangles <code>true</code> if the <code>Rectangle</code>s
1253: * are to be merged into a minimal set.
1254: * @return A <code>LinkedList</code> of <code>Rectangle</code>s.
1255: */
1256: protected LinkedList getAsRectangleList(int x, int y, int width,
1257: int height, boolean mergeRectangles) {
1258: LinkedList rectangleList = null;
1259:
1260: // Create a clipping Rectangle.
1261: Rectangle clip = new Rectangle(x, y, width, height);
1262:
1263: /// XXX bpb 1998/09/28 Is it really necessary to use Area.intersects()?
1264: /// Note that the Polygon.intersects() method appears not to be
1265: /// implemented. Shape.intersects() also appeared not to work in
1266: /// testing the trivial case below.
1267: if (!((new Area(theShape)).intersects(clip))) { // Null overlap.
1268: return null;
1269: } else if (theShape instanceof Rectangle2D) { // Trivial case.
1270: // Return a list consisting of a single Rectangle which is the
1271: // intersection of the clipping Rectangle with the internal
1272: // Shape of the ROIShape rounded to integer coordinates.
1273: Rectangle2D.Double dstRect = new Rectangle2D.Double();
1274: Rectangle2D
1275: .intersect((Rectangle2D) theShape, clip, dstRect);
1276: int rectX = (int) Math.round(dstRect.getMinX());
1277: int rectY = (int) Math.round(dstRect.getMinY());
1278: int rectW = (int) Math.round(dstRect.getMaxX() - rectX);
1279: int rectH = (int) Math.round(dstRect.getMaxY() - rectY);
1280: rectangleList = new LinkedList();
1281: rectangleList.addLast((Object) new Rectangle(rectX, rectY,
1282: rectW, rectH));
1283: } else if (theShape instanceof Polygon) { // Polygon.
1284: rectangleList = polygonToRunLengthList(clip,
1285: (Polygon) theShape);
1286: if (mergeRectangles && rectangleList != null) {
1287: rectangleList = mergeRunLengthList(rectangleList);
1288: }
1289: } else { // Generic case.
1290: // Get the corresponding PlanarImage.
1291: getAsImage();
1292:
1293: // Call the super-class method.
1294: rectangleList = super .getAsRectangleList(x, y, width,
1295: height, mergeRectangles);
1296: }
1297:
1298: return rectangleList;
1299: }
1300:
1301: /**
1302: * Serialize the <code>ROIShape</code>.
1303: *
1304: * @param out The <code>ObjectOutputStream</code>.
1305: */
1306: private void writeObject(ObjectOutputStream out) throws IOException {
1307: // Create a serializable form of the Shape.
1308: LinkedList rectList = null;
1309: if (theShape == null) {
1310: rectList = new LinkedList(); // zero-size LinkedList
1311: } else {
1312: Rectangle r = getBounds();
1313: rectList = getAsRectangleList(r.x, r.y, r.width, r.height);
1314: }
1315:
1316: // Write serialized form to the stream.
1317: out.defaultWriteObject();
1318: out.writeObject(rectList);
1319: }
1320:
1321: /**
1322: * Deserialize the <code>ROIShape</code>.
1323: *
1324: * @param in The <code>ObjectInputStream</code>.
1325: */
1326: private void readObject(ObjectInputStream in) throws IOException,
1327: ClassNotFoundException {
1328:
1329: // Read serialized form from the stream.
1330: LinkedList rectList = null;
1331: in.defaultReadObject();
1332: rectList = (LinkedList) in.readObject();
1333:
1334: // Restore the transient Shape as an Area.
1335: Area a = new Area();
1336: int listSize = rectList.size();
1337: for (int i = 0; i < listSize; i++) {
1338: a.add(new Area((Rectangle) rectList.get(i)));
1339: }
1340: theShape = a;
1341: }
1342: }
|