Attachment #208923 for bug #355997

View | Details | Raw Unified | Return to bug 355997 | Differences between

and this patch

Lines 207-213 Link Here

(-)src/org/eclipse/gef4/geometry/Angle.java (-1 / +2 lines)
207	*/	207	*/
208	@Override	208	@Override
209	public int hashCode() {	209	public int hashCode() {
210	// calculating a better hashCode is not possible	210	// calculating a better hashCode is not possible, because due to the
		211	// imprecision, equals() is no longer transitive
211	return 0;	212	return 0;
212	}	213	}
213		214

Lines 349-357 Link Here

(-)src/org/eclipse/gef4/geometry/Dimension.java (-2 / +2 lines)
349	*/	349	*/
350	@Override	350	@Override
351	public int hashCode() {	351	public int hashCode() {
352	// calculating a better hashCode is not possible	352	// calculating a better hashCode is not possible, because due to the
		353	// imprecision, equals() is no longer transitive
353	return 0;	354	return 0;
354	// return (int) (width * height) ^ (int) (width + height);
355	}	355	}
356		356
357	/**	357	/**

Lines 278-286 Link Here

(-)src/org/eclipse/gef4/geometry/Point.java (-2 / +2 lines)
278	*/	278	*/
279	@Override	279	@Override
280	public int hashCode() {	280	public int hashCode() {
281	// calculating a better hashCode is not possible	281	// calculating a better hashCode is not possible, because due to the
		282	// imprecision, equals() is no longer transitive
282	return 0;	283	return 0;
283	// return (int) (x * y) ^ (int) (x + y);
284	}	284	}
285		285
286	/**	286	/**





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;

/**

	 * @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();
	}

	}

	/**
	 * 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.
	 * 

	 *         if no intersection point exists (or the Straights are equal).
	 */
	public Vector getIntersection(Straight other) {
		Point poi = CurveUtils.getIntersection(this, other);
		if (poi != null) {
			return new Vector(poi);
		}
		return null;
				.getAdded(other.direction));
		double[] l1 = getCrossProduct(p11, p12);
		double[] l2 = getCrossProduct(p21, p22);
		double[] poi = getCrossProduct(l1, l2);
		return fromHomogeneousVector(poi);
	}

	/**

	}

	/**
	 * Checks whether this {@link Straight} and the provided one are parallel to
	 * each other.
	 * 
	 * @param other
	 *            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 {@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)
	 */

	 */
	@Override
	public int hashCode() {
		// calculating a better hashCode is not possible, because due to the
		// imprecision, equals() is no longer transitive
		return 0;
		// return position.hashCode() + direction.hashCode();
	}

	/**

Lines 410-418 Link Here

(-)src/org/eclipse/gef4/geometry/euclidean/Vector.java (-2 / +2 lines)
410	*/	410	*/
411	@Override	411	@Override
412	public int hashCode() {	412	public int hashCode() {
413	// calculating a better hashCode is not possible	413	// calculating a better hashCode is not possible, because due to the
		414	// imprecision, equals() is no longer transitive
414	return 0;	415	return 0;
415	// return (int) x + (int) y;
416	}	416	}
417		417
418	/**	418	/**

Lines 12-17 Link Here

(-)src/org/eclipse/gef4/geometry/shapes/Arc.java (-1 / +165 lines)
12	package org.eclipse.gef4.geometry.shapes;	12	package org.eclipse.gef4.geometry.shapes;
13		13
14	import java.util.ArrayList;	14	import java.util.ArrayList;
		15	import java.util.Arrays;
		16	import java.util.HashSet;
15	import java.util.List;	17	import java.util.List;
16		18
17	import org.eclipse.gef4.geometry.Angle;	19	import org.eclipse.gef4.geometry.Angle;
Lines 125-130 Link Here
125	return height;	127	return height;
126	}	128	}
127		129
		130	/**
		131	* Returns the points of intersection between this {@link Arc} and the given
		132	* {@link CubicCurve}.
		133	*
		134	* @param c
		135	* The {@link CubicCurve} to test for intersections
		136	* @return the points of intersection.
		137	*/
		138	public Point[] getIntersections(CubicCurve c) {
		139	return c.getIntersections(this);
		140	}
		141
		142	/**
		143	* Returns the points of intersection between this {@link Arc} and the given
		144	* other {@link Arc}.
		145	*
		146	* @param other
		147	* The {@link Arc} to test for intersections
		148	* @return the points of intersection.
		149	*/
		150	public Point[] getIntersections(Arc other) {
		151	if (equals(other)) {
		152	return new Point[] {};
		153	}
		154
		155	HashSet<Point> intersections = new HashSet<Point>();
		156
		157	for (CubicCurve seg : getBorderSegments()) {
		158	intersections.addAll(Arrays.asList(getIntersections(seg)));
		159	}
		160
		161	return intersections.toArray(new Point[] {});
		162	}
		163
		164	/**
		165	* Returns the points of intersection between this {@link Arc} and the given
		166	* {@link Ellipse}.
		167	*
		168	* @param e
		169	* The {@link Ellipse} to test for intersections
		170	* @return the points of intersection.
		171	*/
		172	public Point[] getIntersections(Ellipse e) {
		173	return e.getIntersections(this);
		174	}
		175
		176	/**
		177	* Returns the points of intersection between this {@link Arc} and the given
		178	* {@link Line}.
		179	*
		180	* @param l
		181	* The {@link Line} to test for intersections
		182	* @return the points of intersection.
		183	*/
		184	public Point[] getIntersections(Line l) {
		185	HashSet<Point> intersections = new HashSet<Point>();
		186
		187	for (CubicCurve seg : getBorderSegments()) {
		188	intersections.addAll(Arrays.asList(seg.getIntersections(l)));
		189	}
		190
		191	return intersections.toArray(new Point[] {});
		192	}
		193
194	/**
195	* Returns the points of intersection between this {@link Arc} and the given
196	* {@link Polygon}.
197	*
198	* @param p
199	* The {@link Polygon} to test for intersections
200	* @return the points of intersection.
201	*/
202	public Point[] getIntersections(Polygon p) {
203	return p.getIntersections(this);
204	}
205
206	/**
207	* Returns the points of intersection between this {@link Arc} and the given
208	* {@link Polyline}.
209	*
210	* @param p
211	* The {@link Polyline} to test for intersections
212	* @return the points of intersection.
213	*/
214	public Point[] getIntersections(Polyline p) {
215	HashSet<Point> intersections = new HashSet<Point>();
216
217	for (CubicCurve seg : getBorderSegments()) {
218	intersections.addAll(Arrays.asList(seg.getIntersections(p)));
219	}
220
221	return intersections.toArray(new Point[] {});
222	}
223
224	/**
225	* Returns the points of intersection between this {@link Arc} and the given
226	* {@link QuadraticCurve}.
227	*
228	* @param c
229	* The {@link QuadraticCurve} to test for intersections
230	* @return the points of intersection.
231	*/
232	public Point[] getIntersections(QuadraticCurve c) {
233	HashSet<Point> intersections = new HashSet<Point>();
234
235	for (CubicCurve seg : getBorderSegments()) {
236	intersections.addAll(Arrays.asList(seg.getIntersections(c)));
237	}
238
239	return intersections.toArray(new Point[] {});
240	}
241
242	/**
243	* Returns the points of intersection between this {@link Arc} and the given
244	* {@link Rectangle}.
245	*
246	* @param r
247	* The {@link Rectangle} to test for intersections
248	* @return the points of intersection.
249	*/
250	public Point[] getIntersections(Rectangle r) {
251	HashSet<Point> intersections = new HashSet<Point>();
252
253	for (CubicCurve seg : getBorderSegments()) {
254	intersections.addAll(Arrays.asList(seg.getIntersections(r)));
255	}
256
257	return intersections.toArray(new Point[] {});
258	}
259
260	/**
261	* Returns the points of intersection between this {@link Arc} and the given
262	* {@link RoundedRectangle}.
263	*
264	* @param rr
265	* The {@link RoundedRectangle} to test for intersections
266	* @return the points of intersection.
267	*/
268	public Point[] getIntersections(RoundedRectangle rr) {
269	HashSet<Point> intersections = new HashSet<Point>();
270
271	// line segments
272	intersections.addAll(Arrays.asList(getIntersections(rr.getTop())));
273	intersections.addAll(Arrays.asList(getIntersections(rr.getLeft())));
274	intersections.addAll(Arrays.asList(getIntersections(rr.getBottom())));
275	intersections.addAll(Arrays.asList(getIntersections(rr.getRight())));
276
277	// arc segments
278	intersections.addAll(Arrays.asList(getIntersections(rr.getTopRight())));
279	intersections.addAll(Arrays.asList(getIntersections(rr.getTopLeft())));
280	intersections
281	.addAll(Arrays.asList(getIntersections(rr.getBottomLeft())));
282	intersections
283	.addAll(Arrays.asList(getIntersections(rr.getBottomRight())));
284
285	return intersections.toArray(new Point[] {});
286	}
287
128	public void setHeight(double height) {	288	public void setHeight(double height) {
129	this.height = height;	289	this.height = height;
130	}	290	}
Lines 149-155 Link Here
149	* @see Geometry#toPath()	309	* @see Geometry#toPath()
150	*/	310	*/
151	public Path toPath() {	311	public Path toPath() {
		312	CubicCurve[] segments = getBorderSegments();
		313	return toPath(segments);
		314	}
152		315
		316	public CubicCurve[] getBorderSegments() {
153	double start = getStartAngle().rad();	317	double start = getStartAngle().rad();
154	double end = getStartAngle().rad() + getAngularExtent().rad();	318	double end = getStartAngle().rad() + getAngularExtent().rad();
155		319
Lines 184-190 Link Here
184	}	348	}
185	}	349	}
186	}	350	}
187	return toPath(segments.toArray(new CubicCurve[] {}));	351	return segments.toArray(new CubicCurve[] {});
188	}	352	}
189		353
190	private CubicCurve computeApproximation(double start, double end) {	354	private CubicCurve computeApproximation(double start, double end) {





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;


	}

	/**
	 * 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.
	 * 

	 * @see Geometry#contains(Point)
	 */
	public boolean contains(Point p) {
		return CurveUtils.contains(this, p);
		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 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.

	 * @return the two {@link CubicCurve}s
	 */
	public CubicCurve[] split(double t) {
		return CurveUtils.split(this, t);
			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 the {@link CubicCurve} on the interval [t1, t2]
	 */
	public CubicCurve clip(double t1, double t2) {
		return CurveUtils.clip(this, t1, t2);
			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];
	}

	private static double getArea(Polygon p) {

		return new Point[] {};
	}

	/**
	 * Returns the points of intersection between this {@link CubicCurve} and
	 * the given {@link Arc}.
	 * 
	 * @param arc
	 *            The {@link Arc} to test for intersections
	 * @return the points of intersection.
	 */
	public Point[] getIntersections(Arc arc) {
		HashSet<Point> intersections = new HashSet<Point>();
			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)));

		for (CubicCurve seg : arc.getBorderSegments()) {
			intersections.addAll(Arrays.asList(getIntersections(seg)));
		}

		return intersections.toArray(new Point[] {});
		return new Point[] {};
	}

	/**

	 * @return the points of intersection
	 */
	public Point[] getIntersections(CubicCurve other) {
		if (equals(other)) {
			return new Point[] {};
		}
		return CurveUtils.getIntersections(this, other);
	}

	/**
	 * Returns the points of intersection between this {@link CubicCurve} and
	 * the given {@link Ellipse}.
	 * 
	 * @param e
	 *            The {@link Ellipse} to test for intersections
	 * @return the points of intersection.
	 */
	public Point[] getIntersections(Ellipse e) {
		return e.getIntersections(this);
	}

	/**

	}

	/**
	 * Returns the points of intersection between this {@link CubicCurve} and
	 * the given {@link Polygon}.
	 * 
	 * @param p
	 *            The {@link Polygon} to test for intersections
	 * @return the points of intersection.
	 */
	public Point[] getIntersections(Polygon p) {
		return p.getIntersections(this);
	}

	/**
	 * Returns the points of intersection between this {@link CubicCurve} and
	 * the given {@link Polyline}.
	 * 
	 * @param p
	 *            The {@link Polyline} to test for intersections
	 * @return the points of intersection.
	 */
	public Point[] getIntersections(Polyline p) {
		HashSet<Point> intersections = new HashSet<Point>();

		for (Line seg : p.getSegments()) {
			intersections.addAll(Arrays.asList(getIntersections(seg)));
		}

		return intersections.toArray(new Point[] {});
	}

	/**
	 * Returns the points of intersection between this {@link CubicCurve} and
	 * the given {@link QuadraticCurve}.
	 * 
	 * @param c
	 *            The {@link QuadraticCurve} to test for intersections
	 * @return the points of intersection.
	 */
	public Point[] getIntersections(QuadraticCurve c) {
		return getIntersections(c.getElevated());
	}

	/**
	 * Returns the points of intersection between this {@link CubicCurve} and
	 * the given {@link Rectangle}.
	 * 
	 * @param r
	 *            The {@link Rectangle} to test for intersections
	 * @return the points of intersection.
	 */
	public Point[] getIntersections(Rectangle r) {
		HashSet<Point> intersections = new HashSet<Point>();

		for (Line seg : r.getSegments()) {
			intersections.addAll(Arrays.asList(getIntersections(seg)));
		}

		return intersections.toArray(new Point[] {});
	}

	/**
	 * Returns the points of intersection between this {@link CubicCurve} and
	 * the given {@link RoundedRectangle}.
	 * 
	 * @param rr
	 *            The {@link RoundedRectangle} to test for intersections
	 * @return the points of intersection.
	 */
	public Point[] getIntersections(RoundedRectangle rr) {
		HashSet<Point> intersections = new HashSet<Point>();

		// line segments
		intersections.addAll(Arrays.asList(getIntersections(rr.getTop())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getLeft())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getBottom())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getRight())));

		// arc segments
		intersections.addAll(Arrays.asList(getIntersections(rr.getTopRight())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getTopLeft())));
		intersections
				.addAll(Arrays.asList(getIntersections(rr.getBottomLeft())));
		intersections
				.addAll(Arrays.asList(getIntersections(rr.getBottomRight())));

		return intersections.toArray(new Point[] {});
	}

	/**
	 * Returns the first control {@link Point}.
	 * 
	 * @return the first control {@link Point}.

	 */
	@Override
	public int hashCode() {
		// calculating a better hashCode is not possible, because due to the
		// imprecision, equals() is no longer transitive
		return 0;
	}


		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.
	 * 

	 * @return the {@link Point} at parameter t
	 */
	public Point get(double t) {
		return CurveUtils.get(this, t);
	}

	public CubicCurve getCopy() {
		return new CubicCurve(getP1(), getCtrl1(), getCtrl2(), getP2());

		// 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));
	}

}




