bug with unrolling self intersecting polygon

[rlepere <renaud.lepere@…>]

I m tring to remove loops from self intersecting polygon but the following example (a triangle A, B, C with some points nearly aligned between B and C) fails. IMHO it sould return a triangle.

#include <boost/polygon/polygon.hpp>
#include <vector>
#include <iostream>

using namespace boost::polygon;
using namespace std;

typedef point_data< int > point;
typedef vector< point > points;
typedef polygon_set_data< int > polygon_set;
typedef polygon_with_holes_data< int > polygon_with_holes;
typedef vector< polygon_with_holes > polygons_with_holes;


/*
  * A triangle A, B, C with some nearly aligned points between B and C.
  *
  *     A
  *      +
  *      |\
  *      | \
  *       | \
  *       |  \
  *        |  \
  *        |   \
  *        |    \
  *         |    \
  *         |   /-+ C
  *       B +---
  */
polygon_with_holes MakeRawPolygon()
{
     points ps;
     ps.push_back(point(-181928106,288346744));    // A
     ps.push_back(point(-15311797,-289428209));    // B
     ps.push_back(point(56093690,-270295166));
     ps.push_back(point(24502047,-278760121));
     ps.push_back(point(57745146,-269852659));
     ps.push_back(point(56791908,-270108078));
     ps.push_back(point(-14613579,-289241121));
     ps.push_back(point(82923673,-263106094));     // C
     polygon_with_holes poly;
     set_points(poly, ps.begin(), ps.end());
     return poly;
}

int main()
{
     polygon_with_holes polygon(MakeRawPolygon());
     polygon_set ps;
     ps.insert(polygon);

     // first unrool
     polygons_with_holes unrolled_polygons;
     ps.get(unrolled_polygons);

     if (unrolled_polygons.size() == 0u) {
         std::cout << "error" << endl;
     }
}

[Andrii Sydorchuk]

Hi,

Sorry for the late response. I was not able to reproduce your failure. Could you specify which compiler are you using and if the issue is still feasible?

Thanks, Andrii

[anonymous]

I am using visual studio 10 and i still have the bug in 1.53 version. I have just try with gcc-mingw-4.2 and it is ok.

[Andrii Sydorchuk]

I was able to reproduce the error on msvc-2008. Will investigate. My initial assumption is that the bug is related to the specifics of the floating-point operations implementation.

[Andrii Sydorchuk]

I spent a while debugging this issue. In the end it appears that the defect is caused by the integer grid snapping strategy used by the Polygon library. Due to this strategy inputs, that contain almost parallel lines within a distance of 1x1 square, may cause defects. In order to fix this the whole implementation of the intersection handling needs to be rewritten. In terms of the current implementation I am marking this as working as intended.