Boost C++ Libraries: Ticket #8310: Wrong results with overlapping polygons https://svn.boost.org/trac10/ticket/8310 <p> Many algorithms from <code>boost::geometry</code> (<code>difference</code>, <code>intersection</code>, <code>union_</code>, <code>disjoint</code>, <code>sym_difference</code>, <code>intersects</code>, possibly more) give wrong results with some pairs of polygons. </p> <p> I could find many pairs of polygons (could only find pairs of polygons sharing part of an edge since I'm working with this kind of polygons) that are wrongly treated as if they weren't intersecting by all the aforementioned algorithms. </p> <p> Here some examples: </p> <pre class="wiki">POLYGON(( -2.559375047683716 -0.615625500679016, -2.559375047683716 0.384374797344208, 7.940625190734863 0.384374588727951, 7.940625190734863 -0.615625441074371 )) POLYGON(( 1.000000000000000 0.384374707937241, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000, 0.000000000000000 0.384374737739563 )) </pre><pre class="wiki">POLYGON(( 0.000000000000000 0.373437941074371, 1.000000000000000 0.373437792062759, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000 )) POLYGON(( -2.592187881469727 -0.626561701297760, -2.592187643051147 0.373438000679016, 7.907812595367432 0.373437851667404, 7.907812595367432 -0.626561224460602 )) </pre><pre class="wiki">POLYGON(( 1.000000000000000 2.531045913696289, 1.000000000000000 3.000000000000000, 2.000000000000000 3.000000000000000, 2.000000000000000 2.531045913696289 )) POLYGON(( 5.204249382019043 3.531043529510498, 5.204247951507568 2.531045675277710, -5.295750617980957 2.531046152114868, -5.295751094818115 3.531045913696289 )) </pre><p> I'm working on Linux x86-64 (<a class="missing wiki">ArchLinux</a>), and could reproduce this bug both with G++ 4.7.2 and clang 3.2. </p> <p> I'm using the following types to store points and polygons: </p> <pre class="wiki">typedef boost::geometry::model::d2::point_xy&lt;float&gt; point; typedef boost::geometry::model::polygon&lt;point, true, false&gt; polygon; </pre><p> The attached source file (C++11) can be used to reproduce this bug. </p> <p> I believe this bug could be related to <a class="ext-link" href="https://svn.boost.org/trac/boost/ticket/8183"><span class="icon">​</span>https://svn.boost.org/trac/boost/ticket/8183</a> . </p> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/8310 Trac 1.4.3 Paolo Giangrandi <paolo@…> Tue, 19 Mar 2013 15:07:01 GMT attachment set https://svn.boost.org/trac10/ticket/8310 https://svn.boost.org/trac10/ticket/8310 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">geom.cpp</span> </li> </ul> <p> A C++11 source file that reproduces this bug. It can be compiled with `g++ --std=c++11 -o geom geom.cp' </p> Ticket Barend Gehrels Sun, 24 Mar 2013 22:25:28 GMT <link>https://svn.boost.org/trac10/ticket/8310#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/8310#comment:1</guid> <description> <p> Thanks for the report. I can reproduce it and I'm currently busy with a fix. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Wed, 06 Nov 2013 22:42:03 GMT</pubDate> <title>status changed; resolution set https://svn.boost.org/trac10/ticket/8310#comment:2 https://svn.boost.org/trac10/ticket/8310#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/86579" title="[geometry] fixed ticket 8310, disjoint did give the wrong results. ...">[86579]</a>) [geometry] fixed ticket 8310, disjoint did give the wrong results. Fixed using point_on_surface. Added unit test. Also tests for overlay algorithms because they might suffer from the same problem </p> Ticket Barend Gehrels Wed, 06 Nov 2013 22:44:13 GMT milestone changed https://svn.boost.org/trac10/ticket/8310#comment:3 https://svn.boost.org/trac10/ticket/8310#comment:3 <ul> <li><strong>milestone</strong> <span class="trac-field-old">To Be Determined</span> → <span class="trac-field-new">Boost 1.56.0</span> </li> </ul> Ticket