boost::geometry::intersection fails for triangle-triangle intersection.

[Raffael Casagrande <raffael@…>]

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");
  }
}

[Raffael Casagrande <raffael@…>]

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...

[Barend Gehrels]

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.

[Raffael Casagrande <raffael@…>]

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.

[Barend Gehrels]

Thanks for testing this. OK - I will close the ticket then as "fixed"