[Boost-bugs] [Boost C++ Libraries] #13215: Polygon union give a different result depending of the order

Subject: [Boost-bugs] [Boost C++ Libraries] #13215: Polygon union give a different result depending of the order
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-09-18 16:02:20

#13215: Polygon union give a different result depending of the order
-------------------------------+----------------------------
 Reporter:  flamaros.xavier@…  |      Owner:  Barend Gehrels
     Type:  Bugs               |     Status:  new
Milestone:  To Be Determined   |  Component:  geometry
  Version:  Boost 1.66.0       |   Severity:  Showstopper
 Keywords:                     |
-------------------------------+----------------------------
 I found a precision issue with union between polygons and the result vary
 depending of the order.

 We add consecutive polygons to a multi-polygon that contains the previous
 result.
 The union of polygons (that have only one outer contour) in the following
 order give an empty union:
 {{{
 Polygon[(-5.180416107177734375,0.46142292022705078125),(-2.6576340198516845703125,0.46142292022705078125),(-2.6576340198516845703125,4.818223476409912109375),(-2.6576340198516845703125,7.19262790679931640625),(-7.35814762115478515625,7.19262790679931640625),(-7.35814762115478515625,4.818223476409912109375),(-7.35814762115478515625,0.46142292022705078125)]
 Polygon[(-7.35814762115478515625,-1.8333890438079833984375),(-7.35814762115478515625,-5.162303924560546875),(-3.343097686767578125,-5.162303924560546875),(-3.3430979251861572265625,-1.19531953334808349609375),(-3.343098163604736328125,0.4614227116107940673828125),(-2.6576340198516845703125,0.4614226818084716796875),(-2.6576340198516845703125,4.79442691802978515625),(-5.180416107177734375,4.79442691802978515625),(-7.35814762115478515625,4.79442691802978515625),(-7.35814762115478515625,0.46142292022705078125)]
 Polygon[(4.4465618133544921875,-5.162303924560546875),(4.4465618133544921875,-1.195319652557373046875),(3.5822856426239013671875,-1.195319652557373046875),(-3.3430979251861572265625,-1.19531953334808349609375),(-3.343097686767578125,-5.162303924560546875)]
 Polygon[(3.5822856426239013671875,-1.195319652557373046875),(3.5822856426239013671875,0.4614227116107940673828125),(-2.6576340198516845703125,0.4614226818084716796875),(-3.343098163604736328125,0.4614227116107940673828125),(-3.3430979251861572265625,-1.19531953334808349609375)]
 Polygon[(-0.0815036296844482421875,-5.162303924560546875),(-0.0815036296844482421875,-4.110321521759033203125),(-2.6576340198516845703125,-4.110321521759033203125),(-2.6576340198516845703125,-5.162303924560546875)]
 Polygon[(-0.0815036296844482421875,0.46142292022705078125),(-2.6576340198516845703125,0.46142292022705078125),(-2.6576340198516845703125,-0.438062191009521484375),(-0.0815036296844482421875,-0.438062191009521484375)]
 Polygon[(-2.6576340198516845703125,0.46142292022705078125),(-2.6576340198516845703125,-0.438062191009521484375),(-2.6576340198516845703125,-4.110321521759033203125),(-2.6576340198516845703125,-5.162303924560546875),(-0.0815036296844482421875,-5.162303924560546875),(-0.0815036296844482421875,-4.110321521759033203125),(-0.0815036296844482421875,-0.438062191009521484375),(-0.0815036296844482421875,0.46142292022705078125)]
 }}}

 Same polygons in a different order give the expected result:
 {{{
 Polygon[(4.4465618133544921875,-5.162303924560546875),(4.4465618133544921875,-1.195319652557373046875),(3.5822856426239013671875,-1.195319652557373046875),(-3.3430979251861572265625,-1.19531953334808349609375),(-3.343097686767578125,-5.162303924560546875)]
 Polygon[(-2.6576340198516845703125,0.46142292022705078125),(-2.6576340198516845703125,-0.438062191009521484375),(-2.6576340198516845703125,-4.110321521759033203125),(-2.6576340198516845703125,-5.162303924560546875),(-0.0815036296844482421875,-5.162303924560546875),(-0.0815036296844482421875,-4.110321521759033203125),(-0.0815036296844482421875,-0.438062191009521484375),(-0.0815036296844482421875,0.46142292022705078125)]
 Polygon[(-0.0815036296844482421875,-5.162303924560546875),(-0.0815036296844482421875,-4.110321521759033203125),(-2.6576340198516845703125,-4.110321521759033203125),(-2.6576340198516845703125,-5.162303924560546875)]
 Polygon[(3.5822856426239013671875,-1.195319652557373046875),(3.5822856426239013671875,0.4614227116107940673828125),(-2.6576340198516845703125,0.4614226818084716796875),(-3.343098163604736328125,0.4614227116107940673828125),(-3.3430979251861572265625,-1.19531953334808349609375)]
 Polygon[(-0.0815036296844482421875,0.46142292022705078125),(-2.6576340198516845703125,0.46142292022705078125),(-2.6576340198516845703125,-0.438062191009521484375),(-0.0815036296844482421875,-0.438062191009521484375)]
 Polygon[(-7.35814762115478515625,-1.8333890438079833984375),(-7.35814762115478515625,-5.162303924560546875),(-3.343097686767578125,-5.162303924560546875),(-3.3430979251861572265625,-1.19531953334808349609375),(-3.343098163604736328125,0.4614227116107940673828125),(-2.6576340198516845703125,0.4614226818084716796875),(-2.6576340198516845703125,4.79442691802978515625),(-5.180416107177734375,4.79442691802978515625),(-7.35814762115478515625,4.79442691802978515625),(-7.35814762115478515625,0.46142292022705078125)]
 Polygon[(-5.180416107177734375,0.46142292022705078125),(-2.6576340198516845703125,0.46142292022705078125),(-2.6576340198516845703125,4.818223476409912109375),(-2.6576340198516845703125,7.19262790679931640625),(-7.35814762115478515625,7.19262790679931640625),(-7.35814762115478515625,4.818223476409912109375),(-7.35814762115478515625,0.46142292022705078125)]
 }}}

 The result:
 {{{
 Polygon[(-0.0815036296844482421875,-5.162303924560546875),(-0.0815036296844482421875,-4.110321521759033203125),(-2.6576340198516845703125,-4.110321521759033203125),(-2.6576340198516845703125,-5.162303924560546875)]
 }}}

 Notes:
 1. We use float
 2. This issue happens with mingw32, when tested with Visual 2015 (32bits
 compilation too) everything is good. Both compiler are used with default
 options for float precision strategy.
 3. Prints are made with "%.64g" format option of printf to avoid financial
 round.
 4. Those polygons are counter clockwise and open, but I also test them
 reversed and close, it gives the same result.

-- 
Ticket URL: <https://svn.boost.org/trac10/boost/ticket/13215>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.