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-02-03 10:31:07

On Feb 1, 2011, at 5:00 PM, barend wrote:

> Hi John,
> 
>  
> -----Original Message-----
> From: John Swensen <jpswensen_at_[hidden]>
> To: Generic Geometry Library Discussion <ggl_at_[hidden]>
> Date: Tue, 1 Feb 2011 15:06:26 -0500
> Subject: Re: [ggl] Understanding get_turns for linestring/polygon overlay
> 
> 
> On Feb 1, 2011, at 11:57 AM, Barend Gehrels wrote:
> 
> > Hi John,
> > 
> > Welcome to the list!
> > 
> > On 1-2-2011 16:25, John Swensen wrote:
> >> I apologize if this email seems rudimentary.  I am just getting into both Boost and Boost.Geometry.  From the mailing list, I have gleaned that LineString/Polygon boolean operations are not implemented yet.
> > 
> > That is right.
> > 
> >>   So, I am trying to implement it myself from some of the examples.  I am able to successfully create a polygon and a linestring and follow the overlay example to get the list of turn points describing where they intersect.  However, I would like to take the list of turn points and create two new polygons from that are divided by the turn points.
> > So basically you are wishing a "cut operation", cut the polygon into pieces. Very interesting.
> > 
> >> So my questions are:
> >> 1) Is there a way to insert the turn point into the outer ring easily?
> > 
> > Yes, relatively easy. For each turn point you know the coordinate (.point), and at which segment it intersects the polygon (operations[0].seg_id). It must be able to insert a point there, though this is not a Boost.Geometry standard way. Assuming you use the Boost.Geometry polygon, you take the ring (if the ring_id is -1 it is the outer ring), and using std:: you insert that point there.
> > 
> >> 2) Is there a way to find the line segments of the outer ring that are divided by the turn points?
> > Yes, this is related and actually answered above.
> > 
> > The basic case might be relatively easy to solve. However, as soon as intersection points overlay on the vertices of the input polygons, it becomes more complicated (or you can simply ignore those duplications). The sample shows "entering" and "leaving", but as soon as the linestring touches the polygon and does not intersect, it also becomes more complex. But not unsolvable.
> > 
> >> If either of these are easy to find, then splitting my polygon into two polygons should be straightforward.  I'm just not sure if there is a "right" way to do this.  I could always go back and walk my way around the outer ring doing the computation to see of the turn point lies on the line segment and then splitting accordingly, but want to know if this is already implemented and I just can't find it.
> > 
> > No, it is not implemented, and you have the right approach. In case you succeed and want to contribute this, I'm interested in the results.
> > 
> > Regards, Barend
> > 
> 
> Thanks for pointing me in the right direction, however I think there is something wrong with how I am trying it.  When I add the following debug output to my application, I don't get what I expected.
> 
> 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

Barend,

Thanks for your help.  I have a simple case working (where the cut only crosses the boundary of the polygon 2 times).  However, I noticed that when I am building it for the iphone simulator things work fine.  However, when I build it for the iphone device there are errors.  I think it may have to do with the compiler and standard template libraries used for the iphone device.  I think it may be more the compiler than the STL because the problem is occurring in deque.tcc and this file is the same for both the simulator and device source trees.

The offending line of code is when I try to union one half of my split polygon with a reflected version of the other half (I am "folding" the original polygon along a user defined line).
union_(unreflectedPoly, reflectedPoly, ps);

I have included the compiler error output below.  The last Boost line of code in the error trace is in the traverse function.  I don't understand the Boost.Geometry sources fully, but I tried to comment out the offending line:
rings.resize(size_at_start);
        near line 260 of algorithms/detail/overlay/traverse.hpp and things compiled for both simulator and device.  Things also appear to still be working fine, but I am sure that random commenting of lines of source code have definitely messed something up.

/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/deque.tcc:486:0 /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/deque.tcc:486:   instantiated from 'void std::deque<_Tp, _Alloc>::_M_insert_aux(typename std::_Deque_base<_Tp, _Alloc>::iterator, size_t, const _Tp&) [with _Tp = boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator>, _Alloc = std::allocator<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> >]'

/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/deque.tcc:217:0 /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/deque.tcc:217:   instantiated from 'void std::deque<_Tp, _Alloc>::_M_fill_insert(typename std::_Deque_base<_Tp, _Alloc>::iterator, size_t, const _Tp&) [with _Tp = boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator>, _Alloc = std::allocator<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> >]'

/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/stl_deque.h:1130:0 /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/stl_deque.h:1130:   instantiated from 'void std::deque<_Tp, _Alloc>::insert(typename std::_Deque_base<_Tp, _Alloc>::iterator, size_t, const _Tp&) [with _Tp = boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator>, _Alloc = std::allocator<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> >]'

