Geometry Boost List: [ggl] Understanding get_turns for linestring/polygon overlay

Subject: [ggl] Understanding get_turns for linestring/polygon overlay
From: Barend Gehrels (barend.gehrels)
Date: 2011-02-01 11:58:00

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