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-08 13:34:13

On Apr 8, 2011, at 1:27 PM, Simonson, Lucanus J wrote:

> I don't think that the algorithm with the box will work.  What happens if one (or both) of the end points of the linestring is inside the box, but outside the original polygon?  Presumably if an endpoint of the linestring is inside the polygon or inside a hole of polygon then the polygon is left uncut.  What about a spiral shaped line string with one end point inside the box but outside the original polygon?  That is about the worst case I can think of.
>  
> What I would do is bloat the linestring by some small fator and subtract it from the original polygon.  I would probably play some trickery with scaling, bloating the linestring by some value much smaller than the scale factor, do the subract operation then scale down and rely on integer truncation to get the resulting polygons to share edges of the original linestring, but that is only possible due to integer coordinates.
> 

In my special case, the linestring can be arbitrarily long.  In fact, using Barend's suggestions seems reasonable for my application because I will first find the bounding box for the polygon, grow it a little, then make the linestring such that its endpoints are part of the bounding box.  I really like this solution a lot and will try to work on it in the next week or so.

John Swensen