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-04 15:55:21

On 4-4-2011 20:33, John Swensen wrote:
> 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.

Thanks for the links, didn't see that Stackoverflow one before.

I still think that sorting might be an option - this is done in the 
enrichment phase of Boost.Geometry as well, it is quite similar. With 
Boost.Geometry, it then always start at one of the turning points, so 
contrary what is said here.

Anyway, I will look at this in more depth next Friday as I've a little 
more time then.

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110404/31cccc65/attachment.html