Boost logo

Geometry :

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

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

Geometry list run by mateusz at