Attachment 165193 Details for Bug 162082 – Patch for Geometry

Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

[patch] Patch for Geometry

162082.txt (text/plain), 4.77 KB, created by Alexander Nyßen

on 2010-04-17 17:15:19 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Alexander Nyßen

Created: 2010-04-17 17:15:19 EDT

Size: 4.77 KB

patch

obsolete

>### Eclipse Workspace Patch 1.0
>#P org.eclipse.draw2d
>Index: src/org/eclipse/draw2d/geometry/Geometry.java
>===================================================================
>RCS file: /cvsroot/tools/org.eclipse.gef/plugins/org.eclipse.draw2d/src/org/eclipse/draw2d/geometry/Geometry.java,v
>retrieving revision 1.5
>diff -u -r1.5 Geometry.java
>--- src/org/eclipse/draw2d/geometry/Geometry.java	17 Oct 2008 16:49:34 -0000	1.5
>+++ src/org/eclipse/draw2d/geometry/Geometry.java	17 Apr 2010 21:14:26 -0000
>@@ -18,60 +18,77 @@
>  */
> public class Geometry
> {
>+	/**
>+	 * Determines whether the two line segments formed by the given coordinates
>+	 * intersect. If one of the two line segments starts or ends on the other
>+	 * line, then they are considered to be intersecting.
>+	 * TODO: Decide whether co-linear overlapping line segments should be regarded
>+	 *       as intersecting as well.
>+	 * 
>+	 * @param ux
>+	 *            x coordinate of starting point of line 1
>+	 * @param uy
>+	 *            y coordinate of starting point of line 1
>+	 * @param vx
>+	 *            x coordinate of ending point of line 1
>+	 * @param vy
>+	 *            y coordinate of ending point of line 1
>+	 * @param sx
>+	 *            x coordinate of the starting point of line 2
>+	 * @param sy
>+	 *            y coordinate of the starting point of line 2
>+	 * @param tx
>+	 *            x coordinate of the ending point of line 2
>+	 * @param ty
>+	 *            y coordinate of the ending point of line 2
>+	 * @return <code>true</code> if the two line segments formed by the given
>+	 *         coordinates cross
>+	 * @since 3.1
>+	 */
>+	public static boolean linesIntersect(int ux, int uy, int vx, int vy,
>+			int sx, int sy, int tx, int ty) {
>+		/*
>+		 * The following implementation is based on the line intersection
>+		 * algorithm published by Paul Bourke
>+		 * (http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/).
>+		 */
>+		long den = (((long) ty - (long) sy) * ((long) vx - (long) ux))
>+				- (((long) tx - (long) sx) * ((long) vy - (long) uy));
>+
>+		long numA = (((long) tx - (long) sx) * ((long) uy - (long) sy))
>+				- (((long) ty - (long) sy) * ((long) ux - (long) sx));
>+
>+		long numB = (((long) vx - (long) ux) * ((long) uy - (long) sy))
>+				- (((long) vy - (long) uy) * ((long) ux - (long) sx));
>+
>+		if (den == 0) {
>+			if (numA == 0 && numB == 0) {
>+				// co-linear
>+				// TODO: decide whether co-linear overlapping segments should be regarded
>+				// as overlapping
>+				// check if there is an overlap (sufficient to check x coordinates only)
>+				if ((sx > vx && tx > vx) || (sx < ux && tx < ux)) {
>+					// co-linear & non-overlapping
>+					return false;
>+				}
>+				// co-linear & overlapping
>+				return true;
>+			}
>+			// parallel
>+			return false;
>+		}
> 
>-/**
>- * Determines whether the two line segments formed by the given coordinates intersect.  If
>- * one of the two line segments starts or ends on the other line, then they are considered
>- * to be intersecting.
>- * 
>- * @param ux x coordinate of starting point of line 1
>- * @param uy y coordinate of starting point of line 1
>- * @param vx x coordinate of ending point of line 1
>- * @param vy y coordinate of endpoing point of line 1
>- * @param sx x coordinate of the starting point of line 2
>- * @param sy y coordinate of the starting point of line 2
>- * @param tx x coordinate of the ending point of line 2
>- * @param ty y coordinate of the ending point of line 2
>- * @return <code>true</code> if the two line segments formed by the given coordinates 
>- *         cross
>- * @since 3.1
>- */
>-public static boolean linesIntersect(int ux, int uy, int vx, int vy, 
>-		int sx, int sy, int tx, int ty) {
>-	/*
>-	 * Given the segments: u-------v. s-------t. If s->t is inside the triangle u-v-s, 
>-	 * then check whether the line u->u splits the line s->t.
>-	 */
>-	/* Values are casted to long to avoid integer overflows */
>-	long usX = (long) ux - sx;
>-	long usY = (long) uy - sy;
>-	long vsX = (long) vx - sx;
>-	long vsY = (long) vy - sy;
>-	long stX = (long) sx - tx;
>-	long stY = (long) sy - ty;
>-	if (productSign(cross(vsX, vsY, stX, stY), cross(stX, stY, usX, usY)) >= 0) {
>-		long vuX = (long) vx - ux;
>-		long vuY = (long) vy - uy;
>-		long utX = (long) ux - tx;
>-		long utY = (long) uy - ty;
>-		return productSign(cross(-usX, -usY, vuX, vuY), cross(vuX, vuY, utX, utY)) <= 0;
>-	}
>-	return false;
>-}
>-
>-private static int productSign(long x, long y) {
>-	if (x == 0 || y == 0) {
>-		return 0;
>-	} else if (x < 0 ^ y < 0) {
>-		return -1;
>-	}
>-	return 1;
>-}
>-
>-private static long cross(long x1, long y1, long x2, long y2) {
>-	return x1 * y2 - x2 * y1;
>-}
>+		long ua = numA / den;
>+		long ub = numB / den;
> 
>+		if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {
>+			// intersecting
>+			return true;
>+		}
>+		// non intersecting
>+		return false;
>+	}
>+	
> 	/**
> 	 * @see PointList#polylineContainsPoint(int, int, int)
> 	 * @since 3.5

Actions: View | Diff

Attachments on bug 162082: 164484 | 165192 | 165193 | 165195