Boost C++ Libraries: Ticket #7844: bug with unrolling self intersecting polygon https://svn.boost.org/trac10/ticket/7844 <blockquote> <p> I m tring to remove loops from self intersecting polygon but the following example (a triangle A, B, C with some points nearly aligned between B and C) fails. IMHO it sould return a triangle. </p> </blockquote> <pre class="wiki">#include &lt;boost/polygon/polygon.hpp&gt; #include &lt;vector&gt; #include &lt;iostream&gt; using namespace boost::polygon; using namespace std; typedef point_data&lt; int &gt; point; typedef vector&lt; point &gt; points; typedef polygon_set_data&lt; int &gt; polygon_set; typedef polygon_with_holes_data&lt; int &gt; polygon_with_holes; typedef vector&lt; polygon_with_holes &gt; polygons_with_holes; /* * A triangle A, B, C with some nearly aligned points between B and C. * * A * + * |\ * | \ * | \ * | \ * | \ * | \ * | \ * | \ * | /-+ C * B +--- */ polygon_with_holes MakeRawPolygon() { points ps; ps.push_back(point(-181928106,288346744)); // A ps.push_back(point(-15311797,-289428209)); // B ps.push_back(point(56093690,-270295166)); ps.push_back(point(24502047,-278760121)); ps.push_back(point(57745146,-269852659)); ps.push_back(point(56791908,-270108078)); ps.push_back(point(-14613579,-289241121)); ps.push_back(point(82923673,-263106094)); // C polygon_with_holes poly; set_points(poly, ps.begin(), ps.end()); return poly; } int main() { polygon_with_holes polygon(MakeRawPolygon()); polygon_set ps; ps.insert(polygon); // first unrool polygons_with_holes unrolled_polygons; ps.get(unrolled_polygons); if (unrolled_polygons.size() == 0u) { std::cout &lt;&lt; "error" &lt;&lt; endl; } } </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/7844 Trac 1.4.3 Andrii Sydorchuk Wed, 06 Mar 2013 22:58:31 GMT owner changed https://svn.boost.org/trac10/ticket/7844#comment:1 https://svn.boost.org/trac10/ticket/7844#comment:1 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Lucanus Simonson</span> to <span class="trac-author">Andrii Sydorchuk</span> </li> </ul> Ticket Andrii Sydorchuk Sun, 16 Jun 2013 01:43:57 GMT <link>https://svn.boost.org/trac10/ticket/7844#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/7844#comment:2</guid> <description> <p> Hi, </p> <p> Sorry for the late response. I was not able to reproduce your failure. Could you specify which compiler are you using and if the issue is still feasible? </p> <p> Thanks, Andrii </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Andrii Sydorchuk</dc:creator> <pubDate>Sun, 16 Jun 2013 01:56:21 GMT</pubDate> <title>status changed https://svn.boost.org/trac10/ticket/7844#comment:3 https://svn.boost.org/trac10/ticket/7844#comment:3 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> Ticket anonymous Mon, 17 Jun 2013 07:27:28 GMT <link>https://svn.boost.org/trac10/ticket/7844#comment:4 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/7844#comment:4</guid> <description> <p> I am using visual studio 10 and i still have the bug in 1.53 version. I have just try with gcc-mingw-4.2 and it is ok. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Andrii Sydorchuk</dc:creator> <pubDate>Tue, 18 Jun 2013 20:40:43 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/7844#comment:5 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/7844#comment:5</guid> <description> <p> I was able to reproduce the error on msvc-2008. Will investigate. My initial assumption is that the bug is related to the specifics of the floating-point operations implementation. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Andrii Sydorchuk</dc:creator> <pubDate>Tue, 16 Jul 2013 22:23:04 GMT</pubDate> <title>status changed; resolution set https://svn.boost.org/trac10/ticket/7844#comment:6 https://svn.boost.org/trac10/ticket/7844#comment:6 <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">wontfix</span> </li> </ul> <p> I spent a while debugging this issue. In the end it appears that the defect is caused by the integer grid snapping strategy used by the Polygon library. Due to this strategy inputs, that contain almost parallel lines within a distance of 1x1 square, may cause defects. In order to fix this the whole implementation of the intersection handling needs to be rewritten. In terms of the current implementation I am marking this as working as intended. </p> Ticket