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 12:15:00

On Feb 1, 2011, at 5:00 PM, barend wrote:
> 
> BOOST_FOREACH(turn_info const& turn, turns)
>     {
>    std::cout << action << " polygon at " << boost::geometry::dsv(turn.point)  << std::endl;
>         std::cout << action << " polygon at " << boost::geometry::dsv(turn.point) << "with seg_id: " << turn.operations[0].seg_id.segment_index << std::endl;
>       std::cout << "================" << turn.operations[0].seg_id.source_index << "  " << turn.operations[0].seg_id.multi_index << "   " << turn.operations[0].seg_id.ring_index << "    " << turn.operations[0].seg_id.segment_index << std::endl;        
>     }
> 
> I would have expected to see the ring_index be (-1), but I didn't expect for the segment_index to be (0) for both turns.  Just to give some background, I have created the following simple triangle polygon
> OriginalPolygon:  (((100, 100), (200, 200), (200, 100)))
> 
> I then got the turns from a line that crossed it:
> entering polygon at (168.749, 168.749)
> ================0  -1   -1    0
> leaving polygon at (200, 151.114)
> ================0  -1   -1    0
> 
> I would have expected the segments to be numbered clockwise also and that the "entering polygon" turn would be in segment 0 and the "leaving polygon turn" would be in segment 1.
>  
> Source 0 is the first geometry and source 1 is the second geometry. So if you follow the sample, source 0 is the linestring, source 1 is the polygon. So I probably pointed you a bit wrong, by my remark operation[0].seg_id, it should have been operation[1].seg_id for the polygon.
>  
> If I repeat your comments into the origional sample, and replace [0] by [1], I get the right information:
>  
> Intersection of linestring/polygon
> entering polygon at (0.666667, 2.33333)with seg_id: 0
> ================1  -1   -1    0
> leaving polygon at (1.33333, 3.66667)with seg_id: 1
> ================1  -1   -1    1
> entering polygon at (2.85714, 4.42857)with seg_id: 1
> ================1  -1   -1    1
> leaving polygon at (3.76471, 3.82353)with seg_id: 2
> ================1  -1   -1    2
>  
> Where the segment_id's seem all right to me.
>  
> Regards, Barend
>  

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.

Code to generate the polygon
========================
polygon_2d createSimpleBox_InnerOuter()
{
        polygon_2d origPoly;
        ring_type<polygon_2d>::type& origRing = exterior_ring(origPoly);
        append(origRing, make<point_2d>(0, 0));
        append(origRing, make<point_2d>(10, 0));
        append(origRing, make<point_2d>(10, 10));
        append(origRing, make<point_2d>(0, 10));
        append(origRing, make<point_2d>(0, 0));
        correct(origPoly); // Make clockwise if necessary	
        
        origPoly.inners().resize(1);
        model::ring<point_2d>& inner = origPoly.inners().back();
        const double coor[][2] = { {2.5, 2.5}, {7.5, 2.5}, {7.5, 7.5}, {2.5, 7.5}, {2.5, 2.5} };
        assign(inner, coor);
        
        return origPoly;
}

Code to generate the linestring
====================================
linestring_2d splitLine;
append(splitLine, make<point_2d>(-1, 5 ));
append(splitLine, make<point_2d>(11, 5 ));

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?

John Swensen