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

Subject: [geometry] Problems performing boolean operations on polygons with shared edges
From: Oleg Evseev (ev.mipt_at_[hidden])
Date: 2016-04-10 05:13:16

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?

Thank you very much in advance for help.
Kind regards,
Oleg Evseev