import org.eclipse.gef4.geometry.utils.PrecisionUtils;

/**
 * Represents the geometric shape of an ellipse.
 * its enclosing framing rectangle.
 * 
 * Note that while all manipulations (e.g. within shrink, expand) within this
 * class are based on double precision, all comparisons (e.g. within contains,

	}

	/**
	 * Tests whether the given {@link CubicCurve} is fully contained within this
	 * {@link Ellipse}.
	 * 
	 * @param c
	 *            the {@link CubicCurve} to test for containment
	 * @return <code>true</code> in case the given {@link CubicCurve} is fully
	 *         contained, <code>false</code> otherwise
	 */
	public boolean contains(CubicCurve c) {
		return contains(c.getP1()) && contains(c.getP2())
				&& getIntersections(c).length == 0;
	}

	/**
	 * Tests whether the given {@link Ellipse} is fully contained within this
	 * {@link Ellipse}.
	 * 
	 * @param o
	 *            the {@link Ellipse} to test for containment
	 * @return <code>true</code> in case the given {@link Ellipse} is fully
	 *         contained, <code>false</code> otherwise
	 */
	public boolean contains(Ellipse o) {
		for (CubicCurve seg : o.getBorderSegments()) {
			if (!contains(seg)) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Tests whether the given {@link QuadraticCurve} is fully contained within
	 * this {@link Ellipse}.
	 * 
	 * @param c
	 *            the {@link QuadraticCurve} to test for containment
	 * @return <code>true</code> in case the given {@link QuadraticCurve} is
	 *         fully contained, <code>false</code> otherwise
	 */
	public boolean contains(QuadraticCurve c) {
		return contains(c.getP1()) && contains(c.getP2())
				&& getIntersections(c).length == 0;
	}

	/**
	 * Tests whether the given {@link Line} is fully contained within this
	 * {@link Ellipse}.
	 * 

	 *         otherwise
	 */
	public Point[] getIntersections(Rectangle rectangle) {
		HashSet<Point> intersections = new HashSet<Point>();

		for (Line segment : rectangle.getSegments()) {
			for (Point intersection : getIntersections(segment)) {


	/**
	 * Returns the intersection points of this {@link Ellipse}'s outline with
	 * the given {@link RoundedRectangle}'s outline.
	 * 
	 * @param rr
	 *            The {@link RoundedRectangle} to test for intersection
	 * @return an array containing the {@link Point}s of intersection of this
	 *         {@link Ellipse}'s outline with the given {@link RoundedRectangle}
	 *         's outline in case such intersection points exist, an empty array
	 *         otherwise.
	 */
	public Point[] getIntersections(RoundedRectangle rr) {
		HashSet<Point> intersections = new HashSet<Point>();

		// line segments
		intersections.addAll(Arrays.asList(getIntersections(rr.getTop())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getLeft())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getBottom())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getRight())));

		// arc segments
		intersections.addAll(Arrays.asList(getIntersections(rr.getTopRight())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getTopLeft())));
		intersections
				.addAll(Arrays.asList(getIntersections(rr.getBottomLeft())));
		intersections
				.addAll(Arrays.asList(getIntersections(rr.getBottomRight())));

		return intersections.toArray(new Point[] {});
	}

	/**
	 * Returns the intersection points of this {@link Ellipse}'s outline with
	 * the given {@link Line}.
	 * 
	 * @param line

	 */
	@Override
	public int hashCode() {
		// 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;
	}

	/**

	}

	/**
	 * Does the given {@link CubicCurve} intersect (including containment) this
	 * {@link Ellipse}?
	 * 
	 * @param c
	 * @return true if they intersect, false otherwise
	 */
	public boolean intersects(CubicCurve c) {
		return contains(c.getP1()) && contains(c.getP2())
				|| getIntersections(c).length > 0;
	}

	/**
	 * @see Geometry#intersects(Rectangle)
	 */
	public boolean intersects(Rectangle r) {


	/**
	 * Calculates the points of intersection of this {@link Ellipse} and the
	 * given {@link Arc}.
	 * 
	 * @param arc
	 *            The {@link Arc} to compute intersection points with
	 * @return the points of intersection of this {@link Ellipse} and the given
	 *         {@link Arc}.
	 */
	public Point[] getIntersections(Arc arc) {
		HashSet<Point> intersections = new HashSet<Point>();

		for (CubicCurve mySeg : getBorderSegments()) {
			for (CubicCurve arcSeg : arc.getBorderSegments()) {
				intersections.addAll(Arrays.asList(mySeg
						.getIntersections(arcSeg)));
			}
		}

		return intersections.toArray(new Point[] {});
	}

	/**
	 * Calculates the points of intersection of this {@link Ellipse} and the
	 * given {@link CubicCurve}.
	 * 
	 * @param curve


		return segs;
	}

	/**
	 * Computes and returns the points of intersection of this {@link Ellipse}'s
	 * outline with the given {@link QuadraticCurve}.
	 * 
	 * @param c
	 * @return the points of intersection of this {@link Ellipse}'s outline with
	 *         the given {@link QuadraticCurve}
	 */
	public Point[] getIntersections(QuadraticCurve c) {
		return getIntersections(c.getElevated());
	}
}

Lines 12-17 Link Here

(-)src/org/eclipse/gef4/geometry/shapes/Line.java (-2 / +65 lines)
12	*******************************************************************************/	12	*******************************************************************************/
13	package org.eclipse.gef4.geometry.shapes;	13	package org.eclipse.gef4.geometry.shapes;
14		14
		15	import java.util.Arrays;
		16	import java.util.HashSet;
		17
15	import org.eclipse.gef4.geometry.Point;	18	import org.eclipse.gef4.geometry.Point;
16	import org.eclipse.gef4.geometry.euclidean.Straight;	19	import org.eclipse.gef4.geometry.euclidean.Straight;
17	import org.eclipse.gef4.geometry.euclidean.Vector;	20	import org.eclipse.gef4.geometry.euclidean.Vector;
Lines 149-154 Link Here
149	return new Line(x1, y1, x2, y2);	152	return new Line(x1, y1, x2, y2);
150	}	153	}
151		154
		155	public Point[] getIntersections(Arc arc) {
		156	return arc.getIntersections(this);
		157	}
		158
		159	public Point[] getIntersections(CubicCurve c) {
		160	return c.getIntersections(this);
		161	}
		162
		163	public Point[] getIntersections(Ellipse e) {
		164	return e.getIntersections(this);
		165	}
		166
		167	public Point[] getIntersections(Polygon p) {
		168	return p.getIntersections(this);
		169	}
		170
		171	public Point[] getIntersections(Polyline p) {
		172	HashSet<Point> intersections = new HashSet<Point>();
		173
		174	for (Line seg : p.getSegments()) {
		175	intersections.add(getIntersection(seg));
		176	}
		177
		178	return intersections.toArray(new Point[] {});
		179	}
		180
		181	public Point[] getIntersections(QuadraticCurve c) {
		182	return c.getIntersections(this);
		183	}
		184
		185	public Point[] getIntersections(Rectangle r) {
		186	HashSet<Point> intersections = new HashSet<Point>();
		187
		188	for (Line seg : r.getSegments()) {
		189	intersections.addAll(Arrays.asList(getIntersection(seg)));
		190	}
		191
		192	return intersections.toArray(new Point[] {});
		193	}
		194
		195	public Point[] getIntersections(RoundedRectangle rr) {
		196	HashSet<Point> intersections = new HashSet<Point>();
		197
		198	// line segments
		199	intersections.add(getIntersection(rr.getTop()));
		200	intersections.add(getIntersection(rr.getLeft()));
		201	intersections.add(getIntersection(rr.getBottom()));
		202	intersections.add(getIntersection(rr.getRight()));
		203
		204	// arc segments
		205	intersections.addAll(Arrays.asList(getIntersections(rr.getTopRight())));
		206	intersections.addAll(Arrays.asList(getIntersections(rr.getTopLeft())));
		207	intersections
		208	.addAll(Arrays.asList(getIntersections(rr.getBottomLeft())));
		209	intersections
		210	.addAll(Arrays.asList(getIntersections(rr.getBottomRight())));
		211
		212	return intersections.toArray(new Point[] {});
		213	}
		214
