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.awt.geom;
0027:
0028: import java.awt.geom.Rectangle2D;
0029: import java.awt.geom.QuadCurve2D;
0030: import java.awt.geom.CubicCurve2D;
0031: import java.awt.geom.PathIterator;
0032: import java.awt.geom.IllegalPathStateException;
0033: import java.util.Vector;
0034:
0035: public abstract class Curve {
0036: public static final int INCREASING = 1;
0037: public static final int DECREASING = -1;
0038:
0039: protected int direction;
0040:
0041: public static void insertMove(Vector curves, double x, double y) {
0042: curves.add(new Order0(x, y));
0043: }
0044:
0045: public static void insertLine(Vector curves, double x0, double y0,
0046: double x1, double y1) {
0047: if (y0 < y1) {
0048: curves.add(new Order1(x0, y0, x1, y1, INCREASING));
0049: } else if (y0 > y1) {
0050: curves.add(new Order1(x1, y1, x0, y0, DECREASING));
0051: } else {
0052: // Do not add horizontal lines
0053: }
0054: }
0055:
0056: public static void insertQuad(Vector curves, double x0, double y0,
0057: double coords[]) {
0058: double y1 = coords[3];
0059: if (y0 > y1) {
0060: Order2.insert(curves, coords, coords[2], y1, coords[0],
0061: coords[1], x0, y0, DECREASING);
0062: } else if (y0 == y1 && y0 == coords[1]) {
0063: // Do not add horizontal lines
0064: return;
0065: } else {
0066: Order2.insert(curves, coords, x0, y0, coords[0], coords[1],
0067: coords[2], y1, INCREASING);
0068: }
0069: }
0070:
0071: public static void insertCubic(Vector curves, double x0, double y0,
0072: double coords[]) {
0073: double y1 = coords[5];
0074: if (y0 > y1) {
0075: Order3
0076: .insert(curves, coords, coords[4], y1, coords[2],
0077: coords[3], coords[0], coords[1], x0, y0,
0078: DECREASING);
0079: } else if (y0 == y1 && y0 == coords[1] && y0 == coords[3]) {
0080: // Do not add horizontal lines
0081: return;
0082: } else {
0083: Order3.insert(curves, coords, x0, y0, coords[0], coords[1],
0084: coords[2], coords[3], coords[4], y1, INCREASING);
0085: }
0086: }
0087:
0088: /**
0089: * Calculates the number of times the given path
0090: * crosses the ray extending to the right from (px,py).
0091: * If the point lies on a part of the path,
0092: * then no crossings are counted for that intersection.
0093: * +1 is added for each crossing where the Y coordinate is increasing
0094: * -1 is added for each crossing where the Y coordinate is decreasing
0095: * The return value is the sum of all crossings for every segment in
0096: * the path.
0097: * The path must start with a SEG_MOVETO, otherwise an exception is
0098: * thrown.
0099: * The caller must check p[xy] for NaN values.
0100: * The caller may also reject infinite p[xy] values as well.
0101: */
0102: public static int pointCrossingsForPath(PathIterator pi, double px,
0103: double py) {
0104: if (pi.isDone()) {
0105: return 0;
0106: }
0107: double coords[] = new double[6];
0108: if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) {
0109: throw new IllegalPathStateException(
0110: "missing initial moveto " + "in path definition");
0111: }
0112: pi.next();
0113: double movx = coords[0];
0114: double movy = coords[1];
0115: double curx = movx;
0116: double cury = movy;
0117: double endx, endy;
0118: int crossings = 0;
0119: while (!pi.isDone()) {
0120: switch (pi.currentSegment(coords)) {
0121: case PathIterator.SEG_MOVETO:
0122: if (cury != movy) {
0123: crossings += pointCrossingsForLine(px, py, curx,
0124: cury, movx, movy);
0125: }
0126: movx = curx = coords[0];
0127: movy = cury = coords[1];
0128: break;
0129: case PathIterator.SEG_LINETO:
0130: endx = coords[0];
0131: endy = coords[1];
0132: crossings += pointCrossingsForLine(px, py, curx, cury,
0133: endx, endy);
0134: curx = endx;
0135: cury = endy;
0136: break;
0137: case PathIterator.SEG_QUADTO:
0138: endx = coords[2];
0139: endy = coords[3];
0140: crossings += pointCrossingsForQuad(px, py, curx, cury,
0141: coords[0], coords[1], endx, endy, 0);
0142: curx = endx;
0143: cury = endy;
0144: break;
0145: case PathIterator.SEG_CUBICTO:
0146: endx = coords[4];
0147: endy = coords[5];
0148: crossings += pointCrossingsForCubic(px, py, curx, cury,
0149: coords[0], coords[1], coords[2], coords[3],
0150: endx, endy, 0);
0151: curx = endx;
0152: cury = endy;
0153: break;
0154: case PathIterator.SEG_CLOSE:
0155: if (cury != movy) {
0156: crossings += pointCrossingsForLine(px, py, curx,
0157: cury, movx, movy);
0158: }
0159: curx = movx;
0160: cury = movy;
0161: break;
0162: }
0163: pi.next();
0164: }
0165: if (cury != movy) {
0166: crossings += pointCrossingsForLine(px, py, curx, cury,
0167: movx, movy);
0168: }
0169: return crossings;
0170: }
0171:
0172: /**
0173: * Calculates the number of times the line from (x0,y0) to (x1,y1)
0174: * crosses the ray extending to the right from (px,py).
0175: * If the point lies on the line, then no crossings are recorded.
0176: * +1 is returned for a crossing where the Y coordinate is increasing
0177: * -1 is returned for a crossing where the Y coordinate is decreasing
0178: */
0179: public static int pointCrossingsForLine(double px, double py,
0180: double x0, double y0, double x1, double y1) {
0181: if (py < y0 && py < y1)
0182: return 0;
0183: if (py >= y0 && py >= y1)
0184: return 0;
0185: // assert(y0 != y1);
0186: if (px >= x0 && px >= x1)
0187: return 0;
0188: if (px < x0 && px < x1)
0189: return (y0 < y1) ? 1 : -1;
0190: double xintercept = x0 + (py - y0) * (x1 - x0) / (y1 - y0);
0191: if (px >= xintercept)
0192: return 0;
0193: return (y0 < y1) ? 1 : -1;
0194: }
0195:
0196: /**
0197: * Calculates the number of times the quad from (x0,y0) to (x1,y1)
0198: * crosses the ray extending to the right from (px,py).
0199: * If the point lies on a part of the curve,
0200: * then no crossings are counted for that intersection.
0201: * the level parameter should be 0 at the top-level call and will count
0202: * up for each recursion level to prevent infinite recursion
0203: * +1 is added for each crossing where the Y coordinate is increasing
0204: * -1 is added for each crossing where the Y coordinate is decreasing
0205: */
0206: public static int pointCrossingsForQuad(double px, double py,
0207: double x0, double y0, double xc, double yc, double x1,
0208: double y1, int level) {
0209: if (py < y0 && py < yc && py < y1)
0210: return 0;
0211: if (py >= y0 && py >= yc && py >= y1)
0212: return 0;
0213: // Note y0 could equal y1...
0214: if (px >= x0 && px >= xc && px >= x1)
0215: return 0;
0216: if (px < x0 && px < xc && px < x1) {
0217: if (py >= y0) {
0218: if (py < y1)
0219: return 1;
0220: } else {
0221: // py < y0
0222: if (py >= y1)
0223: return -1;
0224: }
0225: // py outside of y01 range, and/or y0==y1
0226: return 0;
0227: }
0228: // double precision only has 52 bits of mantissa
0229: if (level > 52)
0230: return pointCrossingsForLine(px, py, x0, y0, x1, y1);
0231: double x0c = (x0 + xc) / 2;
0232: double y0c = (y0 + yc) / 2;
0233: double xc1 = (xc + x1) / 2;
0234: double yc1 = (yc + y1) / 2;
0235: xc = (x0c + xc1) / 2;
0236: yc = (y0c + yc1) / 2;
0237: if (Double.isNaN(xc) || Double.isNaN(yc)) {
0238: // [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN
0239: // [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN
0240: // These values are also NaN if opposing infinities are added
0241: return 0;
0242: }
0243: return (pointCrossingsForQuad(px, py, x0, y0, x0c, y0c, xc, yc,
0244: level + 1) + pointCrossingsForQuad(px, py, xc, yc, xc1,
0245: yc1, x1, y1, level + 1));
0246: }
0247:
0248: /**
0249: * Calculates the number of times the cubic from (x0,y0) to (x1,y1)
0250: * crosses the ray extending to the right from (px,py).
0251: * If the point lies on a part of the curve,
0252: * then no crossings are counted for that intersection.
0253: * the level parameter should be 0 at the top-level call and will count
0254: * up for each recursion level to prevent infinite recursion
0255: * +1 is added for each crossing where the Y coordinate is increasing
0256: * -1 is added for each crossing where the Y coordinate is decreasing
0257: */
0258: public static int pointCrossingsForCubic(double px, double py,
0259: double x0, double y0, double xc0, double yc0, double xc1,
0260: double yc1, double x1, double y1, int level) {
0261: if (py < y0 && py < yc0 && py < yc1 && py < y1)
0262: return 0;
0263: if (py >= y0 && py >= yc0 && py >= yc1 && py >= y1)
0264: return 0;
0265: // Note y0 could equal yc0...
0266: if (px >= x0 && px >= xc0 && px >= xc1 && px >= x1)
0267: return 0;
0268: if (px < x0 && px < xc0 && px < xc1 && px < x1) {
0269: if (py >= y0) {
0270: if (py < y1)
0271: return 1;
0272: } else {
0273: // py < y0
0274: if (py >= y1)
0275: return -1;
0276: }
0277: // py outside of y01 range, and/or y0==yc0
0278: return 0;
0279: }
0280: // double precision only has 52 bits of mantissa
0281: if (level > 52)
0282: return pointCrossingsForLine(px, py, x0, y0, x1, y1);
0283: double xmid = (xc0 + xc1) / 2;
0284: double ymid = (yc0 + yc1) / 2;
0285: xc0 = (x0 + xc0) / 2;
0286: yc0 = (y0 + yc0) / 2;
0287: xc1 = (xc1 + x1) / 2;
0288: yc1 = (yc1 + y1) / 2;
0289: double xc0m = (xc0 + xmid) / 2;
0290: double yc0m = (yc0 + ymid) / 2;
0291: double xmc1 = (xmid + xc1) / 2;
0292: double ymc1 = (ymid + yc1) / 2;
0293: xmid = (xc0m + xmc1) / 2;
0294: ymid = (yc0m + ymc1) / 2;
0295: if (Double.isNaN(xmid) || Double.isNaN(ymid)) {
0296: // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN
0297: // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN
0298: // These values are also NaN if opposing infinities are added
0299: return 0;
0300: }
0301: return (pointCrossingsForCubic(px, py, x0, y0, xc0, yc0, xc0m,
0302: yc0m, xmid, ymid, level + 1) + pointCrossingsForCubic(
0303: px, py, xmid, ymid, xmc1, ymc1, xc1, yc1, x1, y1,
0304: level + 1));
0305: }
0306:
0307: /**
0308: * The rectangle intersection test counts the number of times
0309: * that the path crosses through the shadow that the rectangle
0310: * projects to the right towards (x => +INFINITY).
0311: *
0312: * During processing of the path it actually counts every time
0313: * the path crosses either or both of the top and bottom edges
0314: * of that shadow. If the path enters from the top, the count
0315: * is incremented. If it then exits back through the top, the
0316: * same way it came in, the count is decremented and there is
0317: * no impact on the winding count. If, instead, the path exits
0318: * out the bottom, then the count is incremented again and a
0319: * full pass through the shadow is indicated by the winding count
0320: * having been incremented by 2.
0321: *
0322: * Thus, the winding count that it accumulates is actually double
0323: * the real winding count. Since the path is continuous, the
0324: * final answer should be a multiple of 2, otherwise there is a
0325: * logic error somewhere.
0326: *
0327: * If the path ever has a direct hit on the rectangle, then a
0328: * special value is returned. This special value terminates
0329: * all ongoing accumulation on up through the call chain and
0330: * ends up getting returned to the calling function which can
0331: * then produce an answer directly. For intersection tests,
0332: * the answer is always "true" if the path intersects the
0333: * rectangle. For containment tests, the answer is always
0334: * "false" if the path intersects the rectangle. Thus, no
0335: * further processing is ever needed if an intersection occurs.
0336: */
0337: public static final int RECT_INTERSECTS = 0x80000000;
0338:
0339: /**
0340: * Accumulate the number of times the path crosses the shadow
0341: * extending to the right of the rectangle. See the comment
0342: * for the RECT_INTERSECTS constant for more complete details.
0343: * The return value is the sum of all crossings for both the
0344: * top and bottom of the shadow for every segment in the path,
0345: * or the special value RECT_INTERSECTS if the path ever enters
0346: * the interior of the rectangle.
0347: * The path must start with a SEG_MOVETO, otherwise an exception is
0348: * thrown.
0349: * The caller must check r[xy]{min,max} for NaN values.
0350: */
0351: public static int rectCrossingsForPath(PathIterator pi,
0352: double rxmin, double rymin, double rxmax, double rymax) {
0353: if (rxmax <= rxmin || rymax <= rymin) {
0354: return 0;
0355: }
0356: if (pi.isDone()) {
0357: return 0;
0358: }
0359: double coords[] = new double[6];
0360: if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) {
0361: throw new IllegalPathStateException(
0362: "missing initial moveto " + "in path definition");
0363: }
0364: pi.next();
0365: double curx, cury, movx, movy, endx, endy;
0366: curx = movx = coords[0];
0367: cury = movy = coords[1];
0368: int crossings = 0;
0369: while (crossings != RECT_INTERSECTS && !pi.isDone()) {
0370: switch (pi.currentSegment(coords)) {
0371: case PathIterator.SEG_MOVETO:
0372: if (curx != movx || cury != movy) {
0373: crossings = rectCrossingsForLine(crossings, rxmin,
0374: rymin, rxmax, rymax, curx, cury, movx, movy);
0375: }
0376: // Count should always be a multiple of 2 here.
0377: // assert((crossings & 1) != 0);
0378: movx = curx = coords[0];
0379: movy = cury = coords[1];
0380: break;
0381: case PathIterator.SEG_LINETO:
0382: endx = coords[0];
0383: endy = coords[1];
0384: crossings = rectCrossingsForLine(crossings, rxmin,
0385: rymin, rxmax, rymax, curx, cury, endx, endy);
0386: curx = endx;
0387: cury = endy;
0388: break;
0389: case PathIterator.SEG_QUADTO:
0390: endx = coords[2];
0391: endy = coords[3];
0392: crossings = rectCrossingsForQuad(crossings, rxmin,
0393: rymin, rxmax, rymax, curx, cury, coords[0],
0394: coords[1], endx, endy, 0);
0395: curx = endx;
0396: cury = endy;
0397: break;
0398: case PathIterator.SEG_CUBICTO:
0399: endx = coords[4];
0400: endy = coords[5];
0401: crossings = rectCrossingsForCubic(crossings, rxmin,
0402: rymin, rxmax, rymax, curx, cury, coords[0],
0403: coords[1], coords[2], coords[3], endx, endy, 0);
0404: curx = endx;
0405: cury = endy;
0406: break;
0407: case PathIterator.SEG_CLOSE:
0408: if (curx != movx || cury != movy) {
0409: crossings = rectCrossingsForLine(crossings, rxmin,
0410: rymin, rxmax, rymax, curx, cury, movx, movy);
0411: }
0412: curx = movx;
0413: cury = movy;
0414: // Count should always be a multiple of 2 here.
0415: // assert((crossings & 1) != 0);
0416: break;
0417: }
0418: pi.next();
0419: }
0420: if (crossings != RECT_INTERSECTS
0421: && (curx != movx || cury != movy)) {
0422: crossings = rectCrossingsForLine(crossings, rxmin, rymin,
0423: rxmax, rymax, curx, cury, movx, movy);
0424: }
0425: // Count should always be a multiple of 2 here.
0426: // assert((crossings & 1) != 0);
0427: return crossings;
0428: }
0429:
0430: /**
0431: * Accumulate the number of times the line crosses the shadow
0432: * extending to the right of the rectangle. See the comment
0433: * for the RECT_INTERSECTS constant for more complete details.
0434: */
0435: public static int rectCrossingsForLine(int crossings, double rxmin,
0436: double rymin, double rxmax, double rymax, double x0,
0437: double y0, double x1, double y1) {
0438: if (y0 >= rymax && y1 >= rymax)
0439: return crossings;
0440: if (y0 <= rymin && y1 <= rymin)
0441: return crossings;
0442: if (x0 <= rxmin && x1 <= rxmin)
0443: return crossings;
0444: if (x0 >= rxmax && x1 >= rxmax) {
0445: // Line is entirely to the right of the rect
0446: // and the vertical ranges of the two overlap by a non-empty amount
0447: // Thus, this line segment is partially in the "right-shadow"
0448: // Path may have done a complete crossing
0449: // Or path may have entered or exited the right-shadow
0450: if (y0 < y1) {
0451: // y-increasing line segment...
0452: // We know that y0 < rymax and y1 > rymin
0453: if (y0 <= rymin)
0454: crossings++;
0455: if (y1 >= rymax)
0456: crossings++;
0457: } else if (y1 < y0) {
0458: // y-decreasing line segment...
0459: // We know that y1 < rymax and y0 > rymin
0460: if (y1 <= rymin)
0461: crossings--;
0462: if (y0 >= rymax)
0463: crossings--;
0464: }
0465: return crossings;
0466: }
0467: // Remaining case:
0468: // Both x and y ranges overlap by a non-empty amount
0469: // First do trivial INTERSECTS rejection of the cases
0470: // where one of the endpoints is inside the rectangle.
0471: if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax)
0472: || (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) {
0473: return RECT_INTERSECTS;
0474: }
0475: // Otherwise calculate the y intercepts and see where
0476: // they fall with respect to the rectangle
0477: double xi0 = x0;
0478: if (y0 < rymin) {
0479: xi0 += ((rymin - y0) * (x1 - x0) / (y1 - y0));
0480: } else if (y0 > rymax) {
0481: xi0 += ((rymax - y0) * (x1 - x0) / (y1 - y0));
0482: }
0483: double xi1 = x1;
0484: if (y1 < rymin) {
0485: xi1 += ((rymin - y1) * (x0 - x1) / (y0 - y1));
0486: } else if (y1 > rymax) {
0487: xi1 += ((rymax - y1) * (x0 - x1) / (y0 - y1));
0488: }
0489: if (xi0 <= rxmin && xi1 <= rxmin)
0490: return crossings;
0491: if (xi0 >= rxmax && xi1 >= rxmax) {
0492: if (y0 < y1) {
0493: // y-increasing line segment...
0494: // We know that y0 < rymax and y1 > rymin
0495: if (y0 <= rymin)
0496: crossings++;
0497: if (y1 >= rymax)
0498: crossings++;
0499: } else if (y1 < y0) {
0500: // y-decreasing line segment...
0501: // We know that y1 < rymax and y0 > rymin
0502: if (y1 <= rymin)
0503: crossings--;
0504: if (y0 >= rymax)
0505: crossings--;
0506: }
0507: return crossings;
0508: }
0509: return RECT_INTERSECTS;
0510: }
0511:
0512: /**
0513: * Accumulate the number of times the quad crosses the shadow
0514: * extending to the right of the rectangle. See the comment
0515: * for the RECT_INTERSECTS constant for more complete details.
0516: */
0517: public static int rectCrossingsForQuad(int crossings, double rxmin,
0518: double rymin, double rxmax, double rymax, double x0,
0519: double y0, double xc, double yc, double x1, double y1,
0520: int level) {
0521: if (y0 >= rymax && yc >= rymax && y1 >= rymax)
0522: return crossings;
0523: if (y0 <= rymin && yc <= rymin && y1 <= rymin)
0524: return crossings;
0525: if (x0 <= rxmin && xc <= rxmin && x1 <= rxmin)
0526: return crossings;
0527: if (x0 >= rxmax && xc >= rxmax && x1 >= rxmax) {
0528: // Quad is entirely to the right of the rect
0529: // and the vertical range of the 3 Y coordinates of the quad
0530: // overlaps the vertical range of the rect by a non-empty amount
0531: // We now judge the crossings solely based on the line segment
0532: // connecting the endpoints of the quad.
0533: // Note that we may have 0, 1, or 2 crossings as the control
0534: // point may be causing the Y range intersection while the
0535: // two endpoints are entirely above or below.
0536: if (y0 < y1) {
0537: // y-increasing line segment...
0538: if (y0 <= rymin && y1 > rymin)
0539: crossings++;
0540: if (y0 < rymax && y1 >= rymax)
0541: crossings++;
0542: } else if (y1 < y0) {
0543: // y-decreasing line segment...
0544: if (y1 <= rymin && y0 > rymin)
0545: crossings--;
0546: if (y1 < rymax && y0 >= rymax)
0547: crossings--;
0548: }
0549: return crossings;
0550: }
0551: // The intersection of ranges is more complicated
0552: // First do trivial INTERSECTS rejection of the cases
0553: // where one of the endpoints is inside the rectangle.
0554: if ((x0 < rxmax && x0 > rxmin && y0 < rymax && y0 > rymin)
0555: || (x1 < rxmax && x1 > rxmin && y1 < rymax && y1 > rymin)) {
0556: return RECT_INTERSECTS;
0557: }
0558: // Otherwise, subdivide and look for one of the cases above.
0559: // double precision only has 52 bits of mantissa
0560: if (level > 52) {
0561: return rectCrossingsForLine(crossings, rxmin, rymin, rxmax,
0562: rymax, x0, y0, x1, y1);
0563: }
0564: double x0c = (x0 + xc) / 2;
0565: double y0c = (y0 + yc) / 2;
0566: double xc1 = (xc + x1) / 2;
0567: double yc1 = (yc + y1) / 2;
0568: xc = (x0c + xc1) / 2;
0569: yc = (y0c + yc1) / 2;
0570: if (Double.isNaN(xc) || Double.isNaN(yc)) {
0571: // [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN
0572: // [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN
0573: // These values are also NaN if opposing infinities are added
0574: return 0;
0575: }
0576: crossings = rectCrossingsForQuad(crossings, rxmin, rymin,
0577: rxmax, rymax, x0, y0, x0c, y0c, xc, yc, level + 1);
0578: if (crossings != RECT_INTERSECTS) {
0579: crossings = rectCrossingsForQuad(crossings, rxmin, rymin,
0580: rxmax, rymax, xc, yc, xc1, yc1, x1, y1, level + 1);
0581: }
0582: return crossings;
0583: }
0584:
0585: /**
0586: * Accumulate the number of times the cubic crosses the shadow
0587: * extending to the right of the rectangle. See the comment
0588: * for the RECT_INTERSECTS constant for more complete details.
0589: */
0590: public static int rectCrossingsForCubic(int crossings,
0591: double rxmin, double rymin, double rxmax, double rymax,
0592: double x0, double y0, double xc0, double yc0, double xc1,
0593: double yc1, double x1, double y1, int level) {
0594: if (y0 >= rymax && yc0 >= rymax && yc1 >= rymax && y1 >= rymax) {
0595: return crossings;
0596: }
0597: if (y0 <= rymin && yc0 <= rymin && yc1 <= rymin && y1 <= rymin) {
0598: return crossings;
0599: }
0600: if (x0 <= rxmin && xc0 <= rxmin && xc1 <= rxmin && x1 <= rxmin) {
0601: return crossings;
0602: }
0603: if (x0 >= rxmax && xc0 >= rxmax && xc1 >= rxmax && x1 >= rxmax) {
0604: // Cubic is entirely to the right of the rect
0605: // and the vertical range of the 4 Y coordinates of the cubic
0606: // overlaps the vertical range of the rect by a non-empty amount
0607: // We now judge the crossings solely based on the line segment
0608: // connecting the endpoints of the cubic.
0609: // Note that we may have 0, 1, or 2 crossings as the control
0610: // points may be causing the Y range intersection while the
0611: // two endpoints are entirely above or below.
0612: if (y0 < y1) {
0613: // y-increasing line segment...
0614: if (y0 <= rymin && y1 > rymin)
0615: crossings++;
0616: if (y0 < rymax && y1 >= rymax)
0617: crossings++;
0618: } else if (y1 < y0) {
0619: // y-decreasing line segment...
0620: if (y1 <= rymin && y0 > rymin)
0621: crossings--;
0622: if (y1 < rymax && y0 >= rymax)
0623: crossings--;
0624: }
0625: return crossings;
0626: }
0627: // The intersection of ranges is more complicated
0628: // First do trivial INTERSECTS rejection of the cases
0629: // where one of the endpoints is inside the rectangle.
0630: if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax)
0631: || (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) {
0632: return RECT_INTERSECTS;
0633: }
0634: // Otherwise, subdivide and look for one of the cases above.
0635: // double precision only has 52 bits of mantissa
0636: if (level > 52) {
0637: return rectCrossingsForLine(crossings, rxmin, rymin, rxmax,
0638: rymax, x0, y0, x1, y1);
0639: }
0640: double xmid = (xc0 + xc1) / 2;
0641: double ymid = (yc0 + yc1) / 2;
0642: xc0 = (x0 + xc0) / 2;
0643: yc0 = (y0 + yc0) / 2;
0644: xc1 = (xc1 + x1) / 2;
0645: yc1 = (yc1 + y1) / 2;
0646: double xc0m = (xc0 + xmid) / 2;
0647: double yc0m = (yc0 + ymid) / 2;
0648: double xmc1 = (xmid + xc1) / 2;
0649: double ymc1 = (ymid + yc1) / 2;
0650: xmid = (xc0m + xmc1) / 2;
0651: ymid = (yc0m + ymc1) / 2;
0652: if (Double.isNaN(xmid) || Double.isNaN(ymid)) {
0653: // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN
0654: // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN
0655: // These values are also NaN if opposing infinities are added
0656: return 0;
0657: }
0658: crossings = rectCrossingsForCubic(crossings, rxmin, rymin,
0659: rxmax, rymax, x0, y0, xc0, yc0, xc0m, yc0m, xmid, ymid,
0660: level + 1);
0661: if (crossings != RECT_INTERSECTS) {
0662: crossings = rectCrossingsForCubic(crossings, rxmin, rymin,
0663: rxmax, rymax, xmid, ymid, xmc1, ymc1, xc1, yc1, x1,
0664: y1, level + 1);
0665: }
0666: return crossings;
0667: }
0668:
0669: public Curve(int direction) {
0670: this .direction = direction;
0671: }
0672:
0673: public final int getDirection() {
0674: return direction;
0675: }
0676:
0677: public final Curve getWithDirection(int direction) {
0678: return (this .direction == direction ? this : getReversedCurve());
0679: }
0680:
0681: public static double round(double v) {
0682: //return Math.rint(v*10)/10;
0683: return v;
0684: }
0685:
0686: public static int orderof(double x1, double x2) {
0687: if (x1 < x2) {
0688: return -1;
0689: }
0690: if (x1 > x2) {
0691: return 1;
0692: }
0693: return 0;
0694: }
0695:
0696: public static long signeddiffbits(double y1, double y2) {
0697: return (Double.doubleToLongBits(y1) - Double
0698: .doubleToLongBits(y2));
0699: }
0700:
0701: public static long diffbits(double y1, double y2) {
0702: return Math.abs(Double.doubleToLongBits(y1)
0703: - Double.doubleToLongBits(y2));
0704: }
0705:
0706: public static double prev(double v) {
0707: return Double.longBitsToDouble(Double.doubleToLongBits(v) - 1);
0708: }
0709:
0710: public static double next(double v) {
0711: return Double.longBitsToDouble(Double.doubleToLongBits(v) + 1);
0712: }
0713:
0714: public String toString() {
0715: return ("Curve["
0716: + getOrder()
0717: + ", "
0718: + ("(" + round(getX0()) + ", " + round(getY0()) + "), ")
0719: + controlPointString()
0720: + ("(" + round(getX1()) + ", " + round(getY1()) + "), ")
0721: + (direction == INCREASING ? "D" : "U") + "]");
0722: }
0723:
0724: public String controlPointString() {
0725: return "";
0726: }
0727:
0728: public abstract int getOrder();
0729:
0730: public abstract double getXTop();
0731:
0732: public abstract double getYTop();
0733:
0734: public abstract double getXBot();
0735:
0736: public abstract double getYBot();
0737:
0738: public abstract double getXMin();
0739:
0740: public abstract double getXMax();
0741:
0742: public abstract double getX0();
0743:
0744: public abstract double getY0();
0745:
0746: public abstract double getX1();
0747:
0748: public abstract double getY1();
0749:
0750: public abstract double XforY(double y);
0751:
0752: public abstract double TforY(double y);
0753:
0754: public abstract double XforT(double t);
0755:
0756: public abstract double YforT(double t);
0757:
0758: public abstract double dXforT(double t, int deriv);
0759:
0760: public abstract double dYforT(double t, int deriv);
0761:
0762: public abstract double nextVertical(double t0, double t1);
0763:
0764: public int crossingsFor(double x, double y) {
0765: if (y >= getYTop() && y < getYBot()) {
0766: if (x < getXMax() && (x < getXMin() || x < XforY(y))) {
0767: return 1;
0768: }
0769: }
0770: return 0;
0771: }
0772:
0773: public boolean accumulateCrossings(Crossings c) {
0774: double xhi = c.getXHi();
0775: if (getXMin() >= xhi) {
0776: return false;
0777: }
0778: double xlo = c.getXLo();
0779: double ylo = c.getYLo();
0780: double yhi = c.getYHi();
0781: double y0 = getYTop();
0782: double y1 = getYBot();
0783: double tstart, ystart, tend, yend;
0784: if (y0 < ylo) {
0785: if (y1 <= ylo) {
0786: return false;
0787: }
0788: ystart = ylo;
0789: tstart = TforY(ylo);
0790: } else {
0791: if (y0 >= yhi) {
0792: return false;
0793: }
0794: ystart = y0;
0795: tstart = 0;
0796: }
0797: if (y1 > yhi) {
0798: yend = yhi;
0799: tend = TforY(yhi);
0800: } else {
0801: yend = y1;
0802: tend = 1;
0803: }
0804: boolean hitLo = false;
0805: boolean hitHi = false;
0806: while (true) {
0807: double x = XforT(tstart);
0808: if (x < xhi) {
0809: if (hitHi || x > xlo) {
0810: return true;
0811: }
0812: hitLo = true;
0813: } else {
0814: if (hitLo) {
0815: return true;
0816: }
0817: hitHi = true;
0818: }
0819: if (tstart >= tend) {
0820: break;
0821: }
0822: tstart = nextVertical(tstart, tend);
0823: }
0824: if (hitLo) {
0825: c.record(ystart, yend, direction);
0826: }
0827: return false;
0828: }
0829:
0830: public abstract void enlarge(Rectangle2D r);
0831:
0832: public Curve getSubCurve(double ystart, double yend) {
0833: return getSubCurve(ystart, yend, direction);
0834: }
0835:
0836: public abstract Curve getReversedCurve();
0837:
0838: public abstract Curve getSubCurve(double ystart, double yend,
0839: int dir);
0840:
0841: public int compareTo(Curve that, double yrange[]) {
0842: /*
0843: System.out.println(this+".compareTo("+that+")");
0844: System.out.println("target range = "+yrange[0]+"=>"+yrange[1]);
0845: */
0846: double y0 = yrange[0];
0847: double y1 = yrange[1];
0848: y1 = Math.min(Math.min(y1, this .getYBot()), that.getYBot());
0849: if (y1 <= yrange[0]) {
0850: System.err.println("this == " + this );
0851: System.err.println("that == " + that);
0852: System.out.println("target range = " + yrange[0] + "=>"
0853: + yrange[1]);
0854: throw new InternalError("backstepping from " + yrange[0]
0855: + " to " + y1);
0856: }
0857: yrange[1] = y1;
0858: if (this .getXMax() <= that.getXMin()) {
0859: if (this .getXMin() == that.getXMax()) {
0860: return 0;
0861: }
0862: return -1;
0863: }
0864: if (this .getXMin() >= that.getXMax()) {
0865: return 1;
0866: }
0867: // Parameter s for thi(s) curve and t for tha(t) curve
0868: // [st]0 = parameters for top of current section of interest
0869: // [st]1 = parameters for bottom of valid range
0870: // [st]h = parameters for hypothesis point
0871: // [d][xy]s = valuations of thi(s) curve at sh
0872: // [d][xy]t = valuations of tha(t) curve at th
0873: double s0 = this .TforY(y0);
0874: double ys0 = this .YforT(s0);
0875: if (ys0 < y0) {
0876: s0 = refineTforY(s0, ys0, y0);
0877: ys0 = this .YforT(s0);
0878: }
0879: double s1 = this .TforY(y1);
0880: if (this .YforT(s1) < y0) {
0881: s1 = refineTforY(s1, this .YforT(s1), y0);
0882: //System.out.println("s1 problem!");
0883: }
0884: double t0 = that.TforY(y0);
0885: double yt0 = that.YforT(t0);
0886: if (yt0 < y0) {
0887: t0 = that.refineTforY(t0, yt0, y0);
0888: yt0 = that.YforT(t0);
0889: }
0890: double t1 = that.TforY(y1);
0891: if (that.YforT(t1) < y0) {
0892: t1 = that.refineTforY(t1, that.YforT(t1), y0);
0893: //System.out.println("t1 problem!");
0894: }
0895: double xs0 = this .XforT(s0);
0896: double xt0 = that.XforT(t0);
0897: double scale = Math.max(Math.abs(y0), Math.abs(y1));
0898: double ymin = Math.max(scale * 1E-14, 1E-300);
0899: if (fairlyClose(xs0, xt0)) {
0900: double bump = ymin;
0901: double maxbump = Math.min(ymin * 1E13, (y1 - y0) * .1);
0902: double y = y0 + bump;
0903: while (y <= y1) {
0904: if (fairlyClose(this .XforY(y), that.XforY(y))) {
0905: if ((bump *= 2) > maxbump) {
0906: bump = maxbump;
0907: }
0908: } else {
0909: y -= bump;
0910: while (true) {
0911: bump /= 2;
0912: double newy = y + bump;
0913: if (newy <= y) {
0914: break;
0915: }
0916: if (fairlyClose(this .XforY(newy), that
0917: .XforY(newy))) {
0918: y = newy;
0919: }
0920: }
0921: break;
0922: }
0923: y += bump;
0924: }
0925: if (y > y0) {
0926: if (y < y1) {
0927: yrange[1] = y;
0928: }
0929: return 0;
0930: }
0931: }
0932: //double ymin = y1 * 1E-14;
0933: if (ymin <= 0) {
0934: System.out.println("ymin = " + ymin);
0935: }
0936: /*
0937: System.out.println("s range = "+s0+" to "+s1);
0938: System.out.println("t range = "+t0+" to "+t1);
0939: */
0940: while (s0 < s1 && t0 < t1) {
0941: double sh = this .nextVertical(s0, s1);
0942: double xsh = this .XforT(sh);
0943: double ysh = this .YforT(sh);
0944: double th = that.nextVertical(t0, t1);
0945: double xth = that.XforT(th);
0946: double yth = that.YforT(th);
0947: /*
0948: System.out.println("sh = "+sh);
0949: System.out.println("th = "+th);
0950: */
0951: try {
0952: if (findIntersect(that, yrange, ymin, 0, 0, s0, xs0,
0953: ys0, sh, xsh, ysh, t0, xt0, yt0, th, xth, yth)) {
0954: break;
0955: }
0956: } catch (Throwable t) {
0957: System.err.println("Error: " + t);
0958: System.err.println("y range was " + yrange[0] + "=>"
0959: + yrange[1]);
0960: System.err.println("s y range is " + ys0 + "=>" + ysh);
0961: System.err.println("t y range is " + yt0 + "=>" + yth);
0962: System.err.println("ymin is " + ymin);
0963: return 0;
0964: }
0965: if (ysh < yth) {
0966: if (ysh > yrange[0]) {
0967: if (ysh < yrange[1]) {
0968: yrange[1] = ysh;
0969: }
0970: break;
0971: }
0972: s0 = sh;
0973: xs0 = xsh;
0974: ys0 = ysh;
0975: } else {
0976: if (yth > yrange[0]) {
0977: if (yth < yrange[1]) {
0978: yrange[1] = yth;
0979: }
0980: break;
0981: }
0982: t0 = th;
0983: xt0 = xth;
0984: yt0 = yth;
0985: }
0986: }
0987: double ymid = (yrange[0] + yrange[1]) / 2;
0988: /*
0989: System.out.println("final this["+s0+", "+sh+", "+s1+"]");
0990: System.out.println("final y["+ys0+", "+ysh+"]");
0991: System.out.println("final that["+t0+", "+th+", "+t1+"]");
0992: System.out.println("final y["+yt0+", "+yth+"]");
0993: System.out.println("final order = "+orderof(this.XforY(ymid),
0994: that.XforY(ymid)));
0995: System.out.println("final range = "+yrange[0]+"=>"+yrange[1]);
0996: */
0997: /*
0998: System.out.println("final sx = "+this.XforY(ymid));
0999: System.out.println("final tx = "+that.XforY(ymid));
1000: System.out.println("final order = "+orderof(this.XforY(ymid),
1001: that.XforY(ymid)));
1002: */
1003: return orderof(this .XforY(ymid), that.XforY(ymid));
1004: }
1005:
1006: public static final double TMIN = 1E-3;
1007:
1008: public boolean findIntersect(Curve that, double yrange[],
1009: double ymin, int slevel, int tlevel, double s0, double xs0,
1010: double ys0, double s1, double xs1, double ys1, double t0,
1011: double xt0, double yt0, double t1, double xt1, double yt1) {
1012: /*
1013: String pad = " ";
1014: pad = pad+pad+pad+pad+pad;
1015: pad = pad+pad;
1016: System.out.println("----------------------------------------------");
1017: System.out.println(pad.substring(0, slevel)+ys0);
1018: System.out.println(pad.substring(0, slevel)+ys1);
1019: System.out.println(pad.substring(0, slevel)+(s1-s0));
1020: System.out.println("-------");
1021: System.out.println(pad.substring(0, tlevel)+yt0);
1022: System.out.println(pad.substring(0, tlevel)+yt1);
1023: System.out.println(pad.substring(0, tlevel)+(t1-t0));
1024: */
1025: if (ys0 > yt1 || yt0 > ys1) {
1026: return false;
1027: }
1028: if (Math.min(xs0, xs1) > Math.max(xt0, xt1)
1029: || Math.max(xs0, xs1) < Math.min(xt0, xt1)) {
1030: return false;
1031: }
1032: // Bounding boxes intersect - back off the larger of
1033: // the two subcurves by half until they stop intersecting
1034: // (or until they get small enough to switch to a more
1035: // intensive algorithm).
1036: if (s1 - s0 > TMIN) {
1037: double s = (s0 + s1) / 2;
1038: double xs = this .XforT(s);
1039: double ys = this .YforT(s);
1040: if (s == s0 || s == s1) {
1041: System.out.println("s0 = " + s0);
1042: System.out.println("s1 = " + s1);
1043: throw new InternalError("no s progress!");
1044: }
1045: if (t1 - t0 > TMIN) {
1046: double t = (t0 + t1) / 2;
1047: double xt = that.XforT(t);
1048: double yt = that.YforT(t);
1049: if (t == t0 || t == t1) {
1050: System.out.println("t0 = " + t0);
1051: System.out.println("t1 = " + t1);
1052: throw new InternalError("no t progress!");
1053: }
1054: if (ys >= yt0 && yt >= ys0) {
1055: if (findIntersect(that, yrange, ymin, slevel + 1,
1056: tlevel + 1, s0, xs0, ys0, s, xs, ys, t0,
1057: xt0, yt0, t, xt, yt)) {
1058: return true;
1059: }
1060: }
1061: if (ys >= yt) {
1062: if (findIntersect(that, yrange, ymin, slevel + 1,
1063: tlevel + 1, s0, xs0, ys0, s, xs, ys, t, xt,
1064: yt, t1, xt1, yt1)) {
1065: return true;
1066: }
1067: }
1068: if (yt >= ys) {
1069: if (findIntersect(that, yrange, ymin, slevel + 1,
1070: tlevel + 1, s, xs, ys, s1, xs1, ys1, t0,
1071: xt0, yt0, t, xt, yt)) {
1072: return true;
1073: }
1074: }
1075: if (ys1 >= yt && yt1 >= ys) {
1076: if (findIntersect(that, yrange, ymin, slevel + 1,
1077: tlevel + 1, s, xs, ys, s1, xs1, ys1, t, xt,
1078: yt, t1, xt1, yt1)) {
1079: return true;
1080: }
1081: }
1082: } else {
1083: if (ys >= yt0) {
1084: if (findIntersect(that, yrange, ymin, slevel + 1,
1085: tlevel, s0, xs0, ys0, s, xs, ys, t0, xt0,
1086: yt0, t1, xt1, yt1)) {
1087: return true;
1088: }
1089: }
1090: if (yt1 >= ys) {
1091: if (findIntersect(that, yrange, ymin, slevel + 1,
1092: tlevel, s, xs, ys, s1, xs1, ys1, t0, xt0,
1093: yt0, t1, xt1, yt1)) {
1094: return true;
1095: }
1096: }
1097: }
1098: } else if (t1 - t0 > TMIN) {
1099: double t = (t0 + t1) / 2;
1100: double xt = that.XforT(t);
1101: double yt = that.YforT(t);
1102: if (t == t0 || t == t1) {
1103: System.out.println("t0 = " + t0);
1104: System.out.println("t1 = " + t1);
1105: throw new InternalError("no t progress!");
1106: }
1107: if (yt >= ys0) {
1108: if (findIntersect(that, yrange, ymin, slevel,
1109: tlevel + 1, s0, xs0, ys0, s1, xs1, ys1, t0,
1110: xt0, yt0, t, xt, yt)) {
1111: return true;
1112: }
1113: }
1114: if (ys1 >= yt) {
1115: if (findIntersect(that, yrange, ymin, slevel,
1116: tlevel + 1, s0, xs0, ys0, s1, xs1, ys1, t, xt,
1117: yt, t1, xt1, yt1)) {
1118: return true;
1119: }
1120: }
1121: } else {
1122: // No more subdivisions
1123: double xlk = xs1 - xs0;
1124: double ylk = ys1 - ys0;
1125: double xnm = xt1 - xt0;
1126: double ynm = yt1 - yt0;
1127: double xmk = xt0 - xs0;
1128: double ymk = yt0 - ys0;
1129: double det = xnm * ylk - ynm * xlk;
1130: if (det != 0) {
1131: double detinv = 1 / det;
1132: double s = (xnm * ymk - ynm * xmk) * detinv;
1133: double t = (xlk * ymk - ylk * xmk) * detinv;
1134: if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
1135: s = s0 + s * (s1 - s0);
1136: t = t0 + t * (t1 - t0);
1137: if (s < 0 || s > 1 || t < 0 || t > 1) {
1138: System.out.println("Uh oh!");
1139: }
1140: double y = (this .YforT(s) + that.YforT(t)) / 2;
1141: if (y <= yrange[1] && y > yrange[0]) {
1142: yrange[1] = y;
1143: return true;
1144: }
1145: }
1146: }
1147: //System.out.println("Testing lines!");
1148: }
1149: return false;
1150: }
1151:
1152: public double refineTforY(double t0, double yt0, double y0) {
1153: double t1 = 1;
1154: while (true) {
1155: double th = (t0 + t1) / 2;
1156: if (th == t0 || th == t1) {
1157: return t1;
1158: }
1159: double y = YforT(th);
1160: if (y < y0) {
1161: t0 = th;
1162: yt0 = y;
1163: } else if (y > y0) {
1164: t1 = th;
1165: } else {
1166: return t1;
1167: }
1168: }
1169: }
1170:
1171: public boolean fairlyClose(double v1, double v2) {
1172: return (Math.abs(v1 - v2) < Math
1173: .max(Math.abs(v1), Math.abs(v2)) * 1E-10);
1174: }
1175:
1176: public abstract int getSegment(double coords[]);
1177: }
|