Boost C++ Libraries: Ticket #10835: difference of multilinestring and polygon yields wrong result https://svn.boost.org/trac10/ticket/10835 <p> I am using the following typedefs to simplify reading: </p> <pre class="wiki">typedef boost::geometry::model::point&lt;int,2,boost::geometry::cs::cartesian&gt; TPoint; typedef boost::geometry::model::linestring&lt;TPoint&gt; TLinestring; typedef boost::geometry::model::multi_linestring&lt;TLinestring&gt; TMultiLinestring; typedef boost::geometry::model::polygon&lt;TPoint, /*ClockWise*/false, /*Closed*/false&gt; TPolygon; </pre><p> I have a multilinestring from which I want to subtract two polygons. The multilinestring and polygons are as follows </p> <pre class="wiki">TMultiLinestring multilinestring; boost::geometry::read_wkt("MULTILINESTRING((5239 2113,1020 2986))", multilinestring); TPolygon polygon1; boost::geometry::read_wkt("POLYGON((5233 2113,5200 2205,1020 2205,1020 2022,5200 2022))", polygon1); TPolygon polygon2; boost::geometry::read_wkt("POLYGON((5233 2986,5200 3078,1020 3078,1020 2895,5200 2895))", polygon2); </pre><p> First, I subtract polygon1 from multilinestring, which works fine: </p> <pre class="wiki">TMultiLinestring multilinestringOut1; boost::geometry::difference(multilinestring, polygon1, multilinestringOut1); // works as expected: multilinestringOut1 holds MULTILINESTRING((5239 2113,5233 2114)(4795 2205, 1020 2986)) </pre><p> Now I want to subtract polygon2 from multilinestringOut1 (the intermediate result from the previous calculation), which yields a wrong result. </p> <pre class="wiki">TMultiLinestring multilinestringOut2; boost::geometry::difference(multilinestringOut1, polygon2, multilinestringOut2); // not as expected: multilinestringOut2 holds MULTILINESTRING((5239 2113,5233,2114)(4795 2205, 5406 1580)) </pre><p> I would expect multilinestringOut2 to hold </p> <pre class="wiki">MULTILINESTRING((5239 2113,5233,2114)(4795 2205, 1460 2895)) </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/10835 Trac 1.4.3 anonymous Tue, 02 Dec 2014 13:59:54 GMT severity changed https://svn.boost.org/trac10/ticket/10835#comment:1 https://svn.boost.org/trac10/ticket/10835#comment:1 <ul> <li><strong>severity</strong> <span class="trac-field-old">Problem</span> → <span class="trac-field-new">Regression</span> </li> </ul> <p> I re-checked this behaviour against an older version of boost and realized that the problem does not occur there. </p> Ticket Philipp Müller <pmueller@…> Tue, 02 Dec 2014 15:06:44 GMT <link>https://svn.boost.org/trac10/ticket/10835#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10835#comment:2</guid> <description> <p> It may help to look at line 187ff in cart_intersect.hpp. There, cramers_rule "returned" values that seem incorrect to me. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>anonymous</dc:creator> <pubDate>Fri, 06 Feb 2015 17:49:46 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/10835#comment:3 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10835#comment:3</guid> <description> <p> I just checked out the latest trunk, where it seems to work as expected (multilinestringOut2 holds <code>MULTILINESTRING((5239 2113,5232 2114),(4794 2205,1459 2895))</code> which differs from expectation probably only because of rounding errors). </p> </description> <category>Ticket</category> </item> <item> <dc:creator>mkaravel</dc:creator> <pubDate>Sat, 28 Mar 2015 18:55:43 GMT</pubDate> <title>status, milestone changed; cc, resolution set https://svn.boost.org/trac10/ticket/10835#comment:4 https://svn.boost.org/trac10/ticket/10835#comment:4 <ul> <li><strong>cc</strong> <span class="trac-author">mkaravel</span> added </li> <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> <li><strong>milestone</strong> <span class="trac-field-old">To Be Determined</span> → <span class="trac-field-new">Boost 1.58.0</span> </li> </ul> <p> The problem was in the computation of the intersection points. In particular, integer overflow was taking place, yielding the wrong results. </p> <p> The problem has been fixed by locally promoting the coordinates to a number type with increased precision, thus avoiding the overflow. </p> Ticket mkaravel Sat, 28 Mar 2015 18:57:31 GMT <link>https://svn.boost.org/trac10/ticket/10835#comment:5 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10835#comment:5</guid> <description> <p> See also tickets <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/10658" title="#10658: Bugs: sym_difference yields bad result for int polygons (closed: fixed)">#10658</a> and <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/11121" title="#11121: Bugs: Invalid result of difference() for integral coordinates. (closed: fixed)">#11121</a>. </p> </description> <category>Ticket</category> </item> </channel> </rss>