152	/**	215	/**
153	* Returns the single intersection point between this {@link Line} and the	216	* Returns the single intersection point between this {@link Line} and the
154	* given one, in case it exists. Note that even in case	217	* given one, in case it exists. Note that even in case
Lines 269-277 Link Here
269	*/	332	*/
270	@Override	333	@Override
271	public int hashCode() {	334	public int hashCode() {
272	// calculating a better hashCode is not possible	335	// calculating a better hashCode is not possible, because due to the
		336	// imprecision, equals() is no longer transitive
273	return 0;	337	return 0;
274	// return (int) x1 + (int) y1 + (int) x2 + (int) y2;
275	}	338	}
276		339
277	/**	340	/**




package org.eclipse.gef4.geometry.shapes;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

import org.eclipse.gef4.geometry.Angle;

		return intersections.toArray(new Point[] {});
	}

	public Point[] getIntersections(RoundedRectangle rr) {
		HashSet<Point> intersections = new HashSet<Point>();

		// line segments
		intersections.addAll(Arrays.asList(getIntersections(rr.getTop())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getLeft())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getBottom())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getRight())));

		// arc segments
		intersections.addAll(Arrays.asList(getIntersections(rr.getTopRight())));
		intersections.addAll(Arrays.asList(getIntersections(rr.getTopLeft())));
		intersections
				.addAll(Arrays.asList(getIntersections(rr.getBottomLeft())));
		intersections
				.addAll(Arrays.asList(getIntersections(rr.getBottomRight())));

		return intersections.toArray(new Point[] {});
	}

	/**
	 * Returns the points of intersection between this {@link Polygon} and the
	 * given {@link Ellipse} e.

	 */
	@Override
	public int hashCode() {
		// calculating a better hashCode is not possible, because due to the
		// imprecision, equals() is no longer transitive
		return 0;
		// return PointListUtils.getHashCode(points);
	}

	/**

		return translate(p.x, p.y);
	}

	/**
	 * Returns the points of intersection between this {@link Polygon} and the
	 * given {@link QuadraticCurve} c.
	 * 
	 * @param c
	 * @return The points of intersection.
	 */
	public Point[] getIntersections(QuadraticCurve c) {
		HashSet<Point> intersections = new HashSet<Point>();

		for (Line seg : getSegments()) {
			for (Point poi : c.getIntersections(seg)) {
				intersections.add(poi);
			}
		}

		return intersections.toArray(new Point[] {});
	}

	/**
	 * Returns the points of intersection between this {@link Polygon} and the
	 * given {@link Arc} arc.
	 * 
	 * @param arc
	 *            The {@link Arc} to test for intersections
	 * @return the points of intersection.
	 */
	public Point[] getIntersections(Arc arc) {
		HashSet<Point> intersections = new HashSet<Point>();

		for (CubicCurve seg : arc.getBorderSegments()) {
			intersections.addAll(Arrays.asList(getIntersections(seg)));
		}

		return intersections.toArray(new Point[] {});
	}

	/**
	 * Returns the points of intersection between this {@link Polygon} and the
	 * given {@link CubicCurve} c.
	 * 
	 * @param c
	 * @return The points of intersection.
	 */
	public Point[] getIntersections(CubicCurve c) {
		HashSet<Point> intersections = new HashSet<Point>();

		for (Line seg : getSegments()) {
			for (Point poi : c.getIntersections(seg)) {
				intersections.add(poi);
			}
		}

		return intersections.toArray(new Point[] {});
	}

	// TODO: union point, rectangle, polygon, etc.
}

Lines 188-194 Link Here

(-)src/org/eclipse/gef4/geometry/shapes/Polyline.java (-1 / +2 lines)
188	*/	188	*/
189	@Override	189	@Override
190	public int hashCode() {	190	public int hashCode() {
191	// calculating a better hashCode is not possible	191	// calculating a better hashCode is not possible, because due to the
		192	// imprecision, equals() is no longer transitive
192	return 0;	193	return 0;
193	}	194	}
194		195





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;


	}

	/**
	 * 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

	}

	/**
	 * 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

	 */
	@Override
	public int hashCode() {
		// calculating a better hashCode is not possible, because due to the
		// imprecision, equals() is no longer transitive
		return 0;
	}


	 * @return the {@link Point} at parameter t
	 */
	public Point get(double t) {
		return CurveUtils.get(this, t);
				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 true if p lies on the curve, false otherwise
	 */
	public boolean contains(Point p) {
		return CurveUtils.contains(this, p);
		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;
	}

	/**

		// "Curves and Surfaces for Computer Aided Geometric Design" by Farin,
		// Gerald E., Academic Press 1988
		controlPoints[0] = getP1();
		controlPoints[1] = getP1().getScaled(1d / 3d).getTranslated(
				getCtrl().getScaled(2d / 3d));
		controlPoints[2] = getCtrl().getScaled(2d / 3d).getTranslated(
				getP2().getScaled(1d / 3d));
		controlPoints[3] = getP2();

		return new CubicCurve(controlPoints);
				controlPoints[2], controlPoints[3]);
	}

	/**

		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

	 *         [0, t] 2. [t, 1]
	 */
	public QuadraticCurve[] split(double t) {
		return CurveUtils.split(this, t);
			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 the {@link QuadraticCurve} on the interval [t1, t2]
	 */
	public QuadraticCurve clip(double t1, double t2) {
		return CurveUtils.clip(this, t1, t2);
			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];
	}

}




	 */
	@Override
	public int hashCode() {
		// 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;
	}

	/**

		double x2 = Math.min(x + width, r.x + r.width);
		double y1 = Math.max(y, r.y);
		double y2 = Math.min(y + height, r.y + r.height);
		if (PrecisionUtils.greaterEqual(x2 - x1, 0)
				&& PrecisionUtils.greaterEqual(y2 - y1, 0)) {
			return setBounds(x1, y1, x2 - x1 < 0 ? 0 : x2 - x1, y2 - y1 < 0 ? 0
					: y2 - y1);
			return setBounds(x1, y1, x2 - x1, y2 - y1);
		}
		return setBounds(0, 0, 0, 0); // no intersection
	}

	/**




 *******************************************************************************/
package org.eclipse.gef4.geometry.shapes;

