[Boost-bugs] [Boost C++ Libraries] #10108: boost::geometry::intersection fails for triangle-triangle intersection

Subject: [Boost-bugs] [Boost C++ Libraries] #10108: boost::geometry::intersection fails for triangle-triangle intersection
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-06-10 09:23:20

#10108: boost::geometry::intersection fails for triangle-triangle intersection
------------------------------------------------+--------------------------
 Reporter:  Raffael Casagrande <raffael@…>      |      Owner:
     Type:  Bugs                                |  barendgehrels
Milestone:  To Be Determined                    |     Status:  new
  Version:  Boost 1.56.0                        |  Component:  geometry
 Keywords:  intersection, triangle, robustness  |   Severity:  Problem
------------------------------------------------+--------------------------
 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.

 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)

 I've attached a picture that depicts the situation to this report.


 {{{
 #include<cmath>
 #include<fstream>

 #include<boost/geometry.hpp>
 #include<boost/geometry/geometries/ring.hpp>
 #include<boost/geometry/io/svg/svg_mapper.hpp>
 #include<boost/geometry/geometries/point_xy.hpp>


 namespace bg = boost::geometry;

 int main() {
   typedef bg::model::d2::point_xy<double> point_t;
   typedef bg::model::ring<point_t, false, true> 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<ring_t> result;
   bg::intersection(ring0, ring1, result);
   std::cout << result.size() << std::endl;


   // Output in SVG:
   std::ofstream stream("debug.svg");
   bg::svg_mapper<point_t> 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");
   }
 }
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10108>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.