### Eclipse Workspace Patch 1.0 #P org.eclipse.gef4.geometry Index: src/org/eclipse/gef4/geometry/Angle.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/Angle.java,v retrieving revision 1.3 diff -u -r1.3 Angle.java --- src/org/eclipse/gef4/geometry/Angle.java 17 Nov 2011 22:00:18 -0000 1.3 +++ src/org/eclipse/gef4/geometry/Angle.java 9 Dec 2011 16:02:34 -0000 @@ -207,7 +207,8 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; } Index: src/org/eclipse/gef4/geometry/Dimension.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/Dimension.java,v retrieving revision 1.5 diff -u -r1.5 Dimension.java --- src/org/eclipse/gef4/geometry/Dimension.java 17 Nov 2011 22:00:18 -0000 1.5 +++ src/org/eclipse/gef4/geometry/Dimension.java 9 Dec 2011 16:02:35 -0000 @@ -349,9 +349,9 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; - // return (int) (width * height) ^ (int) (width + height); } /** Index: src/org/eclipse/gef4/geometry/Point.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/Point.java,v retrieving revision 1.4 diff -u -r1.4 Point.java --- src/org/eclipse/gef4/geometry/Point.java 17 Nov 2011 22:00:18 -0000 1.4 +++ src/org/eclipse/gef4/geometry/Point.java 9 Dec 2011 16:02:35 -0000 @@ -278,9 +278,9 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; - // return (int) (x * y) ^ (int) (x + y); } /** Index: src/org/eclipse/gef4/geometry/euclidean/Straight.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/euclidean/Straight.java,v retrieving revision 1.5 diff -u -r1.5 Straight.java --- src/org/eclipse/gef4/geometry/euclidean/Straight.java 17 Nov 2011 22:00:18 -0000 1.5 +++ src/org/eclipse/gef4/geometry/euclidean/Straight.java 9 Dec 2011 16:02:35 -0000 @@ -17,6 +17,7 @@ import org.eclipse.gef4.geometry.Angle; import org.eclipse.gef4.geometry.Point; +import org.eclipse.gef4.geometry.utils.CurveUtils; import org.eclipse.gef4.geometry.utils.PrecisionUtils; /** @@ -41,10 +42,6 @@ * @param direction */ public Straight(Vector position, Vector direction) { - // if (direction.isNull()) { - // throw new IllegalArgumentException( - // "direction has to be unequal to (0,0)"); //$NON-NLS-1$ - // } this.position = position.clone(); this.direction = direction.clone(); } @@ -122,55 +119,6 @@ } /** - * Converts a given {@link Vector} into a 3-dimensional vector in - * homogeneous coordinates represented as an array. - * - * @param v - * the {@link Vector} to convert - * @return an array representation of the 3-dimensional homogeneous vector - */ - private double[] toHomogeneousVector(Vector v) { - return new double[] { v.x, v.y, 1 }; - } - - /** - * Projects the given 3-dimensional homogeneous-coordinate vector, - * represented as an array, into the 2D space. - * - * @param v - * the array representation of a 3-dimensional - * homogeneous-coordinate vector to project - * @return the projected {@link Vector} - */ - private Vector fromHomogeneousVector(double[] v) { - if (v[2] == 0) { - return null; - } - return new Vector(v[0] / v[2], v[1] / v[2]); - } - - /** - * Calculates the cross product of two 3-dimensional vectors. - * - * Used in calculations based on 2D homogeneous coordinates. - * - * @param a - * an array representation of the first 3-dimensional input - * vector - * @param b - * an array representation of the second 3-deminsional input - * vector - * @return an array representation of the 3-dimensional cross product - */ - private double[] getCrossProduct(double[] a, double[] b) { - double[] r = new double[3]; - r[0] = a[1] * b[2] - a[2] * b[1]; - r[1] = a[2] * b[0] - a[0] * b[2]; - r[2] = a[0] * b[1] - a[1] * b[0]; - return r; - } - - /** * Computes the intersection point of this Straight and the provided one, if * it exists. * @@ -180,16 +128,11 @@ * if no intersection point exists (or the Straights are equal). */ public Vector getIntersection(Straight other) { - // method using homogeneous coordinates - double[] p11 = toHomogeneousVector(position); - double[] p12 = toHomogeneousVector(position.getAdded(direction)); - double[] p21 = toHomogeneousVector(other.position); - double[] p22 = toHomogeneousVector(other.position - .getAdded(other.direction)); - double[] l1 = getCrossProduct(p11, p12); - double[] l2 = getCrossProduct(p21, p22); - double[] poi = getCrossProduct(l1, l2); - return fromHomogeneousVector(poi); + Point poi = CurveUtils.getIntersection(this, other); + if (poi != null) { + return new Vector(poi); + } + return null; } /** @@ -420,22 +363,23 @@ } /** - * Checks whether this Straight and the provided one are parallel to each - * other. + * Checks whether this {@link Straight} and the provided one are parallel to + * each other. * * @param other - * The Straight to test for parallelism. - * @return true if the direction vectors of this Straight and the provided - * one are parallel, false otherwise. + * The {@link Straight} to test for parallelism. + * @return true if the direction {@link Vector}s of this {@link Straight} + * and the provided one are parallel, false otherwise. */ public boolean isParallelTo(Straight other) { return direction.isParallelTo(other.direction); } /** - * Checks whether this Straight is equal to the provided Straight. Two - * Straights s1 and s2 are equal, if the position vector of s2 is a point on - * s1 and the direction vectors of s1 and s2 are parallel. + * Checks whether this {@link Straight} is equal to the provided + * {@link Straight}. Two {@link Straight}s s1 and s2 are equal, if the + * position {@link Vector} of s2 is a point on s1 and the direction + * {@link Vector}s of s1 and s2 are parallel. * * @see java.lang.Object#equals(java.lang.Object) */ @@ -454,9 +398,9 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; - // return position.hashCode() + direction.hashCode(); } /** Index: src/org/eclipse/gef4/geometry/euclidean/Vector.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/euclidean/Vector.java,v retrieving revision 1.7 diff -u -r1.7 Vector.java --- src/org/eclipse/gef4/geometry/euclidean/Vector.java 17 Nov 2011 22:00:18 -0000 1.7 +++ src/org/eclipse/gef4/geometry/euclidean/Vector.java 9 Dec 2011 16:02:35 -0000 @@ -410,9 +410,9 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; - // return (int) x + (int) y; } /** Index: src/org/eclipse/gef4/geometry/shapes/CubicCurve.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/CubicCurve.java,v retrieving revision 1.7 diff -u -r1.7 CubicCurve.java --- src/org/eclipse/gef4/geometry/shapes/CubicCurve.java 22 Nov 2011 19:47:59 -0000 1.7 +++ src/org/eclipse/gef4/geometry/shapes/CubicCurve.java 9 Dec 2011 16:02:35 -0000 @@ -18,6 +18,7 @@ import org.eclipse.gef4.geometry.Point; import org.eclipse.gef4.geometry.transform.AffineTransform; +import org.eclipse.gef4.geometry.utils.CurveUtils; import org.eclipse.gef4.geometry.utils.PolynomCalculationUtils; import org.eclipse.gef4.geometry.utils.PrecisionUtils; @@ -67,6 +68,28 @@ } /** + * Constructs a new {@link CubicCurve} object with the given sequence of x- + * and y-coordinates of the start-, the first and second control-, and the + * end-point. + * + * @param coordinates + * a sequence of coordinates + * + * @see CubicCurve#CubicCurve(double, double, double, double, double, + * double, double, double) + */ + public CubicCurve(double... coordinates) { + x1 = coordinates[0]; + y1 = coordinates[1]; + ctrl1X = coordinates[2]; + ctrl1Y = coordinates[3]; + ctrl2X = coordinates[4]; + ctrl2Y = coordinates[5]; + x2 = coordinates[6]; + y2 = coordinates[7]; + } + + /** * Constructs a new {@link CubicCurve} object with the given control * {@link Point}s. * @@ -115,22 +138,7 @@ * @see Geometry#contains(Point) */ public boolean contains(Point p) { - // find roots of the x(t) - p.x function: - double D = getX1() - p.x; - double C = 3 * (getCtrl1X() - getX1()); - double B = 3 * (getCtrl2X() - getCtrl1X()) - C; - double A = getX2() - getX1() - B - C; - double[] xts = PolynomCalculationUtils.getCubicRoots(A, B, C, D); - - for (double t : xts) { - // t = PrecisionUtils.round(t); - if (PrecisionUtils.greaterEqual(t, 0) - && PrecisionUtils.smallerEqual(t, 1) - && PrecisionUtils.equal(get(t).y, p.y)) { - return true; - } - } - return false; + return CurveUtils.contains(this, p); } /** @@ -215,10 +223,6 @@ return new Rectangle(new Point(xmin, ymin), new Point(xmax, ymax)); } - private Point ratioPoint(Point p, Point q, double ratio) { - return p.getTranslated(q.getTranslated(p.getNegated()).getScaled(ratio)); - } - /** * Subdivides this {@link CubicCurve} into two {@link CubicCurve}s on the * intervals [0, t] and [t, 1] using the de-Casteljau-algorithm. @@ -228,22 +232,7 @@ * @return the two {@link CubicCurve}s */ public CubicCurve[] split(double t) { - if (t < 0 || t > 1) { - throw new IllegalArgumentException( - "Paramter t is out of range! t = " + t + " !in_range(0,1)"); - } - - Point p10 = ratioPoint(getP1(), getCtrl1(), t); - Point p11 = ratioPoint(getCtrl1(), getCtrl2(), t); - Point p12 = ratioPoint(getCtrl2(), getP2(), t); - Point p20 = ratioPoint(p10, p11, t); - Point p21 = ratioPoint(p11, p12, t); - Point p30 = ratioPoint(p20, p21, t); - - CubicCurve left = new CubicCurve(getP1(), p10, p20, p30); - CubicCurve right = new CubicCurve(p30, p21, p12, getP2()); - - return new CubicCurve[] { left, right }; + return CurveUtils.split(this, t); } /** @@ -256,20 +245,7 @@ * @return the {@link CubicCurve} on the interval [t1, t2] */ public CubicCurve clip(double t1, double t2) { - if (t1 < 0 || t1 > 1) { - throw new IllegalArgumentException( - "Paramter t1 is out of range! t1 = " + t1 - + " !in_range(0,1)"); - } - if (t2 < 0 || t2 > 1) { - throw new IllegalArgumentException( - "Paramter t2 is out of range! t2 = " + t2 - + " !in_range(0,1)"); - } - - CubicCurve right = split(t1)[1]; - double rightT2 = (t2 - t1) / (1 - t1); - return right.split(rightT2)[0]; + return CurveUtils.clip(this, t1, t2); } private static double getArea(Polygon p) { @@ -321,79 +297,6 @@ return new Point[] {}; } - private static Point[] getIntersections(CubicCurve p, double ps, double pe, - CubicCurve q, double qs, double qe) { - double pm = (ps + pe) / 2; - double qm = (qs + qe) / 2; - - // point convergence test - Point pPoi = p.get(pm); - Point qPoi = q.get(qm); - - if (pPoi != null && qPoi != null && pPoi.equals(qPoi)) { - return new Point[] { pPoi }; - } - - // no point convergence yet - // clip to parameter ranges - CubicCurve pc = p.clip(ps, pe); - CubicCurve qc = q.clip(qs, qe); - - // check the control polygons - Polygon pPoly = pc.getControlPolygon(); - Polygon qPoly = qc.getControlPolygon(); - - if (pPoly.intersects(qPoly)) { - // check the polygon's areas - double pArea = getArea(pPoly); - double qArea = getArea(qPoly); - - if (PrecisionUtils.equal(pArea, 0, +2) - && PrecisionUtils.equal(qArea, 0, +2)) { - // return line/line intersection - Point poi = new Line(pc.getP1(), pc.getP2()) - .getIntersection(new Line(qc.getP1(), qc.getP2())); - if (poi != null) { - return new Point[] { poi }; - } - return new Point[] {}; - } - - // areas not small enough - - // do not try to find the intersections of two equal curves - if (pc.equals(qc)) { - return new Point[] {}; - } - - // "split" the curves and do the intersection test recursively - HashSet intersections = new HashSet(); - - intersections.addAll(Arrays.asList(getIntersections(p.clip(ps, pm), - 0, 1, q.clip(qs, qm), 0, 1))); - intersections.addAll(Arrays.asList(getIntersections(p.clip(ps, pm), - 0, 1, q.clip(qm, qe), 0, 1))); - intersections.addAll(Arrays.asList(getIntersections(p.clip(pm, pe), - 0, 1, q.clip(qs, qm), 0, 1))); - intersections.addAll(Arrays.asList(getIntersections(p.clip(pm, pe), - 0, 1, q.clip(qm, qe), 0, 1))); - - // intersections.addAll(Arrays.asList(getIntersections(p, ps, pm, q, - // qs, qm))); - // intersections.addAll(Arrays.asList(getIntersections(p, ps, pm, q, - // qm, qe))); - // intersections.addAll(Arrays.asList(getIntersections(p, pm, pe, q, - // qs, qm))); - // intersections.addAll(Arrays.asList(getIntersections(p, pm, pe, q, - // qm, qe))); - - return intersections.toArray(new Point[] {}); - } - - // no intersections - return new Point[] {}; - } - /** * Returns the points of intersection between this {@link CubicCurve} and * the given other {@link CubicCurve}. @@ -402,7 +305,7 @@ * @return the points of intersection */ public Point[] getIntersections(CubicCurve other) { - return getIntersections(this, 0, 1, other, 0, 1); + return CurveUtils.getIntersections(this, other); } /** @@ -536,7 +439,8 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; } @@ -721,6 +625,12 @@ return p; } + public String toString() { + return "CubicCurve(x1 = " + x1 + ", y1 = " + y1 + ", ctrl1X = " + + ctrl1X + ", ctrl1Y = " + ctrl1Y + ", ctrl2X = " + ctrl2X + + ", ctrl2Y = " + ctrl2Y + ", x2 = " + x2 + ", y2 = " + y2; + } + /** * Get a single {@link Point} on this CubicCurve at parameter t. * @@ -729,24 +639,7 @@ * @return the {@link Point} at parameter t */ public Point get(double t) { - if (!(PrecisionUtils.greaterEqual(t, 0) && PrecisionUtils.smallerEqual( - t, 1))) { - throw new IllegalArgumentException( - "Paramter t is out of range! t = " + t + " !in_range(0,1)"); - } - - // compensate rounding effects - if (t < 0) { - t = 0; - } else if (t > 1) { - t = 1; - } - - double d = 1 - t; - return getP1().getScaled(d * d * d) - .getTranslated(getCtrl1().getScaled(3 * t * d * d)) - .getTranslated(getCtrl2().getScaled(3 * t * t * d)) - .getTranslated(getP2().getScaled(t * t * t)); + return CurveUtils.get(this, t); } } Index: src/org/eclipse/gef4/geometry/shapes/Ellipse.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/Ellipse.java,v retrieving revision 1.16 diff -u -r1.16 Ellipse.java --- src/org/eclipse/gef4/geometry/shapes/Ellipse.java 22 Nov 2011 19:41:55 -0000 1.16 +++ src/org/eclipse/gef4/geometry/shapes/Ellipse.java 9 Dec 2011 16:02:35 -0000 @@ -24,8 +24,7 @@ import org.eclipse.gef4.geometry.utils.PrecisionUtils; /** - * Represents the geometric shape of an ellipse, which is defined by means of - * its enclosing framing rectangle. + * Represents the geometric shape of an ellipse. * * Note that while all manipulations (e.g. within shrink, expand) within this * class are based on double precision, all comparisons (e.g. within contains, @@ -479,10 +478,9 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; - // return (int) ((x + height + 1) * (y + width + 1)) ^ (int) x ^ (int) - // y; } /** Index: src/org/eclipse/gef4/geometry/shapes/Line.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/Line.java,v retrieving revision 1.9 diff -u -r1.9 Line.java --- src/org/eclipse/gef4/geometry/shapes/Line.java 17 Nov 2011 22:00:18 -0000 1.9 +++ src/org/eclipse/gef4/geometry/shapes/Line.java 9 Dec 2011 16:02:35 -0000 @@ -269,9 +269,9 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; - // return (int) x1 + (int) y1 + (int) x2 + (int) y2; } /** Index: src/org/eclipse/gef4/geometry/shapes/Path.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/Path.java,v retrieving revision 1.7 diff -u -r1.7 Path.java --- src/org/eclipse/gef4/geometry/shapes/Path.java 20 Oct 2011 21:04:44 -0000 1.7 +++ src/org/eclipse/gef4/geometry/shapes/Path.java 9 Dec 2011 16:02:35 -0000 @@ -177,6 +177,28 @@ } /** + * @see java.lang.Object#equals(Object obj) + */ + @Override + public boolean equals(Object obj) { + if (obj instanceof Path) { + Path p = (Path) obj; + return delegate.equals(p.delegate); + } + return false; + } + + /** + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive + return 0; + } + + /** * {@link Geometry#intersects(Rectangle)} */ public boolean intersects(Rectangle r) { Index: src/org/eclipse/gef4/geometry/shapes/Polygon.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/Polygon.java,v retrieving revision 1.10 diff -u -r1.10 Polygon.java --- src/org/eclipse/gef4/geometry/shapes/Polygon.java 17 Nov 2011 22:00:18 -0000 1.10 +++ src/org/eclipse/gef4/geometry/shapes/Polygon.java 9 Dec 2011 16:02:35 -0000 @@ -650,9 +650,9 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; - // return PointListUtils.getHashCode(points); } /** Index: src/org/eclipse/gef4/geometry/shapes/Polyline.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/Polyline.java,v retrieving revision 1.6 diff -u -r1.6 Polyline.java --- src/org/eclipse/gef4/geometry/shapes/Polyline.java 17 Nov 2011 22:00:18 -0000 1.6 +++ src/org/eclipse/gef4/geometry/shapes/Polyline.java 9 Dec 2011 16:02:35 -0000 @@ -188,7 +188,8 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; } Index: src/org/eclipse/gef4/geometry/shapes/QuadraticCurve.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/QuadraticCurve.java,v retrieving revision 1.6 diff -u -r1.6 QuadraticCurve.java --- src/org/eclipse/gef4/geometry/shapes/QuadraticCurve.java 17 Nov 2011 22:00:18 -0000 1.6 +++ src/org/eclipse/gef4/geometry/shapes/QuadraticCurve.java 9 Dec 2011 16:02:35 -0000 @@ -17,6 +17,7 @@ import org.eclipse.gef4.geometry.Point; import org.eclipse.gef4.geometry.transform.AffineTransform; +import org.eclipse.gef4.geometry.utils.CurveUtils; import org.eclipse.gef4.geometry.utils.PolynomCalculationUtils; import org.eclipse.gef4.geometry.utils.PrecisionUtils; @@ -48,6 +49,19 @@ } /** + * Constructs a new {@link QuadraticCurve} from the given sequence of + * {@link Point}s formed by start-, control-, and end-point. + * + * @param points + * the control {@link Point}s + * + * @see QuadraticCurve#QuadraticCurve(Point, Point, Point) + */ + public QuadraticCurve(Point... points) { + this(points[0], points[1], points[2]); + } + + /** * Constructs a new QuadraticCurve object from the given point coordinates. * * @param x1 @@ -71,6 +85,21 @@ } /** + * Constructs a new {@link QuadraticCurve} from the given sequence of x- and + * y-coordinates of the start-, the control-, and the end-point. + * + * @param coordinates + * a sequence containing the x- and y-coordinates + * + * @see QuadraticCurve#QuadraticCurve(double, double, double, double, + * double, double) + */ + public QuadraticCurve(double... coordinates) { + this(coordinates[0], coordinates[1], coordinates[2], coordinates[3], + coordinates[4], coordinates[5]); + } + + /** * Get the control point. * * @return a Point object representing the control point @@ -161,7 +190,8 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; } @@ -270,23 +300,7 @@ * @return the {@link Point} at parameter t */ public Point get(double t) { - if (!(PrecisionUtils.greaterEqual(t, 0) && PrecisionUtils.smallerEqual( - t, 1))) { - throw new IllegalArgumentException( - "Paramter t is out of range! t = " + t + " !in_range(0,1)"); - } - - // compensate rounding effects - if (t < 0) { - t = 0; - } else if (t > 1) { - t = 1; - } - - return new Point(t * (t * (getP1().x - 2 * getCtrl().x + getP2().x)) - + 2 * (t * (getCtrl().x - getP1().x)) + getP1().x, t - * (t * (getP1().y - 2 * getCtrl().y + getP2().y)) + 2 - * (t * (getCtrl().y - getP1().y)) + getP1().y); + return CurveUtils.get(this, t); } /** @@ -297,19 +311,7 @@ * @return true if p lies on the curve, false otherwise */ public boolean contains(Point p) { - // find roots of the x(t) - p.x function: - double[] xts = PolynomCalculationUtils.getQuadraticRoots(getX1() - 2 - * getCtrlX() + getX2(), 2 * getCtrlX() - 2 * getX1(), getX1() - - p.x); - - for (double t : xts) { - // t = PrecisionUtils.round(t); - if (PrecisionUtils.greaterEqual(t, 0) - && PrecisionUtils.smallerEqual(t, 1)) { - return true; - } - } - return false; + return CurveUtils.contains(this, p); } /** @@ -585,10 +587,6 @@ return false; } - private Point ratioPoint(Point p, Point q, double ratio) { - return p.getTranslated(q.getTranslated(p.getNegated()).getScaled(ratio)); - } - /** * Splits this QuadraticCurve using the de Casteljau algorithm at parameter * t into two separate QuadraticCurve objects. The returned @@ -600,19 +598,7 @@ * [0, t] 2. [t, 1] */ public QuadraticCurve[] split(double t) { - if (t < 0 || t > 1) { - throw new IllegalArgumentException( - "Paramter t is out of range! t = " + t + " !in_range(0,1)"); - } - - Point left1 = ratioPoint(getP1(), getCtrl(), t); - Point right1 = ratioPoint(getCtrl(), getP2(), t); - Point split = ratioPoint(left1, right1, t); - - QuadraticCurve left = new QuadraticCurve(getP1(), left1, split); - QuadraticCurve right = new QuadraticCurve(split, right1, getP2()); - - return new QuadraticCurve[] { left, right }; + return CurveUtils.split(this, t); } /** @@ -625,20 +611,7 @@ * @return the {@link QuadraticCurve} on the interval [t1, t2] */ public QuadraticCurve clip(double t1, double t2) { - if (t1 < 0 || t1 > 1) { - throw new IllegalArgumentException( - "Paramter t1 is out of range! t1 = " + t1 - + " !in_range(0,1)"); - } - if (t2 < 0 || t2 > 1) { - throw new IllegalArgumentException( - "Paramter t2 is out of range! t2 = " + t2 - + " !in_range(0,1)"); - } - - QuadraticCurve right = split(t1)[1]; - double rightT2 = (t2 - t1) / (1 - t1); - return right.split(rightT2)[0]; + return CurveUtils.clip(this, t1, t2); } } Index: src/org/eclipse/gef4/geometry/shapes/Rectangle.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/Rectangle.java,v retrieving revision 1.14 diff -u -r1.14 Rectangle.java --- src/org/eclipse/gef4/geometry/shapes/Rectangle.java 18 Nov 2011 22:08:35 -0000 1.14 +++ src/org/eclipse/gef4/geometry/shapes/Rectangle.java 9 Dec 2011 16:02:35 -0000 @@ -714,10 +714,9 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; - // return (int) ((x + height + 1) * (y + width + 1)) ^ (int) x ^ (int) - // y; } /** Index: src/org/eclipse/gef4/geometry/shapes/RoundedRectangle.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/RoundedRectangle.java,v retrieving revision 1.5 diff -u -r1.5 RoundedRectangle.java --- src/org/eclipse/gef4/geometry/shapes/RoundedRectangle.java 17 Nov 2011 22:00:18 -0000 1.5 +++ src/org/eclipse/gef4/geometry/shapes/RoundedRectangle.java 9 Dec 2011 16:02:35 -0000 @@ -214,7 +214,8 @@ */ @Override public int hashCode() { - // calculating a better hashCode is not possible + // calculating a better hashCode is not possible, because due to the + // imprecision, equals() is no longer transitive return 0; } Index: src/org/eclipse/gef4/geometry/utils/CurveUtils.java =================================================================== RCS file: src/org/eclipse/gef4/geometry/utils/CurveUtils.java diff -N src/org/eclipse/gef4/geometry/utils/CurveUtils.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/gef4/geometry/utils/CurveUtils.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,1268 @@ +/******************************************************************************* + * Copyright (c) 2011 itemis AG and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Matthias Wienand (itemis AG) - initial API and implementation + * + *******************************************************************************/ +package org.eclipse.gef4.geometry.utils; + +import java.util.HashSet; + +import org.eclipse.gef4.geometry.Point; +import org.eclipse.gef4.geometry.euclidean.Straight; +import org.eclipse.gef4.geometry.shapes.CubicCurve; +import org.eclipse.gef4.geometry.shapes.Line; +import org.eclipse.gef4.geometry.shapes.QuadraticCurve; +import org.eclipse.gef4.geometry.shapes.Rectangle; + +/** + * The {@link CurveUtils} class provides functionality that can be used for + * linear curves ({@link Line}, {@link Straight}), as well as quadratic and + * cubic Bezier curves. + * + * @author wienand + * + */ +public class CurveUtils { + + /** + * The Vector3D class implements a three dimensional vector (components x, + * y, z) with its standard operations: addition and multiplication (scalar, + * dot-product, cross-product). + * + * It is used to represent planar lines and planar points which are + * represented by three dimensional planes and three dimensional lines + * through the origin, respectively. + * + * @author wienand + */ + private static final class Vector3D { + public double x, y, z; + + /** + * Constructs a new {@link Vector3D} from the given {@link Point}, + * setting z to 1. + * + * @param p + */ + public Vector3D(Point p) { + this(p.x, p.y, 1); + } + + /** + * Constructs a new {@link Vector3D} object with the given component + * values. + * + * @param px + * @param py + * @param pz + */ + public Vector3D(double px, double py, double pz) { + x = px; + y = py; + z = pz; + } + + /** + * Returns a copy of this {@link Vector3D}. + * + * @return a copy of this {@link Vector3D} + */ + public Vector3D getCopy() { + return new Vector3D(x, y, z); + } + + @Override + public boolean equals(Object other) { + if (other instanceof Vector3D) { + Vector3D o = (Vector3D) other; + return this.toPoint().equals(o.toPoint()); + } + return false; + } + + /** + * Returns a new {@link Vector3D} object with its components set to the + * sum of the individual x, y and z components of this {@link Vector3D} + * and the given other {@link Vector3D}. + * + * @param other + * @return a new {@link Vector3D} object representing the sum of this + * {@link Vector3D} and the given other {@link Vector3D} + */ + public Vector3D getAdded(Vector3D other) { + return new Vector3D(this.x + other.x, this.y + other.y, this.z + + other.z); + } + + /** + * Returns a new {@link Vector3D} object with its components set to the + * difference of the individual x, y and z components of this + * {@link Vector3D} and the given other {@link Vector3D}. + * + * @param other + * @return a new {@link Vector3D} object representing the difference of + * this {@link Vector3D} and the given other {@link Vector3D} + */ + public Vector3D getSubtracted(Vector3D other) { + return new Vector3D(this.x - other.x, this.y - other.y, this.z + - other.z); + } + + /** + * Returns a new {@link Vector3D} object with its components set to the + * x, y and z components of this {@link Vector3D} scaled by the given + * factor. + * + * @param f + * The scaling factor. + * @return a new {@link Vector3D} object with its components set to the + * x, y and z components of this {@link Vector3D} scaled by the + * given factor + */ + public Vector3D getScaled(double f) { + return new Vector3D(x * f, y * f, z * f); + } + + /** + * Returns a new {@link Vector3D} object with its components set to the + * given ratio between this {@link Vector3D} and the given other + * {@link Vector3D}. + * + * @param other + * The other {@link Vector3D}. + * @param t + * The ratio. + * @return a new {@link Vector3D} object with its components set to the + * given ratio between this {@link Vector3D} and the given other + * {@link Vector3D} + */ + public Vector3D getRatio(Vector3D other, double t) { + return getAdded(other.getSubtracted(this).getScaled(t)); + } + + /** + * Returns a new {@link Vector3D} object that has the same direction as + * this {@link Vector3D} but the x- and y-components are normalized so + * that x*x + y*y = 1. + * + * @return a new {@link Vector3D} object with x- and y-components + * normalized to fulfill x*x + y*y = 1. + */ + public Vector3D getLineNormalized() { + double f = Math.sqrt(x * x + y * y); + if (f == 0) { + return null; + } + return new Vector3D(x / f, y / f, z / f); + } + + /** + * Returns a new {@link Vector3D} object that is the cross product of + * this and the given other {@link Vector3D}. + * + * @param other + * @return a new {@link Vector3D} object that is the cross product of + * this and the given other {@link Vector3D} + */ + public Vector3D getCrossed(Vector3D other) { + return new Vector3D(this.y * other.z - this.z * other.y, this.z + * other.x - this.x * other.z, this.x * other.y - this.y + * other.x); + } + + /** + * Returns the dot-product of this and the given other {@link Vector3D}. + * + * @param other + * @return the dot-product of this and the given other {@link Vector3D} + */ + public double getDot(Vector3D other) { + return this.x * other.x + this.y * other.y + this.z * other.z; + } + + /** + * Returns a new {@link Point} object that is represented by this + * {@link Vector3D}. + * + * @return a new {@link Point} object that is represented by this + * {@link Vector3D} + */ + public Point toPoint() { + if (this.z == 0) { + return null; + } + return new Point(this.x / this.z, this.y / this.z); + } + } + + /** + * The {@link BezierCurve} provides a common representation for arbitrary + * Bezier curves. + * + * It can evaluate points on the curve, check points for containment and + * compute intersection points for one curve with another. + * + * It uses homogeneous coordinates (represented by {@link Vector3D} objects) + * to represent planar lines and points and to compute line/line + * intersections and point/line distances. + * + * @author wienand + */ + private static final class BezierCurve { + + private static final double END_POINTS_CHECK_AREA = 1; + + private Vector3D[] points; + private double s = 0, e = 1; + + /** + * Constructs a new {@link BezierCurve} object from the given control + * points. + * + * @param controlPoints + */ + public BezierCurve(Point... controlPoints) { + points = new Vector3D[controlPoints.length]; + for (int i = 0; i < points.length; i++) { + points[i] = new Vector3D(controlPoints[i].x, + controlPoints[i].y, 1); + } + } + + /** + * Constructs a new {@link BezierCurve} object from the given control + * points. + * + * Note that a Point(2, 3) is represented by a Vector3D(2, 3, 1). So for + * a Point(x, y) the corresponding vector is Vector(x, y, 1). + * + * @param controlPoints + */ + public BezierCurve(Vector3D... controlPoints) { + points = new Vector3D[controlPoints.length]; + for (int i = 0; i < points.length; i++) { + points[i] = controlPoints[i].getCopy(); + } + } + + /** + * Constructs a new {@link BezierCurve} from the given + * {@link QuadraticCurve}. + * + * @param c + */ + public BezierCurve(QuadraticCurve c) { + this(c.getP1(), c.getCtrl(), c.getP2()); + } + + /** + * Constructs a new {@link BezierCurve} from the given + * {@link CubicCurve}. + * + * @param c + */ + public BezierCurve(CubicCurve c) { + this(c.getP1(), c.getCtrl1(), c.getCtrl2(), c.getP2()); + } + + /** + * Returns a copy of this {@link BezierCurve}'s points. + * + * @return a copy of this {@link BezierCurve}'s points + */ + private Vector3D[] getPointsCopy() { + Vector3D[] copy = new Vector3D[points.length]; + for (int i = 0; i < points.length; i++) { + copy[i] = points[i].getCopy(); + } + return copy; + } + + /** + * Constructs the explicit Bézier curve for this curve's x-components. + * + * @return the explicit Bézier curve for this curve's x-components + */ + public BezierCurve getExplicitX() { + Vector3D[] explicit = new Vector3D[points.length]; + + for (int i = 0; i < points.length; i++) { + explicit[i] = new Vector3D((double) i + / ((double) points.length - 1d), points[i].toPoint().x, + 1); + } + + return new BezierCurve(explicit); + } + + /** + * Constructs the explicit Bézier curve for this curve's y-components. + * + * @return the explicit Bézier curve for this curve's y-components + */ + public BezierCurve getExplicitY() { + Vector3D[] explicit = new Vector3D[points.length]; + + for (int i = 0; i < points.length; i++) { + explicit[i] = new Vector3D((double) i + / ((double) points.length - 1d), points[i].toPoint().y, + 1); + } + + return new BezierCurve(explicit); + } + + /** + * Checks if all y-components of this {@link BezierCurve}'s points have + * the same sign. + * + * Returns true if either all y-components are positive or all + * y-components are negative. + * + * Returns false, otherwise. + * + * @param c + * @return true if all y-components are either positive or negative, + * otherwise false + */ + private static boolean sameSign(BezierCurve c) { + double sign = c.points[0].toPoint().y; + if (sign == 0) { + return false; + } + for (int i = 1; i < c.points.length; i++) { + if (sign < 0) { + if (c.points[i].toPoint().y >= 0) { + return false; + } + } else if (sign > 0) { + if (c.points[i].toPoint().y <= 0) { + return false; + } + } + } + return true; + } + + /** + * Used to store parameter values in a HashSet with an imprecise + * equals() operation. + * + * @author wienand + */ + private static final class ImpreciseDouble { + private double value; + private int shift; + + public ImpreciseDouble(double a) { + value = a; + shift = 1; + } + + /** + * Returns the double value represented by this + * {@link ImpreciseDouble}. + * + * @return the double value represented by this + * {@link ImpreciseDouble} + */ + public double getValue() { + return value; + } + + @Override + public boolean equals(Object obj) { + if (obj instanceof ImpreciseDouble) { + ImpreciseDouble o = (ImpreciseDouble) obj; + return PrecisionUtils.equal(value, o.value, shift); + } + return false; + } + } + + /** + * Calculates the roots of the given explicit {@link BezierCurve} on the + * interval [a;b]. + * + * You can get an explicit {@link BezierCurve} from an arbitrary + * {@link BezierCurve} for either its x- or y-components using the + * {@link BezierCurve#getExplicitX()} or + * {@link BezierCurve#getExplicitY()} methods, respectively. + * + * @param c + * @param a + * start of the parameter interval + * @param b + * end of the parameter interval + * @return the roots of the given explicit {@link BezierCurve} on the + * interval [a;b] + */ + private static HashSet getRoots(BezierCurve c, + double a, double b) { + BezierCurve clipped = c.getClipped(a, b); + + if (sameSign(clipped)) { + return new HashSet(); + } + + if (PrecisionUtils.equal(a, b, +2)) { + HashSet root = new HashSet(); + root.add(new ImpreciseDouble((a + b) / 2)); + return root; + } + + HashSet left = getRoots(c, a, (a + b) / 2); + HashSet right = getRoots(c, (a + b) / 2, b); + + left.addAll(right); + + return left; + } + + /** + * Calculates the roots of the given {@link BezierCurve} which is + * expected to be explicit. + * + * You can get an explicit {@link BezierCurve} from an arbitrary + * {@link BezierCurve} for either its x- or y-components using the + * {@link BezierCurve#getExplicitX()} or + * {@link BezierCurve#getExplicitY()} methods, respectively. + * + * @param c + * @return the roots of the given explicit {@link BezierCurve} + */ + private static double[] getRoots(BezierCurve c) { + // TODO: check that the given BezierCurve is explicit + HashSet roots = getRoots(c, 0, 1); + ImpreciseDouble[] rootsFuzzyDouble = roots + .toArray(new ImpreciseDouble[] {}); + double[] rootsDouble = new double[rootsFuzzyDouble.length]; + for (int i = 0; i < rootsDouble.length; i++) { + rootsDouble[i] = rootsFuzzyDouble[i].getValue(); + } + return rootsDouble; + } + + /** + * Computes all real roots of this {@link BezierCurve}'s x(t) function. + * + * @return all real roots of this {@link BezierCurve}'s x(t) function + */ + public double[] getRootsX() { + return getRoots(getExplicitX()); + } + + /** + * Computes all real roots of this {@link BezierCurve}'s y(t) function. + * + * @return all real roots of this {@link BezierCurve}'s y(t) function + */ + public double[] getRootsY() { + return getRoots(getExplicitY()); + } + + /** + * Computes the real planar {@link Point}s for this {@link BezierCurve}. + * + * @return the real planar {@link Point}s for this {@link BezierCurve} + */ + public Point[] getRealPoints() { + Point[] realPoints = new Point[points.length]; + for (int i = 0; i < points.length; i++) { + realPoints[i] = points[i].toPoint(); + } + return realPoints; + } + + /** + * Returns the {@link Point} at the given parameter value t. + * + * @param t + * Parameter value + * @return {@link Point} at parameter value t + */ + public Vector3D get(double t) { + if (t < 0 || t > 1) { + throw new IllegalArgumentException("t out of range"); + } + + // using horner's scheme: + int n = points.length; + if (n < 1) { + return null; + } + + double bn = 1, tn = 1, d = 1d - t; + Vector3D pn = points[0].getScaled(bn * tn); + for (int i = 1; i < n; i++) { + bn = bn * (n - i) / i; + tn = tn * t; + pn = pn.getScaled(d).getAdded(points[i].getScaled(bn * tn)); + } + + return pn; + } + + /** + * Creates a new {@link BezierCurve} with all points translated by the + * given {@link Point}. + * + * @param p + * @return a new {@link BezierCurve} with all points translated by the + * given {@link Point} + */ + public BezierCurve getTranslated(Point p) { + Point[] translated = new Point[points.length]; + + for (int i = 0; i < translated.length; i++) { + translated[i] = points[i].toPoint().getTranslated(p); + } + + return new BezierCurve(translated); + } + + /** + * Returns true if the given {@link Point} lies on this + * {@link BezierCurve}. Returns false, otherwise. + * + * @param p + * the {@link Point} to test for containment + * @return true if the {@link Point} is contained, false otherwise + */ + public boolean contains(Point p) { + if (p == null) { + return false; + } + + BezierCurve test = this.getTranslated(p.getNegated()); + double[] xts = test.getRootsX(); + double[] yts = test.getRootsY(); + + for (double xt : xts) { + for (double yt : yts) { + if (PrecisionUtils.equal(xt, yt)) { + return true; + } + } + } + return false; + } + + /** + * Subdivides this {@link BezierCurve} at the given parameter value t + * into two new {@link BezierCurve}. The left-of t and the right-of t + * {@link BezierCurve} objects. + * + * @param t + * Parameter value + * @return The left-of t and right-of t {@link BezierCurve} objects + */ + public BezierCurve[] split(double t) { + Vector3D[] leftPoints = new Vector3D[points.length]; + Vector3D[] rightPoints = new Vector3D[points.length]; + + Vector3D[] ratioPoints = getPointsCopy(); + + for (int i = 0; i < points.length; i++) { + leftPoints[i] = ratioPoints[0]; + rightPoints[points.length - 1 - i] = ratioPoints[points.length + - 1 - i]; + + for (int j = 0; j < points.length - i - 1; j++) { + ratioPoints[j] = ratioPoints[j].getRatio( + ratioPoints[j + 1], t); + } + } + + return new BezierCurve[] { new BezierCurve(leftPoints), + new BezierCurve(rightPoints) }; + } + + /** + * Returns a new {@link BezierCurve} object representing this bezier + * curve on the interval [s;e]. + * + * @return a new {@link BezierCurve} object representing this bezier + * curve on the interval [s;e] + */ + public BezierCurve getClipped() { + BezierCurve right = split(s)[1]; + double rightT2 = (e - s) / (1 - s); + return right.split(rightT2)[0]; + } + + /** + * Returns a new {@link BezierCurve} object representing this bezier + * curve on the interval [s;e]. + * + * @param s + * @param e + * @return a new {@link BezierCurve} object representing this bezier + * curve on the interval [s;e] + */ + public BezierCurve getClipped(double s, double e) { + BezierCurve right = split(s)[1]; + double rightT2 = (e - s) / (1 - s); + return right.split(rightT2)[0]; + } + + /** + * Checks if the parameters are considered equal on both curves and adds + * the point of intersection of the mid lines of the curves. + * + * @param p + * @param q + * @param intersections + * @return true if the parameters are considered equal and false + * otherwise + */ + private static boolean parameterConvergence(BezierCurve p, + BezierCurve q, HashSet intersections) { + if (PrecisionUtils.equal(p.s, p.e, +2)) { + Vector3D poi = p.get((p.s + p.e) / 2); + intersections.add(poi); + return true; + } else if (PrecisionUtils.equal(q.s, q.e, +2)) { + Vector3D poi = q.get((q.s + q.e) / 2); + intersections.add(poi); + return true; + } + return false; + } + + /** + * Accomplishes an end-points-check that will determine the bezier + * clipping algorithm early if two end-points of the given + * {@link BezierCurve} are considered equal. + * + * Calculates the area of the bounding boxes of both curves and checks + * if that maximum area is below some constant value + * END_POINTS_CHECK_AREA. That's why an end-point-intersection is only + * added for very small curve segments. + * + * @param p + * @param q + * @param intersections + * @return true if an end-point intersection was added to the + * intersections {@link HashSet}, otherwise false + */ + private static boolean endPointsCheck(BezierCurve p, BezierCurve q, + HashSet intersections) { + Rectangle pBounds = p.getControlBounds(); + Rectangle qBounds = q.getControlBounds(); + double area = Math.max(pBounds.getWidth() * pBounds.getHeight(), + qBounds.getWidth() * qBounds.getHeight()); + + Vector3D poi = p.get(p.s); + if (poi.equals(q.get(q.s))) { + intersections.add(poi); + if (area < END_POINTS_CHECK_AREA) { + return true; + } + } + if (poi.equals(q.get(q.e))) { + intersections.add(poi); + if (area < END_POINTS_CHECK_AREA) { + return true; + } + } + poi = q.get(q.s); + if (poi.equals(p.get(p.e))) { + intersections.add(poi); + if (area < END_POINTS_CHECK_AREA) { + return true; + } + } + poi = q.get(q.e); + if (poi.equals(p.get(p.e))) { + intersections.add(poi); + if (area < END_POINTS_CHECK_AREA) { + return true; + } + } + return false; + } + + /** + * Returns the bounds of the control polygon of this {@link BezierCurve} + * . + * + * @return a {@link Rectangle} representing the bounds of the control + * polygon of this {@link BezierCurve} + */ + public Rectangle getControlBounds() { + Point[] realPoints = new Point[points.length]; + for (int i = 0; i < points.length; i++) { + realPoints[i] = points[i].toPoint(); + } + + double xmin = realPoints[0].x, xmax = realPoints[0].x, ymin = realPoints[0].y, ymax = realPoints[0].y; + + for (int i = 1; i < points.length; i++) { + if (points[i].x < xmin) { + xmin = points[i].x; + } else if (points[i].x > xmax) { + xmax = points[i].x; + } + + if (points[i].y < ymin) { + ymin = points[i].y; + } else if (points[i].y > ymax) { + ymax = points[i].y; + } + } + + return new Rectangle(xmin, ymin, xmax - xmin, ymax - ymin); + } + + /** + * Calculates and returns the fat line of the given {@link BezierCurve}, + * represented in terms of two delimiting lines Lmin and Lmax. + * + * @param curve + * @return an array containing Lmin and Lmax + */ + private static Vector3D[] findFatLine(BezierCurve curve) { + Vector3D Lmid = curve.points[0] + .getCrossed(curve.points[curve.points.length - 1]); + + Vector3D Lmin = Lmid.getCopy(); + Vector3D Lmax = Lmid.getCopy(); + + double a = Lmid.x; + double b = Lmid.y; + + for (int i = 1; i < curve.points.length - 1; i++) { + double c = -a * curve.points[i].x - b * curve.points[i].y; + + if (c < Lmin.z) { + Lmin.z = c; + } else if (c > Lmax.z) { + Lmax.z = c; + } + } + + return new Vector3D[] { Lmin, Lmax }; + } + + /** + * Generates the difference points of this {@link BezierCurve} to the + * given line. + * + * The difference points are the control points of a Bezier curve that + * yields the signed difference of the point on this curve at a + * determinate parameter value to the given line. + * + * @param line + * @return the difference curve's control points + */ + private Vector3D[] genDifferencePoints(Vector3D line) { + Vector3D[] D = new Vector3D[points.length]; + for (int i = 0; i < points.length; i++) { + D[i] = new Vector3D( + (double) (i) / (double) (points.length - 1), + line.getDot(points[i]), 1); + } + return D; + } + + /** + * Generates the difference lines of this {@link BezierCurve} with the + * given difference points. + * + * The difference lines are the lines through the relative difference + * point (given by an index) and another difference point. + * + * For example: If you have three difference points D[0], D[1], D[2] and + * the relative set to 0, than you get the lines Line(D[0], D[1]) and + * Line(D[0], D[2]). + * + * @param points + * @param relative + * @return the difference lines through the given relative and the other + * given difference points. + */ + private static Vector3D[] genDifferenceLines(Vector3D[] points, + int relative) { + // get last point in position + int lastPointIdx = points.length - 1; + Vector3D rel = points[relative]; + points[relative] = points[lastPointIdx]; + + Vector3D[] lines = new Vector3D[lastPointIdx]; + for (int i = 0; i < lastPointIdx; i++) { + lines[i] = rel.getCrossed(points[i]); + } + + // re-set relative point + points[relative] = rel; + + return lines; + } + + /** + * Returns the points of intersection of the given lines with the x + * axes. + * + * @param lines + * @return the points of intersection of the given lines with the x axes + */ + private static Vector3D[] getXIntersections(Vector3D[] lines) { + Vector3D[] xi = new Vector3D[lines.length]; + for (int i = 0; i < lines.length; i++) { + xi[i] = new Vector3D(-lines[i].z, 0, lines[i].x); + } + return xi; + } + + /** + * Returns the minimum possible clip value for the given difference + * lines. + * + * It therefore computes the intersection points with the x axes of the + * given lines and walks through them to find the smallest value x that + * is 0 <= x <= 1. + * + * @param lines + * @return the minimum possible clip value for the given difference + * lines + */ + private double getMinimumClipValue(Vector3D[] lines) { + double min = 1; + boolean set = false; + + Vector3D[] xi = getXIntersections(lines); + + for (int i = 0; i < xi.length; i++) { + double x = xi[i].z == 0 ? -1 : xi[i].x / xi[i].z; + if (x > 0 && x < min) { + set = true; + min = x; + } + } + + return set ? min : 0; + } + + /** + * Returns the maximum possible clip value for the given difference + * lines. + * + * It therefore computes the intersection points with the x axes of the + * given lines and walks through them to find the largest value x that + * is 0 <= x <= 1. + * + * @param lines + * @return the maximum possible clip value for the given difference + * lines + */ + private double getMaximumClipValue(Vector3D[] lines) { + double max = 0; + boolean set = false; + + Vector3D[] xi = getXIntersections(lines); + + for (int i = 0; i < xi.length; i++) { + double x = xi[i].z == 0 ? 2 : xi[i].x / xi[i].z; + if (x < 1 && x > max) { + set = true; + max = x; + } + } + + return set ? max : 1; + } + + /** + * Returns true if the y component of all of the given point is below + * zero, false otherwise. + * + * @param D + * @return true if the y component of all of the given point is below + * zero, false otherwise + */ + private static boolean allBelowZero(Vector3D[] D) { + for (int i = 0; i < D.length; i++) { + if (D[i].y >= 0) { + return false; + } + } + return true; + } + + /** + * Clips the {@link BezierCurve} at the given line, so that all parts of + * the curve's control polygon below the given line (i.e. with negative + * distance) are removed. + * + * @param line + */ + private void clipAtLine(Vector3D line) { + Vector3D[] D = genDifferencePoints(line); + + // if all difference values are below zero, the whole curve is + // outside of the fat line and may not be clipped. + if (allBelowZero(D)) { + // make parameter range invalid, so that recursion is aborted + e = 0; + s = 1; + return; + } + + // if the first control point lies outside of the fat line, a new + // lower interval bound has to be computed + if (D[0].y < 0) { + Vector3D[] L0 = genDifferenceLines(D, 0); + double ns = getMinimumClipValue(L0); + if (ns > s && !PrecisionUtils.equal(ns, s, +4)) { + s = ns; + } + } + + // if the last control point lies outside of the fat line, a new + // higher bound has to be computed + if (D[D.length - 1].y < 0) { + Vector3D[] Ln = genDifferenceLines(D, D.length - 1); + double ne = getMaximumClipValue(Ln); + if (ne < e && !PrecisionUtils.equal(ne, e, +4)) { + e = ne; + } + } + } + + /** + * Clips this {@link BezierCurve} to the fat line that is given by the + * Lmin and Lmax lines. + * + * The curve is considered to lie in the positive half space of each + * line, so that negative distances indicate parts of the curve that are + * outside of the fat line. + * + * @param Lmin + * @param Lmax + */ + private void clipToFatLine(Vector3D Lmin, Vector3D Lmax) { + // scale Lmin by -1 so that the curve lies in the positive half + // space of each line; this allows the fat line clipping to be + // performed in the same way for both, Lmin and Lmax. + clipAtLine(Lmin.getScaled(-1)); + clipAtLine(Lmax); + } + + /** + * Computes and returns the points of intersection between this + * {@link BezierCurve} and the given other {@link BezierCurve}. + * + * @param other + * @return the intersections between this {@link BezierCurve} and the + * given other {@link BezierCurve} + */ + public HashSet getIntersections(BezierCurve other) { + HashSet intersections = new HashSet(); + + BezierCurve thisClipped = this.getClipped(); + BezierCurve otherClipped = other.getClipped(); + + if (parameterConvergence(this, other, intersections)) { + // one exact intersection + return intersections; + } + + if (endPointsCheck(thisClipped, otherClipped, intersections)) { + // hopefully just one intersection + return intersections; + } + + // calculate first fat line + Vector3D[] fatLine = findFatLine(otherClipped); + thisClipped.clipToFatLine(fatLine[0], fatLine[1]); + + // re-calculate s and e from thisClipped + double news = s + thisClipped.s * (e - s); + double newe = s + thisClipped.e * (e - s); + double ratio = (newe - news) / (e - s); + s = news; + e = newe; + + if (ratio < 0) { + // no intersections + return intersections; + } else if (ratio > 0.8) { + // split longer curve and find intersections for both halves + if ((e - s) > (other.e - other.s)) { + double ts = s, te = e, tm = (s + e) / 2; + double os = other.s, oe = other.e; + s = ts; + e = tm; + intersections.addAll(this.getIntersections(other)); + other.s = os; + other.e = oe; + s = tm; + e = te; + intersections.addAll(this.getIntersections(other)); + s = ts; + e = te; + } else { + double os = other.s, oe = other.e, om = (os + oe) / 2; + double ts = s, te = e; + other.s = os; + other.e = om; + intersections.addAll(other.getIntersections(this)); + s = ts; + e = te; + other.s = om; + other.e = oe; + intersections.addAll(other.getIntersections(this)); + other.s = os; + other.e = oe; + } + + return intersections; + } else { + // clipped more than 20% + return other.getIntersections(this); + } + } + } + + /** + * Computes and returns the points of intersection between two + * {@link CubicCurve}s. + * + * @param p + * the first {@link CubicCurve} to intersect + * @param q + * the second {@link CubicCurve} to intersect + * @return the intersections between two {@link CubicCurve}s + */ + public static Point[] getIntersections(CubicCurve p, CubicCurve q) { + HashSet intersections = new BezierCurve(p) + .getIntersections(new BezierCurve(q)); + + HashSet pois = new HashSet(); + for (CurveUtils.Vector3D poi : intersections) { + if (poi.z != 0) { + pois.add(poi.toPoint()); + } + } + + return pois.toArray(new Point[] {}); + } + + /** + * Computes the {@link Point} of intersection of two {@link Straight}s. + * + * @param s1 + * the first {@link Straight} to test for intersection + * @param s2 + * the second {@link Straight} to test for intersection + * @return the {@link Point} of intersection if it exists, null + * otherwise + */ + public static Point getIntersection(Straight s1, Straight s2) { + Vector3D l1 = new Vector3D(s1.position.toPoint()) + .getCrossed(new Vector3D(s1.position.getAdded(s1.direction) + .toPoint())); + Vector3D l2 = new Vector3D(s2.position.toPoint()) + .getCrossed(new Vector3D(s2.position.getAdded(s2.direction) + .toPoint())); + + return l1.getCrossed(l2).toPoint(); + } + + /** + * Computes the signed distance of the third {@link Point} to the line + * through the first two {@link Point}s. + * + * The signed distance is positive if the three {@link Point}s are in + * counter-clockwise order and negative if the {@link Point}s are in + * clockwise order. It is zero if the third {@link Point} lies on the line. + * + * If the first two {@link Point}s do not form a line (i.e. they are equal) + * this function returns the distance of the first and the last + * {@link Point}. + * + * @param p + * the start-{@link Point} of the line + * @param q + * the end-{@link Point} of the line + * @param r + * the relative {@link Point} to test for + * @return the signed distance of {@link Point} r to the line through + * {@link Point}s p and q + */ + public static double getSignedDistance(Point p, Point q, Point r) { + Vector3D normalizedLine = new Vector3D(p).getCrossed(new Vector3D(q)) + .getLineNormalized(); + + if (normalizedLine == null) { + return p.getDistance(r); + } + + double dot = normalizedLine.getDot(new Vector3D(r)); + return -dot; + } + + /** + * Returns the signed distance of the {@link Point} to the {@link Straight}. + * + * {@link Point}s that are to the left of the {@link Straight} in the + * direction of the {@link Straight}'s direction vector have a positive + * distance whereas {@link Point}s to the right of the {@link Straight} in + * the direction of the {@link Straight}'s direction vector have a negative + * distance. + * + * The absolute value of the signed distance is the actual distance of the + * {@link Point} to the {@link Straight}. + * + * @param s + * @param p + * @return the signed distance of the {@link Point} to the {@link Straight} + * + * @see CurveUtils#getSignedDistance(Point, Point, Point) + */ + public static double getSignedDistance(Straight s, Point p) { + return getSignedDistance(s.position.toPoint(), + s.position.getAdded(s.direction).toPoint(), p); + } + + /** + * Tests if the given {@link Point} lies on the given {@link CubicCurve}. + * + * @param c + * the {@link CubicCurve} to test + * @param p + * the {@link Point} to test for containment + * @return true if the {@link Point} lies on the {@link CubicCurve}, false + * otherwise + */ + public static boolean contains(CubicCurve c, Point p) { + return new BezierCurve(c).contains(p); + } + + /** + * Tests if the given {@link Point} lies on the given {@link QuadraticCurve} + * . + * + * @param c + * the {@link QuadraticCurve} to test + * @param p + * the {@link Point} to test for containment + * @return true if the {@link Point} lies on the {@link QuadraticCurve}, + * false otherwise + */ + public static boolean contains(QuadraticCurve c, Point p) { + return new BezierCurve(c).contains(p); + } + + /** + * Subdivides the given {@link CubicCurve} at parameter value t in the left + * and right sub-curves. + * + * @param c + * the {@link CubicCurve} to subdivide + * @param t + * the parameter value to subdivide at + * @return the left and right sub-curves as an array of {@link CubicCurve} + */ + public static CubicCurve[] split(CubicCurve c, double t) { + BezierCurve[] split = new BezierCurve(c).split(t); + return new CubicCurve[] { new CubicCurve(split[0].getRealPoints()), + new CubicCurve(split[1].getRealPoints()) }; + } + + /** + * Subdivides the given {@link QuadraticCurve} at parameter value t in the + * left and right sub-curves. + * + * @param c + * the {@link QuadraticCurve} to subdivide + * @param t + * the parameter value to subdivide at + * @return the left and right sub-curves as an array of + * {@link QuadraticCurve} + */ + public static QuadraticCurve[] split(QuadraticCurve c, double t) { + BezierCurve[] split = new BezierCurve(c).split(t); + return new QuadraticCurve[] { + new QuadraticCurve(split[0].getRealPoints()), + new QuadraticCurve(split[1].getRealPoints()) }; + } + + /** + * Returns a new {@link QuadraticCurve} that represents the given + * {@link QuadraticCurve} on the parameter interval [t1;t2]. + * + * @param c + * the {@link QuadraticCurve} to clip + * @param t1 + * lower parameter bound + * @param t2 + * upper parameter bound + * @return a new {@link QuadraticCurve} that represents the given + * {@link QuadraticCurve} on the interval [t1;t2] + */ + public static QuadraticCurve clip(QuadraticCurve c, double t1, double t2) { + BezierCurve bc = new BezierCurve(c); + bc.s = t1; + bc.e = t2; + return new QuadraticCurve(bc.getClipped().getRealPoints()); + } + + /** + * Returns a new {@link CubicCurve} that represents the given + * {@link CubicCurve} on the parameter interval [t1;t2]. + * + * @param c + * the {@link CubicCurve} to clip + * @param t1 + * lower parameter bound + * @param t2 + * upper parameter bound + * @return a new {@link CubicCurve} that represents the given + * {@link CubicCurve} on the interval [t1;t2] + */ + public static CubicCurve clip(CubicCurve c, double t1, double t2) { + BezierCurve bc = new BezierCurve(c); + bc.s = t1; + bc.e = t2; + return new CubicCurve(bc.getClipped().getRealPoints()); + } + + /** + * Evaluates the {@link Point} on the given {@link CubicCurve} at parameter + * value t. + * + * @param c + * the {@link CubicCurve} + * @param t + * the parameter value + * @return the {@link Point} on the given {@link CubicCurve} at parameter + * value t + */ + public static Point get(CubicCurve c, double t) { + return new BezierCurve(c).get(t).toPoint(); + } + + /** + * Evaluates the {@link Point} on the given {@link QuadraticCurve} at + * parameter value t. + * + * @param c + * the {@link QuadraticCurve} + * @param t + * the parameter value + * @return the {@link Point} on the given {@link QuadraticCurve} at + * parameter value t + */ + public static Point get(QuadraticCurve c, double t) { + return new BezierCurve(c).get(t).toPoint(); + } + +} Index: src/org/eclipse/gef4/geometry/utils/PointListUtils.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/utils/PointListUtils.java,v retrieving revision 1.6 diff -u -r1.6 PointListUtils.java --- src/org/eclipse/gef4/geometry/utils/PointListUtils.java 31 Oct 2011 22:16:56 -0000 1.6 +++ src/org/eclipse/gef4/geometry/utils/PointListUtils.java 9 Dec 2011 16:02:36 -0000 @@ -11,6 +11,10 @@ *******************************************************************************/ package org.eclipse.gef4.geometry.utils; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Comparator; + import org.eclipse.gef4.geometry.Point; import org.eclipse.gef4.geometry.shapes.Line; import org.eclipse.gef4.geometry.shapes.Polygon; @@ -108,6 +112,79 @@ return hashCode; } + private static void swapLowestYPointToStart(Point[] points) { + int minIdx = 0; + Point min = points[minIdx]; + for (int i = 1; i < points.length; i++) { + if (points[i].y < min.y || points[i].y == min.y + && points[i].x < min.x) { + min = points[i]; + minIdx = i; + } + } + Point tmp = points[0]; + points[0] = points[minIdx]; + points[minIdx] = tmp; + } + + private static void sortPointsByAngleToStart(Point[] points) { + final Point p0 = points[0]; + Arrays.sort(points, 1, points.length, new Comparator() { + public int compare(Point p1, Point p2) { + double m1 = (p1.x - p0.x) / (-p1.y + p0.y); + double m2 = (p2.x - p0.x) / (-p2.y + p0.y); + if (m1 < m2) { + return -1; + } + return 1; + } + }); + } + + private static ArrayList initializeStack(Point[] points) { + ArrayList stack = new ArrayList(); + if (points.length > 0) { + stack.add(0, points[0]); + if (points.length > 1) { + stack.add(0, points[1]); + if (points.length > 2) { + stack.add(0, points[2]); + } + } + } + return stack; + } + + private static void expandToFullConvexHull(ArrayList stack, + Point[] points) { + for (int i = 3; i < points.length; i++) { + // do always turn right + while (stack.size() > 2 + && CurveUtils.getSignedDistance(stack.get(1), stack.get(0), + points[i]) > 0) { + stack.remove(0); + } + stack.add(0, points[i]); + } + } + + /** + * Computes the convex hull of the given set of {@link Point}s using the + * Graham scan algorithm. + * + * @param points + * the set of {@link Point}s to calculate the convex hull for + * @return the convex hull of the given set of {@link Point}s + */ + public static Point[] getConvexHull(Point[] points) { + // do a graham scan to find the convex hull of the given set of points + swapLowestYPointToStart(points); + sortPointsByAngleToStart(points); + ArrayList convexHull = initializeStack(points); + expandToFullConvexHull(convexHull, points); + return convexHull.toArray(new Point[] {}); + } + /** * Converts a given array of {@link Point} into an array of doubles * containing the x and y coordinates of the given points, where the x and y @@ -129,6 +206,26 @@ } /** + * Converts a given array of x/y coordinate values into an array of + * {@link Point}s. + * + * @param coordinates + * @return a new array of {@link Point}s, representing the given x and y + * coordinates + */ + public static Point[] toPointsArray(double[] coordinates) { + if (coordinates.length % 2 != 0) { + throw new IllegalArgumentException( + "The coordinates array may not have an odd number of items."); + } + Point[] points = new Point[coordinates.length / 2]; + for (int i = 0; i < points.length; i++) { + points[i] = new Point(coordinates[2 * i], coordinates[2 * i + 1]); + } + return points; + } + + /** * Converts an array of double values into an array of integer values by * casting them. * Index: src/org/eclipse/gef4/geometry/utils/PolynomCalculationUtils.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/utils/PolynomCalculationUtils.java,v retrieving revision 1.1 diff -u -r1.1 PolynomCalculationUtils.java --- src/org/eclipse/gef4/geometry/utils/PolynomCalculationUtils.java 31 Oct 2011 21:56:41 -0000 1.1 +++ src/org/eclipse/gef4/geometry/utils/PolynomCalculationUtils.java 9 Dec 2011 16:02:36 -0000 @@ -79,34 +79,28 @@ */ public static final double[] getCubicRoots(double A, double B, double C, double D) { + // TODO: use an algorithm that abstracts the polynom's order. A + // possibility would be to use the CurveUtils$BezierCurve#contains(Point + // p) method. + if (A == 0) { return getQuadraticRoots(B, C, D); } - double a = B / A; - double b = C / A; - double c = D / A; + double b = B / A; + double c = C / A; + double d = D / A; - // reduce to z^3 + pz + q = 0 by substituting x = z - a/3 + // reduce to t^3 + pt + q = 0 by substituting x = t - b/3 // (http://en.wikipedia.org/wiki/Cubic_function#Cardano.27s_method) + double p = c - b * b / 3; + double q = 2 * b * b * b / 27 - b * c / 3 + d; - double p = b - a * a / 3; - double q = 2 * a * a * a / 27 - a * b / 3 + c; - - // short-cuts for p = 0, q = 0: + // short-cut for p = 0 if (PrecisionUtils.equal(p, 0, +4)) { - // z^3 = -q => z = cbrt(-q) => x = cbrt(-q) - a / 3 - return new double[] { Math.cbrt(-q) - a / 3 }; - } - if (PrecisionUtils.equal(q, 0, +4)) { - // z^3 - pz = 0 <=> z(z^2 - p) = 0 => z = 0 v z^2 = p => z = - // +-sqrt(p), p >= 0 (p is not zero, because otherwise we would not - // be here) - if (p > 0) { - return new double[] { 0, Math.sqrt(p), -Math.sqrt(p) }; - } else { - return new double[] { 0 }; - } + // t^3 + q = 0 => t^3 = -q => t = cbrt(-q) => t - b/3 = cbrt(-q) - + // b/3 => x = cbrt(-q) - b/3 + return new double[] { Math.cbrt(-q) - b / 3 }; } double p_3 = p / 3; @@ -116,13 +110,13 @@ if (PrecisionUtils.equal(D, 0, +4)) { // two real solutions - return new double[] { 3 * q / p - a / 3, -3 * q / (2 * p) - a / 3 }; + return new double[] { 3 * q / p - b / 3, -3 * q / (2 * p) - b / 3 }; } else if (D > 0) { // one real solution double u = Math.cbrt(-q_2 + Math.sqrt(D)); double v = Math.cbrt(-q_2 - Math.sqrt(D)); - return new double[] { u + v - a / 3 }; + return new double[] { u + v - b / 3 }; } else { // three real solutions double r = Math.sqrt(-p_3 * p_3 * p_3); @@ -130,9 +124,10 @@ double co = 2 * Math.cbrt(r); // co * cos((phi + k * pi)/3) - a/3, k = 2n, n in N - return new double[] { co * Math.cos(phi / 3) - a / 3, - co * Math.cos((phi + 2 * Math.PI) / 3) - a / 3, - co * Math.cos((phi + 4 * Math.PI) / 3) - a / 3 }; + return new double[] { co * Math.cos(phi / 3) - b / 3, + co * Math.cos((phi + 2 * Math.PI) / 3) - b / 3, + co * Math.cos((phi + 4 * Math.PI) / 3) - b / 3 }; } } + } #P org.eclipse.gef4.geometry.doc Index: META-INF/MANIFEST.MF =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry.doc/META-INF/MANIFEST.MF,v retrieving revision 1.4 diff -u -r1.4 MANIFEST.MF --- META-INF/MANIFEST.MF 14 Nov 2011 20:39:16 -0000 1.4 +++ META-INF/MANIFEST.MF 9 Dec 2011 16:02:37 -0000 @@ -4,4 +4,4 @@ Bundle-SymbolicName: org.eclipse.gef4.geometry.doc;singleton:=true Bundle-Version: 0.1.0.qualifier Bundle-Vendor: Eclipse.org -Require-Bundle: org.eclipse.swt;bundle-version="3.7.1" +Require-Bundle: org.eclipse.swt;bundle-version="3.7.0" #P org.eclipse.gef4.geometry.tests Index: src/org/eclipse/gef4/geometry/tests/AllTests.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry.tests/src/org/eclipse/gef4/geometry/tests/AllTests.java,v retrieving revision 1.5 diff -u -r1.5 AllTests.java --- src/org/eclipse/gef4/geometry/tests/AllTests.java 17 Nov 2011 22:00:24 -0000 1.5 +++ src/org/eclipse/gef4/geometry/tests/AllTests.java 9 Dec 2011 16:02:38 -0000 @@ -17,12 +17,12 @@ import org.junit.runners.Suite.SuiteClasses; @RunWith(Suite.class) -@SuiteClasses({ AngleTests.class, CubicCurveTests.class, DimensionTests.class, - EllipseTests.class, LineTests.class, PointListUtilsTests.class, - PointTests.class, PolygonTests.class, PolylineTests.class, - PolynomCalculationUtilsTests.class, PrecisionUtilsTests.class, - QuadraticCurveTests.class, RectangleTests.class, StraightTests.class, - VectorTests.class }) +@SuiteClasses({ AngleTests.class, CubicCurveTests.class, CurveUtilsTests.class, + DimensionTests.class, EllipseTests.class, LineTests.class, + PointListUtilsTests.class, PointTests.class, PolygonTests.class, + PolylineTests.class, PolynomCalculationUtilsTests.class, + PrecisionUtilsTests.class, QuadraticCurveTests.class, + RectangleTests.class, StraightTests.class, VectorTests.class }) public class AllTests { } Index: src/org/eclipse/gef4/geometry/tests/CubicCurveTests.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry.tests/src/org/eclipse/gef4/geometry/tests/CubicCurveTests.java,v retrieving revision 1.2 diff -u -r1.2 CubicCurveTests.java --- src/org/eclipse/gef4/geometry/tests/CubicCurveTests.java 17 Nov 2011 22:26:30 -0000 1.2 +++ src/org/eclipse/gef4/geometry/tests/CubicCurveTests.java 9 Dec 2011 16:02:38 -0000 @@ -16,6 +16,7 @@ import org.eclipse.gef4.geometry.Point; import org.eclipse.gef4.geometry.shapes.CubicCurve; +import org.junit.Ignore; import org.junit.Test; public class CubicCurveTests { @@ -72,11 +73,101 @@ } @Test - public void test_get_Bounds() { + public void test_getBounds() { CubicCurve curve = new CubicCurve(p, c1, c2, q); // p is the top-left point: (y-coordinates are inverted) assertEquals(curve.getBounds().getTopLeft(), p); } + @Test + public void test_getIntersections_with_CubicCurve() { + CubicCurve cc1 = new CubicCurve(new Point(-10, -10), new Point(), + new Point(), new Point(5, 5)); + CubicCurve cc2 = new CubicCurve(new Point(5, -5), new Point(), + new Point(), new Point(-10, 10)); + assertEquals(1, cc1.getIntersections(cc2).length); + assertEquals(1, cc2.getIntersections(cc1).length); + + // same end point + cc1 = new CubicCurve(103.0, 401.0, 400.0, 200.0, 300.0, 300.0, 390.0, + 208.0); + cc2 = new CubicCurve(584.0, 12.0, 200.0, 200.0, 300.0, 100.0, 390.0, + 208.0); + assertEquals(1, cc1.getIntersections(cc2).length); + assertEquals(1, cc2.getIntersections(cc1).length); + + cc1 = new CubicCurve(198.0, 103.0, 410.0, 215.0, 305.0, 320.0, 542.0, + 246.0); + cc2 = new CubicCurve(101.0, 107.0, 197.0, 218.0, 302.0, 106.0, 542.0, + 246.0); + assertEquals(2, cc1.getIntersections(cc2).length); + assertEquals(2, cc2.getIntersections(cc1).length); + + cc1 = new CubicCurve(200.0, 100.0, 400.0, 200.0, 300.0, 300.0, 432.0, + 62.0); + cc2 = new CubicCurve(100.0, 100.0, 200.0, 200.0, 300.0, 100.0, 432.0, + 62.0); + assertEquals(2, cc1.getIntersections(cc2).length); + assertEquals(2, cc2.getIntersections(cc1).length); + + cc1 = new CubicCurve(200.0, 100.0, 400.0, 200.0, 300.0, 300.0, 208.0, + 35.0); + cc2 = new CubicCurve(100.0, 100.0, 200.0, 200.0, 300.0, 100.0, 208.0, + 35.0); + assertEquals(3, cc1.getIntersections(cc2).length); + assertEquals(3, cc2.getIntersections(cc1).length); + + cc1 = new CubicCurve(201.89274447949526, 106.43015521064301, + 403.7854889589905, 212.86031042128602, 302.8391167192429, + 319.290465631929, 81.0, 22.0); + cc2 = new CubicCurve(100.94637223974763, 106.43015521064301, + 201.89274447949526, 212.86031042128602, 302.8391167192429, + 106.43015521064301, 81.0, 22.0); + assertEquals(3, cc1.getIntersections(cc2).length); + assertEquals(3, cc2.getIntersections(cc1).length); + + // torture tests from http://www.truetex.com/bezint.htm + cc1 = new CubicCurve(1.0, 1.5, 15.5, 0.5, -8.0, 3.5, 5.0, 1.5); + cc2 = new CubicCurve(4.0, 0.5, 5.0, 15.0, 2.0, -8.5, 4.0, 4.5); + assertEquals(9, cc1.getIntersections(cc2).length); + assertEquals(9, cc2.getIntersections(cc1).length); + + cc1 = new CubicCurve(664.00168, 0, 726.11545, 124.22757, 736.89069, + 267.89743, 694.0017, 400.0002); + cc2 = new CubicCurve(850.66843, 115.55563, 728.515, 115.55563, + 725.21347, 275.15309, 694.0017, 400.0002); + assertEquals(2, cc1.getIntersections(cc2).length); + assertEquals(2, cc2.getIntersections(cc1).length); + + cc1 = new CubicCurve(1, 1, 12.5, 6.5, -4, 6.5, 7.5, 1); + cc2 = new CubicCurve(1, 6.5, 12.5, 1, -4, 1, 7.5, 6); + assertEquals(6, cc1.getIntersections(cc2).length); + assertEquals(6, cc2.getIntersections(cc1).length); + + // not sure about these: (getIntersections() returns 3) + // cc1 = new CubicCurve(315.748, 312.84, 312.644, 318.134, 305.836, + // 319.909, 300.542, 316.804); + // cc2 = new CubicCurve(317.122, 309.05, 316.112, 315.102, 310.385, + // 319.19, 304.332, 318.179); + + // not sure about these: (getIntrsections() returns 0) + // cc1 = new CubicCurve(125.79356, 199.57382, 51.16556, 128.93575, + // 87.494, + // 16.67848, 167.29361, 16.67848); + // cc2 = new CubicCurve(167.29361, 55.81876, 100.36128, 55.81876, + // 68.64099, 145.4755, 125.7942, 199.57309); + } + + @Test + @Ignore + public void test_getIntersections_with_CubicCurve_endPointsCheck() { + CubicCurve cc1 = new CubicCurve(new Point(0, 0), new Point(0.1, 0), + new Point(0.1, 0), new Point(0.1, 0.1)); + CubicCurve cc2 = new CubicCurve(new Point(0, 0), new Point(0.05, 0.1), + new Point(0.05, 0.1), new Point(0.1, -0.1)); + assertEquals(2, cc1.getIntersections(cc2).length); + assertEquals(2, cc2.getIntersections(cc1).length); + } + } Index: src/org/eclipse/gef4/geometry/tests/CurveUtilsTests.java =================================================================== RCS file: src/org/eclipse/gef4/geometry/tests/CurveUtilsTests.java diff -N src/org/eclipse/gef4/geometry/tests/CurveUtilsTests.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/gef4/geometry/tests/CurveUtilsTests.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,267 @@ +/******************************************************************************* + * Copyright (c) 2011 itemis AG and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Matthias Wienand (itemis AG) - initial API and implementation + * + *******************************************************************************/ +package org.eclipse.gef4.geometry.tests; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +import java.util.Random; + +import org.eclipse.gef4.geometry.Point; +import org.eclipse.gef4.geometry.shapes.CubicCurve; +import org.eclipse.gef4.geometry.shapes.QuadraticCurve; +import org.eclipse.gef4.geometry.utils.CurveUtils; +import org.eclipse.gef4.geometry.utils.PrecisionUtils; +import org.junit.Test; + +public class CurveUtilsTests { + + private static final long SEED = 123; + + @Test + public void test_getSignedDistance_direction() { + // sign-checks: + // first quadrant (y-axis is inverted) + assertTrue(CurveUtils.getSignedDistance(new Point(), + new Point(10, -10), new Point(0, -10)) > 0); + assertTrue(CurveUtils.getSignedDistance(new Point(10, -10), + new Point(), new Point(0, -10)) < 0); + assertTrue(CurveUtils.getSignedDistance(new Point(), + new Point(10, -10), new Point(1, -1)) == 0); + + // second quadrant (y-axis is inverted) + assertTrue(CurveUtils.getSignedDistance(new Point(), + new Point(-10, -10), new Point(0, -10)) < 0); + assertTrue(CurveUtils.getSignedDistance(new Point(-10, -10), + new Point(), new Point(0, -10)) > 0); + assertTrue(CurveUtils.getSignedDistance(new Point(), + new Point(-10, -10), new Point(-1, -1)) == 0); + + // third quadrant (y-axis is inverted) + assertTrue(CurveUtils.getSignedDistance(new Point(), new Point(10, 10), + new Point(0, 10)) < 0); + assertTrue(CurveUtils.getSignedDistance(new Point(10, 10), new Point(), + new Point(0, 10)) > 0); + assertTrue(CurveUtils.getSignedDistance(new Point(), new Point(10, 10), + new Point(1, 1)) == 0); + + // forth quadrant (y-axis is inverted) + assertTrue(CurveUtils.getSignedDistance(new Point(), + new Point(-10, 10), new Point(0, 10)) > 0); + assertTrue(CurveUtils.getSignedDistance(new Point(-10, 10), + new Point(), new Point(0, 10)) < 0); + assertTrue(CurveUtils.getSignedDistance(new Point(), + new Point(-10, 10), new Point(-1, 1)) == 0); + } + + @Test + public void test_getSignedDistance_abs() { + // do only check for the absolute value of the signed distance + + assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance( + new Point(0, -5), new Point(0, 5), new Point(5, 0))), 5)); + assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance( + new Point(0, 5), new Point(0, -5), new Point(5, 0))), 5)); + + assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance( + new Point(0, -1), new Point(0, 1), new Point(5, 0))), 5)); + assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance( + new Point(0, 1), new Point(0, -1), new Point(5, 0))), 5)); + + assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance( + new Point(-5, 0), new Point(5, 0), new Point(0, 5))), 5)); + assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance( + new Point(-5, 0), new Point(5, 0), new Point(0, 5))), 5)); + + assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance( + new Point(-1, 0), new Point(1, 0), new Point(0, 5))), 5)); + assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance( + new Point(-1, 0), new Point(1, 0), new Point(0, 5))), 5)); + } + + @Test + public void test_getSignedDistance() { + // check both, direction and value: + // first quadrant (y-axis is inverted) + double len = 10d / Math.sqrt(2); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance( + new Point(), new Point(10, -10), new Point(0, -10)), len)); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(new Point( + 10, -10), new Point(), new Point(0, -10)), -len)); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance( + new Point(), new Point(10, -10), new Point(1, -1)), 0)); + + // second quadrant (y-axis is inverted) + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance( + new Point(), new Point(-10, -10), new Point(0, -10)), -len)); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(new Point( + -10, -10), new Point(), new Point(0, -10)), len)); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance( + new Point(), new Point(-10, -10), new Point(-1, -1)), 0)); + + // third quadrant (y-axis is inverted) + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance( + new Point(), new Point(10, 10), new Point(0, 10)), -len)); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(new Point( + 10, 10), new Point(), new Point(0, 10)), len)); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance( + new Point(), new Point(10, 10), new Point(1, 1)), 0)); + + // forth quadrant (y-axis is inverted) + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance( + new Point(), new Point(-10, 10), new Point(0, 10)), len)); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(new Point( + -10, 10), new Point(), new Point(0, 10)), -len)); + assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance( + new Point(), new Point(-10, 10), new Point(-1, 1)), 0)); + } + + @Test + public void test_split_with_QuadraticCurve() { + final int numPoints = 4; + final double step = 0.123456789; + + Random rng = new Random(SEED); + + for (int i = 0; i < 1000; i++) { + Point[] points = new Point[numPoints]; + for (int j = 0; j < numPoints; j++) { + points[j] = new Point(rng.nextDouble(), rng.nextDouble()); + } + + QuadraticCurve c = new QuadraticCurve(points); + for (double t = 0; t <= 1; t += step) { + QuadraticCurve[] cs = c.split(t); + assertEquals(c.get(t), cs[0].get(1)); + assertEquals(c.get(t), cs[1].get(0)); + assertEquals(c.get(0), cs[0].get(0)); + assertEquals(c.get(1), cs[1].get(1)); + } + } + } + + @Test + public void test_clip_with_QuadraticCurve() { + final int numPoints = 4; + final double step = 0.123456789; + + Random rng = new Random(SEED); + + for (int i = 0; i < 1000; i++) { + Point[] points = new Point[numPoints]; + for (int j = 0; j < numPoints; j++) { + points[j] = new Point(rng.nextDouble(), rng.nextDouble()); + } + + QuadraticCurve c = new QuadraticCurve(points); + for (double t1 = 0; t1 <= 1; t1 += step) { + for (double t2 = 0; t2 <= 1; t2 += step) { + QuadraticCurve cc = c.clip(t1, t2); + assertEquals(c.get(t1), cc.get(0)); + assertEquals(c.get(t2), cc.get(1)); + } + } + } + } + + @Test + public void test_split_with_CubicCurve() { + final int numPoints = 6; + final double step = 0.123456789; + + Random rng = new Random(SEED); + + for (int i = 0; i < 1000; i++) { + Point[] points = new Point[numPoints]; + for (int j = 0; j < numPoints; j++) { + points[j] = new Point(rng.nextDouble(), rng.nextDouble()); + } + + CubicCurve c = new CubicCurve(points); + for (double t = 0; t <= 1; t += step) { + CubicCurve[] cs = c.split(t); + assertEquals(c.get(t), cs[0].get(1)); + assertEquals(c.get(t), cs[1].get(0)); + assertEquals(c.get(0), cs[0].get(0)); + assertEquals(c.get(1), cs[1].get(1)); + } + } + } + + @Test + public void test_clip_with_CubicCurve() { + final int numPoints = 6; + final double step = 0.123456789; + + Random rng = new Random(SEED); + + for (int i = 0; i < 1000; i++) { + Point[] points = new Point[numPoints]; + for (int j = 0; j < numPoints; j++) { + points[j] = new Point(rng.nextDouble(), rng.nextDouble()); + } + + CubicCurve c = new CubicCurve(points); + for (double t1 = 0; t1 <= 1; t1 += step) { + for (double t2 = 0; t2 <= 1; t2 += step) { + CubicCurve cc = c.clip(t1, t2); + assertEquals(c.get(t1), cc.get(0)); + assertEquals(c.get(t2), cc.get(1)); + } + } + } + } + + @Test + public void test_contains_with_QuadraticCurve() { + final int numPoints = 4; + final double step = 0.123456789; + + Random rng = new Random(SEED); + + for (int i = 0; i < 1000; i++) { + Point[] points = new Point[numPoints]; + for (int j = 0; j < numPoints; j++) { + points[j] = new Point(rng.nextDouble(), rng.nextDouble()); + } + + QuadraticCurve c = new QuadraticCurve(points); + for (double t = 0; t <= 1; t += step) { + assertTrue(c.contains(c.get(t))); + } + } + } + + @Test + public void test_contains_with_CubicCurve() { + final int numPoints = 6; + final double step = 0.123456789; + + Random rng = new Random(SEED); + + for (int i = 0; i < 1000; i++) { + Point[] points = new Point[numPoints]; + for (int j = 0; j < numPoints; j++) { + points[j] = new Point(rng.nextDouble(), rng.nextDouble()); + } + + CubicCurve c = new CubicCurve(points); + for (double t = 0; t <= 1; t += step) { + if (!c.contains(c.get(t))) { + System.out.println("OH NOEZ!"); + } + assertTrue(c.contains(c.get(t))); + } + } + } + +} Index: src/org/eclipse/gef4/geometry/tests/EllipseTests.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry.tests/src/org/eclipse/gef4/geometry/tests/EllipseTests.java,v retrieving revision 1.6 diff -u -r1.6 EllipseTests.java --- src/org/eclipse/gef4/geometry/tests/EllipseTests.java 17 Nov 2011 22:26:30 -0000 1.6 +++ src/org/eclipse/gef4/geometry/tests/EllipseTests.java 9 Dec 2011 16:02:39 -0000 @@ -19,7 +19,6 @@ import org.eclipse.gef4.geometry.shapes.Ellipse; import org.eclipse.gef4.geometry.shapes.Line; import org.eclipse.gef4.geometry.shapes.Rectangle; -import org.junit.Ignore; import org.junit.Test; /** @@ -74,7 +73,16 @@ } } - @Ignore + @Test + public void test_intersects_with_Line() { + Rectangle r = new Rectangle(34.3435, 56.458945, 123.3098, 146.578); + Ellipse e = new Ellipse(r); + for (Line l : r.getSegments()) { + assertTrue(e.intersects(l)); // line touches ellipse (tangent) + } + } + + @Test public void test_get_intersections_with_Ellipse() { Rectangle r = new Rectangle(34.3435, 56.458945, 123.3098, 146.578); Ellipse e1 = new Ellipse(r); @@ -85,9 +93,15 @@ Point[] intersections = e1.getIntersections(e2); assertEquals(0, intersections.length); + // touching left + Rectangle r2 = r.getExpanded(0, -10, -10, -10); + e2 = new Ellipse(r2); + intersections = e1.getIntersections(e2); + assertEquals(1, intersections.length); + // if we create an x-scaled ellipse at the same position as before, they // should have 3 poi (the touching point and two crossing intersections) - Rectangle r2 = r.getExpanded(0, 0, 100, 0); + r2 = r.getExpanded(0, 0, 100, 0); e2 = new Ellipse(r2); intersections = e1.getIntersections(e2); assertEquals(3, intersections.length); @@ -160,11 +174,19 @@ } @Test - public void test_intersects_with_Line() { - Rectangle r = new Rectangle(34.3435, 56.458945, 123.3098, 146.578); - Ellipse e = new Ellipse(r); - for (Line l : r.getSegments()) { - assertTrue(e.intersects(l)); // line touches ellipse (tangent) - } + public void test_getIntersections_with_Ellipse_Bezier_special() { + Ellipse e1 = new Ellipse(126, 90, 378, 270); + Ellipse e2 = new Ellipse(222, 77, 200, 200); + assertEquals(2, e1.getIntersections(e2).length); + + e2 = new Ellipse(133, 90, 2 * (315 - 133), 200); + assertEquals(3, e1.getIntersections(e2).length); + + e2 = new Ellipse(143, 90, 2 * (315 - 143), 200); + assertEquals(3, e1.getIntersections(e2).length); + + e2 = new Ellipse(145, 90, 2 * (315 - 145), 200); + assertEquals(3, e1.getIntersections(e2).length); } + } Index: src/org/eclipse/gef4/geometry/tests/PointListUtilsTests.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry.tests/src/org/eclipse/gef4/geometry/tests/PointListUtilsTests.java,v retrieving revision 1.2 diff -u -r1.2 PointListUtilsTests.java --- src/org/eclipse/gef4/geometry/tests/PointListUtilsTests.java 17 Nov 2011 22:26:30 -0000 1.2 +++ src/org/eclipse/gef4/geometry/tests/PointListUtilsTests.java 9 Dec 2011 16:02:39 -0000 @@ -19,6 +19,7 @@ import org.eclipse.gef4.geometry.Point; import org.eclipse.gef4.geometry.shapes.Line; +import org.eclipse.gef4.geometry.shapes.Polygon; import org.eclipse.gef4.geometry.shapes.Rectangle; import org.eclipse.gef4.geometry.utils.PointListUtils; import org.eclipse.gef4.geometry.utils.PrecisionUtils; @@ -161,4 +162,49 @@ assertTrue(PrecisionUtils.equal(points[i].y, i - 1)); } } + + @Test + public void test_getConvexHull() { + // test case from + // http://stackoverflow.com/questions/482278/test-case-data-for-convex-hull + + Point[] points = PointListUtils.toPointsArray(new double[] { + 0.3215348546593775, 0.03629583077160248, 0.02402358131857918, + -0.2356728797179394, 0.04590851212470659, -0.4156409924995536, + 0.3218384001607433, 0.1379850698988746, 0.11506479756447, + -0.1059521474930943, 0.2622539999543261, -0.29702873322836, + -0.161920957418085, -0.4055339716426413, 0.1905378631228002, + 0.3698601009043493, 0.2387090918968516, -0.01629827079949742, + 0.07495888748668034, -0.1659825110491202, 0.3319341836794598, + -0.1821814101954749, 0.07703635755650362, -0.2499430638271785, + 0.2069242999022122, -0.2232970760420869, 0.04604079532068295, + -0.1923573186549892, 0.05054295812784038, 0.4754929463150845, + -0.3900589168910486, 0.2797829520700341, 0.3120693385713448, + -0.0506329867529059, 0.01138812723698857, 0.4002504701728471, + 0.009645149586391732, 0.1060251100976254, -0.03597933197019559, + 0.2953639456959105, 0.1818290866742182, 0.001454397571696298, + 0.444056063372694, 0.2502497166863175, -0.05301752458607545, + -0.06553921621808712, 0.4823896228171788, -0.4776170002088109, + -0.3089226845734964, -0.06356112199235814, -0.271780741188471, + 0.1810810595574612, 0.4293626522918815, 0.2980897964891882, + -0.004796652127799228, 0.382663812844701, 0.430695573269106, + -0.2995073500084759, 0.1799668387323309, -0.2973467472915973, + 0.4932166845474547, 0.4928094162538735, -0.3521487911717489, + 0.4352656197131292, -0.4907368011686362, 0.1865826865533206, + -0.1047924716070224, -0.247073392148198, 0.4374961861758457, + -0.001606279519951237, 0.003256207800708899, + -0.2729194320486108, 0.04310378203457577, 0.4452604050238248, + 0.4916198379282093, -0.345391701297268, 0.001675087028811806, + 0.1531837672490476, -0.4404289572876217, -0.2894855991839297 }); + + Point[] convexHull = PointListUtils.getConvexHull(points); + + assertTrue(new Polygon(PointListUtils.toPointsArray(new double[] { + -0.161920957418085, -0.4055339716426413, -0.4404289572876217, + -0.2894855991839297, -0.4907368011686362, 0.1865826865533206, + -0.3521487911717489, 0.4352656197131292, 0.05054295812784038, + 0.4754929463150845, 0.4932166845474547, 0.4928094162538735, + 0.4916198379282093, -0.345391701297268, 0.4823896228171788, + -0.4776170002088109 })).equals(new Polygon(convexHull))); + } } Index: src/org/eclipse/gef4/geometry/tests/PolynomCalculationUtilsTests.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry.tests/src/org/eclipse/gef4/geometry/tests/PolynomCalculationUtilsTests.java,v retrieving revision 1.3 diff -u -r1.3 PolynomCalculationUtilsTests.java --- src/org/eclipse/gef4/geometry/tests/PolynomCalculationUtilsTests.java 17 Nov 2011 22:26:30 -0000 1.3 +++ src/org/eclipse/gef4/geometry/tests/PolynomCalculationUtilsTests.java 9 Dec 2011 16:02:39 -0000 @@ -30,16 +30,16 @@ solutions = PolynomCalculationUtils.getCubicRoots(1, 0, 1, 0); Arrays.sort(solutions); + assertEquals("one real solution", 1, solutions.length); + assertTrue("x1 = 0", PrecisionUtils.equal(solutions[0], 0)); + + solutions = PolynomCalculationUtils.getCubicRoots(1, 0, -1, 0); + Arrays.sort(solutions); assertEquals("three real solutions", 3, solutions.length); assertTrue("x1 = -1", PrecisionUtils.equal(solutions[0], -1)); assertTrue("x2 = 0", PrecisionUtils.equal(solutions[1], 0)); assertTrue("x3 = 1", PrecisionUtils.equal(solutions[2], 1)); - solutions = PolynomCalculationUtils.getCubicRoots(1, 0, -1, 0); - Arrays.sort(solutions); - assertEquals("one real solution", 1, solutions.length); - assertTrue("x1 = 0", PrecisionUtils.equal(solutions[0], 0)); - solutions = PolynomCalculationUtils.getCubicRoots(1, 1, 1, 0); Arrays.sort(solutions); assertEquals("one real solution", 1, solutions.length); @@ -66,6 +66,14 @@ PrecisionUtils.equal(-0.15524041215, solutions[1])); assertTrue("x3 = 1.48705072", PrecisionUtils.equal(1.487050722353, solutions[2])); + + // q = 0 + solutions = PolynomCalculationUtils.getCubicRoots(-10, 30, 0, -20); + Arrays.sort(solutions); + assertEquals(3, solutions.length); + assertTrue(PrecisionUtils.equal(-0.7320508075688774, solutions[0])); + assertTrue(PrecisionUtils.equal(1, solutions[1])); + assertTrue(PrecisionUtils.equal(2.7320508075688776, solutions[2])); } @Test @@ -170,4 +178,54 @@ true); } } + + // @Test + // public void test_getRoots_arbitrary() { + // // double[] solutions = PolynomCalculationUtils.getRoots(1, 0, 1, 0); + // // Arrays.sort(solutions); + // // assertEquals("one real solution", 1, solutions.length); + // // assertTrue("x1 = 0", PrecisionUtils.equal(solutions[0], 0)); + // + // solutions = PolynomCalculationUtils.getCubicRoots(1, 0, -1, 0); + // Arrays.sort(solutions); + // assertEquals("three real solutions", 3, solutions.length); + // assertTrue("x1 = -1", PrecisionUtils.equal(solutions[0], -1)); + // assertTrue("x2 = 0", PrecisionUtils.equal(solutions[1], 0)); + // assertTrue("x3 = 1", PrecisionUtils.equal(solutions[2], 1)); + // + // solutions = PolynomCalculationUtils.getCubicRoots(1, 1, 1, 0); + // Arrays.sort(solutions); + // assertEquals("one real solution", 1, solutions.length); + // assertTrue("x^3 + x^2 + x = 0 <=> x(x^2 + x + 1) = 0 => x = 0", + // PrecisionUtils.equal(0, solutions[0])); + // + // solutions = PolynomCalculationUtils.getCubicRoots(1, -6, 12, -8); + // assertEquals("one real solution", 1, solutions.length); + // assertTrue("x = 2 solves the polynom", + // PrecisionUtils.equal(2, solutions[0])); + // + // solutions = PolynomCalculationUtils.getCubicRoots(1, 1, -33, 63); + // Arrays.sort(solutions); + // assertEquals("two real solutions", 2, solutions.length); + // assertTrue("x1 = -7", PrecisionUtils.equal(-7, solutions[0])); + // assertTrue("x2 = 3", PrecisionUtils.equal(3, solutions[1])); + // + // solutions = PolynomCalculationUtils.getCubicRoots(1, 3, -6, -1); + // Arrays.sort(solutions); + // assertEquals("three real solutions", 3, solutions.length); + // assertTrue("x1 = -4.33181031", + // PrecisionUtils.equal(-4.331810310203, solutions[0])); + // assertTrue("x2 = -0.15524041", + // PrecisionUtils.equal(-0.15524041215, solutions[1])); + // assertTrue("x3 = 1.48705072", + // PrecisionUtils.equal(1.487050722353, solutions[2])); + // + // // q = 0 + // solutions = PolynomCalculationUtils.getCubicRoots(-10, 30, 0, -20); + // Arrays.sort(solutions); + // assertEquals(3, solutions.length); + // assertTrue(PrecisionUtils.equal(-0.7320508075688774, solutions[0])); + // assertTrue(PrecisionUtils.equal(1, solutions[1])); + // assertTrue(PrecisionUtils.equal(2.7320508075688776, solutions[2])); + // } } Index: src/org/eclipse/gef4/geometry/tests/RectangleTests.java =================================================================== RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry.tests/src/org/eclipse/gef4/geometry/tests/RectangleTests.java,v retrieving revision 1.5 diff -u -r1.5 RectangleTests.java --- src/org/eclipse/gef4/geometry/tests/RectangleTests.java 17 Nov 2011 22:26:30 -0000 1.5 +++ src/org/eclipse/gef4/geometry/tests/RectangleTests.java 9 Dec 2011 16:02:39 -0000 @@ -360,6 +360,7 @@ assertEquals(new Rectangle(0, 3, 3, 4), r1.getTranslated(-1, 1)); } + @Test public void test_getTransposed() { forRectangles(new IAction() { public void action(Rectangle rect, Point tl, Point br) { @@ -553,19 +554,6 @@ } @Test - public void test_setSize() { - Rectangle r = new Rectangle(); - - r.setSize(new Dimension(10, 20)); - assertEquals(new Point(), r.getTopLeft()); - assertEquals(new Point(10, 20), r.getBottomRight()); - - r.setSize(5, -10); - assertEquals(new Point(), r.getTopLeft()); - assertEquals(new Point(5, 0), r.getBottomRight()); - } - - @Test public void test_setters() { Rectangle r = new Rectangle(); @@ -691,4 +679,21 @@ }); } + @Test + public void test_setSize() { + Rectangle r = new Rectangle(); + + r.setSize(new Dimension(10, 20)); + assertEquals(new Point(), r.getTopLeft()); + assertEquals(new Point(10, 20), r.getBottomRight()); + + r.setSize(5, -10); + assertEquals(new Point(), r.getTopLeft()); + assertEquals(new Point(5, 0), r.getBottomRight()); + + r.setSize(-5, 10); + assertEquals(new Point(), r.getTopLeft()); + assertEquals(new Point(0, 10), r.getBottomRight()); + } + }