import org.eclipse.gef4.geometry.Angle;
import org.eclipse.gef4.geometry.Point;
import org.eclipse.gef4.geometry.transform.AffineTransform;
import org.eclipse.gef4.geometry.utils.PrecisionUtils;

	 */
	@Override
	public int hashCode() {
		// calculating a better hashCode is not possible, because due to the
		// imprecision, equals() is no longer transitive
		return 0;
	}


		return path;
	}

	/**
	 * Returns the top edge of this {@link RoundedRectangle}.
	 * 
	 * @return the top edge of this {@link RoundedRectangle}.
	 */
	public Line getTop() {
		return new Line(x + arcWidth, y, x + width - arcWidth, y);
	}

	/**
	 * Returns the bottom edge of this {@link RoundedRectangle}.
	 * 
	 * @return the bottom edge of this {@link RoundedRectangle}.
	 */
	public Line getBottom() {
		return new Line(x + arcWidth, y + height - arcHeight, x + width
				- arcWidth, y + height - arcHeight);
	}

	/**
	 * Returns the right edge of this {@link RoundedRectangle}.
	 * 
	 * @return the right edge of this {@link RoundedRectangle}.
	 */
	public Line getRight() {
		return new Line(x + width, y + arcHeight, x + width, y + height
				- arcHeight);
	}

	/**
	 * Returns the left edge of this {@link RoundedRectangle}.
	 * 
	 * @return the left edge of this {@link RoundedRectangle}.
	 */
	public Line getLeft() {
		return new Line(x, y + arcHeight, x, y + height - arcHeight);
	}

	/**
	 * Returns the top left {@link Arc} of this {@link RoundedRectangle}.
	 * 
	 * @return the top left {@link Arc} of this {@link RoundedRectangle}.
	 */
	public Arc getTopLeft() {
		return new Arc(x, y, arcWidth, arcHeight, Angle.fromDeg(90),
				Angle.fromDeg(90));
	}

	/**
	 * Returns the top right {@link Arc} of this {@link RoundedRectangle}.
	 * 
	 * @return the top right {@link Arc} of this {@link RoundedRectangle}.
	 */
	public Arc getTopRight() {
		return new Arc(x + width - arcWidth, y, arcWidth, arcHeight,
				Angle.fromDeg(0), Angle.fromDeg(90));
	}

	/**
	 * Returns the bottom left {@link Arc} of this {@link RoundedRectangle}.
	 * 
	 * @return the bottom left {@link Arc} of this {@link RoundedRectangle}.
	 */
	public Arc getBottomLeft() {
		return new Arc(x, y + height - arcHeight, arcWidth, arcHeight,
				Angle.fromDeg(180), Angle.fromDeg(90));
	}

	/**
	 * Returns the bottom right {@link Arc} of this {@link RoundedRectangle}.
	 * 
	 * @return the bottom right {@link Arc} of this {@link RoundedRectangle}.
	 */
	public Arc getBottomRight() {
		return new Arc(x + width - arcWidth, y + height - arcHeight, arcWidth,
				arcHeight, Angle.fromDeg(270), Angle.fromDeg(90));
	}

	@Override
	public String toString() {
		return "RoundedRectangle: (" + x + ", " + y + ", " + width + ", " + height + ", " + arcWidth + ", " + arcHeight; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$ //$NON-NLS-6$




/*******************************************************************************
 * 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 java.util.Set;

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;
				Point tmp = this.toPoint();
				if (tmp == null) {
					return o.toPoint() == null;
				}
				return tmp.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 <code>x*x + y*y = 1</code>.
		 * 
		 * @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);
		}

		public String toString() {
			return "Vector3D (" + x + ", " + y + ", " + z + ")";
		}

		@Override
		public int hashCode() {
			// cannot generate a good hash-code because of the imprecise
			// comparisons
			return 0;
		}
	}

	/**
	 * 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 UNRECOGNIZABLE_PRECISION_FRACTION = PrecisionUtils
				.calculateFraction(0) / 10;

		private static final double END_POINTS_CHECK_AREA = 1;

		private Vector3D[] points;

		/**
		 * 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<ImpreciseDouble> getRoots(BezierCurve c,
				double a, double b) {
			BezierCurve clipped = c.getClipped(a, b);

			if (sameSign(clipped)) {
				return new HashSet<ImpreciseDouble>();
			}

			if (PrecisionUtils.equal(a, b, +2)) {
				HashSet<ImpreciseDouble> root = new HashSet<ImpreciseDouble>();
				root.add(new ImpreciseDouble((a + b) / 2));
				return root;
			}

			HashSet<ImpreciseDouble> left = getRoots(c, a, (a + b) / 2);
			HashSet<ImpreciseDouble> 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<ImpreciseDouble> 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;
					} else {
						Point qx = get(xt).toPoint();
						Point qy = get(yt).toPoint();
						// qx != null && qy != null &&
						if (qx.equals(qy)) {
							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].
		 * 
		 * @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 Vector3D parameterConvergence(BezierCurve p, double ps,
				double pe, BezierCurve q, double qs, double qe) {
			// localEndPointsCheck();
			if (PrecisionUtils.equal(ps, pe, +2)) {
				Vector3D poi = p.get((ps + pe) / 2);
				return poi;
			}
			if (PrecisionUtils.equal(qs, qe, +2)) {
				Vector3D poi = q.get((qs + qe) / 2);
				return poi;
			}
			return null;
		}

		/**
		 * 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 = getRealPoints();

			double xmin = realPoints[0].x, xmax = realPoints[0].x, ymin = realPoints[0].y, ymax = realPoints[0].y;

			for (int i = 1; i < realPoints.length; i++) {
				if (realPoints[i].x < xmin) {
					xmin = realPoints[i].x;
				} else if (realPoints[i].x > xmax) {
					xmax = realPoints[i].x;
				}

				if (realPoints[i].y < ymin) {
					ymin = realPoints[i].y;
				} else if (realPoints[i].y > ymax) {
					ymax = realPoints[i].y;
				}
			}

			return new Rectangle(xmin, ymin, xmax - xmin, ymax - ymin);
		}

		/**
		 * 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++) {
				double y = line.getDot(points[i]);
				D[i] = new Vector3D(
						(double) (i) / (double) (points.length - 1), y, 1);
			}
			return D;
		}

		public Set<Vector3D> getIntersections(BezierCurve other) {
			// end point intersections
			Set<Vector3D> endPointIntersections = getEndPointIntersections(
					this, other);

			// TODO: tangential intersections

			// simple intersections
			// TODO: recursion => iteration
			Set<Vector3D> intersections = getIntersections(
					endPointIntersections, this, 0, 1, other, 0, 1);

			intersections.addAll(endPointIntersections);
			return intersections;
		}

		private Set<Vector3D> getEndPointIntersections(BezierCurve p,
				BezierCurve q) {
			Set<Vector3D> intersections = new HashSet<Vector3D>();
			for (int i : new int[] { 0, p.points.length - 1 }) {
				if (q.contains(p.points[i].toPoint())) {
					intersections.add(p.points[i]);
				}
			}
			for (int i : new int[] { 0, q.points.length - 1 }) {
				if (p.contains(q.points[i].toPoint())) {
					intersections.add(q.points[i]);
				}
			}
			return intersections;
		}

		private static class FatLine {
			public Vector3D line;
			public double dmin, dmax;

			private FatLine() {
				line = new Vector3D(0, 0, 0);
				dmin = dmax = 0;
			}

			public static FatLine from(BezierCurve c, boolean ortho) {
				FatLine L = new FatLine();
				L.dmin = L.dmax = 0;

				L.line = c.points[0].getCrossed(c.points[c.points.length - 1]);

				if (ortho) {
					L.line = c.points[0].getCrossed(c.points[0]
							.getAdded(new Vector3D(L.line.x, L.line.y, 0)));
				}

				L.line = L.line.getLineNormalized();

				if (L.line == null) {
					return null;
				}

				for (int i = 0; i < c.points.length; i++) {
					double d = L.line.getDot(c.points[i]);
					if (d < L.dmin)
						L.dmin = d;
					else if (d > L.dmax)
						L.dmax = d;
				}

				return L;
			}
		}

		private static double intersectXAxisParallel(Point p, Point q, double y) {
			// p.y != q.y because this routine is only called when either the
			// lower or the higher fat line bound is crossed.
			return new Vector3D(p).getCrossed(new Vector3D(q))
					.getCrossed(new Vector3D(0, 1, -y)).toPoint().x;
			// double dy = q.y - p.y;
			// double s = (y - p.y) / dy;
			// return (q.x - p.x) * s + p.x;
		}

		private static Point[] getConvexHull(Vector3D[] points) {
			Point[] chPoints = new Point[points.length];
			for (int i = 0; i < points.length; i++) {
				chPoints[i] = points[i].toPoint();
			}
			return PointListUtils.getConvexHull(chPoints);
		}

		/**
		 * @param L
		 * @return
		 */
		private double[] clipTo(FatLine L) {
			double[] interval = new double[] { 1, 0 };

			Point[] D = getConvexHull(genDifferencePoints(L.line));

			// we do not know which point is returned first by the
			// getConvexHull() method. That's why we have to check the "first"
			// point, too.
			boolean isBelow = D[0].y < L.dmin;
			boolean isAbove = D[0].y > L.dmax;
			insideFatLineCheck(interval, D, 0, isBelow, isAbove);

			boolean wasBelow = isBelow, wasAbove = isAbove;

			for (int i = 1; i < D.length; i++) {
				isBelow = D[i].y < L.dmin;
				isAbove = D[i].y > L.dmax;

				insideFatLineCheck(interval, D, i, isBelow, isAbove);
				wasBelow = belowFatLineCheck(interval, L, D, i - 1, i, isBelow,
						wasBelow);
				wasAbove = aboveFatLineCheck(interval, L, D, i - 1, i, isAbove,
						wasAbove);
			}

			// closing segment
			isBelow = D[0].y < L.dmin;
			isAbove = D[0].y > L.dmax;
			belowFatLineCheck(interval, L, D, D.length - 1, 0, isBelow,
					wasBelow);
			aboveFatLineCheck(interval, L, D, D.length - 1, 0, isAbove,
					wasAbove);

			return interval;
		}

		private boolean aboveFatLineCheck(double[] interval, FatLine L,
				Point[] D, int i, int j, boolean isAbove, boolean wasAbove) {
			if (isAbove != wasAbove) {
				// crosses higher
				double x = intersectXAxisParallel(D[i], D[j], L.dmax);
				moveInterval(interval, x);
				wasAbove = isAbove;
			}
			return wasAbove;
		}

		private boolean belowFatLineCheck(double[] interval, FatLine L,
				Point[] D, int i, int j, boolean isBelow, boolean wasBelow) {
			if (isBelow != wasBelow) {
				// crosses lower
				double x = intersectXAxisParallel(D[i], D[j], L.dmin);
				moveInterval(interval, x);
				wasBelow = isBelow;
			}
			return wasBelow;
		}

		private void insideFatLineCheck(double[] interval, Point[] D, int i,
				boolean isBelow, boolean isAbove) {
			if (!(isBelow || isAbove)) {
				// inside
				moveInterval(interval, D[i].x);
			}
		}

		private void moveInterval(double[] interval, double x) {
			if (interval[0] > x)
				interval[0] = x;
			if (interval[1] < x)
				interval[1] = x;
		}

		/**
		 * Computes and returns the points of intersection between this
		 * {@link BezierCurve} and the given other {@link BezierCurve}.
		 * 
		 * @param endPointIntersections
		 *            all points of intersections that are end-points of one of
		 *            the curves
		 * @param p
		 *            first {@link BezierCurve}
		 * @param ps
		 *            start value of the first {@link BezierCurve}'s parameter
		 *            interval
		 * @param pe
		 *            end value of the first {@link BezierCurve}'s parameter
		 *            interval
		 * @param q
		 *            second {@link BezierCurve}
		 * @param qs
		 *            start value of the second {@link BezierCurve}'s parameter
		 *            interval
		 * @param qe
		 *            end value of the second {@link BezierCurve}'s parameter
		 *            interval
		 * @return the intersections between this {@link BezierCurve} and the
		 *         given other {@link BezierCurve}
		 */
		@SuppressWarnings("unchecked")
		public static Set<Vector3D> getIntersections(
				Set<Vector3D> endPointIntersections, BezierCurve p, double ps,
				double pe, BezierCurve q, double qs, double qe) {
			BezierCurve pClipped = p.getClipped(ps, pe);
			BezierCurve qClipped = q.getClipped(qs, qe);

			// end point intersection check
			if (endPointIntersectionConvergence(endPointIntersections,
					pClipped, ps, pe, qClipped, qs, qe)) {
				Set<Vector3D> no_intersections = new HashSet<Vector3D>(0);
				return no_intersections;
			}

			// TODO: tangential intersection check

			// parameter convergence check
			Vector3D poi = parameterConvergence(p, ps, pe, q, qs, qe);
			if (poi != null) {
				// "exactly" one intersection
				if (p.contains(poi.toPoint()) && q.contains(poi.toPoint())) {
					Set<Vector3D> intersection = new HashSet<Vector3D>(1);
					intersection.add(poi);
					return intersection;
				}
				Set<Vector3D> no_intersections = new HashSet<Vector3D>(0);
				return no_intersections;
			}

			Set<Vector3D> intersections = new HashSet<Vector3D>();

			// construct "parallel" and "orthogonal" fat lines
			FatLine L1 = FatLine.from(qClipped, false);
			FatLine L2 = FatLine.from(qClipped, true);

			// curve implosion check
			if (L1 == null || L2 == null) {
				// qClipped is too small to construct a fat line from it
				// therefore, return its mid-point if it is contained by the
				// other curve
				Vector3D mid = q.get((qs + qe) / 2);
				if (p.contains(mid.toPoint())) {
					Set<Vector3D> intersection = new HashSet<Vector3D>(1);
					intersection.add(mid);
					return intersection;
				}
				Set<Vector3D> no_intersections = new HashSet<Vector3D>(0);
				return no_intersections;
			}

			// clip to the fat lines
			double[] interval = pClipped.clipTo(L1);
			double[] interval_ortho = pClipped.clipTo(L2);

			// pick smaller interval range
			if ((interval[1] - interval[0]) > (interval_ortho[1] - interval_ortho[0])) {
				interval[0] = interval_ortho[0];
				interval[1] = interval_ortho[1];
			}

			// re-calculate s and e from the clipped interval
			double news = ps + interval[0] * (pe - ps);
			double newe = ps + interval[1] * (pe - ps);
			double ratio = (newe - news) / (pe - ps);
			ps = news;
			pe = newe;

			if (ratio < 0) {
				// no more intersections
				return intersections;
			} else if (ratio > 0.8) {
				// split longer curve and find intersections for both halves
				if ((pe - ps) > (qe - qs)) {
					double pm = (ps + pe) / 2;
					intersections.addAll(getIntersections(
							endPointIntersections, p, ps, pm, q, qs, qe));
					intersections.addAll(getIntersections(
							endPointIntersections, p, pm
									+ UNRECOGNIZABLE_PRECISION_FRACTION, pe, q,
							qs, qe));
				} else {
					double qm = (qs + qe) / 2;
					intersections.addAll(getIntersections(
							endPointIntersections, q, qs, qm, p, ps, pe));
					intersections.addAll(getIntersections(
							endPointIntersections, q, qm
									+ UNRECOGNIZABLE_PRECISION_FRACTION, qe, p,
							ps, pe));
				}

				return intersections;
			} else {
				// clipped more than 20%
				return getIntersections(endPointIntersections, q, qs, qe, p,
						ps, pe);
			}
		}

		private static boolean endPointIntersectionConvergence(
				Set<Vector3D> endPointIntersections, BezierCurve pClipped,
				double ps, double pe, BezierCurve qClipped, double qs, double qe) {
			if (PrecisionUtils.equal(ps, pe, -3)) {
				if (endPointIntersections.contains(pClipped.points[0])
						|| endPointIntersections
								.contains(pClipped.points[pClipped.points.length - 1])) {
					return true;
				}
			}
			if (PrecisionUtils.equal(qs, qe, -3)) {
				if (endPointIntersections.contains(qClipped.points[0])
						|| endPointIntersections
								.contains(qClipped.points[qClipped.points.length - 1])) {
					return true;
				}
			}
			return false;
		}
	}

	/**
	 * 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) {
		Set<CurveUtils.Vector3D> intersections = new BezierCurve(p)
				.getIntersections(new BezierCurve(q));

		Set<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();
	}

	/**
	 * 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);
		return new QuadraticCurve(bc.getClipped(t1, t2).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);
		return new CubicCurve(bc.getClipped(t1, t2).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();
	}

	/**
	 * Computes and returns the bounds of the control polygon of the given
	 * {@link CubicCurve}. The control polygon is the convex hull of the start-,
	 * end-, and control points of the {@link CubicCurve}.
	 * 
	 * @param c
	 *            the {@link CubicCurve} to compute the control bounds for
	 * @return the bounds of the control polygon of the given {@link CubicCurve}
	 */
	public static Rectangle getControlBounds(CubicCurve c) {
		return new BezierCurve(c).getControlBounds();
	}
}

Lines 11-16 Link Here

(-)src/org/eclipse/gef4/geometry/utils/PointListUtils.java (+97 lines)
11	*******************************************************************************/	11	*******************************************************************************/
12	package org.eclipse.gef4.geometry.utils;	12	package org.eclipse.gef4.geometry.utils;
13		13
		14	import java.util.ArrayList;
		15	import java.util.Arrays;
		16	import java.util.Comparator;
		17
14	import org.eclipse.gef4.geometry.Point;	18	import org.eclipse.gef4.geometry.Point;
15	import org.eclipse.gef4.geometry.shapes.Line;	19	import org.eclipse.gef4.geometry.shapes.Line;
16	import org.eclipse.gef4.geometry.shapes.Polygon;	20	import org.eclipse.gef4.geometry.shapes.Polygon;
Lines 108-113 Link Here
108	return hashCode;	112	return hashCode;
109	}	113	}
110		114
		115	private static void swapLowestYPointToStart(Point[] points) {
		116	int minIdx = 0;
		117	Point min = points[minIdx];
		118	for (int i = 1; i < points.length; i++) {
		119	if (points[i].y < min.y \|\| points[i].y == min.y
		120	&& points[i].x < min.x) {
		121	min = points[i];
		122	minIdx = i;
		123	}
		124	}
		125	Point tmp = points[0];
		126	points[0] = points[minIdx];
		127	points[minIdx] = tmp;
		128	}
		129
		130	private static void sortPointsByAngleToStart(Point[] points) {
		131	final Point p0 = points[0];
		132	Arrays.sort(points, 1, points.length, new Comparator<Point>() {
		133	public int compare(Point p1, Point p2) {
		134	double m1 = (p1.x - p0.x) / (-p1.y + p0.y);
		135	double m2 = (p2.x - p0.x) / (-p2.y + p0.y);
		136	if (m1 < m2) {
		137	return -1;
		138	}
		139	return 1;
		140	}
		141	});
		142	}
		143
		144	private static ArrayList<Point> initializeStack(Point[] points) {
		145	ArrayList<Point> stack = new ArrayList<Point>();
		146	if (points.length > 0) {
		147	stack.add(0, points[0]);
		148	if (points.length > 1) {
		149	stack.add(0, points[1]);
		150	if (points.length > 2) {
		151	stack.add(0, points[2]);
		152	}
		153	}
		154	}
		155	return stack;
		156	}
		157
		158	private static void expandToFullConvexHull(ArrayList<Point> stack,
		159	Point[] points) {
		160	for (int i = 3; i < points.length; i++) {
		161	// do always turn right
		162	while (stack.size() > 2
		163	&& CurveUtils.getSignedDistance(stack.get(1), stack.get(0),
		164	points[i]) > 0) {
		165	stack.remove(0);
		166	}
		167	stack.add(0, points[i]);
		168	}
		169	}
		170
		171	/**
		172	* Computes the convex hull of the given set of {@link Point}s using the
		173	* Graham scan algorithm.
		174	*
		175	* @param points
		176	* the set of {@link Point}s to calculate the convex hull for
		177	* @return the convex hull of the given set of {@link Point}s
		178	*/
