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-04 14:33:14

On Apr 4, 2011, at 1:14 PM, Barend Gehrels wrote:

> Hi John,
> 
>> I am finally getting back to working on this.  I have a few more questions.  I have found a couple of papers with simple algorithms for splitting polygons.  However, they all require that the turn points be ordered in terms of "when" they intersect the polygon.  That is, assuming the line has an implicit directions, then they would expect that the turn points be ordered from the implicit direction (it doesn't really matter which direction is assumed).  I am beginning my tests with the simple test case of a square with an inner hole that is also a square cut by a line running horizontally through the center. (...)
>> 
>> Then when using the same BOOST_FOREACH on the turns as shown in my previous email the turn points are returned order first going "forward" for the outer ring and "backward for the inner ring.  Is there someway with the policy input to get_turns to get it to return them in the order they occurred?
> 
> get_turns collects turning points in no particular order. The order depends on the geometric configuration of the input geometries.
> 
> But, it is possible to sort them afterwards. In fact that is done internally as well.
> 
> So if you want to order them on the first input polygon, you can use std::sort using a comparing functor, using the seg_id and the other_id, and of that the source_index (which refers to 0 and 1 for the first and second geometry, so to order on the first input polygon, use 0). If you want to order them on the second input line, use 1.
> 
> Didn't try this right now, but I think that must be possible.
> 
> Regards, Barend

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.

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?
John