Boost C++ Libraries: Ticket #12751: difference algorithm returning invalid geometry https://svn.boost.org/trac10/ticket/12751 <p> My "tc::geo::polygon" type is actually a <strong>multi-polygon</strong>, using a polygon type that is based on <strong>int</strong>, oriented <strong>counter-clockwise</strong> and <strong>open</strong> (not closed). Please consider the following example: </p> <pre class="wiki">tc::geo::polygon&lt;int&gt; polygonA; boost::geometry::read_wkt("MULTIPOLYGON(((1920 1462,3720 1462,3720 3262,1920 3262,1920 1462)))", polygonA); boost::geometry::is_valid(polygonA); // returns true tc::geo::polygon&lt;int&gt; polygonB; boost::geometry::read_wkt("MULTIPOLYGON(((1918 1957,1918 1657,2218 2189,1918 1957)),((3718 1957,3360 2233,3718 1561,3718 1957)),((3360 2233,2818 3253,2218 2189,2818 2653,3360 2233)))", polygonB); boost::geometry::is_valid(polygonB); // returns true tc::geo::polygon&lt;int&gt; polygonC; boost::geometry::difference(polygonA, polygonB, polygonC); // polygonC: MULTIPOLYGON(((1920 1660,1920 1462,3720 1462,3720 3262,1920 3262,1920 1959,2218 2189,1920 1660),(3718 1561,3360 2233,3718 1957,3718 1561),(2818 2653,2218 2189,2818 3253,3360 2233,2818 2653))) boost::geometry::is_valid(polygonC); // returns true tc::geo::polygon&lt;int&gt; polygonD; boost::geometry::read_wkt("MULTIPOLYGON(((1918 2155,1918 1957,2818 2653,3718 1957,3718 2154,2818 3055,1918 2155)))", polygonD); boost::geometry::is_valid(polygonD); // returns true tc::geo::polygon&lt;int&gt; polygonE; boost::geometry::difference(polygonC, polygonD, polygonE); // polygonE: MULTIPOLYGON(((2218 2189,1920 1660,1920 1462,3720 1462,3720 3262,1920 3262,1920 2157,2562 2799,2818 3253,3043 2829,3718 2154,3718 1957,3360 2234,3360 2233,2818 2653,2218 2189),(3718 1957,3718 1561,3360 2233,3718 1957))) boost::geometry::is_valid(polygonD); // returns false! </pre><p> The difference of two valid multi-polygons yields an invalid multi-polygon. </p> <p> May be related to tickets <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/10661" title="#10661: Bugs: difference algorithm returning invalid geometry (closed: duplicate)">#10661</a>, <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/11674" title="#11674: Bugs: difference algorithm returning invalid geometry (closed: duplicate)">#11674</a>, <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/11676" title="#11676: Bugs: difference algorithm returning invalid geometry (closed: fixed)">#11676</a>. </p> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/12751 Trac 1.4.3 Barend Gehrels Sun, 26 Mar 2017 11:56:18 GMT status changed https://svn.boost.org/trac10/ticket/12751#comment:1 https://svn.boost.org/trac10/ticket/12751#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> <p> Unfortunately not yet fixed </p> Ticket Volker Schöch <vschoech@…> Thu, 04 Jan 2018 15:12:05 GMT version changed https://svn.boost.org/trac10/ticket/12751#comment:2 https://svn.boost.org/trac10/ticket/12751#comment:2 <ul> <li><strong>version</strong> <span class="trac-field-old">Boost 1.63.0</span> → <span class="trac-field-new">Boost 1.66.0</span> </li> </ul> <p> Still present in boost 1.66.0. </p> Ticket Volker Schöch <vschoech@…> Mon, 25 Jun 2018 07:32:38 GMT <link>https://svn.boost.org/trac10/ticket/12751#comment:3 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/12751#comment:3</guid> <description> <p> No longer reproducible in 1.67.0. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Mon, 25 Jun 2018 18:32:11 GMT</pubDate> <title>status, milestone changed; resolution set https://svn.boost.org/trac10/ticket/12751#comment:4 https://svn.boost.org/trac10/ticket/12751#comment:4 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> <li><strong>milestone</strong> <span class="trac-field-old">To Be Determined</span> → <span class="trac-field-new">Boost 1.67.0</span> </li> </ul> <p> Thanks for verifying! </p> Ticket