179	public static Point[] getConvexHull(Point[] points) {
180	// do a graham scan to find the convex hull of the given set of points
181	swapLowestYPointToStart(points);
182	sortPointsByAngleToStart(points);
183	ArrayList<Point> convexHull = initializeStack(points);
184	expandToFullConvexHull(convexHull, points);
185	return convexHull.toArray(new Point[] {});
186	}
187
111	/**	188	/**
112	* Converts a given array of {@link Point} into an array of doubles	189	* Converts a given array of {@link Point} into an array of doubles
113	* containing the x and y coordinates of the given points, where the x and y	190	* containing the x and y coordinates of the given points, where the x and y
Lines 129-134 Link Here
129	}	206	}
130		207
131	/**	208	/**
		209	* Converts a given array of x/y coordinate values into an array of
		210	* {@link Point}s.
		211	*
		212	* @param coordinates
		213	* @return a new array of {@link Point}s, representing the given x and y
		214	* coordinates
		215	*/
		216	public static Point[] toPointsArray(double[] coordinates) {
		217	if (coordinates.length % 2 != 0) {
		218	throw new IllegalArgumentException(
		219	"The coordinates array may not have an odd number of items.");
		220	}
		221	Point[] points = new Point[coordinates.length / 2];
		222	for (int i = 0; i < points.length; i++) {
		223	points[i] = new Point(coordinates[2 * i], coordinates[2 * i + 1]);
		224	}
		225	return points;
		226	}
		227
		228	/**
132	* Converts an array of double values into an array of integer values by	229	* Converts an array of double values into an array of integer values by
133	* casting them.	230	* casting them.
134	*	231	*




	 */
	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 b = B / A;
		double c = C / A;
		double d = D / A;

		// 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;

		// short-cut for p = 0
		double q = 2 * a * a * a / 27 - a * b / 3 + c;

		// short-cuts for p = 0, q = 0:
		if (PrecisionUtils.equal(p, 0, +4)) {
			// 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 };
		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 };
			}
		}

		double p_3 = p / 3;


		if (PrecisionUtils.equal(D, 0, +4)) {
			// two real solutions
			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 - b / 3 };
		} else {
			// three real solutions
			double r = Math.sqrt(-p_3 * p_3 * p_3);

			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) - b / 3,
					co * Math.cos((phi + 2 * Math.PI) / 3) - b / 3,
					co * Math.cos((phi + 4 * Math.PI) / 3) - b / 3 };
		}
	}

}

Lines 28-34 Link Here

(-)src/org/eclipse/gef4/geometry/utils/PrecisionUtils.java (-1 / +1 lines)
28	*/	28	*/
29	private static final int DEFAULT_SCALE = 6;	29	private static final int DEFAULT_SCALE = 6;
30		30
31	private static final double calculateFraction(int shift) {	31	public static final double calculateFraction(int shift) {
32	return 1 / Math.pow(10, DEFAULT_SCALE + shift);	32	return 1 / Math.pow(10, DEFAULT_SCALE + shift);
33	}	33	}
34		34




import org.junit.runners.Suite.SuiteClasses;

@RunWith(Suite.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 {

}




	}

	@Test
	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
	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);
	}

}




/*******************************************************************************
 * 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.shapes.Rectangle;
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) {
				assertTrue(c.contains(c.get(t)));
			}
		}
	}

	@Test
	public void test_getControlBounds() {
		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);
			Rectangle bounds = CurveUtils.getControlBounds(c);
			for (double t = 0; t <= 1; t += step) {
				assertTrue(bounds.contains(c.get(t)));
			}
			assertTrue(bounds.contains(c.get(1)));
		}
	}

	@Test
	public void test_getIntersections_BezierClipping_simple() {
		CubicCurve c1 = new CubicCurve(new double[] { 100, 200, 200, 100, 300,
				300, 400, 200 });
		CubicCurve c2 = new CubicCurve(new double[] { 250, 100, 350, 200, 150,
				300, 250, 400 });

		assertEquals(1, c1.getIntersections(c2).length);
	}

}




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;

/**

		}
	}

	@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);

		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)
		r2 = r.getExpanded(0, 0, 100, 0);
		e2 = new Ellipse(r2);
		intersections = e1.getIntersections(e2);
		assertEquals(3, intersections.length);

	}

	@Test
	public void test_getIntersections_with_Ellipse_Bezier_special() {
		// 3 nearly tangential intersections
		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);
	}

}

Lines 19-24 Link Here

(-)src/org/eclipse/gef4/geometry/tests/PointListUtilsTests.java (+46 lines)
19		19
20	import org.eclipse.gef4.geometry.Point;	20	import org.eclipse.gef4.geometry.Point;
21	import org.eclipse.gef4.geometry.shapes.Line;	21	import org.eclipse.gef4.geometry.shapes.Line;
		22	import org.eclipse.gef4.geometry.shapes.Polygon;
22	import org.eclipse.gef4.geometry.shapes.Rectangle;	23	import org.eclipse.gef4.geometry.shapes.Rectangle;
23	import org.eclipse.gef4.geometry.utils.PointListUtils;	24	import org.eclipse.gef4.geometry.utils.PointListUtils;
24	import org.eclipse.gef4.geometry.utils.PrecisionUtils;	25	import org.eclipse.gef4.geometry.utils.PrecisionUtils;
Lines 161-164 Link Here
161	assertTrue(PrecisionUtils.equal(points[i].y, i - 1));	162	assertTrue(PrecisionUtils.equal(points[i].y, i - 1));
162	}	163	}
163	}	164	}
		165
		166	@Test
		167	public void test_getConvexHull() {
		168	// test case from
		169	// http://stackoverflow.com/questions/482278/test-case-data-for-convex-hull
		170
		171	Point[] points = PointListUtils.toPointsArray(new double[] {
		172	0.3215348546593775, 0.03629583077160248, 0.02402358131857918,
		173	-0.2356728797179394, 0.04590851212470659, -0.4156409924995536,
		174	0.3218384001607433, 0.1379850698988746, 0.11506479756447,
		175	-0.1059521474930943, 0.2622539999543261, -0.29702873322836,
		176	-0.161920957418085, -0.4055339716426413, 0.1905378631228002,
		177	0.3698601009043493, 0.2387090918968516, -0.01629827079949742,
		178	0.07495888748668034, -0.1659825110491202, 0.3319341836794598,
		179	-0.1821814101954749, 0.07703635755650362, -0.2499430638271785,
		180	0.2069242999022122, -0.2232970760420869, 0.04604079532068295,
		181	-0.1923573186549892, 0.05054295812784038, 0.4754929463150845,
		182	-0.3900589168910486, 0.2797829520700341, 0.3120693385713448,
		183	-0.0506329867529059, 0.01138812723698857, 0.4002504701728471,
		184	0.009645149586391732, 0.1060251100976254, -0.03597933197019559,
		185	0.2953639456959105, 0.1818290866742182, 0.001454397571696298,
		186	0.444056063372694, 0.2502497166863175, -0.05301752458607545,
		187	-0.06553921621808712, 0.4823896228171788, -0.4776170002088109,
		188	-0.3089226845734964, -0.06356112199235814, -0.271780741188471,
		189	0.1810810595574612, 0.4293626522918815, 0.2980897964891882,
		190	-0.004796652127799228, 0.382663812844701, 0.430695573269106,
		191	-0.2995073500084759, 0.1799668387323309, -0.2973467472915973,
		192	0.4932166845474547, 0.4928094162538735, -0.3521487911717489,
		193	0.4352656197131292, -0.4907368011686362, 0.1865826865533206,
		194	-0.1047924716070224, -0.247073392148198, 0.4374961861758457,
		195	-0.001606279519951237, 0.003256207800708899,
		196	-0.2729194320486108, 0.04310378203457577, 0.4452604050238248,
		197	0.4916198379282093, -0.345391701297268, 0.001675087028811806,
		198	0.1531837672490476, -0.4404289572876217, -0.2894855991839297 });
		199
		200	Point[] convexHull = PointListUtils.getConvexHull(points);
		201
		202	assertTrue(new Polygon(PointListUtils.toPointsArray(new double[] {
		203	-0.161920957418085, -0.4055339716426413, -0.4404289572876217,
		204	-0.2894855991839297, -0.4907368011686362, 0.1865826865533206,
		205	-0.3521487911717489, 0.4352656197131292, 0.05054295812784038,
		206	0.4754929463150845, 0.4932166845474547, 0.4928094162538735,
		207	0.4916198379282093, -0.345391701297268, 0.4823896228171788,
		208	-0.4776170002088109 })).equals(new Polygon(convexHull)));
		209	}
164	}	210	}

Lines 30-45 Link Here

(-)src/org/eclipse/gef4/geometry/tests/PolynomCalculationUtilsTests.java (-5 / +63 lines)
30		30
31	solutions = PolynomCalculationUtils.getCubicRoots(1, 0, 1, 0);	31	solutions = PolynomCalculationUtils.getCubicRoots(1, 0, 1, 0);
32	Arrays.sort(solutions);	32	Arrays.sort(solutions);
		33	assertEquals("one real solution", 1, solutions.length);
		34	assertTrue("x1 = 0", PrecisionUtils.equal(solutions[0], 0));
		35
		36	solutions = PolynomCalculationUtils.getCubicRoots(1, 0, -1, 0);
		37	Arrays.sort(solutions);
33	assertEquals("three real solutions", 3, solutions.length);	38	assertEquals("three real solutions", 3, solutions.length);
34	assertTrue("x1 = -1", PrecisionUtils.equal(solutions[0], -1));	39	assertTrue("x1 = -1", PrecisionUtils.equal(solutions[0], -1));
35	assertTrue("x2 = 0", PrecisionUtils.equal(solutions[1], 0));	40	assertTrue("x2 = 0", PrecisionUtils.equal(solutions[1], 0));
36	assertTrue("x3 = 1", PrecisionUtils.equal(solutions[2], 1));	41	assertTrue("x3 = 1", PrecisionUtils.equal(solutions[2], 1));
37		42
38	solutions = PolynomCalculationUtils.getCubicRoots(1, 0, -1, 0);
39	Arrays.sort(solutions);
40	assertEquals("one real solution", 1, solutions.length);
41	assertTrue("x1 = 0", PrecisionUtils.equal(solutions[0], 0));
42
43	solutions = PolynomCalculationUtils.getCubicRoots(1, 1, 1, 0);	43	solutions = PolynomCalculationUtils.getCubicRoots(1, 1, 1, 0);
44	Arrays.sort(solutions);	44	Arrays.sort(solutions);
45	assertEquals("one real solution", 1, solutions.length);	45	assertEquals("one real solution", 1, solutions.length);
Lines 66-71 Link Here
66	PrecisionUtils.equal(-0.15524041215, solutions[1]));	66	PrecisionUtils.equal(-0.15524041215, solutions[1]));
67	assertTrue("x3 = 1.48705072",	67	assertTrue("x3 = 1.48705072",
68	PrecisionUtils.equal(1.487050722353, solutions[2]));	68	PrecisionUtils.equal(1.487050722353, solutions[2]));
		69
		70	// q = 0
		71	solutions = PolynomCalculationUtils.getCubicRoots(-10, 30, 0, -20);
		72	Arrays.sort(solutions);
		73	assertEquals(3, solutions.length);
		74	assertTrue(PrecisionUtils.equal(-0.7320508075688774, solutions[0]));
		75	assertTrue(PrecisionUtils.equal(1, solutions[1]));
		76	assertTrue(PrecisionUtils.equal(2.7320508075688776, solutions[2]));
69	}	77	}
70		78
71	@Test	79	@Test
Lines 170-173 Link Here
170	true);	178	true);
171	}	179	}
172	}	180	}
		181
		182	// @Test
		183	// public void test_getRoots_arbitrary() {
		184	// // double[] solutions = PolynomCalculationUtils.getRoots(1, 0, 1, 0);
		185	// // Arrays.sort(solutions);
		186	// // assertEquals("one real solution", 1, solutions.length);
		187	// // assertTrue("x1 = 0", PrecisionUtils.equal(solutions[0], 0));
		188	//
		189	// solutions = PolynomCalculationUtils.getCubicRoots(1, 0, -1, 0);
		190	// Arrays.sort(solutions);
		191	// assertEquals("three real solutions", 3, solutions.length);
		192	// assertTrue("x1 = -1", PrecisionUtils.equal(solutions[0], -1));
		193	// assertTrue("x2 = 0", PrecisionUtils.equal(solutions[1], 0));
		194	// assertTrue("x3 = 1", PrecisionUtils.equal(solutions[2], 1));
		195	//
		196	// solutions = PolynomCalculationUtils.getCubicRoots(1, 1, 1, 0);
		197	// Arrays.sort(solutions);
		198	// assertEquals("one real solution", 1, solutions.length);
		199	// assertTrue("x^3 + x^2 + x = 0 <=> x(x^2 + x + 1) = 0 => x = 0",
		200	// PrecisionUtils.equal(0, solutions[0]));
		201	//
		202	// solutions = PolynomCalculationUtils.getCubicRoots(1, -6, 12, -8);
		203	// assertEquals("one real solution", 1, solutions.length);
		204	// assertTrue("x = 2 solves the polynom",
		205	// PrecisionUtils.equal(2, solutions[0]));
		206	//
		207	// solutions = PolynomCalculationUtils.getCubicRoots(1, 1, -33, 63);
		208	// Arrays.sort(solutions);
		209	// assertEquals("two real solutions", 2, solutions.length);
		210	// assertTrue("x1 = -7", PrecisionUtils.equal(-7, solutions[0]));
		211	// assertTrue("x2 = 3", PrecisionUtils.equal(3, solutions[1]));
		212	//
		213	// solutions = PolynomCalculationUtils.getCubicRoots(1, 3, -6, -1);
		214	// Arrays.sort(solutions);
		215	// assertEquals("three real solutions", 3, solutions.length);
		216	// assertTrue("x1 = -4.33181031",
		217	// PrecisionUtils.equal(-4.331810310203, solutions[0]));
		218	// assertTrue("x2 = -0.15524041",
		219	// PrecisionUtils.equal(-0.15524041215, solutions[1]));
		220	// assertTrue("x3 = 1.48705072",
		221	// PrecisionUtils.equal(1.487050722353, solutions[2]));
		222	//
		223	// // q = 0
		224	// solutions = PolynomCalculationUtils.getCubicRoots(-10, 30, 0, -20);
		225	// Arrays.sort(solutions);
		226	// assertEquals(3, solutions.length);
		227	// assertTrue(PrecisionUtils.equal(-0.7320508075688774, solutions[0]));
		228	// assertTrue(PrecisionUtils.equal(1, solutions[1]));
		229	// assertTrue(PrecisionUtils.equal(2.7320508075688776, solutions[2]));
		230	// }
173	}	231	}

Lines 14-24 Link Here

(-)src/org/eclipse/gef4/geometry/tests/QuadraticCurveTests.java (+24 lines)
14	import static org.junit.Assert.assertEquals;	14	import static org.junit.Assert.assertEquals;
15	import static org.junit.Assert.assertTrue;	15	import static org.junit.Assert.assertTrue;
16		16
		17	import java.util.Random;
		18
17	import org.eclipse.gef4.geometry.Point;	19	import org.eclipse.gef4.geometry.Point;
		20	import org.eclipse.gef4.geometry.shapes.CubicCurve;
18	import org.eclipse.gef4.geometry.shapes.QuadraticCurve;	21	import org.eclipse.gef4.geometry.shapes.QuadraticCurve;
19	import org.junit.Test;	22	import org.junit.Test;
20		23
21	public class QuadraticCurveTests {	24	public class QuadraticCurveTests {
		25	private static final int SEED = 123;
22	private final Point p = new Point(-10, -10), c = new Point(10, 0),	26	private final Point p = new Point(-10, -10), c = new Point(10, 0),
23	q = new Point(0, 10);	27	q = new Point(0, 10);
24		28
Lines 198-201 Link Here
198	public void test_intersects_Rectangle() {	202	public void test_intersects_Rectangle() {
199	// TODO!	203	// TODO!
200	}	204	}
		205
		206	@Test
		207	public void test_getElevated() {
		208	Random rng = new Random(SEED);
		209
		210	for (int i = 0; i < 100; i++) {
		211	Point[] points = new Point[3];
		212	for (int j = 0; j < 3; j++) {
		213	points[j] = new Point(rng.nextDouble(), rng.nextDouble());
		214	}
		215	QuadraticCurve qc = new QuadraticCurve(points);
		216	CubicCurve cc = qc.getElevated();
		217
		218	for (double t = 0; t <= 1; t += 0.0123456789) {
		219	assertTrue(cc.contains(qc.get(t)));
		220	assertTrue(qc.contains(cc.get(t)));
		221	}
		222	}
		223	}
		224
201	}	225	}




		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) {

	}

	@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();


		});
	}

	@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());
	}

}




 *******************************************************************************/
