Boost logo

Geometry :

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

Geometry list run by mateusz at