Geometry Boost List: [ggl] Understanding get_turns for linestring/polygon overlay

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

On Apr 15, 2011, at 4:17 PM, Barend Gehrels wrote:

> Hi John,
> 
>> 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?
> 
> Yes, a box_2d is not really a polygon_2d but you can convert it to one. Which branch of Boost.Geometry are you using? If 0.9.0, you can use boost::geometry::convert to convert the box into a polygon.
> 
> Indeed the get_turns fails in case of a linestring and a box, and a polygon succeeds. In a future version the box will be supported as well in this algorithm.
> 
> Regards, Barend

Barend,
Thank you for all your help.  This technique worked great.  I did the following
1) User defines the cut line in the iphone interface
2) Create the box and buffer it
3) I extend the line in both directions to ensure it crosses the box at two points (if it crosses it at just one point, I consider that invalid and don't do anything)
4) Get the turn points for the buffered box and the line.
5) Extract the two pieces of the buffered square
6) Intersect each half with the polygon

I also am getting more used to Boost::Geometry.  It is quite easy to use, as it follows STL and Boost patterns, but I just don't know which algorithms and methods to use and how to find them.

I found along the way that I had to use std::unique_copy in several places to get rid of duplicates, but it is all working.  I haven't checked how fast it is on the real device, but can't imagine that will be a problem (my polygons end up being pretty simple).  This was the last semi-major obstacle to really making progress on my game.  I will definitely let you know when the game is done (and give you promo codes if you have any iOS devices).

John Swensen