/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/stl_deque.h:893:0 /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/stl_deque.h:893:   instantiated from 'void std::deque<_Tp, _Alloc>::resize(size_t, _Tp) [with _Tp = boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator>, _Alloc = std::allocator<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> >]'

/Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp:260:0 /Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp:260:   instantiated from 'void boost::geometry::detail::overlay::backtrack(size_t, bool&, Rings&, typename boost::range_value<T>::type&, Turns&, Operation&, const std::string&, const Geometry1&, const Geometry2&) [with Rings = std::deque<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator>, std::allocator<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> > >, Turns = std::deque<boost::geometry::detail::overlay::traversal_turn_info<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian> >, std::allocator<boost::geometry::detail::overlay::traversal_turn_info<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::
cartesian> > > >, Operation = boost::geometry::detail::overlay::traversal_turn_operation<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian> >, Geometry1 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, Geometry2 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>]'

/Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp:366:0 /Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp:366:   instantiated from 'void boost::geometry::traverse(const Geometry1&, const Geometry2&, boost::geometry::detail::overlay::operation_type, Turns&, Rings&) [with bool Reverse1 = false, bool Reverse2 = false, Geometry1 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, Geometry2 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, Turns = std::deque<boost::geometry::detail::overlay::traversal_turn_info<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian> >, std::allocator<boost::geometry::detail::overlay::traversal_turn_info<boost::geometry::model::
d2::point_xy<double, boost::geometry::cs::cartesian> > > >, Rings = std::deque<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator>, std::allocator<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> > >]'

/Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp:124:0 /Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp:124:   instantiated from 'static OutputIterator boost::geometry::detail::overlay::overlay<Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, OutputIterator, GeometryOut, Direction, Strategy>::apply(const Geometry1&, const Geometry2&, OutputIterator, const Strategy&) [with Geometry1 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, Geometry2 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, bool Reverse1 = false, bool Reverse2 = false, bool ReverseOut = true, OutputIterator = std::back_insert_iterator<boost::geometry::model::multi_polygon<boost::geometry::model::polygon<
boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, std::vector, std::allocator> >, GeometryOut = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, boost::geometry::overlay_type Direction = overlay_union, Strategy = boost::geometry::strategy_intersection<boost::geometry::cartesian_tag, boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, void>]'

/Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/union.hpp:158:0 /Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/union.hpp:158:   instantiated from 'OutputIterator boost::geometry::detail::union_::inserter(const Geometry1&, const Geometry2&, OutputIterator, const Strategy&) [with GeometryOut = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, bool Reverse1 = false, bool Reverse2 = false, bool ReverseOut = true, Geometry1 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, Geometry2 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, OutputIterator = std::back_insert_iterator<boost::geometry::model::mul
ti_polygon<boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, std::vector, std::allocator> >, Strategy = boost::geometry::strategy_intersection<boost::geometry::cartesian_tag, boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, void>]'

/Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/union.hpp:192:0 /Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/union.hpp:192:   instantiated from 'OutputIterator boost::geometry::union_inserter(const Geometry1&, const Geometry2&, OutputIterator, const Strategy&) [with GeometryOut = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, Geometry1 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, Geometry2 = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, OutputIterator = std::back_insert_iterator<boost::geometry::model::multi_polygon<boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<
double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, std::vector, std::allocator> >, Strategy = boost::geometry::strategy_intersection<boost::geometry::cartesian_tag, boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator>, boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, void>]'

/Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/union.hpp:269:0 /Users/jpswensen/src/boost-trunk/boost/geometry/algorithms/union.hpp:269:   instantiated from 'void boost::geometry::union_(const Geometry1&, const Geometry2&, Collection&) [with Geometry1 = -[ShapeNode mirrorShapeAboutLine:](ShapeNode*, objc_selector*, Line)::polygon_2d, Geometry2 = -[ShapeNode mirrorShapeAboutLine:](ShapeNode*, objc_selector*, Line)::polygon_2d, Collection = -[ShapeNode mirrorShapeAboutLine:](ShapeNode*, objc_selector*, Line)::polygon_set]'

/Users/jpswensen/Documents/iphoneprojects/TanTastic/Classes/ShapeNode.mm:351:0 /Users/jpswensen/Documents/iphoneprojects/TanTastic/Classes/ShapeNode.mm:351:   instantiated from here

/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/deque.tcc:763:0 /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/deque.tcc:763: error: type/value mismatch at argument 3 in template parameter list for 'template<class _Tp, class _Ref, class _Ptr> struct std::_Deque_iterator'

/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/deque.tcc:763:0 /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.1.sdk/usr/include/c++/4.2.1/bits/deque.tcc:763: confused by earlier errors, bailing out

Any suggestions on how to fix this the right way?  Should I create a ticket in the Boost bug tracker?

John Swensen