| /* | |
| * Copyright (c) 1998, 2023, Oracle and/or its affiliates. All rights reserved. | |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| * | |
| * This code is free software; you can redistribute it and/or modify it | |
| * under the terms of the GNU General Public License version 2 only, as | |
| * published by the Free Software Foundation. Oracle designates this | |
| * particular file as subject to the "Classpath" exception as provided | |
| * by Oracle in the LICENSE file that accompanied this code. | |
| * | |
| * This code is distributed in the hope that it will be useful, but WITHOUT | |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| * version 2 for more details (a copy is included in the LICENSE file that | |
| * accompanied this code). | |
| * | |
| * You should have received a copy of the GNU General Public License version | |
| * 2 along with this work; if not, write to the Free Software Foundation, | |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| * | |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| * or visit www.oracle.com if you need additional information or have any | |
| * questions. | |
| */ | |
| package sun.awt.geom; | |
| import java.awt.geom.Rectangle2D; | |
| import java.awt.geom.QuadCurve2D; | |
| import java.awt.geom.CubicCurve2D; | |
| import java.awt.geom.PathIterator; | |
| import java.awt.geom.IllegalPathStateException; | |
| import java.util.Vector; | |
| public abstract class Curve { | |
| public static final int INCREASING = 1; | |
| public static final int DECREASING = -1; | |
| protected int direction; | |
| public static void insertMove(Vector<Curve> curves, double x, double y) { | |
| curves.add(new Order0(x, y)); | |
| } | |
| public static void insertLine(Vector<Curve> curves, | |
| double x0, double y0, | |
| double x1, double y1) | |
| { | |
| if (y0 < y1) { | |
| curves.add(new Order1(x0, y0, | |
| x1, y1, | |
| INCREASING)); | |
| } else if (y0 > y1) { | |
| curves.add(new Order1(x1, y1, | |
| x0, y0, | |
| DECREASING)); | |
| } else { | |
| // Do not add horizontal lines | |
| } | |
| } | |
| public static void insertQuad(Vector<Curve> curves, | |
| double x0, double y0, | |
| double[] coords) | |
| { | |
| double y1 = coords[3]; | |
| if (y0 > y1) { | |
| Order2.insert(curves, coords, | |
| coords[2], y1, | |
| coords[0], coords[1], | |
| x0, y0, | |
| DECREASING); | |
| } else if (y0 == y1 && y0 == coords[1]) { | |
| // Do not add horizontal lines | |
| return; | |
| } else { | |
| Order2.insert(curves, coords, | |
| x0, y0, | |
| coords[0], coords[1], | |
| coords[2], y1, | |
| INCREASING); | |
| } | |
| } | |
| public static void insertCubic(Vector<Curve> curves, | |
| double x0, double y0, | |
| double[] coords) | |
| { | |
| double y1 = coords[5]; | |
| if (y0 > y1) { | |
| Order3.insert(curves, coords, | |
| coords[4], y1, | |
| coords[2], coords[3], | |
| coords[0], coords[1], | |
| x0, y0, | |
| DECREASING); | |
| } else if (y0 == y1 && y0 == coords[1] && y0 == coords[3]) { | |
| // Do not add horizontal lines | |
| return; | |
| } else { | |
| Order3.insert(curves, coords, | |
| x0, y0, | |
| coords[0], coords[1], | |
| coords[2], coords[3], | |
| coords[4], y1, | |
| INCREASING); | |
| } | |
| } | |
| /** | |
| * Calculates the number of times the given path | |
| * crosses the ray extending to the right from (px,py). | |
| * If the point lies on a part of the path, | |
| * then no crossings are counted for that intersection. | |
| * +1 is added for each crossing where the Y coordinate is increasing | |
| * -1 is added for each crossing where the Y coordinate is decreasing | |
| * The return value is the sum of all crossings for every segment in | |
| * the path. | |
| * The path must start with a SEG_MOVETO, otherwise an exception is | |
| * thrown. | |
| * The caller must check p[xy] for NaN values. | |
| * The caller may also reject infinite p[xy] values as well. | |
| */ | |
| public static int pointCrossingsForPath(PathIterator pi, | |
| double px, double py) | |
| { | |
| if (pi.isDone()) { | |
| return 0; | |
| } | |
| double[] coords = new double[6]; | |
| if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) { | |
| throw new IllegalPathStateException("missing initial moveto "+ | |
| "in path definition"); | |
| } | |
| pi.next(); | |
| double movx = coords[0]; | |
| double movy = coords[1]; | |
| double curx = movx; | |
| double cury = movy; | |
| double endx, endy; | |
| int crossings = 0; | |
| while (!pi.isDone()) { | |
| switch (pi.currentSegment(coords)) { | |
| case PathIterator.SEG_MOVETO: | |
| if (cury != movy) { | |
| crossings += pointCrossingsForLine(px, py, | |
| curx, cury, | |
| movx, movy); | |
| } | |
| movx = curx = coords[0]; | |
| movy = cury = coords[1]; | |
| break; | |
| case PathIterator.SEG_LINETO: | |
| endx = coords[0]; | |
| endy = coords[1]; | |
| crossings += pointCrossingsForLine(px, py, | |
| curx, cury, | |
| endx, endy); | |
| curx = endx; | |
| cury = endy; | |
| break; | |
| case PathIterator.SEG_QUADTO: | |
| endx = coords[2]; | |
| endy = coords[3]; | |
| crossings += pointCrossingsForQuad(px, py, | |
| curx, cury, | |
| coords[0], coords[1], | |
| endx, endy, 0); | |
| curx = endx; | |
| cury = endy; | |
| break; | |
| case PathIterator.SEG_CUBICTO: | |
| endx = coords[4]; | |
| endy = coords[5]; | |
| crossings += pointCrossingsForCubic(px, py, | |
| curx, cury, | |
| coords[0], coords[1], | |
| coords[2], coords[3], | |
| endx, endy, 0); | |
| curx = endx; | |
| cury = endy; | |
| break; | |
| case PathIterator.SEG_CLOSE: | |
| if (cury != movy) { | |
| crossings += pointCrossingsForLine(px, py, | |
| curx, cury, | |
| movx, movy); | |
| } | |
| curx = movx; | |
| cury = movy; | |
| break; | |
| } | |
| pi.next(); | |
| } | |
| if (cury != movy) { | |
| crossings += pointCrossingsForLine(px, py, | |
| curx, cury, | |
| movx, movy); | |
| } | |
| return crossings; | |
| } | |
| /** | |
| * Calculates the number of times the line from (x0,y0) to (x1,y1) | |
| * crosses the ray extending to the right from (px,py). | |
| * If the point lies on the line, then no crossings are recorded. | |
| * +1 is returned for a crossing where the Y coordinate is increasing | |
| * -1 is returned for a crossing where the Y coordinate is decreasing | |
| */ | |
| public static int pointCrossingsForLine(double px, double py, | |
| double x0, double y0, | |
| double x1, double y1) | |
| { | |
| if (py < y0 && py < y1) return 0; | |
| if (py >= y0 && py >= y1) return 0; | |
| // assert(y0 != y1); | |
| if (px >= x0 && px >= x1) return 0; | |
| if (px < x0 && px < x1) return (y0 < y1) ? 1 : -1; | |
| double xintercept = x0 + (py - y0) * (x1 - x0) / (y1 - y0); | |
| if (px >= xintercept) return 0; | |
| return (y0 < y1) ? 1 : -1; | |
| } | |
| /** | |
| * Calculates the number of times the quad from (x0,y0) to (x1,y1) | |
| * crosses the ray extending to the right from (px,py). | |
| * If the point lies on a part of the curve, | |
| * then no crossings are counted for that intersection. | |
| * the level parameter should be 0 at the top-level call and will count | |
| * up for each recursion level to prevent infinite recursion | |
| * +1 is added for each crossing where the Y coordinate is increasing | |
| * -1 is added for each crossing where the Y coordinate is decreasing | |
| */ | |
| public static int pointCrossingsForQuad(double px, double py, | |
| double x0, double y0, | |
| double xc, double yc, | |
| double x1, double y1, int level) | |
| { | |
| if (py < y0 && py < yc && py < y1) return 0; | |
| if (py >= y0 && py >= yc && py >= y1) return 0; | |
| // Note y0 could equal y1... | |
| if (px >= x0 && px >= xc && px >= x1) return 0; | |
| if (px < x0 && px < xc && px < x1) { | |
| if (py >= y0) { | |
| if (py < y1) return 1; | |
| } else { | |
| // py < y0 | |
| if (py >= y1) return -1; | |
| } | |
| // py outside of y01 range, and/or y0==y1 | |
| return 0; | |
| } | |
| // double precision only has 52 bits of mantissa | |
| if (level > 52) return pointCrossingsForLine(px, py, x0, y0, x1, y1); | |
| double x0c = (x0 + xc) / 2; | |
| double y0c = (y0 + yc) / 2; | |
| double xc1 = (xc + x1) / 2; | |
| double yc1 = (yc + y1) / 2; | |
| xc = (x0c + xc1) / 2; | |
| yc = (y0c + yc1) / 2; | |
| if (Double.isNaN(xc) || Double.isNaN(yc)) { | |
| // [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN | |
| // [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN | |
| // These values are also NaN if opposing infinities are added | |
| return 0; | |
| } | |
| return (pointCrossingsForQuad(px, py, | |
| x0, y0, x0c, y0c, xc, yc, | |
| level+1) + | |
| pointCrossingsForQuad(px, py, | |
| xc, yc, xc1, yc1, x1, y1, | |
| level+1)); | |
| } | |
| /** | |
| * Calculates the number of times the cubic from (x0,y0) to (x1,y1) | |
| * crosses the ray extending to the right from (px,py). | |
| * If the point lies on a part of the curve, | |
| * then no crossings are counted for that intersection. | |
| * the level parameter should be 0 at the top-level call and will count | |
| * up for each recursion level to prevent infinite recursion | |
| * +1 is added for each crossing where the Y coordinate is increasing | |
| * -1 is added for each crossing where the Y coordinate is decreasing | |
| */ | |
| public static int pointCrossingsForCubic(double px, double py, | |
| double x0, double y0, | |
| double xc0, double yc0, | |
| double xc1, double yc1, | |
| double x1, double y1, int level) | |
| { | |
| if (py < y0 && py < yc0 && py < yc1 && py < y1) return 0; | |
| if (py >= y0 && py >= yc0 && py >= yc1 && py >= y1) return 0; | |
| // Note y0 could equal yc0... | |
| if (px >= x0 && px >= xc0 && px >= xc1 && px >= x1) return 0; | |
| if (px < x0 && px < xc0 && px < xc1 && px < x1) { | |
| if (py >= y0) { | |
| if (py < y1) return 1; | |
| } else { | |
| // py < y0 | |
| if (py >= y1) return -1; | |
| } | |
| // py outside of y01 range, and/or y0==yc0 | |
| return 0; | |
| } | |
| // double precision only has 52 bits of mantissa | |
| if (level > 52) return pointCrossingsForLine(px, py, x0, y0, x1, y1); | |
| double xmid = (xc0 + xc1) / 2; | |
| double ymid = (yc0 + yc1) / 2; | |
| xc0 = (x0 + xc0) / 2; | |
| yc0 = (y0 + yc0) / 2; | |
| xc1 = (xc1 + x1) / 2; | |
| yc1 = (yc1 + y1) / 2; | |
| double xc0m = (xc0 + xmid) / 2; | |
| double yc0m = (yc0 + ymid) / 2; | |
| double xmc1 = (xmid + xc1) / 2; | |
| double ymc1 = (ymid + yc1) / 2; | |
| xmid = (xc0m + xmc1) / 2; | |
| ymid = (yc0m + ymc1) / 2; | |
| if (Double.isNaN(xmid) || Double.isNaN(ymid)) { | |
| // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN | |
| // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN | |
| // These values are also NaN if opposing infinities are added | |
| return 0; | |
| } | |
| return (pointCrossingsForCubic(px, py, | |
| x0, y0, xc0, yc0, | |
| xc0m, yc0m, xmid, ymid, level+1) + | |
| pointCrossingsForCubic(px, py, | |
| xmid, ymid, xmc1, ymc1, | |
| xc1, yc1, x1, y1, level+1)); | |
| } | |
| /** | |
| * The rectangle intersection test counts the number of times | |
| * that the path crosses through the shadow that the rectangle | |
| * projects to the right towards (x => +INFINITY). | |
| * | |
| * During processing of the path it actually counts every time | |
| * the path crosses either or both of the top and bottom edges | |
| * of that shadow. If the path enters from the top, the count | |
| * is incremented. If it then exits back through the top, the | |
| * same way it came in, the count is decremented and there is | |
| * no impact on the winding count. If, instead, the path exits | |
| * out the bottom, then the count is incremented again and a | |
| * full pass through the shadow is indicated by the winding count | |
| * having been incremented by 2. | |
| * | |
| * Thus, the winding count that it accumulates is actually double | |
| * the real winding count. Since the path is continuous, the | |
| * final answer should be a multiple of 2, otherwise there is a | |
| * logic error somewhere. | |
| * | |
| * If the path ever has a direct hit on the rectangle, then a | |
| * special value is returned. This special value terminates | |
| * all ongoing accumulation on up through the call chain and | |
| * ends up getting returned to the calling function which can | |
| * then produce an answer directly. For intersection tests, | |
| * the answer is always "true" if the path intersects the | |
| * rectangle. For containment tests, the answer is always | |
| * "false" if the path intersects the rectangle. Thus, no | |
| * further processing is ever needed if an intersection occurs. | |
| */ | |
| public static final int RECT_INTERSECTS = 0x80000000; | |
| /** | |
| * Accumulate the number of times the path crosses the shadow | |
| * extending to the right of the rectangle. See the comment | |
| * for the RECT_INTERSECTS constant for more complete details. | |
| * The return value is the sum of all crossings for both the | |
| * top and bottom of the shadow for every segment in the path, | |
| * or the special value RECT_INTERSECTS if the path ever enters | |
| * the interior of the rectangle. | |
| * The path must start with a SEG_MOVETO, otherwise an exception is | |
| * thrown. | |
| * The caller must check r[xy]{min,max} for NaN values. | |
| */ | |
| public static int rectCrossingsForPath(PathIterator pi, | |
| double rxmin, double rymin, | |
| double rxmax, double rymax) | |
| { | |
| if (rxmax <= rxmin || rymax <= rymin) { | |
| return 0; | |
| } | |
| if (pi.isDone()) { | |
| return 0; | |
| } | |
| double[] coords = new double[6]; | |
| if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) { | |
| throw new IllegalPathStateException("missing initial moveto "+ | |
| "in path definition"); | |
| } | |
| pi.next(); | |
| double curx, cury, movx, movy, endx, endy; | |
| curx = movx = coords[0]; | |
| cury = movy = coords[1]; | |
| int crossings = 0; | |
| while (crossings != RECT_INTERSECTS && !pi.isDone()) { | |
| switch (pi.currentSegment(coords)) { | |
| case PathIterator.SEG_MOVETO: | |
| if (curx != movx || cury != movy) { | |
| crossings = rectCrossingsForLine(crossings, | |
| rxmin, rymin, | |
| rxmax, rymax, | |
| curx, cury, | |
| movx, movy); | |
| } | |
| // Count should always be a multiple of 2 here. | |
| // assert((crossings & 1) != 0); | |
| movx = curx = coords[0]; | |
| movy = cury = coords[1]; | |
| break; | |
| case PathIterator.SEG_LINETO: | |
| endx = coords[0]; | |
| endy = coords[1]; | |
| crossings = rectCrossingsForLine(crossings, | |
| rxmin, rymin, | |
| rxmax, rymax, | |
| curx, cury, | |
| endx, endy); | |
| curx = endx; | |
| cury = endy; | |
| break; | |
| case PathIterator.SEG_QUADTO: | |
| endx = coords[2]; | |
| endy = coords[3]; | |
| crossings = rectCrossingsForQuad(crossings, | |
| rxmin, rymin, | |
| rxmax, rymax, | |
| curx, cury, | |
| coords[0], coords[1], | |
| endx, endy, 0); | |
| curx = endx; | |
| cury = endy; | |
| break; | |
| case PathIterator.SEG_CUBICTO: | |
| endx = coords[4]; | |
| endy = coords[5]; | |
| crossings = rectCrossingsForCubic(crossings, | |
| rxmin, rymin, | |
| rxmax, rymax, | |
| curx, cury, | |
| coords[0], coords[1], | |
| coords[2], coords[3], | |
| endx, endy, 0); | |
| curx = endx; | |
| cury = endy; | |
| break; | |
| case PathIterator.SEG_CLOSE: | |
| if (curx != movx || cury != movy) { | |
| crossings = rectCrossingsForLine(crossings, | |
| rxmin, rymin, | |
| rxmax, rymax, | |
| curx, cury, | |
| movx, movy); | |
| } | |
| curx = movx; | |
| cury = movy; | |
| // Count should always be a multiple of 2 here. | |
| // assert((crossings & 1) != 0); | |
| break; | |
| } | |
| pi.next(); | |
| } | |
| if (crossings != RECT_INTERSECTS && (curx != movx || cury != movy)) { | |
| crossings = rectCrossingsForLine(crossings, | |
| rxmin, rymin, | |
| rxmax, rymax, | |
| curx, cury, | |
| movx, movy); | |
| } | |
| // Count should always be a multiple of 2 here. | |
| // assert((crossings & 1) != 0); | |
| return crossings; | |
| } | |
| /** | |
| * Accumulate the number of times the line crosses the shadow | |
| * extending to the right of the rectangle. See the comment | |
| * for the RECT_INTERSECTS constant for more complete details. | |
| */ | |
| public static int rectCrossingsForLine(int crossings, | |
| double rxmin, double rymin, | |
| double rxmax, double rymax, | |
| double x0, double y0, | |
| double x1, double y1) | |
| { | |
| if (y0 >= rymax && y1 >= rymax) return crossings; | |
| if (y0 <= rymin && y1 <= rymin) return crossings; | |
| if (x0 <= rxmin && x1 <= rxmin) return crossings; | |
| if (x0 >= rxmax && x1 >= rxmax) { | |
| // Line is entirely to the right of the rect | |
| // and the vertical ranges of the two overlap by a non-empty amount | |
| // Thus, this line segment is partially in the "right-shadow" | |
| // Path may have done a complete crossing | |
| // Or path may have entered or exited the right-shadow | |
| if (y0 < y1) { | |
| // y-increasing line segment... | |
| // We know that y0 < rymax and y1 > rymin | |
| if (y0 <= rymin) crossings++; | |
| if (y1 >= rymax) crossings++; | |
| } else if (y1 < y0) { | |
| // y-decreasing line segment... | |
| // We know that y1 < rymax and y0 > rymin | |
| if (y1 <= rymin) crossings--; | |
| if (y0 >= rymax) crossings--; | |
| } | |
| return crossings; | |
| } | |
| // Remaining case: | |
| // Both x and y ranges overlap by a non-empty amount | |
| // First do trivial INTERSECTS rejection of the cases | |
| // where one of the endpoints is inside the rectangle. | |
| if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) || | |
| (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) | |
| { | |
| return RECT_INTERSECTS; | |
| } | |
| // Otherwise calculate the y intercepts and see where | |
| // they fall with respect to the rectangle | |
| double xi0 = x0; | |
| if (y0 < rymin) { | |
| xi0 += ((rymin - y0) * (x1 - x0) / (y1 - y0)); | |
| } else if (y0 > rymax) { | |
| xi0 += ((rymax - y0) * (x1 - x0) / (y1 - y0)); | |
| } | |
| double xi1 = x1; | |
| if (y1 < rymin) { | |
| xi1 += ((rymin - y1) * (x0 - x1) / (y0 - y1)); | |
| } else if (y1 > rymax) { | |
| xi1 += ((rymax - y1) * (x0 - x1) / (y0 - y1)); | |
| } | |
| if (xi0 <= rxmin && xi1 <= rxmin) return crossings; | |
| if (xi0 >= rxmax && xi1 >= rxmax) { | |
| if (y0 < y1) { | |
| // y-increasing line segment... | |
| // We know that y0 < rymax and y1 > rymin | |
| if (y0 <= rymin) crossings++; | |
| if (y1 >= rymax) crossings++; | |
| } else if (y1 < y0) { | |
| // y-decreasing line segment... | |
| // We know that y1 < rymax and y0 > rymin | |
| if (y1 <= rymin) crossings--; | |
| if (y0 >= rymax) crossings--; | |
| } | |
| return crossings; | |
| } | |
| return RECT_INTERSECTS; | |
| } | |
| /** | |
| * Accumulate the number of times the quad crosses the shadow | |
| * extending to the right of the rectangle. See the comment | |
| * for the RECT_INTERSECTS constant for more complete details. | |
| */ | |
| public static int rectCrossingsForQuad(int crossings, | |
| double rxmin, double rymin, | |
| double rxmax, double rymax, | |
| double x0, double y0, | |
| double xc, double yc, | |
| double x1, double y1, | |
| int level) | |
| { | |
| if (y0 >= rymax && yc >= rymax && y1 >= rymax) return crossings; | |
| if (y0 <= rymin && yc <= rymin && y1 <= rymin) return crossings; | |
| if (x0 <= rxmin && xc <= rxmin && x1 <= rxmin) return crossings; | |
| if (x0 >= rxmax && xc >= rxmax && x1 >= rxmax) { | |
| // Quad is entirely to the right of the rect | |
| // and the vertical range of the 3 Y coordinates of the quad | |
| // overlaps the vertical range of the rect by a non-empty amount | |
| // We now judge the crossings solely based on the line segment | |
| // connecting the endpoints of the quad. | |
| // Note that we may have 0, 1, or 2 crossings as the control | |
| // point may be causing the Y range intersection while the | |
| // two endpoints are entirely above or below. | |
| if (y0 < y1) { | |
| // y-increasing line segment... | |
| if (y0 <= rymin && y1 > rymin) crossings++; | |
| if (y0 < rymax && y1 >= rymax) crossings++; | |
| } else if (y1 < y0) { | |
| // y-decreasing line segment... | |
| if (y1 <= rymin && y0 > rymin) crossings--; | |
| if (y1 < rymax && y0 >= rymax) crossings--; | |
| } | |
| return crossings; | |
| } | |
| // The intersection of ranges is more complicated | |
| // First do trivial INTERSECTS rejection of the cases | |
| // where one of the endpoints is inside the rectangle. | |
| if ((x0 < rxmax && x0 > rxmin && y0 < rymax && y0 > rymin) || | |
| (x1 < rxmax && x1 > rxmin && y1 < rymax && y1 > rymin)) | |
| { | |
| return RECT_INTERSECTS; | |
| } | |
| // Otherwise, subdivide and look for one of the cases above. | |
| // double precision only has 52 bits of mantissa | |
| if (level > 52) { | |
| return rectCrossingsForLine(crossings, | |
| rxmin, rymin, rxmax, rymax, | |
| x0, y0, x1, y1); | |
| } | |
| double x0c = (x0 + xc) / 2; | |
| double y0c = (y0 + yc) / 2; | |
| double xc1 = (xc + x1) / 2; | |
| double yc1 = (yc + y1) / 2; | |
| xc = (x0c + xc1) / 2; | |
| yc = (y0c + yc1) / 2; | |
| if (Double.isNaN(xc) || Double.isNaN(yc)) { | |
| // [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN | |
| // [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN | |
| // These values are also NaN if opposing infinities are added | |
| return 0; | |
| } | |
| crossings = rectCrossingsForQuad(crossings, | |
| rxmin, rymin, rxmax, rymax, | |
| x0, y0, x0c, y0c, xc, yc, | |
| level+1); | |
| if (crossings != RECT_INTERSECTS) { | |
| crossings = rectCrossingsForQuad(crossings, | |
| rxmin, rymin, rxmax, rymax, | |
| xc, yc, xc1, yc1, x1, y1, | |
| level+1); | |
| } | |
| return crossings; | |
| } | |
| /** | |
| * Accumulate the number of times the cubic crosses the shadow | |
| * extending to the right of the rectangle. See the comment | |
| * for the RECT_INTERSECTS constant for more complete details. | |
| */ | |
| public static int rectCrossingsForCubic(int crossings, | |
| double rxmin, double rymin, | |
| double rxmax, double rymax, | |
| double x0, double y0, | |
| double xc0, double yc0, | |
| double xc1, double yc1, | |
| double x1, double y1, | |
| int level) | |
| { | |
| if (y0 >= rymax && yc0 >= rymax && yc1 >= rymax && y1 >= rymax) { | |
| return crossings; | |
| } | |
| if (y0 <= rymin && yc0 <= rymin && yc1 <= rymin && y1 <= rymin) { | |
| return crossings; | |
| } | |
| if (x0 <= rxmin && xc0 <= rxmin && xc1 <= rxmin && x1 <= rxmin) { | |
| return crossings; | |
| } | |
| if (x0 >= rxmax && xc0 >= rxmax && xc1 >= rxmax && x1 >= rxmax) { | |
| // Cubic is entirely to the right of the rect | |
| // and the vertical range of the 4 Y coordinates of the cubic | |
| // overlaps the vertical range of the rect by a non-empty amount | |
| // We now judge the crossings solely based on the line segment | |
| // connecting the endpoints of the cubic. | |
| // Note that we may have 0, 1, or 2 crossings as the control | |
| // points may be causing the Y range intersection while the | |
| // two endpoints are entirely above or below. | |
| if (y0 < y1) { | |
| // y-increasing line segment... | |
| if (y0 <= rymin && y1 > rymin) crossings++; | |
| if (y0 < rymax && y1 >= rymax) crossings++; | |
| } else if (y1 < y0) { | |
| // y-decreasing line segment... | |
| if (y1 <= rymin && y0 > rymin) crossings--; | |
| if (y1 < rymax && y0 >= rymax) crossings--; | |
| } | |
| return crossings; | |
| } | |
| // The intersection of ranges is more complicated | |
| // First do trivial INTERSECTS rejection of the cases | |
| // where one of the endpoints is inside the rectangle. | |
| if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) || | |
| (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) | |
| { | |
| return RECT_INTERSECTS; | |
| } | |
| // Otherwise, subdivide and look for one of the cases above. | |
| // double precision only has 52 bits of mantissa | |
| if (level > 52) { | |
| return rectCrossingsForLine(crossings, | |
| rxmin, rymin, rxmax, rymax, | |
| x0, y0, x1, y1); | |
| } | |
| double xmid = (xc0 + xc1) / 2; | |
| double ymid = (yc0 + yc1) / 2; | |
| xc0 = (x0 + xc0) / 2; | |
| yc0 = (y0 + yc0) / 2; | |
| xc1 = (xc1 + x1) / 2; | |
| yc1 = (yc1 + y1) / 2; | |
| double xc0m = (xc0 + xmid) / 2; | |
| double yc0m = (yc0 + ymid) / 2; | |
| double xmc1 = (xmid + xc1) / 2; | |
| double ymc1 = (ymid + yc1) / 2; | |
| xmid = (xc0m + xmc1) / 2; | |
| ymid = (yc0m + ymc1) / 2; | |
| if (Double.isNaN(xmid) || Double.isNaN(ymid)) { | |
| // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN | |
| // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN | |
| // These values are also NaN if opposing infinities are added | |
| return 0; | |
| } | |
| crossings = rectCrossingsForCubic(crossings, | |
| rxmin, rymin, rxmax, rymax, | |
| x0, y0, xc0, yc0, | |
| xc0m, yc0m, xmid, ymid, level+1); | |
| if (crossings != RECT_INTERSECTS) { | |
| crossings = rectCrossingsForCubic(crossings, | |
| rxmin, rymin, rxmax, rymax, | |
| xmid, ymid, xmc1, ymc1, | |
| xc1, yc1, x1, y1, level+1); | |
| } | |
| return crossings; | |
| } | |
| /** | |
| * Accumulate the quadratic extrema into the pre-existing bounding array. | |
| * <p> | |
| * This method focuses on one dimension at a time, so to get both the x and y | |
| * dimensions you'll need to call this method twice. | |
| * </p> | |
| * <p> | |
| * Whenever we have to examine cubic or quadratic extrema that change our bounding | |
| * box: we run the risk of machine error that may produce a box that is slightly | |
| * too small. But the contract of {@link Shape#getBounds2D()} says we should err | |
| * on the side of being too large. So to address this: we'll apply a margin based | |
| * on the upper limit of numerical error caused by the polynomial evaluation (horner | |
| * scheme). | |
| * </p> | |
| * | |
| * @param bounds the bounds to update, which are expressed as: { minX, maxX } | |
| * @param boundsOffset the index in boundsof the minimum value | |
| * @param x1 the starting value of the bezier curve where t = 0.0 | |
| * @param ctrlX the control value of the bezier curve | |
| * @param x2 the ending value of the bezier curve where t = 1.0 | |
| * @param coeff an array of at least 3 elements that will be overwritten and reused | |
| * @param deriv_coeff an array of at least 2 elements that will be overwritten and reused | |
| */ | |
| public static void accumulateExtremaBoundsForQuad(double[] bounds, int boundsOffset, double x1, double ctrlX, double x2, double[] coeff, double[] deriv_coeff) { | |
| if (ctrlX < bounds[boundsOffset] || | |
| ctrlX > bounds[boundsOffset + 1]) { | |
| final double dx21 = ctrlX - x1; | |
| coeff[2] = (x2 - ctrlX) - dx21; // A = P3 - P0 - 2 P2 | |
| coeff[1] = 2.0 * dx21; // B = 2 (P2 - P1) | |
| coeff[0] = x1; // C = P1 | |
| deriv_coeff[0] = coeff[1]; | |
| deriv_coeff[1] = 2.0 * coeff[2]; | |
| final double t = -deriv_coeff[0] / deriv_coeff[1]; | |
| if (t > 0.0 && t < 1.0) { | |
| final double v = coeff[0] + t * (coeff[1] + t * coeff[2]); | |
| // error condition = sum ( abs (coeff) ): | |
| final double margin = Math.ulp(Math.abs(coeff[0]) | |
| + Math.abs(coeff[1]) + Math.abs(coeff[2])); | |
| if (v - margin < bounds[boundsOffset]) { | |
| bounds[boundsOffset] = v - margin; | |
| } | |
| if (v + margin > bounds[boundsOffset + 1]) { | |
| bounds[boundsOffset + 1] = v + margin; | |
| } | |
| } | |
| } | |
| } | |
| /** | |
| * Accumulate the cubic extrema into the pre-existing bounding array. | |
| * <p> | |
| * This method focuses on one dimension at a time, so to get both the x and y | |
| * dimensions you'll need to call this method twice. | |
| * </p> | |
| * <p> | |
| * Whenever we have to examine cubic or quadratic extrema that change our bounding | |
| * box: we run the risk of machine error that may produce a box that is slightly | |
| * too small. But the contract of {@link Shape#getBounds2D()} says we should err | |
| * on the side of being too large. So to address this: we'll apply a margin based | |
| * on the upper limit of numerical error caused by the polynomial evaluation (horner | |
| * scheme). | |
| * </p> | |
| * | |
| * @param bounds the bounds to update, which are expressed as: { minX, maxX } | |
| * @param boundsOffset the index in boundsof the minimum value | |
| * @param x1 the starting value of the bezier curve where t = 0.0 | |
| * @param ctrlX1 the first control value of the bezier curve | |
| * @param ctrlX2 the second control value of the bezier curve | |
| * @param x2 the ending value of the bezier curve where t = 1.0 | |
| * @param coeff an array of at least 3 elements that will be overwritten and reused | |
| * @param deriv_coeff an array of at least 2 elements that will be overwritten and reused | |
| */ | |
| public static void accumulateExtremaBoundsForCubic(double[] bounds, int boundsOffset, double x1, double ctrlX1, double ctrlX2, double x2, double[] coeff, double[] deriv_coeff) { | |
| if (ctrlX1 < bounds[boundsOffset] || | |
| ctrlX1 > bounds[boundsOffset + 1] || | |
| ctrlX2 < bounds[boundsOffset] || | |
| ctrlX2 > bounds[boundsOffset + 1]) { | |
| final double dx32 = 3.0 * (ctrlX2 - ctrlX1); | |
| final double dx21 = 3.0 * (ctrlX1 - x1); | |
| coeff[3] = (x2 - x1) - dx32; // A = P3 - P0 - 3 (P2 - P1) = (P3 - P0) + 3 (P1 - P2) | |
| coeff[2] = (dx32 - dx21); // B = 3 (P2 - P1) - 3(P1 - P0) = 3 (P2 + P0) - 6 P1 | |
| coeff[1] = dx21; // C = 3 (P1 - P0) | |
| coeff[0] = x1; // D = P0 | |
| deriv_coeff[0] = coeff[1]; | |
| deriv_coeff[1] = 2.0 * coeff[2]; | |
| deriv_coeff[2] = 3.0 * coeff[3]; | |
| // reuse this array, give it a new name for readability: | |
| final double[] tExtrema = deriv_coeff; | |
| // solveQuadratic should be improved to get correct t extrema (1 ulp): | |
| final int tExtremaCount = QuadCurve2D.solveQuadratic(deriv_coeff, tExtrema); | |
| if (tExtremaCount > 0) { | |
| // error condition = sum ( abs (coeff) ): | |
| final double margin = Math.ulp(Math.abs(coeff[0]) | |
| + Math.abs(coeff[1]) + Math.abs(coeff[2]) | |
| + Math.abs(coeff[3])); | |
| for (int i = 0; i < tExtremaCount; i++) { | |
| final double t = tExtrema[i]; | |
| if (t > 0.0 && t < 1.0) { | |
| final double v = coeff[0] + t * (coeff[1] + t * (coeff[2] + t * coeff[3])); | |
| if (v - margin < bounds[boundsOffset]) { | |
| bounds[boundsOffset] = v - margin; | |
| } | |
| if (v + margin > bounds[boundsOffset + 1]) { | |
| bounds[boundsOffset + 1] = v + margin; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| public Curve(int direction) { | |
| this.direction = direction; | |
| } | |
| public final int getDirection() { | |
| return direction; | |
| } | |
| public final Curve getWithDirection(int direction) { | |
| return (this.direction == direction ? this : getReversedCurve()); | |
| } | |
| public static double round(double v) { | |
| //return Math.rint(v*10)/10; | |
| return v; | |
| } | |
| public static int orderof(double x1, double x2) { | |
| if (x1 < x2) { | |
| return -1; | |
| } | |
| if (x1 > x2) { | |
| return 1; | |
| } | |
| return 0; | |
| } | |
| public static long signeddiffbits(double y1, double y2) { | |
| return (Double.doubleToLongBits(y1) - Double.doubleToLongBits(y2)); | |
| } | |
| public static long diffbits(double y1, double y2) { | |
| return Math.abs(Double.doubleToLongBits(y1) - | |
| Double.doubleToLongBits(y2)); | |
| } | |
| public static double prev(double v) { | |
| return Double.longBitsToDouble(Double.doubleToLongBits(v)-1); | |
| } | |
| public static double next(double v) { | |
| return Double.longBitsToDouble(Double.doubleToLongBits(v)+1); | |
| } | |
| public String toString() { | |
| return ("Curve["+ | |
| getOrder()+", "+ | |
| ("("+round(getX0())+", "+round(getY0())+"), ")+ | |
| controlPointString()+ | |
| ("("+round(getX1())+", "+round(getY1())+"), ")+ | |
| (direction == INCREASING ? "D" : "U")+ | |
| "]"); | |
| } | |
| public String controlPointString() { | |
| return ""; | |
| } | |
| public abstract int getOrder(); | |
| public abstract double getXTop(); | |
| public abstract double getYTop(); | |
| public abstract double getXBot(); | |
| public abstract double getYBot(); | |
| public abstract double getXMin(); | |
| public abstract double getXMax(); | |
| public abstract double getX0(); | |
| public abstract double getY0(); | |
| public abstract double getX1(); | |
| public abstract double getY1(); | |
| public abstract double XforY(double y); | |
| public abstract double TforY(double y); | |
| public abstract double XforT(double t); | |
| public abstract double YforT(double t); | |
| public abstract double dXforT(double t, int deriv); | |
| public abstract double dYforT(double t, int deriv); | |
| public abstract double nextVertical(double t0, double t1); | |
| public int crossingsFor(double x, double y) { | |
| if (y >= getYTop() && y < getYBot()) { | |
| if (x < getXMax() && (x < getXMin() || x < XforY(y))) { | |
| return 1; | |
| } | |
| } | |
| return 0; | |
| } | |
| public boolean accumulateCrossings(Crossings c) { | |
| double xhi = c.getXHi(); | |
| if (getXMin() >= xhi) { | |
| return false; | |
| } | |
| double xlo = c.getXLo(); | |
| double ylo = c.getYLo(); | |
| double yhi = c.getYHi(); | |
| double y0 = getYTop(); | |
| double y1 = getYBot(); | |
| double tstart, ystart, tend, yend; | |
| if (y0 < ylo) { | |
| if (y1 <= ylo) { | |
| return false; | |
| } | |
| ystart = ylo; | |
| tstart = TforY(ylo); | |
| } else { | |
| if (y0 >= yhi) { | |
| return false; | |
| } | |
| ystart = y0; | |
| tstart = 0; | |
| } | |
| if (y1 > yhi) { | |
| yend = yhi; | |
| tend = TforY(yhi); | |
| } else { | |
| yend = y1; | |
| tend = 1; | |
| } | |
| boolean hitLo = false; | |
| boolean hitHi = false; | |
| while (true) { | |
| double x = XforT(tstart); | |
| if (x < xhi) { | |
| if (hitHi || x > xlo) { | |
| return true; | |
| } | |
| hitLo = true; | |
| } else { | |
| if (hitLo) { | |
| return true; | |
| } | |
| hitHi = true; | |
| } | |
| if (tstart >= tend) { | |
| break; | |
| } | |
| tstart = nextVertical(tstart, tend); | |
| } | |
| if (hitLo) { | |
| c.record(ystart, yend, direction); | |
| } | |
| return false; | |
| } | |
| public abstract void enlarge(Rectangle2D r); | |
| public Curve getSubCurve(double ystart, double yend) { | |
| return getSubCurve(ystart, yend, direction); | |
| } | |
| public abstract Curve getReversedCurve(); | |
| public abstract Curve getSubCurve(double ystart, double yend, int dir); | |
| public int compareTo(Curve that, double[] yrange) { | |
| /* | |
| System.out.println(this+".compareTo("+that+")"); | |
| System.out.println("target range = "+yrange[0]+"=>"+yrange[1]); | |
| */ | |
| double y0 = yrange[0]; | |
| double y1 = yrange[1]; | |
| y1 = Math.min(Math.min(y1, this.getYBot()), that.getYBot()); | |
| if (y1 <= yrange[0]) { | |
| System.err.println("this == "+this); | |
| System.err.println("that == "+that); | |
| System.out.println("target range = "+yrange[0]+"=>"+yrange[1]); | |
| throw new InternalError("backstepping from "+yrange[0]+" to "+y1); | |
| } | |
| yrange[1] = y1; | |
| if (this.getXMax() <= that.getXMin()) { | |
| if (this.getXMin() == that.getXMax()) { | |
| return 0; | |
| } | |
| return -1; | |
| } | |
| if (this.getXMin() >= that.getXMax()) { | |
| return 1; | |
| } | |
| // Parameter s for thi(s) curve and t for tha(t) curve | |
| // [st]0 = parameters for top of current section of interest | |
| // [st]1 = parameters for bottom of valid range | |
| // [st]h = parameters for hypothesis point | |
| // [d][xy]s = valuations of thi(s) curve at sh | |
| // [d][xy]t = valuations of tha(t) curve at th | |
| double s0 = this.TforY(y0); | |
| double ys0 = this.YforT(s0); | |
| if (ys0 < y0) { | |
| s0 = refineTforY(s0, ys0, y0); | |
| ys0 = this.YforT(s0); | |
| } | |
| double s1 = this.TforY(y1); | |
| if (this.YforT(s1) < y0) { | |
| s1 = refineTforY(s1, this.YforT(s1), y0); | |
| //System.out.println("s1 problem!"); | |
| } | |
| double t0 = that.TforY(y0); | |
| double yt0 = that.YforT(t0); | |
| if (yt0 < y0) { | |
| t0 = that.refineTforY(t0, yt0, y0); | |
| yt0 = that.YforT(t0); | |
| } | |
| double t1 = that.TforY(y1); | |
| if (that.YforT(t1) < y0) { | |
| t1 = that.refineTforY(t1, that.YforT(t1), y0); | |
| //System.out.println("t1 problem!"); | |
| } | |
| double xs0 = this.XforT(s0); | |
| double xt0 = that.XforT(t0); | |
| double scale = Math.max(Math.abs(y0), Math.abs(y1)); | |
| double ymin = Math.max(scale * 1E-14, 1E-300); | |
| if (fairlyClose(xs0, xt0)) { | |
| double bump = ymin; | |
| double maxbump = Math.min(ymin * 1E13, (y1 - y0) * .1); | |
| double y = y0 + bump; | |
| while (y <= y1) { | |
| if (fairlyClose(this.XforY(y), that.XforY(y))) { | |
| if ((bump *= 2) > maxbump) { | |
| bump = maxbump; | |
| } | |
| } else { | |
| y -= bump; | |
| while (true) { | |
| bump /= 2; | |
| double newy = y + bump; | |
| if (newy <= y) { | |
| break; | |
| } | |
| if (fairlyClose(this.XforY(newy), that.XforY(newy))) { | |
| y = newy; | |
| } | |
| } | |
| break; | |
| } | |
| y += bump; | |
| } | |
| if (y > y0) { | |
| if (y < y1) { | |
| yrange[1] = y; | |
| } | |
| return 0; | |
| } | |
| } | |
| //double ymin = y1 * 1E-14; | |
| if (ymin <= 0) { | |
| System.out.println("ymin = "+ymin); | |
| } | |
| /* | |
| System.out.println("s range = "+s0+" to "+s1); | |
| System.out.println("t range = "+t0+" to "+t1); | |
| */ | |
| while (s0 < s1 && t0 < t1) { | |
| double sh = this.nextVertical(s0, s1); | |
| double xsh = this.XforT(sh); | |
| double ysh = this.YforT(sh); | |
| double th = that.nextVertical(t0, t1); | |
| double xth = that.XforT(th); | |
| double yth = that.YforT(th); | |
| /* | |
| System.out.println("sh = "+sh); | |
| System.out.println("th = "+th); | |
| */ | |
| try { | |
| if (findIntersect(that, yrange, ymin, 0, 0, | |
| s0, xs0, ys0, sh, xsh, ysh, | |
| t0, xt0, yt0, th, xth, yth)) { | |
| break; | |
| } | |
| } catch (Throwable t) { | |
| System.err.println("Error: "+t); | |
| System.err.println("y range was "+yrange[0]+"=>"+yrange[1]); | |
| System.err.println("s y range is "+ys0+"=>"+ysh); | |
| System.err.println("t y range is "+yt0+"=>"+yth); | |
| System.err.println("ymin is "+ymin); | |
| return 0; | |
| } | |
| if (ysh < yth) { | |
| if (ysh > yrange[0]) { | |
| if (ysh < yrange[1]) { | |
| yrange[1] = ysh; | |
| } | |
| break; | |
| } | |
| s0 = sh; | |
| xs0 = xsh; | |
| ys0 = ysh; | |
| } else { | |
| if (yth > yrange[0]) { | |
| if (yth < yrange[1]) { | |
| yrange[1] = yth; | |
| } | |
| break; | |
| } | |
| t0 = th; | |
| xt0 = xth; | |
| yt0 = yth; | |
| } | |
| } | |
| double ymid = (yrange[0] + yrange[1]) / 2; | |
| /* | |
| System.out.println("final this["+s0+", "+sh+", "+s1+"]"); | |
| System.out.println("final y["+ys0+", "+ysh+"]"); | |
| System.out.println("final that["+t0+", "+th+", "+t1+"]"); | |
| System.out.println("final y["+yt0+", "+yth+"]"); | |
| System.out.println("final order = "+orderof(this.XforY(ymid), | |
| that.XforY(ymid))); | |
| System.out.println("final range = "+yrange[0]+"=>"+yrange[1]); | |
| */ | |
| /* | |
| System.out.println("final sx = "+this.XforY(ymid)); | |
| System.out.println("final tx = "+that.XforY(ymid)); | |
| System.out.println("final order = "+orderof(this.XforY(ymid), | |
| that.XforY(ymid))); | |
| */ | |
| return orderof(this.XforY(ymid), that.XforY(ymid)); | |
| } | |
| public static final double TMIN = 1E-3; | |
| public boolean findIntersect(Curve that, double[] yrange, double ymin, | |
| int slevel, int tlevel, | |
| double s0, double xs0, double ys0, | |
| double s1, double xs1, double ys1, | |
| double t0, double xt0, double yt0, | |
| double t1, double xt1, double yt1) | |
| { | |
| /* | |
| String pad = " "; | |
| pad = pad+pad+pad+pad+pad; | |
| pad = pad+pad; | |
| System.out.println("----------------------------------------------"); | |
| System.out.println(pad.substring(0, slevel)+ys0); | |
| System.out.println(pad.substring(0, slevel)+ys1); | |
| System.out.println(pad.substring(0, slevel)+(s1-s0)); | |
| System.out.println("-------"); | |
| System.out.println(pad.substring(0, tlevel)+yt0); | |
| System.out.println(pad.substring(0, tlevel)+yt1); | |
| System.out.println(pad.substring(0, tlevel)+(t1-t0)); | |
| */ | |
| if (ys0 > yt1 || yt0 > ys1) { | |
| return false; | |
| } | |
| if (Math.min(xs0, xs1) > Math.max(xt0, xt1) || | |
| Math.max(xs0, xs1) < Math.min(xt0, xt1)) | |
| { | |
| return false; | |
| } | |
| // Bounding boxes intersect - back off the larger of | |
| // the two subcurves by half until they stop intersecting | |
| // (or until they get small enough to switch to a more | |
| // intensive algorithm). | |
| if (s1 - s0 > TMIN) { | |
| double s = (s0 + s1) / 2; | |
| double xs = this.XforT(s); | |
| double ys = this.YforT(s); | |
| if (s == s0 || s == s1) { | |
| System.out.println("s0 = "+s0); | |
| System.out.println("s1 = "+s1); | |
| throw new InternalError("no s progress!"); | |
| } | |
| if (t1 - t0 > TMIN) { | |
| double t = (t0 + t1) / 2; | |
| double xt = that.XforT(t); | |
| double yt = that.YforT(t); | |
| if (t == t0 || t == t1) { | |
| System.out.println("t0 = "+t0); | |
| System.out.println("t1 = "+t1); | |
| throw new InternalError("no t progress!"); | |
| } | |
| if (ys >= yt0 && yt >= ys0) { | |
| if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, | |
| s0, xs0, ys0, s, xs, ys, | |
| t0, xt0, yt0, t, xt, yt)) { | |
| return true; | |
| } | |
| } | |
| if (ys >= yt) { | |
| if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, | |
| s0, xs0, ys0, s, xs, ys, | |
| t, xt, yt, t1, xt1, yt1)) { | |
| return true; | |
| } | |
| } | |
| if (yt >= ys) { | |
| if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, | |
| s, xs, ys, s1, xs1, ys1, | |
| t0, xt0, yt0, t, xt, yt)) { | |
| return true; | |
| } | |
| } | |
| if (ys1 >= yt && yt1 >= ys) { | |
| if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, | |
| s, xs, ys, s1, xs1, ys1, | |
| t, xt, yt, t1, xt1, yt1)) { | |
| return true; | |
| } | |
| } | |
| } else { | |
| if (ys >= yt0) { | |
| if (findIntersect(that, yrange, ymin, slevel+1, tlevel, | |
| s0, xs0, ys0, s, xs, ys, | |
| t0, xt0, yt0, t1, xt1, yt1)) { | |
| return true; | |
| } | |
| } | |
| if (yt1 >= ys) { | |
| if (findIntersect(that, yrange, ymin, slevel+1, tlevel, | |
| s, xs, ys, s1, xs1, ys1, | |
| t0, xt0, yt0, t1, xt1, yt1)) { | |
| return true; | |
| } | |
| } | |
| } | |
| } else if (t1 - t0 > TMIN) { | |
| double t = (t0 + t1) / 2; | |
| double xt = that.XforT(t); | |
| double yt = that.YforT(t); | |
| if (t == t0 || t == t1) { | |
| System.out.println("t0 = "+t0); | |
| System.out.println("t1 = "+t1); | |
| throw new InternalError("no t progress!"); | |
| } | |
| if (yt >= ys0) { | |
| if (findIntersect(that, yrange, ymin, slevel, tlevel+1, | |
| s0, xs0, ys0, s1, xs1, ys1, | |
| t0, xt0, yt0, t, xt, yt)) { | |
| return true; | |
| } | |
| } | |
| if (ys1 >= yt) { | |
| if (findIntersect(that, yrange, ymin, slevel, tlevel+1, | |
| s0, xs0, ys0, s1, xs1, ys1, | |
| t, xt, yt, t1, xt1, yt1)) { | |
| return true; | |
| } | |
| } | |
| } else { | |
| // No more subdivisions | |
| double xlk = xs1 - xs0; | |
| double ylk = ys1 - ys0; | |
| double xnm = xt1 - xt0; | |
| double ynm = yt1 - yt0; | |
| double xmk = xt0 - xs0; | |
| double ymk = yt0 - ys0; | |
| double det = xnm * ylk - ynm * xlk; | |
| if (det != 0) { | |
| double detinv = 1 / det; | |
| double s = (xnm * ymk - ynm * xmk) * detinv; | |
| double t = (xlk * ymk - ylk * xmk) * detinv; | |
| if (s >= 0 && s <= 1 && t >= 0 && t <= 1) { | |
| s = s0 + s * (s1 - s0); | |
| t = t0 + t * (t1 - t0); | |
| if (s < 0 || s > 1 || t < 0 || t > 1) { | |
| System.out.println("Uh oh!"); | |
| } | |
| double y = (this.YforT(s) + that.YforT(t)) / 2; | |
| if (y <= yrange[1] && y > yrange[0]) { | |
| yrange[1] = y; | |
| return true; | |
| } | |
| } | |
| } | |
| //System.out.println("Testing lines!"); | |
| } | |
| return false; | |
| } | |
| public double refineTforY(double t0, double yt0, double y0) { | |
| double t1 = 1; | |
| while (true) { | |
| double th = (t0 + t1) / 2; | |
| if (th == t0 || th == t1) { | |
| return t1; | |
| } | |
| double y = YforT(th); | |
| if (y < y0) { | |
| t0 = th; | |
| yt0 = y; | |
| } else if (y > y0) { | |
| t1 = th; | |
| } else { | |
| return t1; | |
| } | |
| } | |
| } | |
| public boolean fairlyClose(double v1, double v2) { | |
| return (Math.abs(v1 - v2) < | |
| Math.max(Math.abs(v1), Math.abs(v2)) * 1E-10); | |
| } | |
| public abstract int getSegment(double[] coords); | |
| } |