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

Subject: [ggl] Understanding get_turns for linestring/polygon overlay
From: Barend Gehrels (barend)
Date: 2011-04-08 13:44:05

On 8-4-2011 19:27, 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.

Right, I assumed that a "cut" algorithm has both endpoints outside the 
polygon. Otherwise the polygon cannot be cut at all by that line (even 
not by bloating - that would give a different result). It can be checked 
easily - if one of the end points is inside the polygon, don't cut. If 
it is inside the whole of a polygon, yes you are right, but even then 
the whole cut would have to fail (and this is also detectable).

That having said, the algorithm is indeed not full-proof. It can cut the 
cases on StackOverflow or the cases John attached, but the next case 
will fail.

It will either not cross the enlarged bounding box, or (if the segment 
is extended) cut the extra piece of the polygon.

Anyway (John's mail also just arrived), if these cases are not relevant, 
it will probably work well.

By the way - we used that bloating trick (in GIS it is called buffering) 
in one of our projects, in floating point. Scaling down is not necessary 
- you can follow it up by an intersection and add that to either one of 
the sides.

Regards, Barend

-------------- next part --------------
Skipped content of type multipart/related