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

Subject: [Boost-bugs] [Boost C++ Libraries] #10107: boost::geometry::intersection fails for triangle-triangle intersection.
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-06-09 11:45:05

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

 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)


 {{{
 #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,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<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<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/10107>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.