[boost] [GGL][Polygon][Union] Union returns hole (inner ring) of the expected result as the output polygon (outer ring)

Subject: [boost] [GGL][Polygon][Union] Union returns hole (inner ring) of the expected result as the output polygon (outer ring)
From: Mohammad Morshed Alam Helal (helal_at_[hidden])
Date: 2010-01-27 12:02:23

Hi,

Union of two polygon_2d returns a hole (inner ring) as result. Where -

Input polygons -
Polygon 1: A big rectangle with a hexagonal hole inside
Polygon 2: A triangle that intersects the hole from inside leaving 
portion of it in the hole

Output polygon -
The hexagonal hole without the triangle-portion.

Expected output polygon -
The big rectangle with current output polygon as hole (inner)as 
described in this picture.

The Union of a rectangle with a hexagonal hole and a triangle 
intersecting the first polygon

*****************************
*****************************
*****************************
********            *********
*******              **X*****
******               XXX*****
*****               XXX******
****               XX   *****
*****                  ******
******                *******
*******              ********
********            *********
*****************************
*****************************
*****************************

returns this polygon, instead of the correct result.

         ++++++++++++
        ++++++++++++++
       +++++++++++++++
      +++++++++++++++
     +++++++++++++++  +++
      ++++++++++++++++++
       ++++++++++++++++
        ++++++++++++++
         ++++++++++++

You can use the code bellow to generate the case and some PPM images. 
You may use a WSQ Viewer to see the polygons.

Please let me know any workaround or anything thats I am missing.

Thank and regards,

Helal

// the code

void uniontest()    // Your main should call it
{
     double L = 200.0;
     const double outloop[][2] = { {L, L}, {L, -L}, {-L, -L}, {-L, L}, 
{L, L} };

     double R = 100.0;
     double H = R * sqrt(3.0) / 2;
     const double inloop[][2] = { {R, 0}, {R/2, -H}, {-R/2, -H}, {-R, 
0}, {-R/2, H}, {R/2, H}, {R, 0} };

     polygon_2d BIGpoly;                                     //A 
rectangle with a hexagonal hole in it
     assign(BIGpoly, outloop);                               //the rectangle
     BIGpoly.inners().resize(1);
     linear_ring<point_2d>& inner = BIGpoly.inners().back();
     assign(inner, inloop);                                  //the inner 
hexagon
     correct(BIGpoly);                                       //correct 
the order iff not

     double a = 20.0;
     double h = a * sqrt(3.0) / 2;
     const double t1[][2] = { { 30+0,  10+0}, { 30+a/2,  10+h}, { 30+a,  
10+0} };
     const double t2[][2] = { {    0,     0}, {    a/2,     h}, {    
a,     0} };
     const double t3[][2] = { {-10+0, -10+0}, {-10+a/2, -10+h}, {-10+a, 
-10+0} };
     const double t4[][2] = { {    0, -15+0}, {    a/2, -15+h}, {    a, 
-15+0} };

     const double t5[][2] = { {-50, -40}, {-110, 0}, {-100, 30}, {-50, 
-40} };

     polygon_2d T1, T2, T3, T4, T5, T6;                              
//the triangles
     assign(T1, t1);
     correct(T1);
     assign(T2, t2);
     correct(T2);
     assign(T3, t3);
     correct(T3);
     assign(T4, t4);
     correct(T4);
     assign(T5, t5);
     correct(T5);

     std::vector<polygon_2d > P_list, P_union, P_tmp;

     //the outer shape
     P_union.push_back(BIGpoly);
     DumbPPMPrint("c:\\BIGpoly.ppm", P_union.begin(), P_union.size());

     //Case 1: floating triangle in hole
     P_union.clear();
     ggl::union_inserter<ggl::polygon_2d >(BIGpoly, T1, 
std::back_inserter(P_union));
     DumbPPMPrint("c:\\case1.ppm", P_union.begin(), P_union.size());

     //Case 2: three solid triangle creating a small hole
     P_union.clear();
     P_tmp.clear();
     ggl::union_inserter<ggl::polygon_2d >(T2, T3, 
std::back_inserter(P_tmp));
     DumbPPMPrint("c:\\case2_i.ppm", P_tmp.begin(), P_tmp.size());
     ggl::union_inserter<ggl::polygon_2d >( (*(P_tmp.begin())), T4, 
std::back_inserter(P_union));
     DumbPPMPrint("c:\\case2.ppm", P_union.begin(), P_union.size());

     //Case 3: floating holed-polygon in hole
     //P_union.clear(); //contains result of case 2
     P_tmp.clear();
     ggl::union_inserter<ggl::polygon_2d >(BIGpoly, 
(*(P_union.begin())), std::back_inserter(P_tmp));
     DumbPPMPrint("c:\\case3.ppm", P_tmp.begin(), P_tmp.size());

     //Case 4: a triangle intersecting the hole from inside
     P_union.clear();
     P_union.push_back(BIGpoly);
     P_union.push_back(T5);
     DumbPPMPrint("c:\\case4_pre.ppm", P_union.begin(), P_union.size());
     P_union.clear();
     ggl::union_inserter<ggl::polygon_2d >( BIGpoly, T5, 
std::back_inserter(P_union));
     DumbPPMPrint("c:\\case4.ppm", P_union.begin(), P_union.size());
     P_union.clear();
     ggl::union_inserter<ggl::polygon_2d >( T5, BIGpoly, 
std::back_inserter(P_union));
     DumbPPMPrint("c:\\case4_rev_order.ppm", P_union.begin(), 
P_union.size());
}

