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