[Boost-users] [polygon] bug with self intersecting polygons ?

Subject: [Boost-users] [polygon] bug with self intersecting polygons ?
From: Renaud Lepère (renaud.lepere_at_[hidden])
Date: 2012-12-20 10:04:39

Hello,
  I'm trying to remove some internal loops on polygons as illustrated in 
the following drawing :

            +---------------+    +---------------+
            |          |   /     |              /
            |          |\ /      |             /
            |          | X       |            X
            |          |/ \      |             \
            |          /   \     |              \
            +----->---------+    +----->---------+

  I need strong numerical robustness, i am using boost polyon with 
integer coordinates (using boost-1.52 + win32).
It works on a lot of samples but i encounter a bug on an example. I 
reduced to the following sample which is roughtly a triangle (IMHO it 
should 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;
     }
}

Is there something wrong in my code ? or is this a real bug.

Thanks for your help and time.

Renaud