Geometry Boost List: Re: [geometry] Problems performing boolean operations on polygons with shared edges

Subject: Re: [geometry] Problems performing boolean operations on polygons with shared edges
From: Barend Gehrels (barend_at_[hidden])
Date: 2016-04-10 12:34:23

Hi Oleg,

Op 10-4-2016 om 11:13 schreef Oleg Evseev:
> Hello,
>
> I'm trying to use boost geometry to build vehicle ongoing path of 
> constant width with self intersections calculations.
> Faced problems with result of boolean operations on polygons 
> (multipolygons).
>
> Here my path polygon on some step (more precisely multipolygon in 
> boost geometry):
> https://pp.vk.me/c631319/v631319687/1effe/gQOBvWUNJRM.jpg
>
> On every step I use two points x,y (floats) - left and right offseted 
> by half of constant width from current vehicle location. Let's call 
> x-y line a segment.
>
> When location of vehicle is updated, I construct appended mpolygon 
> using old x,y point and new ones and firstly intersect it with path 
> mpolygon, and then union_ them (so path mpolygon gets longer).
>
> Sometimes (especially for large enough width values) there can be 
> intersection of new segment with previous. In that cases I construct 
> appended mpolygon as two polygons using calculated intersection point 
> with bg::intersection of two segments.
> See the picture: https://pp.vk.me/c631319/v631319687/1f03a/elt4y5KSfSM.jpg
>
> And when I union_ it with path mpolygon there is first sign of a problem:
> https://pp.vk.me/c631319/v631319687/1f012/2e1MycdOkB8.jpg
> result is a two polygons within mpolygon, not the one as I expected. 
> It appears not always, but quite often.
>
> Next step, and again intersection of new segment with previous, and 
> again two polygons in appended mpolygon
> https://pp.vk.me/c631319/v631319687/1f026/FzIQKqXtFH4.jpg
>
> Union result:
> https://pp.vk.me/c631319/v631319687/1efea/oitwcdfUPbA.jpg
>
> And one last step
> https://pp.vk.me/c631319/v631319687/1f030/V-5FwqnfdEU.jpg
>
> This almost zero areas can be part of outer ring of one polygon, or 
> can be a separate polygon in mpolygon within another biggest one 
> (which brakes mpolygon model's rule).
>
> I suppose this is in the end cause this overlay invalid input 
> exceptions when performing intersection or union_ with such mpolygon.
>
> Thinking that problem is in the floating point inaccuracy (that maybe 
> calculates slightly different intersection point of polygons with 
> shared edge when performing union_ ), I even trying to solve this by 
> inserting intersection point of segments in outer ring of current path 
> polygon before doing union_. It slightly reduces overlay invalid input 
> exceptions when perform intersection or union_, but not solve problem 
> completely.
>
> If there any solutions of such problems?

First, the upcoming 1.61 release will have changes in overlay. Please 
check there if the problem still appears.

Second, the JPG's are illustrative, but hard to reproduce the problem. 
Could you file a ticket with the WKT representations of two polygons 
where the union fails? Tickets can be created here:
https://svn.boost.org/trac/boost/newticket

WKT can easily be generated with the library using std::cout << 
boost::geometry::wkt(input1), etc

Thanks, Barend