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

[Raffael Casagrande <raffael@…>]

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

[anonymous]

I run your code against Boost 1.56.0 and it works just fine (returns 0 intersection).

[dgb@…]

Hi,

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.

Trying to attach the image 'IntersectionReturnsFourangleBInsteadOfIntersection.png' to visualize the situation.

typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > 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);

--> intersect returns 'green' polygon

[dgb@…]

additional example image with barely adjacent polygons

[dgb@…]

Additional info: running Windows 7 Enterprise Service Pack 1, compiling with Visual Studio 2010 (V10.0.40219.1 SP1 Rel)

[Barend Gehrels]

Thanks for the report, will be looked at.

[Barend Gehrels]

I cannot reproduce the original case, but I can reproduce the other case (four-angle)

[Barend Gehrels]

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.

[Barend Gehrels]

Fixed in branch develop. Will be released in 1.58