Boost logo

Geometry :

Subject: [ggl] Understanding get_turns for linestring/polygon overlay
From: John Swensen (jpswensen)
Date: 2011-04-15 11:14:41

On Apr 8, 2011, at 1:27 PM, Simonson, Lucanus J wrote:
> The corner cases are really the most difficult to get right. I think I spend 20% on the algorithm and 80% on the corner cases, or more.
> I thought of another method, avoiding the cutline but just using polygon intersections.
> See the picture below.
> 1) create the envelope (bounding box) of the black polygon using boost::geometry::envelope
> 2) buffer it with some arbitrary value to create a larger box using boost::geometry::buffer (it exists for boxes)
> 3) the difficult, but now not really difficult, part: cut that box with the cutline. This is not yet completely possible using Boost.Geometry, but it is not too difficult (if the cutline is one segment only; if it is a linestring it might return in several polygons and not trivial anymore).
> 4) you end up with two polygons, here left and right, with the blue/red lines, and can intersect both polygons with the original black polygon and they are cut. This can be done by Boost.Geometry
> So it is basically similar but changes cutting a polygon with a line to cutting a box with a line, which should be much easier.
> Regards, Barend

Maybe I am a total idiot, but I have the hardest time debugging my own problems with Boost::Geometry. I was able to create the envelope and extend it to a box with a buffer. I also was able to create a linestring that I am sure extends beyond the extent of the box. Now I am trying to get the turn points for the intersection of the linestring and the box. Previously, I was able to do the following with a linestring and a polygon_2d
typedef boost::geometry::detail::overlay::turn_info<point_2d> turn_info;
std::vector<turn_info> turns;
boost::geometry::detail::get_turns::no_interrupt_policy policy;
boost::geometry::get_turns<false, false, boost::geometry::detail::overlay::assign_null_policy>(splitLine, bufferBox, turns, policy);

However, this fails with a box_2d. I'm assuming that the box_2d is somehow not really a polygon_2d, but can't figure out how to make it a polygon. I know I could probably iterate through all the points of the box and add it to a polygon, but is there a better way?

John Swensen

Geometry list run by mateusz at