Boost logo

Geometry :

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> {};

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,

    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

Regards, Barend

Geometry list run by mateusz at