Geometry Boost List: Re: [geometry] Dectecting if two linestrings cut each other

Subject: Re: [geometry] Dectecting if two linestrings cut each other
From: Barend Gehrels (barend_at_[hidden])
Date: 2012-07-12 16:20:26

Hi,

On 12-7-2012 16:57, undu wrote:
> Hi
>
> I'm currently looking for a way to know if two linestrings "really cross"
> each other (they can have common points or segments without really crossing)

This is (probably/partly) called ST_Crosses according to OGC specs. It 
is not yet implemented.

> and if they do, where.

OK, interesting.

> My linestrings are 2D building outlines.
> As I understand, there is no simple way (an implemented algorithm) to do
> this using BGL ?

No.

> So I'm trying to develop an algorithm doing this, but it gets really messy
> when dealing with closed linestrings intersecting on closing vertex, and
> more generally with intersection on common vertices. I also have problems
> when the intersection is a segment (or a linestring itself).

Are you building it on top of Boost.Geometry?

> I browsed the web looking for such an algorithm, but it seems I'm the only
> guy around trying to do this (which surprises me a lot).
>
> Does someone know any ressources that could help me achieving this ?

You can look at the documentation or samples for ST_Crosses (Sql Server, 
PostGIS) but I'm afraid it is not that extensive (just looked). The 
definition when it exactly crosses has to be clear (common segments, 
common points? On internal vertices? On corners?). You already defined 
much of this - but it is not always clear in the documentation of 
libraries...

OK, Boost.Geometry then has an algorithm get_turns which might be used 
to get information from it. This is this type of information (real 
intersection, touching, equal, collinear, etc). But it is not trivial. 
This algorithm is used internally, it is not in the docs.

Hope this reply helps a bit.

Regards, Barend