CubicCurve2D.java revision 2362
2362N/A * Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2362N/A * or visit www.oracle.com if you need additional information or have any 0N/A * The <code>CubicCurve2D</code> class defines a cubic parametric curve 0N/A * segment in {@code (x,y)} coordinate space. 0N/A * This class is only the abstract superclass for all objects which 0N/A * store a 2D cubic curve segment. 0N/A * The actual storage representation of the coordinates is left to 0N/A * @author Jim Graham 0N/A * A cubic parametric curve segment specified with 0N/A * {@code float} coordinates. 0N/A * The X coordinate of the start point 0N/A * of the cubic curve segment. 0N/A * The Y coordinate of the start point 0N/A * of the cubic curve segment. 0N/A * The X coordinate of the first control point 0N/A * of the cubic curve segment. 0N/A * The Y coordinate of the first control point 0N/A * of the cubic curve segment. 0N/A * The X coordinate of the second control point 0N/A * of the cubic curve segment. 0N/A * The Y coordinate of the second control point 0N/A * of the cubic curve segment. 0N/A * The X coordinate of the end point 0N/A * of the cubic curve segment. 0N/A * The Y coordinate of the end point 0N/A * of the cubic curve segment. 0N/A * Constructs and initializes a CubicCurve with coordinates 0N/A * (0, 0, 0, 0, 0, 0, 0, 0). 0N/A * Constructs and initializes a {@code CubicCurve2D} from 0N/A * the specified {@code float} coordinates. 0N/A * @param x1 the X coordinate for the start point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param y1 the Y coordinate for the start point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param ctrlx1 the X coordinate for the first control point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param ctrly1 the Y coordinate for the first control point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param ctrlx2 the X coordinate for the second control point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param ctrly2 the Y coordinate for the second control point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param x2 the X coordinate for the end point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param y2 the Y coordinate for the end point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * Sets the location of the end points and control points 0N/A * of this curve to the specified {@code float} coordinates. 0N/A * @param x1 the X coordinate used to set the start point 0N/A * of this {@code CubicCurve2D} 0N/A * @param y1 the Y coordinate used to set the start point 0N/A * of this {@code CubicCurve2D} 0N/A * @param ctrlx1 the X coordinate used to set the first control point 0N/A * of this {@code CubicCurve2D} 0N/A * @param ctrly1 the Y coordinate used to set the first control point 0N/A * of this {@code CubicCurve2D} 0N/A * @param ctrlx2 the X coordinate used to set the second control point 0N/A * of this {@code CubicCurve2D} 0N/A * @param ctrly2 the Y coordinate used to set the second control point 0N/A * of this {@code CubicCurve2D} 0N/A * @param x2 the X coordinate used to set the end point 0N/A * of this {@code CubicCurve2D} 0N/A * @param y2 the Y coordinate used to set the end point 0N/A * of this {@code CubicCurve2D} 0N/A * JDK 1.6 serialVersionUID 0N/A * A cubic parametric curve segment specified with 0N/A * {@code double} coordinates. 0N/A * The X coordinate of the start point 0N/A * of the cubic curve segment. 0N/A * The Y coordinate of the start point 0N/A * of the cubic curve segment. 0N/A * The X coordinate of the first control point 0N/A * of the cubic curve segment. 0N/A * The Y coordinate of the first control point 0N/A * of the cubic curve segment. 0N/A * The X coordinate of the second control point 0N/A * of the cubic curve segment. 0N/A * The Y coordinate of the second control point 0N/A * of the cubic curve segment. 0N/A * The X coordinate of the end point 0N/A * of the cubic curve segment. 0N/A * The Y coordinate of the end point 0N/A * of the cubic curve segment. 0N/A * Constructs and initializes a CubicCurve with coordinates 0N/A * (0, 0, 0, 0, 0, 0, 0, 0). 0N/A * Constructs and initializes a {@code CubicCurve2D} from 0N/A * the specified {@code double} coordinates. 0N/A * @param x1 the X coordinate for the start point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param y1 the Y coordinate for the start point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param ctrlx1 the X coordinate for the first control point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param ctrly1 the Y coordinate for the first control point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param ctrlx2 the X coordinate for the second control point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param ctrly2 the Y coordinate for the second control point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param x2 the X coordinate for the end point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * @param y2 the Y coordinate for the end point 0N/A * of the resulting {@code CubicCurve2D} 0N/A * JDK 1.6 serialVersionUID 0N/A * This is an abstract class that cannot be instantiated directly. 0N/A * Type-specific implementation subclasses are available for 0N/A * instantiation and provide a number of formats for storing 0N/A * the information necessary to satisfy the various accessor 0N/A * @see java.awt.geom.CubicCurve2D.Float 0N/A * @see java.awt.geom.CubicCurve2D.Double 0N/A * Returns the X coordinate of the start point in double precision. 0N/A * @return the X coordinate of the start point of the 0N/A * {@code CubicCurve2D}. 0N/A * Returns the Y coordinate of the start point in double precision. 0N/A * @return the Y coordinate of the start point of the 0N/A * {@code CubicCurve2D}. 0N/A * Returns the start point. 0N/A * @return a {@code Point2D} that is the start point of 0N/A * the {@code CubicCurve2D}. 0N/A * Returns the X coordinate of the first control point in double precision. 0N/A * @return the X coordinate of the first control point of the 0N/A * {@code CubicCurve2D}. 0N/A * Returns the Y coordinate of the first control point in double precision. 0N/A * @return the Y coordinate of the first control point of the 0N/A * {@code CubicCurve2D}. 0N/A * Returns the first control point. 0N/A * @return a {@code Point2D} that is the first control point of 0N/A * the {@code CubicCurve2D}. 0N/A * Returns the X coordinate of the second control point 0N/A * in double precision. 0N/A * @return the X coordinate of the second control point of the 0N/A * {@code CubicCurve2D}. 0N/A * Returns the Y coordinate of the second control point 0N/A * in double precision. 0N/A * @return the Y coordinate of the second control point of the 0N/A * {@code CubicCurve2D}. 0N/A * Returns the second control point. 0N/A * @return a {@code Point2D} that is the second control point of 0N/A * the {@code CubicCurve2D}. 0N/A * Returns the X coordinate of the end point in double precision. 0N/A * @return the X coordinate of the end point of the 0N/A * {@code CubicCurve2D}. 0N/A * Returns the Y coordinate of the end point in double precision. 0N/A * @return the Y coordinate of the end point of the 0N/A * {@code CubicCurve2D}. 0N/A * Returns the end point. 0N/A * @return a {@code Point2D} that is the end point of 0N/A * the {@code CubicCurve2D}. 0N/A * Sets the location of the end points and control points of this curve 0N/A * to the specified double coordinates. 0N/A * @param x1 the X coordinate used to set the start point 0N/A * of this {@code CubicCurve2D} 0N/A * @param y1 the Y coordinate used to set the start point 0N/A * of this {@code CubicCurve2D} 0N/A * @param ctrlx1 the X coordinate used to set the first control point 0N/A * of this {@code CubicCurve2D} 0N/A * @param ctrly1 the Y coordinate used to set the first control point 0N/A * of this {@code CubicCurve2D} 0N/A * @param ctrlx2 the X coordinate used to set the second control point 0N/A * of this {@code CubicCurve2D} 0N/A * @param ctrly2 the Y coordinate used to set the second control point 0N/A * of this {@code CubicCurve2D} 0N/A * @param x2 the X coordinate used to set the end point 0N/A * of this {@code CubicCurve2D} 0N/A * @param y2 the Y coordinate used to set the end point 0N/A * of this {@code CubicCurve2D} 0N/A * Sets the location of the end points and control points of this curve 0N/A * to the double coordinates at the specified offset in the specified 0N/A * @param coords a double array containing coordinates 0N/A * @param offset the index of <code>coords</code> from which to begin 0N/A * setting the end points and control points of this curve 0N/A * to the coordinates contained in <code>coords</code> 0N/A * Sets the location of the end points and control points of this curve 0N/A * to the specified <code>Point2D</code> coordinates. 0N/A * @param p1 the first specified <code>Point2D</code> used to set the 0N/A * start point of this curve 0N/A * @param cp1 the second specified <code>Point2D</code> used to set the 0N/A * first control point of this curve 0N/A * @param cp2 the third specified <code>Point2D</code> used to set the 0N/A * second control point of this curve 0N/A * @param p2 the fourth specified <code>Point2D</code> used to set the 0N/A * end point of this curve 0N/A * Sets the location of the end points and control points of this curve 0N/A * to the coordinates of the <code>Point2D</code> objects at the specified 0N/A * offset in the specified array. 0N/A * @param pts an array of <code>Point2D</code> objects 0N/A * @param offset the index of <code>pts</code> from which to begin setting 0N/A * the end points and control points of this curve to the 0N/A * points contained in <code>pts</code> 0N/A * Sets the location of the end points and control points of this curve 0N/A * to the same as those in the specified <code>CubicCurve2D</code>. 0N/A * @param c the specified <code>CubicCurve2D</code> 0N/A * Returns the square of the flatness of the cubic curve specified 0N/A * by the indicated control points. The flatness is the maximum distance 0N/A * of a control point from the line connecting the end points. 0N/A * @param x1 the X coordinate that specifies the start point 0N/A * of a {@code CubicCurve2D} 0N/A * @param y1 the Y coordinate that specifies the start point 0N/A * of a {@code CubicCurve2D} 0N/A * @param ctrlx1 the X coordinate that specifies the first control point 0N/A * of a {@code CubicCurve2D} 0N/A * @param ctrly1 the Y coordinate that specifies the first control point 0N/A * of a {@code CubicCurve2D} 0N/A * @param ctrlx2 the X coordinate that specifies the second control point 0N/A * of a {@code CubicCurve2D} 0N/A * @param ctrly2 the Y coordinate that specifies the second control point 0N/A * of a {@code CubicCurve2D} 0N/A * @param x2 the X coordinate that specifies the end point 0N/A * of a {@code CubicCurve2D} 0N/A * @param y2 the Y coordinate that specifies the end point 0N/A * of a {@code CubicCurve2D} 0N/A * @return the square of the flatness of the {@code CubicCurve2D} 0N/A * represented by the specified coordinates. 0N/A * Returns the flatness of the cubic curve specified 0N/A * by the indicated control points. The flatness is the maximum distance 0N/A * of a control point from the line connecting the end points. 0N/A * @param x1 the X coordinate that specifies the start point 0N/A * of a {@code CubicCurve2D} 0N/A * @param y1 the Y coordinate that specifies the start point 0N/A * of a {@code CubicCurve2D} 0N/A * @param ctrlx1 the X coordinate that specifies the first control point 0N/A * of a {@code CubicCurve2D} 0N/A * @param ctrly1 the Y coordinate that specifies the first control point 0N/A * of a {@code CubicCurve2D} 0N/A * @param ctrlx2 the X coordinate that specifies the second control point 0N/A * of a {@code CubicCurve2D} 0N/A * @param ctrly2 the Y coordinate that specifies the second control point 0N/A * of a {@code CubicCurve2D} 0N/A * @param x2 the X coordinate that specifies the end point 0N/A * of a {@code CubicCurve2D} 0N/A * @param y2 the Y coordinate that specifies the end point 0N/A * of a {@code CubicCurve2D} 0N/A * @return the flatness of the {@code CubicCurve2D} 0N/A * represented by the specified coordinates. 0N/A * Returns the square of the flatness of the cubic curve specified 0N/A * by the control points stored in the indicated array at the 0N/A * indicated index. The flatness is the maximum distance 0N/A * of a control point from the line connecting the end points. 0N/A * @param coords an array containing coordinates 0N/A * @param offset the index of <code>coords</code> from which to begin 0N/A * getting the end points and control points of the curve 0N/A * @return the square of the flatness of the <code>CubicCurve2D</code> 0N/A * specified by the coordinates in <code>coords</code> at 0N/A * the specified offset. 0N/A * Returns the flatness of the cubic curve specified 0N/A * by the control points stored in the indicated array at the 0N/A * indicated index. The flatness is the maximum distance 0N/A * of a control point from the line connecting the end points. 0N/A * @param coords an array containing coordinates 0N/A * @param offset the index of <code>coords</code> from which to begin 0N/A * getting the end points and control points of the curve 0N/A * @return the flatness of the <code>CubicCurve2D</code> 0N/A * specified by the coordinates in <code>coords</code> at 0N/A * the specified offset. 0N/A * Returns the square of the flatness of this curve. The flatness is the 0N/A * maximum distance of a control point from the line connecting the 0N/A * @return the square of the flatness of this curve. 0N/A * Returns the flatness of this curve. The flatness is the 0N/A * maximum distance of a control point from the line connecting the 0N/A * @return the flatness of this curve. 0N/A * Subdivides this cubic curve and stores the resulting two 0N/A * subdivided curves into the left and right curve parameters. 0N/A * Either or both of the left and right objects may be the same 0N/A * as this object or null. 0N/A * @param left the cubic curve object for storing for the left or 0N/A * first half of the subdivided curve 0N/A * @param right the cubic curve object for storing for the right or 0N/A * second half of the subdivided curve 0N/A * Subdivides the cubic curve specified by the <code>src</code> parameter 0N/A * and stores the resulting two subdivided curves into the 0N/A * <code>left</code> and <code>right</code> curve parameters. 0N/A * Either or both of the <code>left</code> and <code>right</code> objects 0N/A * may be the same as the <code>src</code> object or <code>null</code>. 0N/A * @param src the cubic curve to be subdivided 0N/A * @param left the cubic curve object for storing the left or 0N/A * first half of the subdivided curve 0N/A * @param right the cubic curve object for storing the right or 0N/A * second half of the subdivided curve 0N/A * Subdivides the cubic curve specified by the coordinates 0N/A * stored in the <code>src</code> array at indices <code>srcoff</code> 0N/A * through (<code>srcoff</code> + 7) and stores the 0N/A * resulting two subdivided curves into the two result arrays at the 0N/A * corresponding indices. 0N/A * Either or both of the <code>left</code> and <code>right</code> 0N/A * arrays may be <code>null</code> or a reference to the same array 0N/A * as the <code>src</code> array. 0N/A * Note that the last point in the first subdivided curve is the 0N/A * same as the first point in the second subdivided curve. Thus, 0N/A * it is possible to pass the same array for <code>left</code> 0N/A * and <code>right</code> and to use offsets, such as <code>rightoff</code> 0N/A * equals (<code>leftoff</code> + 6), in order 0N/A * to avoid allocating extra storage for this common point. 0N/A * @param src the array holding the coordinates for the source curve 0N/A * @param srcoff the offset into the array of the beginning of the 0N/A * the 6 source coordinates 0N/A * @param left the array for storing the coordinates for the first 0N/A * half of the subdivided curve 0N/A * @param leftoff the offset into the array of the beginning of the 0N/A * the 6 left coordinates 0N/A * @param right the array for storing the coordinates for the second 0N/A * half of the subdivided curve 0N/A * @param rightoff the offset into the array of the beginning of the 0N/A * the 6 right coordinates 0N/A * Solves the cubic whose coefficients are in the <code>eqn</code> 0N/A * array and places the non-complex roots back into the same array, 0N/A * returning the number of roots. The solved cubic is represented 0N/A * eqn = {c, b, a, d} 0N/A * dx^3 + ax^2 + bx + c = 0 0N/A * A return value of -1 is used to distinguish a constant equation 0N/A * that might be always 0 or never 0 from an equation that has no 0N/A * @param eqn an array containing coefficients for a cubic 0N/A * @return the number of roots, or -1 if the equation is a constant. 0N/A * Solve the cubic whose coefficients are in the <code>eqn</code> 0N/A * array and place the non-complex roots into the <code>res</code> 0N/A * array, returning the number of roots. 0N/A * The cubic solved is represented by the equation: 0N/A * eqn = {c, b, a, d} 0N/A * dx^3 + ax^2 + bx + c = 0 0N/A * A return value of -1 is used to distinguish a constant equation, 0N/A * which may be always 0 or never 0, from an equation which has no 0N/A * @param eqn the specified array of coefficients to use to solve 0N/A * the cubic equation 0N/A * @param res the array that contains the non-complex roots 0N/A * resulting from the solution of the cubic equation 0N/A * @return the number of roots, or -1 if the equation is a constant 0N/A // From Numerical Recipes, 5.6, Quadratic and Cubic Equations 0N/A // The cubic has degenerated to quadratic (or line or ...). 0N/A double Q = (a * a -
3.0 * b) /
9.0;
0N/A double R = (
2.0 * a * a * a -
9.0 * a * b +
27.0 * c) /
54.0;
0N/A // Copy the eqn so that we don't clobber it with the 0N/A // roots. This is needed so that fixRoots can do its 0N/A // work with the original equation. 0N/A double B = (A ==
0.0) ?
0.0 : (Q / A);
0N/A * This pruning step is necessary since solveCubic uses the 0N/A * cosine function to calculate the roots when there are 3 0N/A * of them. Since the cosine method can have an error of 0N/A * +/- 1E-14 we need to make sure that we don't make any 0N/A * bad decisions due to an error. 0N/A * If the root is not near one of the endpoints, then we will 0N/A * only have a slight inaccuracy in calculating the x intercept 0N/A * which will only cause a slightly wrong answer for some 0N/A * points very close to the curve. While the results in that 0N/A * case are not as accurate as they could be, they are not 0N/A * disastrously inaccurate either. 0N/A * On the other hand, if the error happens near one end of 0N/A * the curve, then our processing to reject values outside 0N/A * of the t=[0,1] range will fail and the results of that 0N/A * failure will be disastrous since for an entire horizontal 0N/A * range of test points, we will either overcount or undercount 0N/A * the crossings and get a wrong answer for all of them, even 0N/A * when they are clearly and obviously inside or outside the 0N/A * To work around this problem, we try a couple of Newton-Raphson 0N/A * iterations to see if the true root is closer to the endpoint 0N/A * or further away. If it is further away, then we can stop 0N/A * since we know we are on the right side of the endpoint. If 0N/A * we change direction, then either we are now being dragged away 0N/A * from the endpoint in which case the first condition will cause 0N/A * us to stop, or we have passed the endpoint and are headed back. 0N/A * In the second case, we simply evaluate the slope at the 0N/A * endpoint itself and place ourselves on the appropriate side 0N/A * of it or on it depending on that result. 0N/A for (
int i =
0; i <
3; i++) {
0N/A // At a local minima - must return 0N/A // Found it! - return it 0N/A // assert(slope != 0 && y != 0); 0N/A // assert(delta != 0); 0N/A }
else {
/* t == target */ 0N/A // The deltas are so small that we aren't moving... 0N/A // We have reversed our path. 0N/A // Local minima found away from target - return the middle 0N/A // Local minima somewhere near target - move to target 0N/A // and let the slope determine the resulting t. 0N/A if (!(x *
0.0 + y *
0.0 ==
0.0)) {
0N/A /* Either x or y was infinite or NaN. 0N/A * A NaN always produces a negative response to any test 0N/A * and Infinity values cannot be "inside" any path so 0N/A * they should return false as well. 0N/A // We count the "Y" crossings to determine if the point is 0N/A // inside the curve bounded by its closing line. 0N/A * Fill an array with the coefficients of the parametric equation 0N/A * in t, ready for solving against val with solveCubic. 0N/A * We currently have: 0N/A * val = P(t) = C1(1-t)^3 + 3CP1 t(1-t)^2 + 3CP2 t^2(1-t) + C2 t^3 0N/A * = C1 - 3C1t + 3C1t^2 - C1t^3 + 0N/A * 3CP1t - 6CP1t^2 + 3CP1t^3 + 0N/A * 3CP2t^2 - 3CP2t^3 + 0N/A * (3C1 - 6CP1 + 3CP2) t^2 + 0N/A * (C2 - 3CP2 + 3CP1 - C1) t^3 0N/A * 0 = C + Bt + At^2 + Dt^3 0N/A * A = 3*CP2 - 6*CP1 + 3*C1 0N/A * D = C2 - 3*CP2 + 3*CP1 - C1 0N/A * Evaluate the t values in the first num slots of the vals[] array 0N/A * and place the evaluated values back into the same array. Only 0N/A * evaluate t values that are within the range <0, 1>, including 0N/A * the 0 and 1 ends of the range iff the include0 or include1 0N/A * booleans are true. If an "inflection" equation is handed in, 0N/A * then any points which represent a point of inflection for that 0N/A * cubic equation are also ignored. 0N/A for (
int i =
0; i <
num; i++) {
0N/A * Determine where coord lies with respect to the range from 0N/A * low to high. It is assumed that low <= high. The return 0N/A * value is one of the 5 values BELOW, LOWEDGE, INSIDE, HIGHEDGE, 0N/A * Determine if the pttag represents a coordinate that is already 0N/A * in its test range, or is on the border with either of the two 0N/A * opttags representing another coordinate that is "towards the 0N/A * inside" of that test range. In other words, are either of the 0N/A * two "opt" points "drawing the pt inward"? 0N/A public boolean intersects(
double x,
double y,
double w,
double h) {
0N/A // Trivially reject non-existant rectangles 0N/A if (w <=
0 || h <=
0) {
0N/A // Trivially accept if either endpoint is inside the rectangle 0N/A // (not on its border since it may end there and not go inside) 0N/A // Record where they lie with respect to the rectangle. 0N/A // -1 => left, 0 => inside, 1 => right 0N/A // Trivially reject if all points are entirely to one side of 0N/A return false;
// All points left 0N/A return false;
// All points above 0N/A return false;
// All points right 0N/A return false;
// All points below 0N/A // Test for endpoints on the edge where either the segment 0N/A // or the curve is headed "inwards" from them 0N/A // Note: These tests are a superset of the fast endpoint tests 0N/A // above and thus repeat those tests, but take more time 0N/A // and cover more cases 0N/A // First endpoint on border with either edge moving inside 0N/A // Second endpoint on border with either edge moving inside 0N/A // Trivially accept if endpoints span directly across the rectangle 0N/A // We now know that both endpoints are outside the rectangle 0N/A // but the 4 points are not all on one side of the rectangle. 0N/A // Therefore the curve cannot be contained inside the rectangle, 0N/A // but the rectangle might be contained inside the curve, or 0N/A // the curve might intersect the boundary of the rectangle. 0N/A // Both y coordinates for the closing segment are above or 0N/A // below the rectangle which means that we can only intersect 0N/A // if the curve crosses the top (or bottom) of the rectangle 0N/A // in more than one place and if those crossing locations 0N/A // span the horizontal range of the rectangle. 0N/A // odd counts imply the crossing was out of [0,1] bounds 0N/A // otherwise there is no way for that part of the curve to 0N/A // "return" to meet its endpoint 0N/A // Y ranges overlap. Now we examine the X ranges 0N/A // Both x coordinates for the closing segment are left of 0N/A // or right of the rectangle which means that we can only 0N/A // intersect if the curve crosses the left (or right) edge 0N/A // of the rectangle in more than one place and if those 0N/A // crossing locations span the vertical range of the rectangle. 0N/A // odd counts imply the crossing was out of [0,1] bounds 0N/A // otherwise there is no way for that part of the curve to 0N/A // "return" to meet its endpoint 0N/A // The X and Y ranges of the endpoints overlap the X and Y 0N/A // ranges of the rectangle, now find out how the endpoint 0N/A // line segment intersects the Y range of the rectangle 0N/A // If the part of the line segment that intersects the Y range 0N/A // of the rectangle crosses it horizontally - trivially accept 0N/A // Now we know that both the X and Y ranges intersect and that 0N/A // the endpoint line segment does not directly cross the rectangle. 0N/A // We can almost treat this case like one of the cases above 0N/A // where both endpoints are to one side, except that we may 0N/A // get one or three intersections of the curve with the vertical 0N/A // side of the rectangle. This is because the endpoint segment 0N/A // accounts for the other intersection in an even pairing. Thus, 0N/A // with the endpoint crossing we end up with 2 or 4 total crossings. 0N/A // (Remember there is overlap in both the X and Y ranges which 0N/A // means that the segment itself must cross at least one vertical 0N/A // edge of the rectangle - in particular, the "near vertical side" 0N/A // - leaving an odd number of intersections for the curve.) 0N/A // Now we calculate the y tags of all the intersections on the 0N/A // "near vertical side" of the rectangle. We will have one with 0N/A // the endpoint segment, and one or three with the curve. If 0N/A // any pair of those vertical intersections overlap the Y range 0N/A // of the rectangle, we have an intersection. Otherwise, we don't. 0N/A // c1tag = vertical intersection class of the endpoint segment 0N/A // Choose the y tag of the endpoint that was not on the same 0N/A // side of the rectangle as the subsegment calculated above. 0N/A // Note that we can "steal" the existing Y tag of that endpoint 0N/A // since it will be provably the same as the vertical intersection. 0N/A // Now we have to calculate an array of solutions of the curve 0N/A // with the "near vertical side" of the rectangle. Then we 0N/A // need to sort the tags and do a pairwise range test to see 0N/A // if either of the pairs of crossings spans the Y range of 0N/A // Note that the c2tag can still tell us which vertical edge 0N/A // Now put all of the tags into a bucket and sort them. There 0N/A // is an intersection iff one of the pairs of tags "spans" the 0N/A // Y range of the rectangle. 0N/A for (
int i =
0; i <
num; i++) {
0N/A public boolean contains(
double x,
double y,
double w,
double h) {
0N/A if (w <=
0 || h <=
0) {
0N/A // Assertion: Cubic curves closed by connecting their 0N/A // endpoints form either one or two convex halves with 0N/A // the closing line segment as an edge of both sides. 0N/A // Either the rectangle is entirely inside one of the convex 0N/A // halves or it crosses from one to the other, in which case 0N/A // it must intersect the closing line segment. 0N/A * Returns an iteration object that defines the boundary of the 0N/A * The iterator for this class is not multi-threaded safe, 0N/A * which means that this <code>CubicCurve2D</code> class does not 0N/A * guarantee that modifications to the geometry of this 0N/A * <code>CubicCurve2D</code> object do not affect any iterations of 0N/A * that geometry that are already in process. 0N/A * @param at an optional <code>AffineTransform</code> to be applied to the 0N/A * coordinates as they are returned in the iteration, or <code>null</code> 0N/A * if untransformed coordinates are desired 0N/A * @return the <code>PathIterator</code> object that returns the 0N/A * geometry of the outline of this <code>CubicCurve2D</code>, one 0N/A * segment at a time. 0N/A * Return an iteration object that defines the boundary of the 0N/A * The iterator for this class is not multi-threaded safe, 0N/A * which means that this <code>CubicCurve2D</code> class does not 0N/A * guarantee that modifications to the geometry of this 0N/A * <code>CubicCurve2D</code> object do not affect any iterations of 0N/A * that geometry that are already in process. 0N/A * @param at an optional <code>AffineTransform</code> to be applied to the 0N/A * coordinates as they are returned in the iteration, or <code>null</code> 0N/A * if untransformed coordinates are desired 0N/A * @param flatness the maximum amount that the control points 0N/A * for a given curve can vary from colinear before a subdivided 0N/A * curve is replaced by a straight line connecting the end points 0N/A * @return the <code>PathIterator</code> object that returns the 0N/A * geometry of the outline of this <code>CubicCurve2D</code>, 0N/A * one segment at a time. 0N/A * Creates a new object of the same class as this object. 0N/A * @return a clone of this instance. 0N/A * @exception OutOfMemoryError if there is not enough memory. 0N/A * @see java.lang.Cloneable 0N/A // this shouldn't happen, since we are Cloneable