OpenJDK / portola / portola
changeset 7942:e1e8a8dd8cd8
4493128: CubicCurve2D intersects method fails
Summary: Now using subdivision code in sun.awt.geom.Curve.
Reviewed-by: flar
author | dlila |
---|---|
date | Wed, 19 Jan 2011 11:31:27 -0500 |
parents | e71443fb9af6 |
children | 5229d3140556 |
files | jdk/src/share/classes/java/awt/geom/CubicCurve2D.java |
diffstat | 1 files changed, 7 insertions(+), 197 deletions(-) [+] |
line wrap: on
line diff
--- a/jdk/src/share/classes/java/awt/geom/CubicCurve2D.java Wed Jan 19 09:44:52 2011 -0500 +++ b/jdk/src/share/classes/java/awt/geom/CubicCurve2D.java Wed Jan 19 11:31:27 2011 -0500 @@ -1387,203 +1387,13 @@ return false; } - // Trivially accept if either endpoint is inside the rectangle - // (not on its border since it may end there and not go inside) - // Record where they lie with respect to the rectangle. - // -1 => left, 0 => inside, 1 => right - double x1 = getX1(); - double y1 = getY1(); - int x1tag = getTag(x1, x, x+w); - int y1tag = getTag(y1, y, y+h); - if (x1tag == INSIDE && y1tag == INSIDE) { - return true; - } - double x2 = getX2(); - double y2 = getY2(); - int x2tag = getTag(x2, x, x+w); - int y2tag = getTag(y2, y, y+h); - if (x2tag == INSIDE && y2tag == INSIDE) { - return true; - } - - double ctrlx1 = getCtrlX1(); - double ctrly1 = getCtrlY1(); - double ctrlx2 = getCtrlX2(); - double ctrly2 = getCtrlY2(); - int ctrlx1tag = getTag(ctrlx1, x, x+w); - int ctrly1tag = getTag(ctrly1, y, y+h); - int ctrlx2tag = getTag(ctrlx2, x, x+w); - int ctrly2tag = getTag(ctrly2, y, y+h); - - // Trivially reject if all points are entirely to one side of - // the rectangle. - if (x1tag < INSIDE && x2tag < INSIDE && - ctrlx1tag < INSIDE && ctrlx2tag < INSIDE) - { - return false; // All points left - } - if (y1tag < INSIDE && y2tag < INSIDE && - ctrly1tag < INSIDE && ctrly2tag < INSIDE) - { - return false; // All points above - } - if (x1tag > INSIDE && x2tag > INSIDE && - ctrlx1tag > INSIDE && ctrlx2tag > INSIDE) - { - return false; // All points right - } - if (y1tag > INSIDE && y2tag > INSIDE && - ctrly1tag > INSIDE && ctrly2tag > INSIDE) - { - return false; // All points below - } - - // Test for endpoints on the edge where either the segment - // or the curve is headed "inwards" from them - // Note: These tests are a superset of the fast endpoint tests - // above and thus repeat those tests, but take more time - // and cover more cases - if (inwards(x1tag, x2tag, ctrlx1tag) && - inwards(y1tag, y2tag, ctrly1tag)) - { - // First endpoint on border with either edge moving inside - return true; - } - if (inwards(x2tag, x1tag, ctrlx2tag) && - inwards(y2tag, y1tag, ctrly2tag)) - { - // Second endpoint on border with either edge moving inside - return true; - } - - // Trivially accept if endpoints span directly across the rectangle - boolean xoverlap = (x1tag * x2tag <= 0); - boolean yoverlap = (y1tag * y2tag <= 0); - if (x1tag == INSIDE && x2tag == INSIDE && yoverlap) { - return true; - } - if (y1tag == INSIDE && y2tag == INSIDE && xoverlap) { - return true; - } - - // We now know that both endpoints are outside the rectangle - // but the 4 points are not all on one side of the rectangle. - // Therefore the curve cannot be contained inside the rectangle, - // but the rectangle might be contained inside the curve, or - // the curve might intersect the boundary of the rectangle. - - double[] eqn = new double[4]; - double[] res = new double[4]; - if (!yoverlap) { - // Both y coordinates for the closing segment are above or - // below the rectangle which means that we can only intersect - // if the curve crosses the top (or bottom) of the rectangle - // in more than one place and if those crossing locations - // span the horizontal range of the rectangle. - fillEqn(eqn, (y1tag < INSIDE ? y : y+h), y1, ctrly1, ctrly2, y2); - int num = solveCubic(eqn, res); - num = evalCubic(res, num, true, true, null, - x1, ctrlx1, ctrlx2, x2); - // odd counts imply the crossing was out of [0,1] bounds - // otherwise there is no way for that part of the curve to - // "return" to meet its endpoint - return (num == 2 && - getTag(res[0], x, x+w) * getTag(res[1], x, x+w) <= 0); - } - - // Y ranges overlap. Now we examine the X ranges - if (!xoverlap) { - // Both x coordinates for the closing segment are left of - // or right of the rectangle which means that we can only - // intersect if the curve crosses the left (or right) edge - // of the rectangle in more than one place and if those - // crossing locations span the vertical range of the rectangle. - fillEqn(eqn, (x1tag < INSIDE ? x : x+w), x1, ctrlx1, ctrlx2, x2); - int num = solveCubic(eqn, res); - num = evalCubic(res, num, true, true, null, - y1, ctrly1, ctrly2, y2); - // odd counts imply the crossing was out of [0,1] bounds - // otherwise there is no way for that part of the curve to - // "return" to meet its endpoint - return (num == 2 && - getTag(res[0], y, y+h) * getTag(res[1], y, y+h) <= 0); - } - - // The X and Y ranges of the endpoints overlap the X and Y - // ranges of the rectangle, now find out how the endpoint - // line segment intersects the Y range of the rectangle - double dx = x2 - x1; - double dy = y2 - y1; - double k = y2 * x1 - x2 * y1; - int c1tag, c2tag; - if (y1tag == INSIDE) { - c1tag = x1tag; - } else { - c1tag = getTag((k + dx * (y1tag < INSIDE ? y : y+h)) / dy, x, x+w); - } - if (y2tag == INSIDE) { - c2tag = x2tag; - } else { - c2tag = getTag((k + dx * (y2tag < INSIDE ? y : y+h)) / dy, x, x+w); - } - // If the part of the line segment that intersects the Y range - // of the rectangle crosses it horizontally - trivially accept - if (c1tag * c2tag <= 0) { - return true; - } - - // Now we know that both the X and Y ranges intersect and that - // the endpoint line segment does not directly cross the rectangle. - // - // We can almost treat this case like one of the cases above - // where both endpoints are to one side, except that we may - // get one or three intersections of the curve with the vertical - // side of the rectangle. This is because the endpoint segment - // accounts for the other intersection in an even pairing. Thus, - // with the endpoint crossing we end up with 2 or 4 total crossings. - // - // (Remember there is overlap in both the X and Y ranges which - // means that the segment itself must cross at least one vertical - // edge of the rectangle - in particular, the "near vertical side" - // - leaving an odd number of intersections for the curve.) - // - // Now we calculate the y tags of all the intersections on the - // "near vertical side" of the rectangle. We will have one with - // the endpoint segment, and one or three with the curve. If - // any pair of those vertical intersections overlap the Y range - // of the rectangle, we have an intersection. Otherwise, we don't. - - // c1tag = vertical intersection class of the endpoint segment - // - // Choose the y tag of the endpoint that was not on the same - // side of the rectangle as the subsegment calculated above. - // Note that we can "steal" the existing Y tag of that endpoint - // since it will be provably the same as the vertical intersection. - c1tag = ((c1tag * x1tag <= 0) ? y1tag : y2tag); - - // Now we have to calculate an array of solutions of the curve - // with the "near vertical side" of the rectangle. Then we - // need to sort the tags and do a pairwise range test to see - // if either of the pairs of crossings spans the Y range of - // the rectangle. - // - // Note that the c2tag can still tell us which vertical edge - // to test against. - fillEqn(eqn, (c2tag < INSIDE ? x : x+w), x1, ctrlx1, ctrlx2, x2); - int num = solveCubic(eqn, res); - num = evalCubic(res, num, true, true, null, y1, ctrly1, ctrly2, y2); - - // Now put all of the tags into a bucket and sort them. There - // is an intersection iff one of the pairs of tags "spans" the - // Y range of the rectangle. - int tags[] = new int[num+1]; - for (int i = 0; i < num; i++) { - tags[i] = getTag(res[i], y, y+h); - } - tags[num] = c1tag; - Arrays.sort(tags); - return ((num >= 1 && tags[0] * tags[1] <= 0) || - (num >= 3 && tags[2] * tags[3] <= 0)); + int numCrossings = rectCrossings(x, y, w, h); + // the intended return value is + // numCrossings != 0 || numCrossings == Curve.RECT_INTERSECTS + // but if (numCrossings != 0) numCrossings == INTERSECTS won't matter + // and if !(numCrossings != 0) then numCrossings == 0, so + // numCrossings != RECT_INTERSECT + return numCrossings != 0; } /**