Geometry Boost List: [ggl] How to intersect two linestrings?

Subject: [ggl] How to intersect two linestrings?
From: Barend Gehrels (barend.gehrels)
Date: 2010-08-28 10:33:32

hi Hartmut,

> I'm trying to find my way through GGL in order to use it in a real
> application and got stuck at something which is probably very simple. I have
> two linestrings std::vector<point_2d>, containing 2 points each (i.e. two
> line segments). How do I calculate a) whether these line segments intersect,
> and b) if they intersect, at what (single) coordinate?
>   

Indeed not that simple though it should be.

There are several solutions.

ONE: If the linestring is always a line segment, you can use it as a 
boost::geometry segment concept. This is the snippet then:

void snippet_intersection_segment()
{
    typedef boost::geometry::point_xy<double> P;
    custom_segment<P> line1, line2;
    boost::geometry::read_wkt("linestring(1 1,2 2)", line1);
    boost::geometry::read_wkt("linestring(2 1,1 2)", line2);

    std::vector<P> intersections;
    boost::geometry::intersection(line1, line2, intersections);
}

where custom_segment is a segment defined, for example, like this:

template <typename P> struct custom_segment : std::pair<P, P> {};
BOOST_GEOMETRY_REGISTER_SEGMENT_TEMPLATIZED(custom_segment, first, second)

The boost::geometry::segment can also be used, but is (currently) 
referring to point references, an issue which is still to be solved, but 
that was planned when moving to namespace "model" for all geometries 
(which is not yet done). For some algorithms the fields in the segment 
needs still need to be named "first"/"second" (will solve that).

Anyway, the snippet above gives you the intersection point(s) (one, zero 
or two))

TWO You ask for whether the segments intersect. You can do that checking 
the intersections (see above), but the free function "intersects" is 
made for that. Unfortunately it was not implemented for all 
combinations, I just added/committed it for segments and linestrings 
(based on functionality which was already there).

THREE you are using std::vector's as a linestring, even though you use 
it as segments. Basically no problem. Linestrings should also work. 
Again unfortunately, the combination linestring/linestring delivering 
points is not yet there, it is however possible to use the underlying 
"get_turns" algorithm, conform next snippet.

void snippet_intersection_linestring()
{
    typedef boost::geometry::point_xy<double> P;
    std::vector<P> line1, line2;
    boost::geometry::read_wkt("linestring(1 1,2 2)", line1);
    boost::geometry::read_wkt("linestring(2 1,1 2)", line2);

    std::vector<P> intersection_points;
    //NYI: boost::geometry::intersection(line1, line2, 
intersection_points);

    namespace bg = boost::geometry;
    typedef bg::detail::overlay::turn_info<P> turn_info;
    std::vector<turn_info> turns;

    bg::detail::get_turns::no_interrupt_policy policy;
    bg::get_turns<bg::detail::overlay::assign_null_policy>(line1, line2, 
turns, policy);
}

I will implement this also for "intersection", that is the algorithm to 
be used.

There can be zero intersections, one, or two (in case of parallel 
segments and point output, there will be two points, being the 
intersection points) (see comment Arash appearing when I was writing 
this mail), however, get_turns will surpress one of the two in case of 
parallel (because it is not a "turn").

Nice to use it in a real application, if you need any help, welcome of 
course.

Regards, Barend