Boost C++ Libraries: Ticket #10661: difference algorithm returning invalid geometry https://svn.boost.org/trac10/ticket/10661 <p> My "_TPolygon" 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">_TPolygon&lt;int&gt; polygonA; boost::geometry::read_wkt("MULTIPOLYGON(((1701 985,3501 985,3501 2785,1701 2785,1701 985)))", polygonA); // does not throw boost::geometry::is_valid(polygonA); // returns true _TPolygon&lt;int&gt; polygonB; boost::geometry::read_wkt("MULTIPOLYGON(((1698 1860,1698 1122,2598 1392,3492 1842,3492 32706,2598 2340,1698 1860)))", polygonB); // does not throw boost::geometry::is_valid(polygonB); // returns true _TPolygon&lt;int&gt; polygonC; boost::geometry::difference(polygonA, polygonB, polygonC); // does not throw // polygonC: MULTIPOLYGON(((1701 1122,1701 985,3501 985,3501 2785,3492 1857,3492 1842,2598 1392,1701 1122)),((1701 1861,2598 2340,1669 2785,1701 2785,1701 1861))) boost::geometry::is_valid(polygonC); // returns false! _TPolygon&lt;int&gt; polygonD; boost::geometry::read_wkt("MULTIPOLYGON(((1698 2772,1698 1860,2598 2340,3492 2412,3492 32743,1698 2772)))", polygonD); // does not throw boost::geometry::is_valid(polygonD); // returns true _TPolygon&lt;int&gt; polygonE; boost::geometry::difference(polygonC, polygonD, polygonE); // throws "Boost.Geometry Overlay invalid input exception"! </pre><p> This <strong>worked in boost 1.55.0</strong>. The result for polygonC was slightly different in 1.55.0, and there was a reasonable(?) result for polygonE: </p> <pre class="wiki">polygonC: MULTIPOLYGON(((1701 1122,1701 985,3501 985,3501 2785,3492 2785,3492 1842,2598 1392,1701 1122)),((1701 1861,2598 2340,2611 2785,1701 2785,1701 1861))) polygonE: MULTIPOLYGON(((3492 2412,3492 1842,2598 1392,1701 1122,1701 985,3501 985,3501 2785,3492 2785,3492 2412),(1701 1861,2598 2340,1701 1861))) </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/10661 Trac 1.4.3 Volker Schöch <vschoech@…> Wed, 15 Oct 2014 16:28:27 GMT <link>https://svn.boost.org/trac10/ticket/10661#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10661#comment:1</guid> <description> <p> This may be related to <br /> </p> <ul><li>Ticket <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/9768" title="#9768: Bugs: difference of multi-polygon and box returns multi-polygon with ... (closed: duplicate)">#9768</a> (difference of multi-polygon and box returns multi-polygon with redundant points) <br /> </li><li>Ticket <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/9942" title="#9942: Bugs: Result of difference of multi-polygons contains spike (closed: fixed)">#9942</a> (Result of difference of multi-polygons contains spike) </li></ul> </description> <category>Ticket</category> </item> <item> <author>Volker Schöch <vschoech@…></author> <pubDate>Wed, 19 Nov 2014 12:38:07 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/10661#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10661#comment:2</guid> <description> <p> May be related to <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/10803" title="#10803: Bugs: union algorithm returning invalid geometry (closed: fixed)">#10803</a> (union algorithm returning invalid geometry). </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Sun, 01 Nov 2015 16:35:07 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/10661#comment:3 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10661#comment:3</guid> <description> <ul><li>Added test case in unit tests </li><li>For 1.60 this is still a problem </li><li>However, the first stage (the generated polygon C) is now valid </li><li>And (therefore) E=C-D does not generate an exception anymore, but that result is still invalid </li></ul> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Wed, 26 Jun 2019 10:14:28 GMT</pubDate> <title>status changed; resolution set https://svn.boost.org/trac10/ticket/10661#comment:4 https://svn.boost.org/trac10/ticket/10661#comment:4 <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">duplicate</span> </li> </ul> <p> Transfered to <a class="ext-link" href="https://github.com/boostorg/geometry/issues/602"><span class="icon">​</span>https://github.com/boostorg/geometry/issues/602</a> </p> Ticket