Bug 162082

Comment 1 Alexander Nyßen 2010-04-11 06:58:31 EDT

The problem does not occur with parallel line segments in general, but in case of co-linear line segments (which also holds for the reported example). I added a test case (testLinesIntersect) to GeometryTest, which reproduces the problem.

Comment 2 Alexander Nyßen 2010-04-11 07:53:28 EDT

Created attachment 164484 [details]
Re-implemenation of Geometry#linesIntersect

As the existing code within lineIntersects is quite hard to understand (at least for me), I did a re-implementation based on the line intersection algorithm published by Paul Bourke (http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/), which I have attached.

While doing the re-implementing a came along the question, whether two overlapping co-linear line segments should indeed be regarded as being intersecting or not. Or reformulated : Should two line segments be regarded as intersecting if they (1) share at least one common point, or if there is (2) exactly one intersection point?

The current Javadoc of does not say anything explicitly about it: 
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.

The intention of this bug as well as the JUnit tests I have added to Geometry Test are based on assumption (1), while the algorithm published by Bourke seems to be initially based on assumption (2); I altered it to check for overlap in case of co-linear line segments.

Comment 3 Anthony Hunter 2010-04-17 16:02:28 EDT

(In reply to comment #2)
> Created an attachment (id=164484) [details]
> Re-implemenation of Geometry#linesIntersect

This must be the wrong patch, the patch only has an update to GeometryTest

Comment 4 Alexander Nyßen 2010-04-17 17:11:24 EDT

Created attachment 165192 [details]
Patch for Geometry.

You are right, sorry for that. I have attached the correct one now.

Comment 5 Alexander Nyßen 2010-04-17 17:15:19 EDT

Created attachment 165193 [details]
Patch for Geometry

Comment 6 Alexander Nyßen 2010-04-17 17:51:48 EDT

Created attachment 165195 [details]
Patch for Geometry (based on double)

Sorry for this. Let me shortly explain why I uploaded all these revisions:

My initial implementation (which I uploaded first) was based on floats. When I had uploaded it and looked into the patch again I noticed that the former implementation of linesIntersect was based on converting int to long to not run into overflows, so I thought this could be a problem with float as well. As the intersection point is never directly computed and the numerators are only checked to be within the range 0..1, the algorithm could indeed also use longs (so I uploaded a second version with longs). However, while it would also behave correctly this way (as the intersection points are never computed directly), I do not think it would be straightforward, so here is a version based on doubles.

Comment 7 Alexander Nyßen 2010-04-18 06:12:51 EDT

(In reply to comment #6)
> Created an attachment (id=165195) [details]
> Patch for Geometry (based on double)
> 
> Sorry for this. Let me shortly explain why I uploaded all these revisions:
> 
> My initial implementation (which I uploaded first) was based on floats. When I
> had uploaded it and looked into the patch again I noticed that the former
> implementation of linesIntersect was based on converting int to long to not run
> into overflows, so I thought this could be a problem with float as well. As the
> intersection point is never directly computed and the numerators are only
> checked to be within the range 0..1, the algorithm could indeed also use longs
> (so I uploaded a second version with longs). However, while it would also
> behave correctly this way (as the intersection points are never computed
> directly), I do not think it would be straightforward, so here is a version
> based on doubles.

Having reconsidered this, my statement that the long-based version would have behaved correctly (as intersection points are not directly computed) was of course nonsense. Thus, the double-based version I have uploaded at last is the one of relevance.

Comment 8 Anthony Hunter 2010-04-19 14:37:05 EDT

(In reply to comment #2)
> As the existing code within lineIntersects is quite hard to understand (at
> least for me), I did a re-implementation based on the line intersection
> algorithm published by Paul Bourke
> (http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/), which I have
> attached.

Hi Alexander, The web site says copyright Paul Bourke. I am not sure if we can reference his implementation or not. Ian, what do you think?

Comment 9 Ian Bull 2010-04-20 01:37:29 EDT

(In reply to comment #8)
> Hi Alexander, The web site says copyright Paul Bourke. I am not sure if we can
> reference his implementation or not. Ian, what do you think?

This is great question.  I use the rule of thumb that we should not look at the code when implementing an algorithm.  If you can read the pseudo code and implement it then I think you're ok, but if you have to read (and subsequently copy) the code, then you're likely breaking licensing rules.  

We obviously make use of algorithms that others have written (binary search, quick sort, Dijkstra's, etc..) but we cannot copy the code.  

Of course I'm not a lawyer.  This might be a good thing to ask at the next tools PMC meeting, I'm sure someone must have hit this before.

Comment 10 Alexander Nyßen 2010-04-26 03:34:05 EDT

Well, I am no lawyer as well, but I think unless the algorithm is not patented, it should be implementable. Anyhow, as this is not a very complicated problem I think it would also be possible to come up with another alternative implementation. 

Actually I was investigating a re-implemenation based on the Euclidean geometry support we have available in terms of Ray/Straight (compute straight intersection and decide whether the intersection point is covered by both segments). However, when doing so I ran into the problem that the current Euclidean geometry support is all integer-based, leading to quite harmful rounding effects. I have opened a new issue (bug #310397) to address this.

Comment 11 Alexander Nyßen 2010-04-26 18:14:55 EDT

Let me mention that if we plan to migrate GMF's LineSeg class (and related PointListUtilites and PrecisionPointList) to the draw2d geometry package in the post-Helios time-frame (as covered by bug #108119), we wouldn't be in need of any of the currently offered Geometry helper functions any more, as decent object-oriented implementations could then be used. As such, this issue could be regarded as some sort of "temporary" issue, and - before we might run into copyright issues here - a fix based on a revised Geometry-API (see # 310397) may also be an option, even if not as elegant as the proposed Bourke-algorithm.

Comment 12 Anthony Hunter 2010-04-29 11:08:07 EDT

(In reply to comment #10)
> Well, I am no lawyer as well, but I think unless the algorithm is not patented,
> it should be implementable. Anyhow, as this is not a very complicated problem I
> think it would also be possible to come up with another alternative
> implementation. 

Are you able to do this before M7 Alexander?

We still have one JUnit failure in testLinesIntersect that we need to fix before M7.

Comment 13 Alexander Nyßen 2010-04-29 11:10:15 EDT

Yes, I think that should be possible.

Comment 14 Alexander Nyßen 2010-05-02 09:11:55 EDT

Having investigated that a solution based on Vector/Straight would be rather slow (as it uses double precision, which is not needed for a simple intersection test), I simply added a quick check based on the boundary boxes of the two segments that sorts out the degenerated case that co-linear line segments are always reported as intersecting.