Download
Getting Started
Members
Projects
Community
Marketplace
Events
Planet Eclipse
Newsletter
Videos
Participate
Report a Bug
Forums
Mailing Lists
Wiki
IRC
How to Contribute
Working Groups
Automotive
Internet of Things
LocationTech
Long-Term Support
PolarSys
Science
OpenMDM
More
Community
Marketplace
Events
Planet Eclipse
Newsletter
Videos
Participate
Report a Bug
Forums
Mailing Lists
Wiki
IRC
How to Contribute
Working Groups
Automotive
Internet of Things
LocationTech
Long-Term Support
PolarSys
Science
OpenMDM
Toggle navigation
Bugzilla – Attachment 165193 Details for
Bug 162082
Segment intersection test fails in degenerate case
Home
|
New
|
Browse
|
Search
|
[?]
|
Reports
|
Requests
|
Help
|
Log In
[x]
|
Terms of Use
|
Copyright Agent
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:
Patch for Geometry
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
You cannot view the attachment while viewing its details because your browser does not support IFRAMEs.
View the attachment on a separate page
.
View Attachment As Diff
View Attachment As Raw
Actions:
View
|
Diff
Attachments on
bug 162082
:
164484
|
165192
|
165193
|
165195