package org.eclipse.gef4.geometry.tests;

import java.lang.reflect.Method;

import org.eclipse.gef4.geometry.utils.PrecisionUtils;

/**

public class TestUtils {

	public static double getPrecisionFraction() {
		// TODO: remove TestUtils
		return PrecisionUtils.calculateFraction(0);
			f = PrecisionUtils.class.getDeclaredMethod("calculateFraction",
					int.class);
			f.setAccessible(true);
			return ((Double) f.invoke(PrecisionUtils.class, 0)).doubleValue();
		} catch (Exception e) {
			throw new IllegalArgumentException(e);
		}
	}

	private TestUtils() {

Return to bug 355997

Lines 79-112 Link Here

(-)src/org/eclipse/gef4/geometry/utils/PolynomCalculationUtils.java (-25 / +20 lines)
79	*/	79	*/
80	public static final double[] getCubicRoots(double A, double B, double C,	80	public static final double[] getCubicRoots(double A, double B, double C,
81	double D) {	81	double D) {
		82	// TODO: use an algorithm that abstracts the polynom's order. A
		83	// possibility would be to use the CurveUtils$BezierCurve#contains(Point
		84	// p) method.
		85
82	if (A == 0) {	86	if (A == 0) {
83	return getQuadraticRoots(B, C, D);	87	return getQuadraticRoots(B, C, D);
84	}	88	}
85		89
86	double a = B / A;	90	double b = B / A;
87	double b = C / A;	91	double c = C / A;
88	double c = D / A;	92	double d = D / A;
89		93
90	// reduce to z^3 + pz + q = 0 by substituting x = z - a/3	94	// reduce to t^3 + pt + q = 0 by substituting x = t - b/3
91	// (http://en.wikipedia.org/wiki/Cubic_function#Cardano.27s_method)	95	// (http://en.wikipedia.org/wiki/Cubic_function#Cardano.27s_method)
		96	double p = c - b * b / 3;
		97	double q = 2 * b * b * b / 27 - b * c / 3 + d;
92		98
93	double p = b - a * a / 3;	99	// short-cut for p = 0
94	double q = 2 * a * a * a / 27 - a * b / 3 + c;
95
96	// short-cuts for p = 0, q = 0:
97	if (PrecisionUtils.equal(p, 0, +4)) {	100	if (PrecisionUtils.equal(p, 0, +4)) {
98	// z^3 = -q => z = cbrt(-q) => x = cbrt(-q) - a / 3	101	// t^3 + q = 0 => t^3 = -q => t = cbrt(-q) => t - b/3 = cbrt(-q) -
99	return new double[] { Math.cbrt(-q) - a / 3 };	102	// b/3 => x = cbrt(-q) - b/3
100	}	103	return new double[] { Math.cbrt(-q) - b / 3 };
101	if (PrecisionUtils.equal(q, 0, +4)) {
102	// z^3 - pz = 0 <=> z(z^2 - p) = 0 => z = 0 v z^2 = p => z =
103	// +-sqrt(p), p >= 0 (p is not zero, because otherwise we would not
104	// be here)
105	if (p > 0) {
106	return new double[] { 0, Math.sqrt(p), -Math.sqrt(p) };
107	} else {
108	return new double[] { 0 };
109	}
110	}	104	}
111		105
112	double p_3 = p / 3;	106	double p_3 = p / 3;
Lines 116-128 Link Here
116		110
117	if (PrecisionUtils.equal(D, 0, +4)) {	111	if (PrecisionUtils.equal(D, 0, +4)) {
118	// two real solutions	112	// two real solutions
119	return new double[] { 3 * q / p - a / 3, -3 * q / (2 * p) - a / 3 };	113	return new double[] { 3 * q / p - b / 3, -3 * q / (2 * p) - b / 3 };
120	} else if (D > 0) {	114	} else if (D > 0) {
121	// one real solution	115	// one real solution
122	double u = Math.cbrt(-q_2 + Math.sqrt(D));	116	double u = Math.cbrt(-q_2 + Math.sqrt(D));
123	double v = Math.cbrt(-q_2 - Math.sqrt(D));	117	double v = Math.cbrt(-q_2 - Math.sqrt(D));
124		118
125	return new double[] { u + v - a / 3 };	119	return new double[] { u + v - b / 3 };
126	} else {	120	} else {
127	// three real solutions	121	// three real solutions
128	double r = Math.sqrt(-p_3 * p_3 * p_3);	122	double r = Math.sqrt(-p_3 * p_3 * p_3);
Lines 130-138 Link Here
130	double co = 2 * Math.cbrt(r);	124	double co = 2 * Math.cbrt(r);
131		125
132	// co * cos((phi + k * pi)/3) - a/3, k = 2n, n in N	126	// co * cos((phi + k * pi)/3) - a/3, k = 2n, n in N
133	return new double[] { co * Math.cos(phi / 3) - a / 3,	127	return new double[] { co * Math.cos(phi / 3) - b / 3,
134	co * Math.cos((phi + 2 * Math.PI) / 3) - a / 3,	128	co * Math.cos((phi + 2 * Math.PI) / 3) - b / 3,
135	co * Math.cos((phi + 4 * Math.PI) / 3) - a / 3 };	129	co * Math.cos((phi + 4 * Math.PI) / 3) - b / 3 };
136	}	130	}
137	}	131	}
		132
138	}	133	}

Lines 17-28 Link Here

(-)src/org/eclipse/gef4/geometry/tests/AllTests.java (-6 / +6 lines)
17	import org.junit.runners.Suite.SuiteClasses;	17	import org.junit.runners.Suite.SuiteClasses;
18		18
19	@RunWith(Suite.class)	19	@RunWith(Suite.class)
20	@SuiteClasses({ AngleTests.class, CubicCurveTests.class, DimensionTests.class,	20	@SuiteClasses({ AngleTests.class, CubicCurveTests.class, CurveUtilsTests.class,
21	EllipseTests.class, LineTests.class, PointListUtilsTests.class,	21	DimensionTests.class, EllipseTests.class, LineTests.class,
22	PointTests.class, PolygonTests.class, PolylineTests.class,	22	PointListUtilsTests.class, PointTests.class, PolygonTests.class,
23	PolynomCalculationUtilsTests.class, PrecisionUtilsTests.class,	23	PolylineTests.class, PolynomCalculationUtilsTests.class,
24	QuadraticCurveTests.class, RectangleTests.class, StraightTests.class,	24	PrecisionUtilsTests.class, QuadraticCurveTests.class,
25	VectorTests.class })	25	RectangleTests.class, StraightTests.class, VectorTests.class })
26	public class AllTests {	26	public class AllTests {
27		27
28	}	28	}

Lines 72-82 Link Here

