Attachment 202501 Details for Bug 355997 – Implementation of the getIntersections(...) methods in the Ellipse class

[patch] Implementation of the getIntersections(...) methods in the Ellipse class

org.eclipse.gef4.geometry.shapes.Ellipse.patch.txt (text/plain), 5.08 KB, created by Matthias Wienand

on 2011-08-31 07:35:24 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Matthias Wienand

Created: 2011-08-31 07:35:24 EDT

Size: 5.08 KB

patch

obsolete

>### Eclipse Workspace Patch 1.0
>#P org.eclipse.gef4.geometry
>Index: src/org/eclipse/gef4/geometry/shapes/Ellipse.java
>===================================================================
>RCS file: /cvsroot/tools/org.eclipse.gef/GEF4/plugins/org.eclipse.gef4.geometry/src/org/eclipse/gef4/geometry/shapes/Ellipse.java,v
>retrieving revision 1.1
>diff -u -r1.1 Ellipse.java
>--- src/org/eclipse/gef4/geometry/shapes/Ellipse.java	30 Aug 2011 20:43:54 -0000	1.1
>+++ src/org/eclipse/gef4/geometry/shapes/Ellipse.java	31 Aug 2011 11:31:15 -0000
>@@ -11,6 +11,10 @@
>  *******************************************************************************/
> package org.eclipse.gef4.geometry.shapes;
> 
>+import java.util.ArrayList;
>+import java.util.Iterator;
>+import java.util.List;
>+
> import org.eclipse.gef4.geometry.Dimension;
> import org.eclipse.gef4.geometry.Point;
> import org.eclipse.gef4.geometry.transform.AffineTransform;
>@@ -141,8 +145,144 @@
> 		return height;
> 	}
> 
>+	public Point[] getIntersections(Polyline polyline) {
>+		List<Point> intersections = new ArrayList<Point>();
>+
>+		for (Line segment : polyline.getSegments()) {
>+			for (Point intersection : getIntersections(segment)) {
>+				intersections.add(intersection);
>+			}
>+		}
>+
>+		return intersections.toArray(new Point[] {});
>+	}
>+
>+	public Point[] getIntersections(Polygon polygon) {
>+		List<Point> intersections = new ArrayList<Point>();
>+
>+		for (Line segment : polygon.getSegments()) {
>+			for (Point intersection : getIntersections(segment)) {
>+				intersections.add(intersection);
>+			}
>+		}
>+
>+		return intersections.toArray(new Point[] {});
>+	}
>+
>+	public Point[] getIntersections(Rectangle rect) {
>+		List<Point> intersections = new ArrayList<Point>(8); // 2*4
>+
>+		for (Line segment : rect.getSegments()) {
>+			for (Point intersection : getIntersections(segment)) {
>+				intersections.add(intersection);
>+			}
>+		}
>+
>+		return intersections.toArray(new Point[] {});
>+	}
>+
> 	public Point[] getIntersections(Line l) {
>-		throw new UnsupportedOperationException();
>+		List<Point> intersections = new ArrayList<Point>(2);
>+
>+		// ellipse equation x^2/(width/2)^2 + y^2/(height/2)^2 = 1 may be
>+		// written as x^2/aSq + y^2/bSq = 1 with:
>+		double a = width / 2;
>+		double b = height / 2;
>+		double aSq = width * width * 0.25d;
>+		double bSq = height * height * 0.25d;
>+
>+		// ellipse's center
>+		double xOffset = x + a;
>+		double yOffset = y + b;
>+
>+		// normalized line points as if the ellipse was centered around origin
>+		double x1 = l.getX1() - xOffset;
>+		double y1 = l.getY1() - yOffset;
>+		double x2 = l.getX2() - xOffset;
>+		double y2 = l.getY2() - yOffset;
>+
>+		// deltas to calculate the line's slope
>+		double dy = y2 - y1;
>+		double dx = x2 - x1;
>+
>+		// special-case the vertical line
>+		if (PrecisionUtils.equal(dx, 0)) {
>+			// vertical line
>+			if (PrecisionUtils.smallerEqual(-a, x1)
>+					&& PrecisionUtils.smallerEqual(x1, a)) { // -a <= x1 <= a
>+				// inside the ellipse
>+				double y = Math.sqrt(PrecisionUtils.round(bSq
>+						* (1 - x1 * x1 / aSq)));
>+
>+				if (PrecisionUtils.greaterEqual(y1, y)) {
>+					if (PrecisionUtils.smallerEqual(y2, y)) {
>+						intersections.add(new Point(x1, y));
>+					}
>+					if (!PrecisionUtils.equal(y, 0)
>+							&& PrecisionUtils.smallerEqual(y2, -y)) {
>+						intersections.add(new Point(x1, -y));
>+					}
>+				} else if (PrecisionUtils.smallerEqual(y1, -y)) {
>+					if (PrecisionUtils.greaterEqual(y2, -y)) {
>+						intersections.add(new Point(x1, -y));
>+					}
>+					if (!PrecisionUtils.equal(y, 0)
>+							&& PrecisionUtils.greaterEqual(y2, y)) {
>+						intersections.add(new Point(x1, y));
>+					}
>+				}
>+			}
>+		} else {
>+			// calculating the line function's slope and y-offset:
>+			double m = dy / dx;
>+			double n = y1 - m * x1;
>+
>+			// substituting y within ellipse equation leads to a quadratic
>+			// equation of the form q2*x^2 + q1*x + q0 = 0 with:
>+			double q2 = bSq + aSq * m * m;
>+			double q1 = 2 * m * aSq * n;
>+			double q0 = aSq * (n * n - bSq);
>+
>+			// values for the pq-formula:
>+			double p = q1 / q2;
>+			double q = q0 / q2;
>+
>+			// check if equation has at least one solution
>+			double d = p * p / 4 - q;
>+			if (PrecisionUtils.smaller(d, 0)) {
>+				// discriminant smaller zero, so no solutions possible
>+			} else if (PrecisionUtils.equal(d, 0)) {
>+				// discriminant equals zero, so one possible solution
>+				double px = -p / 2;
>+				double py = px * m + n;
>+				intersections.add(new Point(px, py));
>+			} else {
>+				// discriminant greater than zero, so two possible solutions
>+				double sqrt = Math.sqrt(PrecisionUtils.round(d));
>+
>+				// first
>+				double px = -p / 2 + sqrt;
>+				double py = px * m + n;
>+				intersections.add(new Point(px, py));
>+
>+				// second
>+				px = -p / 2 - sqrt;
>+				py = px * m + n;
>+				intersections.add(new Point(px, py));
>+			}
>+		}
>+
>+		// sort out all points that do not lie on the given line and translate
>+		// the coordinates back:
>+		for (Iterator<Point> i = intersections.iterator(); i.hasNext();) {
>+			Point p = i.next();
>+			p.translate(xOffset, yOffset);
>+			if (!l.contains(p)) {
>+				i.remove();
>+			}
>+		}
>+
>+		return intersections.toArray(new Point[] {});
> 	}
> 
> 	public Point getLocation() {

Flags:

nyssen: iplog+

Actions: View | Diff

Attachments on bug 355997: 202484 | 202501 | 205718 | 206845 | 206852 | 207479 | 207484 | 208179 | 208923 | 212739 | 212771 | 212775 | 212776 | 213615 | 216278 | 216482 | 217706