### 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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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<Point> intersections = new HashSet<Point>();
-
-			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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:38 -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	24 Nov 2011 13:17:39 -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	24 Nov 2011 13:17:39 -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	24 Nov 2011 13:17:39 -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,1028 @@
+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, so that the resulting {@link Vector3D} yields the
+		 * {@link Point} in homogeneous coordinates.
+		 * 
+		 * @param p
+		 *            the point to transform into homogeneous coordinates
+		 */
+		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 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 SAME_POINTS_SAME_SIGNS_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());
+		}
+
+		private Vector3D[] getPointsCopy() {
+			Vector3D[] copy = new Vector3D[points.length];
+			for (int i = 0; i < points.length; i++) {
+				copy[i] = points[i].getCopy();
+			}
+			return copy;
+		}
+
+		/**
+		 * 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;
+		}
+
+		/**
+		 * 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;
+			}
+
+			double[] xts, yts;
+			if (points.length == 2) {
+				// P(t) = t(P2 - P1) + P1
+				Point p1 = points[0].toPoint();
+				Point p2 = points[1].toPoint();
+
+				if (p1 == null || p2 == null) {
+					return false;
+				}
+
+				xts = PolynomCalculationUtils.getLinearRoots(p2.x - p1.x, p1.x
+						- p.x);
+				yts = PolynomCalculationUtils.getLinearRoots(p2.y - p1.y, p1.y
+						- p.y);
+			} else if (points.length == 3) {
+				// P(t) = t^2(P1 - P2 + P3) + t(P2 - 2P1) + P1
+				Point p1 = points[0].toPoint();
+				Point p2 = points[1].toPoint();
+				Point p3 = points[2].toPoint();
+
+				if (p1 == null || p2 == null || p3 == null) {
+					return false;
+				}
+
+				xts = PolynomCalculationUtils.getQuadraticRoots(p1.x - 2 * p2.x
+						+ p3.x, 2 * p2.x - 2 * p1.x, p1.x - p.x);
+				yts = PolynomCalculationUtils.getQuadraticRoots(p1.y - 2 * p2.y
+						+ p3.y, 2 * p2.y - 2 * p1.y, p1.y - p.y);
+			} else if (points.length == 4) {
+				// P(t) = (-p1 + 3p2 - 3p3 + p4)t^3 + (3p1 - 6p2 + 3p3)t^2 +
+				// (-3p1 + 3p2)t + p1
+				Point p1 = points[0].toPoint();
+				Point p2 = points[1].toPoint();
+				Point p3 = points[2].toPoint();
+				Point p4 = points[3].toPoint();
+
+				if (p1 == null || p2 == null || p3 == null || p4 == null) {
+					return false;
+				}
+
+				xts = PolynomCalculationUtils.getCubicRoots(-p1.x + 3 * p2.x
+						- 3 * p3.x + p4.x, 3 * p1.x - 6 * p2.x + 3 * p3.x, -3
+						* p1.x + 3 * p2.x, p1.x - p.x);
+				yts = PolynomCalculationUtils.getCubicRoots(-p1.y + 3 * p2.y
+						- 3 * p3.y + p4.y, 3 * p1.y - 6 * p2.y + 3 * p3.y, -3
+						* p1.y + 3 * p2.y, p1.y - p.y);
+			} else {
+				// TODO: implement root finding for higher degree curves
+				throw new UnsupportedOperationException();
+			}
+
+			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];
+		}
+
+		/**
+		 * 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<Vector3D> intersections) {
+			if (PrecisionUtils.equal(p.s, p.e, +1)) {
+				Vector3D poi = p.get(p.s);
+				if (q.contains(poi.toPoint())) {
+					intersections.add(poi);
+				}
+				return true;
+			}
+			if (PrecisionUtils.equal(q.s, q.e, +1)) {
+				Vector3D poi = q.get(q.s);
+				if (p.contains(poi.toPoint())) {
+					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 and this is the only point
+		 * of intersection on the given {@link BezierCurve}.
+		 * 
+		 * Calculates the area of the bounding boxes of both curves and checks
+		 * if that maximum area is below some constant value
+		 * SAME_POINTS_SAME_SIGNS_AREA. So an end-point-intersection is only
+		 * added for very small curve segments.
+		 * 
+		 * TODO: at the moment the distanceSignCheck() is not working correctly.
+		 * It will never separate two curves, because they all share one point
+		 * with a difference of 0. To make this work, the distanceSignCheck()
+		 * has to be specialized to work for end-points only.
+		 * 
+		 * @param p
+		 * @param q
+		 * @param intersections
+		 * @return
+		 */
+		private static boolean endPointsCheck(BezierCurve p, BezierCurve q,
+				HashSet<Vector3D> 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 < SAME_POINTS_SAME_SIGNS_AREA) {
+					return true;
+				}
+			}
+			if (poi.equals(q.get(q.e))) {
+				intersections.add(poi);
+				if (area < SAME_POINTS_SAME_SIGNS_AREA) {
+					return true;
+				}
+			}
+			poi = q.get(q.s);
+			if (poi.equals(p.get(p.e))) {
+				intersections.add(poi);
+				if (area < SAME_POINTS_SAME_SIGNS_AREA) {
+					return true;
+				}
+			}
+			poi = q.get(q.e);
+			if (poi.equals(p.get(p.e))) {
+				intersections.add(poi);
+				if (area < SAME_POINTS_SAME_SIGNS_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 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;
+
+			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) {
+					min = x;
+				}
+			}
+
+			return min;
+		}
+
+		/**
+		 * 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;
+
+			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) {
+					max = x;
+				}
+			}
+
+			return max;
+		}
+
+		/**
+		 * 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 && PrecisionUtils.equal(D[i].y, 0, +6)) {
+					D[i].y = 0;
+					return false;
+				} else 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) {
+					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) {
+					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<Vector3D> getIntersections(BezierCurve other) {
+			HashSet<Vector3D> intersections = new HashSet<Vector3D>();
+
+			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;
+			}
+
+			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);
+
+			if (ratio < 0) {
+				// no intersections
+				return intersections;
+			} else if (ratio > 0.8) {
+				// do not change the interval in the case of a too small change
+				if (ratio < 0.9) {
+					s = news;
+					e = newe;
+				}
+
+				// 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%
+				s = news;
+				e = newe;
+				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<CurveUtils.Vector3D> intersections = new BezierCurve(p)
+				.getIntersections(new BezierCurve(q));
+
+		HashSet<Point> pois = new HashSet<Point>();
+		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, <code>null</code>
+	 *         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();
+	}
+
+	/**
+	 * 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/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	24 Nov 2011 13:17:40 -0000
@@ -83,30 +83,20 @@
 			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 +106,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 +120,9 @@
 			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.tests
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	24 Nov 2011 13:17:40 -0000
@@ -72,11 +72,58 @@
 	}
 
 	@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);
+
+		// 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);
+
+		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);
+
+		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);
+
+		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);
+
+		// 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));
+
+		// 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);
+	}
+
 }
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	24 Nov 2011 13:17:40 -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/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	24 Nov 2011 13:17:41 -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
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	24 Nov 2011 13:17:41 -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());
+	}
+
 }