[geos-devel] how to know if two linestrings "really" cross each other

[Todd Jellett]

This algorithm will work if you can guarantee that there will be no 
overlapping line segments on your linestrings. If overlaps are possible, 
you will get a mixture of 4 line segment intersections and pairs of 3 
line segment intersections with overlap between them.

To robustly determine if you have a transverse intersection between 2 
linestrings:

- create a circle centered at the intersection point (4 segment case) or 
at the start and end of the overlap interval (3 segment case)
- decompose each circle into two circular arcs where one line string 
intersects the circle

You have a transverse intersection if the incoming line segment of the 
other linestring intersects a different circular arc than the outgoing 
line segment.

On 30/05/2012 5:26 PM, Martin Davis wrote:
> The DE-9IM model isn't designed to be able to distinguish between 
> these two cases, so there's no way to compute this by using any of the 
> named predicates, or even a custom relate matrix.
>
> You could do this via some fairly straightforward custom code.  The 
> algorithm is:
> -  identify vertices in each linestring which are coincident
> - build a simple "local topology" for the 4 incident line segments at 
> each intersection
> - examine the intersection to see if the segments alternate or are 
> adjacent (you can do this by using the angles of the segments)
>
> On 5/30/2012 3:40 AM, Jasmin FORMONT wrote:
>>
>> Hi everyone
>>
>> I can't find a way to tell if two linestrings "really" cross each other.
>>
>> For instance if I have this linestring :
>>
>> Line1 : LINESTRING(0 0, 1 1, 2 0)
>>
>> How can I differentiate the relation of line 1 with one of the 
>> following :
>>
>> Line2 : LINESTRING(0 2, 1 1, 2 2)    -> no "real" cross, just a 
>> contact point
>>
>> Line3 : LINESTRING(0 2, 1 1, 1 0)    -> lines "really" cross each other
>>
>> I can't find a good combination of crosses, touches, etc... to 
>> differentiate these cases.
>>
>>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20120531/0285bcc8/attachment.html>