void DumbPPMPrint(char *name, std::vector<polygon_2d >::iterator it, 
unsigned int n)
{
     //WSQ Viewer can be of help
     //http://www.cognaxon.com/index.php?page=wsqview

     //the holes are black.
     //the more number of polygons are present at a pixel the brighter 
the pixel is.

     unsigned int imgwidth  = 512;   //pixel width of image
     unsigned int imgheight = 512;   //pixel height of image

     float width  = 400.0;           //width of image: 10 units (e.g. 
meters)
     float height = 400.0;           //height of image: 10 units (e.g. 
meters)
     //float width  = 6000.0;        //width of image: 10 units (e.g. 
meters)
     //float height = 6000.0;        //height of image: 10 units (e.g. 
meters)

     //header
     FILE *signal = fopen(name, "wt");
     fprintf(signal, "P3\n");
     fprintf(signal, "# %s\n", name);
     fprintf(signal, "%d %d\n", imgwidth, imgheight);
     fprintf(signal, "255\n");

     unsigned int x, y, i;
     float xpos, ypos;
     // PPM images carry red, green, blue color channels.
     int val0, val1, val2;
     std::vector<polygon_2d >::iterator poly;

     for (y = 0; y < imgheight; y++)
     {
         ypos = height/2 - height * y / imgheight;

         for (x = 0; x < imgwidth; x++)
         {
             xpos = width/2 - width * x / imgwidth;

             val0 = val1 = val2 = 0;     //black

             ggl::point_xy<float> point(xpos, ypos);

             poly = it;
             for (i = 0; i < n; i++, poly++)
             {
                 if( ggl::within( point, (*poly) ) )
                 {
                     val0 += 255/n;
                     val1 += 255/n;
                     val2 += 255/n;
                 }
             } //fi_poly

             // clamp to allowed range
             if (val0 < 0) val0 = 0; else if (val0 > 255) val0 = 255;
             if (val1 < 0) val1 = 0; else if (val1 > 255) val1 = 255;
             if (val2 < 0) val2 = 0; else if (val2 > 255) val2 = 255;

             fprintf(signal, "%3d %3d %3d  ", val0, val1, val2);

             if (x%16 == 15) fprintf(signal, "\n");
         } //fi_x
     } //fi_y

     fclose(signal);
}

//@End_of_Code