id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
10108,boost::geometry::intersection fails for triangle-triangle intersection,Raffael Casagrande <raffael@…>,Barend Gehrels,"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"");
  }
}
}}}",Bugs,closed,To Be Determined,geometry,Boost 1.56.0,Problem,fixed,"intersection, triangle, robustness",