(-)src/org/eclipse/gef4/geometry/tests/CubicCurveTests.java (-1 / +90 lines)
72	}	72	}
73		73
74	@Test	74	@Test
75	public void test_get_Bounds() {	75	public void test_getBounds() {
76	CubicCurve curve = new CubicCurve(p, c1, c2, q);	76	CubicCurve curve = new CubicCurve(p, c1, c2, q);
77		77
78	// p is the top-left point: (y-coordinates are inverted)	78	// p is the top-left point: (y-coordinates are inverted)
79	assertEquals(curve.getBounds().getTopLeft(), p);	79	assertEquals(curve.getBounds().getTopLeft(), p);
80	}	80	}
81		81
		82	@Test
		83	public void test_getIntersections_with_CubicCurve() {
		84	CubicCurve cc1 = new CubicCurve(new Point(-10, -10), new Point(),
		85	new Point(), new Point(5, 5));
		86	CubicCurve cc2 = new CubicCurve(new Point(5, -5), new Point(),
		87	new Point(), new Point(-10, 10));
		88	assertEquals(1, cc1.getIntersections(cc2).length);
		89	assertEquals(1, cc2.getIntersections(cc1).length);
		90
		91	// same end point
		92	cc1 = new CubicCurve(103.0, 401.0, 400.0, 200.0, 300.0, 300.0, 390.0,
		93	208.0);
		94	cc2 = new CubicCurve(584.0, 12.0, 200.0, 200.0, 300.0, 100.0, 390.0,
		95	208.0);
		96	assertEquals(1, cc1.getIntersections(cc2).length);
		97	assertEquals(1, cc2.getIntersections(cc1).length);
		98
		99	cc1 = new CubicCurve(198.0, 103.0, 410.0, 215.0, 305.0, 320.0, 542.0,
		100	246.0);
		101	cc2 = new CubicCurve(101.0, 107.0, 197.0, 218.0, 302.0, 106.0, 542.0,
		102	246.0);
		103	assertEquals(2, cc1.getIntersections(cc2).length);
		104	assertEquals(2, cc2.getIntersections(cc1).length);
		105
		106	cc1 = new CubicCurve(200.0, 100.0, 400.0, 200.0, 300.0, 300.0, 432.0,
		107	62.0);
		108	cc2 = new CubicCurve(100.0, 100.0, 200.0, 200.0, 300.0, 100.0, 432.0,
		109	62.0);
		110	assertEquals(2, cc1.getIntersections(cc2).length);
		111	assertEquals(2, cc2.getIntersections(cc1).length);
		112
		113	cc1 = new CubicCurve(200.0, 100.0, 400.0, 200.0, 300.0, 300.0, 208.0,
		114	35.0);
		115	cc2 = new CubicCurve(100.0, 100.0, 200.0, 200.0, 300.0, 100.0, 208.0,
		116	35.0);
		117	assertEquals(3, cc1.getIntersections(cc2).length);
		118	assertEquals(3, cc2.getIntersections(cc1).length);
		119
		120	cc1 = new CubicCurve(201.89274447949526, 106.43015521064301,
		121	403.7854889589905, 212.86031042128602, 302.8391167192429,
		122	319.290465631929, 81.0, 22.0);
		123	cc2 = new CubicCurve(100.94637223974763, 106.43015521064301,
		124	201.89274447949526, 212.86031042128602, 302.8391167192429,
		125	106.43015521064301, 81.0, 22.0);
		126	assertEquals(3, cc1.getIntersections(cc2).length);
		127	assertEquals(3, cc2.getIntersections(cc1).length);
		128
		129	// torture tests from http://www.truetex.com/bezint.htm
		130	cc1 = new CubicCurve(1.0, 1.5, 15.5, 0.5, -8.0, 3.5, 5.0, 1.5);
		131	cc2 = new CubicCurve(4.0, 0.5, 5.0, 15.0, 2.0, -8.5, 4.0, 4.5);
		132	assertEquals(9, cc1.getIntersections(cc2).length);
		133	assertEquals(9, cc2.getIntersections(cc1).length);
		134
		135	cc1 = new CubicCurve(664.00168, 0, 726.11545, 124.22757, 736.89069,
		136	267.89743, 694.0017, 400.0002);
		137	cc2 = new CubicCurve(850.66843, 115.55563, 728.515, 115.55563,
		138	725.21347, 275.15309, 694.0017, 400.0002);
		139	assertEquals(2, cc1.getIntersections(cc2).length);
		140	assertEquals(2, cc2.getIntersections(cc1).length);
		141
		142	cc1 = new CubicCurve(1, 1, 12.5, 6.5, -4, 6.5, 7.5, 1);
		143	cc2 = new CubicCurve(1, 6.5, 12.5, 1, -4, 1, 7.5, 6);
		144	assertEquals(6, cc1.getIntersections(cc2).length);
		145	assertEquals(6, cc2.getIntersections(cc1).length);
146
147	// not sure about these: (getIntersections() returns 3)
148	// cc1 = new CubicCurve(315.748, 312.84, 312.644, 318.134, 305.836,
149	// 319.909, 300.542, 316.804);
150	// cc2 = new CubicCurve(317.122, 309.05, 316.112, 315.102, 310.385,
151	// 319.19, 304.332, 318.179);
152
153	// not sure about these: (getIntrsections() returns 0)
154	// cc1 = new CubicCurve(125.79356, 199.57382, 51.16556, 128.93575,
155	// 87.494,
156	// 16.67848, 167.29361, 16.67848);
157	// cc2 = new CubicCurve(167.29361, 55.81876, 100.36128, 55.81876,
158	// 68.64099, 145.4755, 125.7942, 199.57309);
159	}
160
161	@Test
162	public void test_getIntersections_with_CubicCurve_endPointsCheck() {
163	CubicCurve cc1 = new CubicCurve(new Point(0, 0), new Point(0.1, 0),
164	new Point(0.1, 0), new Point(0.1, 0.1));
165	CubicCurve cc2 = new CubicCurve(new Point(0, 0), new Point(0.05, 0.1),
166	new Point(0.05, 0.1), new Point(0.1, -0.1));
167	assertEquals(2, cc1.getIntersections(cc2).length);
168	assertEquals(2, cc2.getIntersections(cc1).length);
169	}
170
82	}	171	}

Added Link Here

(-)src/org/eclipse/gef4/geometry/tests/CurveUtilsTests.java (+297 lines)
1	/*******************************************************************************
2	* Copyright (c) 2011 itemis AG and others.
3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at
6	* http://www.eclipse.org/legal/epl-v10.html
7	*
8	* Contributors:
9	* Matthias Wienand (itemis AG) - initial API and implementation
10	*
11	*******************************************************************************/
12	package org.eclipse.gef4.geometry.tests;
13
14	import static org.junit.Assert.assertEquals;
15	import static org.junit.Assert.assertTrue;
16
17	import java.util.Random;
18
19	import org.eclipse.gef4.geometry.Point;
20	import org.eclipse.gef4.geometry.shapes.CubicCurve;
21	import org.eclipse.gef4.geometry.shapes.QuadraticCurve;
22	import org.eclipse.gef4.geometry.shapes.Rectangle;
23	import org.eclipse.gef4.geometry.utils.CurveUtils;
24	import org.eclipse.gef4.geometry.utils.PrecisionUtils;
25	import org.junit.Test;
26
27	public class CurveUtilsTests {
28
29	private static final long SEED = 123;
30
31	@Test
32	public void test_getSignedDistance_direction() {
33	// sign-checks:
34	// first quadrant (y-axis is inverted)
35	assertTrue(CurveUtils.getSignedDistance(new Point(),
36	new Point(10, -10), new Point(0, -10)) > 0);
37	assertTrue(CurveUtils.getSignedDistance(new Point(10, -10),
38	new Point(), new Point(0, -10)) < 0);
39	assertTrue(CurveUtils.getSignedDistance(new Point(),
40	new Point(10, -10), new Point(1, -1)) == 0);
41
42	// second quadrant (y-axis is inverted)
43	assertTrue(CurveUtils.getSignedDistance(new Point(),
44	new Point(-10, -10), new Point(0, -10)) < 0);
45	assertTrue(CurveUtils.getSignedDistance(new Point(-10, -10),
46	new Point(), new Point(0, -10)) > 0);
47	assertTrue(CurveUtils.getSignedDistance(new Point(),
48	new Point(-10, -10), new Point(-1, -1)) == 0);
49
50	// third quadrant (y-axis is inverted)
51	assertTrue(CurveUtils.getSignedDistance(new Point(), new Point(10, 10),
52	new Point(0, 10)) < 0);
53	assertTrue(CurveUtils.getSignedDistance(new Point(10, 10), new Point(),
54	new Point(0, 10)) > 0);
55	assertTrue(CurveUtils.getSignedDistance(new Point(), new Point(10, 10),
56	new Point(1, 1)) == 0);
57
58	// forth quadrant (y-axis is inverted)
59	assertTrue(CurveUtils.getSignedDistance(new Point(),
60	new Point(-10, 10), new Point(0, 10)) > 0);
61	assertTrue(CurveUtils.getSignedDistance(new Point(-10, 10),
62	new Point(), new Point(0, 10)) < 0);
63	assertTrue(CurveUtils.getSignedDistance(new Point(),
64	new Point(-10, 10), new Point(-1, 1)) == 0);
65	}
66
67	@Test
68	public void test_getSignedDistance_abs() {
69	// do only check for the absolute value of the signed distance
70
71	assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance(
72	new Point(0, -5), new Point(0, 5), new Point(5, 0))), 5));
73	assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance(
74	new Point(0, 5), new Point(0, -5), new Point(5, 0))), 5));
75
76	assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance(
77	new Point(0, -1), new Point(0, 1), new Point(5, 0))), 5));
78	assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance(
79	new Point(0, 1), new Point(0, -1), new Point(5, 0))), 5));
80
81	assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance(
82	new Point(-5, 0), new Point(5, 0), new Point(0, 5))), 5));
83	assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance(
84	new Point(-5, 0), new Point(5, 0), new Point(0, 5))), 5));
85
86	assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance(
87	new Point(-1, 0), new Point(1, 0), new Point(0, 5))), 5));
88	assertTrue(PrecisionUtils.equal(Math.abs(CurveUtils.getSignedDistance(
89	new Point(-1, 0), new Point(1, 0), new Point(0, 5))), 5));
90	}
91
92	@Test
93	public void test_getSignedDistance() {
94	// check both, direction and value:
95	// first quadrant (y-axis is inverted)
96	double len = 10d / Math.sqrt(2);
97	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(
98	new Point(), new Point(10, -10), new Point(0, -10)), len));
99	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(new Point(
100	10, -10), new Point(), new Point(0, -10)), -len));
101	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(
102	new Point(), new Point(10, -10), new Point(1, -1)), 0));
103
104	// second quadrant (y-axis is inverted)
105	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(
106	new Point(), new Point(-10, -10), new Point(0, -10)), -len));
107	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(new Point(
108	-10, -10), new Point(), new Point(0, -10)), len));
109	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(
110	new Point(), new Point(-10, -10), new Point(-1, -1)), 0));
111
112	// third quadrant (y-axis is inverted)
113	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(
114	new Point(), new Point(10, 10), new Point(0, 10)), -len));
115	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(new Point(
116	10, 10), new Point(), new Point(0, 10)), len));
117	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(
118	new Point(), new Point(10, 10), new Point(1, 1)), 0));
119
120	// forth quadrant (y-axis is inverted)
121	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(
122	new Point(), new Point(-10, 10), new Point(0, 10)), len));
123	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(new Point(
124	-10, 10), new Point(), new Point(0, 10)), -len));
125	assertTrue(PrecisionUtils.equal(CurveUtils.getSignedDistance(
126	new Point(), new Point(-10, 10), new Point(-1, 1)), 0));
127	}
128
129	@Test
130	public void test_split_with_QuadraticCurve() {
131	final int numPoints = 4;
132	final double step = 0.123456789;
133
134	Random rng = new Random(SEED);
135
136	for (int i = 0; i < 1000; i++) {
137	Point[] points = new Point[numPoints];
138	for (int j = 0; j < numPoints; j++) {
139	points[j] = new Point(rng.nextDouble(), rng.nextDouble());
140	}
141
142	QuadraticCurve c = new QuadraticCurve(points);
143	for (double t = 0; t <= 1; t += step) {
144	QuadraticCurve[] cs = c.split(t);
145	assertEquals(c.get(t), cs[0].get(1));
146	assertEquals(c.get(t), cs[1].get(0));
147	assertEquals(c.get(0), cs[0].get(0));
148	assertEquals(c.get(1), cs[1].get(1));
149	}
150	}
151	}
152
153	@Test
154	public void test_clip_with_QuadraticCurve() {
155	final int numPoints = 4;
156	final double step = 0.123456789;
157
158	Random rng = new Random(SEED);
159
160	for (int i = 0; i < 1000; i++) {
161	Point[] points = new Point[numPoints];
162	for (int j = 0; j < numPoints; j++) {
163	points[j] = new Point(rng.nextDouble(), rng.nextDouble());
164	}
165
166	QuadraticCurve c = new QuadraticCurve(points);
167	for (double t1 = 0; t1 <= 1; t1 += step) {
168	for (double t2 = 0; t2 <= 1; t2 += step) {
169	QuadraticCurve cc = c.clip(t1, t2);
170	assertEquals(c.get(t1), cc.get(0));
171	assertEquals(c.get(t2), cc.get(1));
172	}
173	}
174	}
175	}
176
177	@Test
178	public void test_split_with_CubicCurve() {
179	final int numPoints = 6;
180	final double step = 0.123456789;
181
182	Random rng = new Random(SEED);
183
184	for (int i = 0; i < 1000; i++) {
185	Point[] points = new Point[numPoints];
186	for (int j = 0; j < numPoints; j++) {
187	points[j] = new Point(rng.nextDouble(), rng.nextDouble());
188	}
189
190	CubicCurve c = new CubicCurve(points);
191	for (double t = 0; t <= 1; t += step) {
192	CubicCurve[] cs = c.split(t);
193	assertEquals(c.get(t), cs[0].get(1));
194	assertEquals(c.get(t), cs[1].get(0));
195	assertEquals(c.get(0), cs[0].get(0));
196	assertEquals(c.get(1), cs[1].get(1));
197	}
198	}
199	}
200
201	@Test
202	public void test_clip_with_CubicCurve() {
203	final int numPoints = 6;
204	final double step = 0.123456789;
205
206	Random rng = new Random(SEED);
207
208	for (int i = 0; i < 1000; i++) {
209	Point[] points = new Point[numPoints];
210	for (int j = 0; j < numPoints; j++) {
211	points[j] = new Point(rng.nextDouble(), rng.nextDouble());
212	}
213
214	CubicCurve c = new CubicCurve(points);
215	for (double t1 = 0; t1 <= 1; t1 += step) {
216	for (double t2 = 0; t2 <= 1; t2 += step) {
217	CubicCurve cc = c.clip(t1, t2);
218	assertEquals(c.get(t1), cc.get(0));
219	assertEquals(c.get(t2), cc.get(1));
220	}
221	}
222	}
223	}
224
225	@Test
226	public void test_contains_with_QuadraticCurve() {
227	final int numPoints = 4;
228	final double step = 0.123456789;
229
230	Random rng = new Random(SEED);
231
232	for (int i = 0; i < 1000; i++) {
233	Point[] points = new Point[numPoints];
234	for (int j = 0; j < numPoints; j++) {
235	points[j] = new Point(rng.nextDouble(), rng.nextDouble());
236	}
237
238	QuadraticCurve c = new QuadraticCurve(points);
239	for (double t = 0; t <= 1; t += step) {
240	assertTrue(c.contains(c.get(t)));
241	}
242	}
243	}
244
245	@Test
246	public void test_contains_with_CubicCurve() {
247	final int numPoints = 6;
248	final double step = 0.123456789;
249
250	Random rng = new Random(SEED);
251
252	for (int i = 0; i < 1000; i++) {
253	Point[] points = new Point[numPoints];
254	for (int j = 0; j < numPoints; j++) {
255	points[j] = new Point(rng.nextDouble(), rng.nextDouble());
256	}
257
258	CubicCurve c = new CubicCurve(points);
259	for (double t = 0; t <= 1; t += step) {
260	assertTrue(c.contains(c.get(t)));
261	}
262	}
263	}
264
265	@Test
266	public void test_getControlBounds() {
267	final int numPoints = 6;
268	final double step = 0.123456789;
269
270	Random rng = new Random(SEED);
271
272	for (int i = 0; i < 1000; i++) {
273	Point[] points = new Point[numPoints];
274	for (int j = 0; j < numPoints; j++) {
275	points[j] = new Point(rng.nextDouble(), rng.nextDouble());
276	}
277
278	CubicCurve c = new CubicCurve(points);
279	Rectangle bounds = CurveUtils.getControlBounds(c);
280	for (double t = 0; t <= 1; t += step) {
281	assertTrue(bounds.contains(c.get(t)));
282	}
283	assertTrue(bounds.contains(c.get(1)));
284	}
285	}
286
287	@Test
288	public void test_getIntersections_BezierClipping_simple() {
289	CubicCurve c1 = new CubicCurve(new double[] { 100, 200, 200, 100, 300,
290	300, 400, 200 });
291	CubicCurve c2 = new CubicCurve(new double[] { 250, 100, 350, 200, 150,
292	300, 250, 400 });
293
294	assertEquals(1, c1.getIntersections(c2).length);
295	}
296
297	}

