|
|
Geometry : |
Subject: [ggl] Understanding get_turns for linestring/polygon overlay
From: Barend Gehrels (barend)
Date: 2011-04-08 10:14:44
Hi John,
On 4-4-2011 20:33, John Swensen wrote:
>
> I'm not sure if what I want is possible in an easy manner. I can definitely do it by sorting the turn points in order of distance from one of the endpoints of the cutting line, but it seems this isn't built-in. That is OK. Here is a picture of what I intend to do: http://imgur.com/3FTsW
>
> Maybe I will run the algorithm by you folks who know geometry much better than I to see if you think it is a reasonable approach to splitting polygons. This technique is an adaptation from a StackOverflow answer, extending it to work with polygons that have holes and in which the line may intersect a vertex.
> http://stackoverflow.com/questions/1775457/generate-new-polygons-from-a-cut-polygon-2d
> The one thing this person forgot to mention was that you must always start the traversal at points not on the cut line, otherwise you risk having two identical polygons.
I thought about this and I think it will be quite difficult. At least
with our implementation, it is heavily based on direction. So two
polygons (both clockwise) intersect each other, and the results are
traversed by direction.
As soon as there is a line involved, it has no real clockwise or
counterclockwise direction of course. So it does not know which path to
follow.
Of course it is possible using another algorithm, but that might be
quite complex as well.
It is not only that our algorithm is based on direction, it is valid for
all Weiler-Atherton family algorithms, and the solution based on
StackOverflow is one of them.
> The basic algorithm is given in the StackOverflow article. The two corner cases not treated there are as follows:
> 1) when dealing with inner rings, the traversal direction should change for each nesting level. In the example given in the picture above, the outer ring would be traversed clockwise until reaching a cut point, hopping to the appropriate cut point and continue traversing counter-clockwise
> 2) the rules concerning how to determine the next cut point during traversal are changed in the special cases when the line intersects a vertex and does not enter the polygon. This is illustrated in the following image: http://imgur.com/d7g9c
>
> Does this seem a reasonable method?
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
-- Barend Gehrels http://about.me/barendgehrels -------------- next part -------------- Skipped content of type multipart/related
Geometry list run by mateusz at loskot.net