Boost C++ Libraries: Ticket #10108: boost::geometry::intersection fails for triangle-triangle intersection https://svn.boost.org/trac10/ticket/10108 <p> A small test case which involves two triangles that intersect each other in a very tiny patch. boost::geometry::intersection returns one of the triangles instead of the correct (tiny) intersection triangle. </p> <p> Note that boost 1.55 returned an empty intersection in this case which seems more appropriate (although there is in a fact a small, tiny intersection triangle) </p> <p> I've attached a picture that depicts the situation to this report. </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.85012528418186883439,0.66468648958045217778)); bg::append(ring0, point_t(-1.0190633474909247536, 0.58375169123203618504)); bg::append(ring0, point_t(-0.81735787096893253167, 0.85208889314502478385)); bg::append(ring0, ring0[0]); ring_t ring1; bg::append(ring1, point_t(-1.0898104946524889147, 1.0651111163194444398)); bg::append(ring1, point_t(-1.0543813205484939832, 0.82438792455048248708)); bg::append(ring1, point_t(-0.81735787088719669136, 0.8520888930811181261)); bg::append(ring1, ring1[0]); bg::correct(ring0); bg::correct(ring1); 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/10108 Trac 1.4.3 Raffael Casagrande <raffael@…> Tue, 10 Jun 2014 09:24:58 GMT attachment set https://svn.boost.org/trac10/ticket/10108 https://svn.boost.org/trac10/ticket/10108 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">debug.jpg</span> </li> </ul> Ticket anonymous Tue, 01 Jul 2014 17:17:28 GMT <link>https://svn.boost.org/trac10/ticket/10108#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10108#comment:1</guid> <description> <p> I run your code against Boost 1.56.0 and it works just fine (returns 0 intersection). </p> </description> <category>Ticket</category> </item> <item> <author>dgb@…</author> <pubDate>Wed, 22 Oct 2014 11:36:00 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/10108#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10108#comment:2</guid> <description> <p> Hi, </p> <p> I have a strikingly similar problem that persists from Boos 1.47 through 1.56: When intersecting two adjacent polygons (fourangles in my case) that share part of an edge, in some cases one of the inputs is erroneously returned as the output. </p> <p> Trying to attach the image 'IntersectionReturnsFourangleBInsteadOfIntersection.png' to visualize the situation. </p> <pre class="wiki">typedef boost::geometry::model::polygon&lt;boost::geometry::model::d2::point_xy&lt;double&gt; &gt; polygon; polygon red, green; boost::geometry::read_wkt("POLYGON((818.61020100991334 686.40744987236633, 818.94520828641623 714.37814489343316, 857.67308553468195 713.83138513092547, 857.33807828316174 685.94987141847253, 818.61020100991334 686.40744987236633))", red); boost::geometry::read_wkt("POLYGON((857.33807828316174 685.94987141847253, 857.64395373587263 711.40684463430682, 910.49336536223325 710.67130033421233, 910.18750000000000 685.32544378698219, 857.33807828316174 685.94987141847253))", green); --&gt; intersect returns 'green' polygon </pre> </description> <category>Ticket</category> </item> <item> <author>dgb@…</author> <pubDate>Wed, 22 Oct 2014 11:36:54 GMT</pubDate> <title>attachment set https://svn.boost.org/trac10/ticket/10108 https://svn.boost.org/trac10/ticket/10108 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">IntersectionReturnsFourangleBInsteadOfIntersection.png</span> </li> </ul> <p> additional example image with barely adjacent polygons </p> Ticket dgb@… Wed, 22 Oct 2014 11:41:59 GMT <link>https://svn.boost.org/trac10/ticket/10108#comment:3 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10108#comment:3</guid> <description> <p> Additional info: running Windows 7 Enterprise Service Pack 1, compiling with Visual Studio 2010 (V10.0.40219.1 SP1 Rel) </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Thu, 23 Oct 2014 18:25:33 GMT</pubDate> <title>status changed https://svn.boost.org/trac10/ticket/10108#comment:4 https://svn.boost.org/trac10/ticket/10108#comment:4 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> <p> Thanks for the report, will be looked at. </p> Ticket Barend Gehrels Wed, 05 Nov 2014 13:44:07 GMT <link>https://svn.boost.org/trac10/ticket/10108#comment:5 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10108#comment:5</guid> <description> <p> I cannot reproduce the original case, but I can reproduce the other case (four-angle) </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Wed, 05 Nov 2014 16:15:34 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/10108#comment:6 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10108#comment:6</guid> <description> <p> It currently goes wrong in select_ring, where a point-on-border is selected to see if rings should be included in the output. Because there is one intersection-point, which is discarded later, and the point-on-border happens to be that, this should change. Will come back to this soon. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Barend Gehrels</dc:creator> <pubDate>Thu, 06 Nov 2014 13:36:22 GMT</pubDate> <title>status changed; resolution set https://svn.boost.org/trac10/ticket/10108#comment:7 https://svn.boost.org/trac10/ticket/10108#comment:7 <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> </ul> <p> Fixed in branch develop. Will be released in 1.58 </p> Ticket