Lines 19-25 Link Here

(-)src/org/eclipse/gef4/geometry/tests/EllipseTests.java (-9 / +32 lines)
19	import org.eclipse.gef4.geometry.shapes.Ellipse;	19	import org.eclipse.gef4.geometry.shapes.Ellipse;
20	import org.eclipse.gef4.geometry.shapes.Line;	20	import org.eclipse.gef4.geometry.shapes.Line;
21	import org.eclipse.gef4.geometry.shapes.Rectangle;	21	import org.eclipse.gef4.geometry.shapes.Rectangle;
22	import org.junit.Ignore;
23	import org.junit.Test;	22	import org.junit.Test;
24		23
25	/**	24	/**
Lines 74-80 Link Here
74	}	73	}
75	}	74	}
76		75
77	@Ignore	76	@Test
		77	public void test_intersects_with_Line() {
		78	Rectangle r = new Rectangle(34.3435, 56.458945, 123.3098, 146.578);
		79	Ellipse e = new Ellipse(r);
		80	for (Line l : r.getSegments()) {
		81	assertTrue(e.intersects(l)); // line touches ellipse (tangent)
		82	}
		83	}
		84
		85	@Test
78	public void test_get_intersections_with_Ellipse() {	86	public void test_get_intersections_with_Ellipse() {
79	Rectangle r = new Rectangle(34.3435, 56.458945, 123.3098, 146.578);	87	Rectangle r = new Rectangle(34.3435, 56.458945, 123.3098, 146.578);
80	Ellipse e1 = new Ellipse(r);	88	Ellipse e1 = new Ellipse(r);
Lines 85-93 Link Here
85	Point[] intersections = e1.getIntersections(e2);	93	Point[] intersections = e1.getIntersections(e2);
86	assertEquals(0, intersections.length);	94	assertEquals(0, intersections.length);
87		95
		96	// touching left
		97	Rectangle r2 = r.getExpanded(0, -10, -10, -10);
		98	e2 = new Ellipse(r2);
		99	intersections = e1.getIntersections(e2);
		100	assertEquals(1, intersections.length);
		101
88	// if we create an x-scaled ellipse at the same position as before, they	102	// if we create an x-scaled ellipse at the same position as before, they
89	// should have 3 poi (the touching point and two crossing intersections)	103	// should have 3 poi (the touching point and two crossing intersections)
90	Rectangle r2 = r.getExpanded(0, 0, 100, 0);	104	r2 = r.getExpanded(0, 0, 100, 0);
91	e2 = new Ellipse(r2);	105	e2 = new Ellipse(r2);
92	intersections = e1.getIntersections(e2);	106	intersections = e1.getIntersections(e2);
93	assertEquals(3, intersections.length);	107	assertEquals(3, intersections.length);
Lines 160-170 Link Here
160	}	174	}
161		175
162	@Test	176	@Test
163	public void test_intersects_with_Line() {	177	public void test_getIntersections_with_Ellipse_Bezier_special() {
164	Rectangle r = new Rectangle(34.3435, 56.458945, 123.3098, 146.578);	178	// 3 nearly tangential intersections
165	Ellipse e = new Ellipse(r);	179	Ellipse e1 = new Ellipse(126, 90, 378, 270);
166	for (Line l : r.getSegments()) {	180	Ellipse e2 = new Ellipse(222, 77, 200, 200);
167	assertTrue(e.intersects(l)); // line touches ellipse (tangent)	181	assertEquals(2, e1.getIntersections(e2).length);
168	}	182
		183	e2 = new Ellipse(133, 90, 2 * (315 - 133), 200);
		184	assertEquals(3, e1.getIntersections(e2).length);
		185
		186	e2 = new Ellipse(143, 90, 2 * (315 - 143), 200);
		187	assertEquals(3, e1.getIntersections(e2).length);
		188
		189	e2 = new Ellipse(145, 90, 2 * (315 - 145), 200);
		190	assertEquals(3, e1.getIntersections(e2).length);
169	}	191	}
		192
170	}	193	}

Lines 360-365 Link Here

(-)src/org/eclipse/gef4/geometry/tests/RectangleTests.java (-13 / +18 lines)
360	assertEquals(new Rectangle(0, 3, 3, 4), r1.getTranslated(-1, 1));	360	assertEquals(new Rectangle(0, 3, 3, 4), r1.getTranslated(-1, 1));
361	}	361	}
362		362
		363	@Test
363	public void test_getTransposed() {	364	public void test_getTransposed() {
364	forRectangles(new IAction() {	365	forRectangles(new IAction() {
365	public void action(Rectangle rect, Point tl, Point br) {	366	public void action(Rectangle rect, Point tl, Point br) {
Lines 553-571 Link Here
553	}	554	}
554		555
555	@Test	556	@Test
556	public void test_setSize() {
557	Rectangle r = new Rectangle();
558
559	r.setSize(new Dimension(10, 20));
560	assertEquals(new Point(), r.getTopLeft());
561	assertEquals(new Point(10, 20), r.getBottomRight());
562
563	r.setSize(5, -10);
564	assertEquals(new Point(), r.getTopLeft());
565	assertEquals(new Point(5, 0), r.getBottomRight());
566	}
567
568	@Test
569	public void test_setters() {	557	public void test_setters() {
570	Rectangle r = new Rectangle();	558	Rectangle r = new Rectangle();
571		559
Lines 691-694 Link Here
691	});	679	});
692	}	680	}
693		681
		682	@Test
		683	public void test_setSize() {
		684	Rectangle r = new Rectangle();
		685
		686	r.setSize(new Dimension(10, 20));
		687	assertEquals(new Point(), r.getTopLeft());
		688	assertEquals(new Point(10, 20), r.getBottomRight());
		689
		690	r.setSize(5, -10);
		691	assertEquals(new Point(), r.getTopLeft());
		692	assertEquals(new Point(5, 0), r.getBottomRight());
		693
		694	r.setSize(-5, 10);
		695	assertEquals(new Point(), r.getTopLeft());
		696	assertEquals(new Point(0, 10), r.getBottomRight());
		697	}
		698
694	}	699	}

Lines 12-19 Link Here

(-)src/org/eclipse/gef4/geometry/tests/TestUtils.java (-11 / +2 lines)
12	*******************************************************************************/	12	*******************************************************************************/
13	package org.eclipse.gef4.geometry.tests;	13	package org.eclipse.gef4.geometry.tests;
14		14
15	import java.lang.reflect.Method;
16
17	import org.eclipse.gef4.geometry.utils.PrecisionUtils;	15	import org.eclipse.gef4.geometry.utils.PrecisionUtils;
18		16
19	/**	17	/**
Lines 25-39 Link Here
25	public class TestUtils {	23	public class TestUtils {
26		24
27	public static double getPrecisionFraction() {	25	public static double getPrecisionFraction() {
28	Method f;	26	// TODO: remove TestUtils
29	try {	27	return PrecisionUtils.calculateFraction(0);
30	f = PrecisionUtils.class.getDeclaredMethod("calculateFraction",
31	int.class);
32	f.setAccessible(true);
33	return ((Double) f.invoke(PrecisionUtils.class, 0)).doubleValue();
34	} catch (Exception e) {
35	throw new IllegalArgumentException(e);
36	}
37	}	28	}
38		29
39	private TestUtils() {	30	private TestUtils() {