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

Subject: [ggl] How to intersect two linestrings?
From: Hartmut Kaiser (hartmut.kaiser)
Date: 2010-08-28 23:59:49

Barend,

Thanks for the elaborate reply. Everything works as expected now!

Regards Hartmut

---------------
Meet me at BoostCon
www.boostcon.com

> -----Original Message-----
> From: ggl-bounces_at_[hidden] [mailto:ggl-bounces_at_[hidden]] On
> Behalf Of Barend Gehrels
> Sent: Saturday, August 28, 2010 9:34 AM
> To: Generic Geometry Library Discussion
> Subject: Re: [ggl] How to intersect two linestrings?
> 
> 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
> 
> 
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl