Boost C++ Libraries: Ticket #10107: boost::geometry::intersection fails for triangle-triangle intersection. https://svn.boost.org/trac10/ticket/10107 <p> The intersection between two triangles fails. The two triangles have a considerable intersection but boost::geometry::intersects returns no intersection at all (see attached svg to get an understanding of the problem). The points of the triangles have been taken from a concrete application where the error was initially detected. </p> <p> Also note that if we round the nodes of the triangle a bit (by uncommenting the piece of code in the middle) intersection() will return a result, but it is unfortunately wrong. (see attached svg file) </p> <pre class="wiki">#include&lt;cmath&gt; #include&lt;fstream&gt; #include&lt;boost/geometry.hpp&gt; #include&lt;boost/geometry/geometries/ring.hpp&gt; #include&lt;boost/geometry/io/svg/svg_mapper.hpp&gt; #include&lt;boost/geometry/geometries/point_xy.hpp&gt; namespace bg = boost::geometry; int main() { typedef bg::model::d2::point_xy&lt;double&gt; point_t; typedef bg::model::ring&lt;point_t, false, true&gt; ring_t; ring_t ring0; bg::append(ring0, point_t(0,0)); bg::append(ring0, point_t(0.34729635524768009969, -8.0779356694631608874e-28)); bg::append(ring0, point_t(2.7755575615628913511e-17, 0.27215593674075533315)); bg::append(ring0, point_t(0,0)); ring_t ring1; bg::append(ring1, point_t(0.098648844641721203375, 0.11754520657592185118)); bg::append(ring1, point_t(0.20919064161456801809, 0.21645083936158207583)); bg::append(ring1, point_t(0.34729635524768026622, -2.8837044695958157593e-16)); bg::append(ring1, point_t(0.098648844641721203375, 0.11754520657592185118)); /* static const double roundFactor = std::pow(2., -30); for(int i=0; i&lt;4; ++i) { ring0[i].x(std::round(ring0[i].x()/roundFactor)*roundFactor); ring0[i].y(std::round(ring0[i].y()/roundFactor)*roundFactor); ring1[i].x(std::round(ring1[i].x()/roundFactor)*roundFactor); ring1[i].y(std::round(ring1[i].y()/roundFactor)*roundFactor); }*/ std::vector&lt;ring_t&gt; result; bg::intersection(ring0, ring1, result); std::cout &lt;&lt; result.size() &lt;&lt; std::endl; // Output in SVG: std::ofstream stream("debug.svg"); bg::svg_mapper&lt;point_t&gt; mapper(stream, 400,400); mapper.add(ring0); mapper.add(ring1); mapper.map(ring0, "fill-opacity:0.5;fill:rgb(153,204,0)"); mapper.map(ring1, "fill-opacity:0.3;fill:rgb(51,51,153)"); if(result.size()==1) { mapper.map(result[0], "fill:none;stroke:rgb(0,0,0);stroke-width:1"); } } </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/10107 Trac 1.4.3 Raffael Casagrande <raffael@…> Mon, 09 Jun 2014 11:49:03 GMT <link>https://svn.boost.org/trac10/ticket/10107#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10107#comment:1</guid> <description> <p> Unfortunately the boost bug tracking system doesn't allow me to upload .svg images, but if you execute the code youreself you will get them... </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Mon, 09 Jun 2014 12:54:31 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/10107#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10107#comment:2</guid> <description> <p> It is most probably fixed by 1.56 (which is not yet released). I will have a look soon if this is indeed the case. </p> </description> <category>Ticket</category> </item> <item> <author>Raffael Casagrande <raffael@…></author> <pubDate>Mon, 09 Jun 2014 18:39:04 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/10107#comment:3 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10107#comment:3</guid> <description> <p> I've just checked out the trunk version and indeed it seems to be fixed in 1.56. I also noticed that ring1 in the example above had a wrong orientation which explains why integer rounding produced the rong result. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Tue, 10 Jun 2014 16:53:39 GMT</pubDate> <title>status, milestone changed; resolution set https://svn.boost.org/trac10/ticket/10107#comment:4 https://svn.boost.org/trac10/ticket/10107#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">fixed</span> </li> <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> <p> Thanks for testing this. OK - I will close the ticket then as "fixed" </p> Ticket