[boost] [GGL][Polygon][Union] Union of multi_polygon returns unexpected

5 Feb 2010

      Hello Barend,

Union of multi_polygon has some bugs. I must admit I could not pinpoint 
the problem. Please let me know if I am missing something.
These are the test cases I tried and most of them failed:

Case 5: both list has equal number of polygon (PASS)

Case 6: one of the list has a single polygon (FAIL)

Case 7: both list has one polygon (intersecting) (PASS)

Case 8: Different number of polygons in the lists (FAIL)

Case 9: 2nd list has a single polygon (FAIL)

Case 10: both list has one polygon (non-intersecting) (PASS)

Case 11: one list has same polygon twice (FAIL)

Case 12A: using same list twice. Its a mess. (FAIL)

Case 12B: keeping one of the list empty. Returns empty. (FAIL)

Images from Case 9:

Before:

Multi_polygon 1:
****************************
****************************
****************************
********            ********
******* X            *******
****** XXX            ******
*****                  *****
****      Y             ****
*****    YYYS          *****
******    S SS        ******
*******  XXXX        *******
********            ********
****************************
****************************
****************************

Multi_polygon 1: (only the X marked area)
............................
............................
............................
........            ........
.......              ..X....
......               XXX....
.....               XXX.....
....               XX   ....
.....                  .....
......                ......
.......              .......
........            ........
............................
............................
............................

After:

Multi_polygon:
****************************
****************************
****************************
********            ********
*******              *******
******               *******
*****               ********
****               **   ****
*****                  *****
******                ******
*******              *******
********            ********
****************************
****************************
****************************
As you see, the floating polygons are missing.

You can use the code below to regenerate the cases.
I have the PPM images. Please let me know if you need them.

Thank you for the fixes for the previous problem with union of polygons. 
It worked.

Best regards,

Helal

//@_Begin_of_Code

void uniontest()
{
     bool case_1   = false,
          case_2   = false,
          case_2_3 = false,
          case_4   = false,
          case_5   = true,
          case_6   = true,
          case_7   = true,
          case_8   = true,
          case_9   = true,
          case_10  = true,
          case_11  = true,
          case_12  = true,
          isDump   = false;

     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);
     if (isDump) DumbPPMPrint("c:\\BIGpoly.ppm", P_union.begin(), 
P_union.size());

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

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

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

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

     //Case 5: using multi_polygon (PASS)
     // both list has equal number of polygon
     if (case_5)
     {
         typedef multi_polygon<polygon_2d> polygon_set;
         polygon_set ps1, ps2, ps3;

         ps1.push_back(BIGpoly);
         ps1.push_back(T1);
         ps1.push_back(T2);
         ps2.push_back(T3);
         ps2.push_back(T4);
         ps2.push_back(T5);

         union_inserter<polygon_2d>(ps1, ps2, std::back_inserter(ps3));
         if (isDump) DumbPPMPrint("c:\\case5.ppm", ps3.begin(), ps3.size());
         if (isDump) DumbPPMPrint("c:\\case5_A.ppm", ps1.begin(), 
ps1.size());
         if (isDump) DumbPPMPrint("c:\\case5_B.ppm", ps2.begin(), 
ps2.size());
     }

     //Case 6: using multi_polygon (FAIL)
     // one of the list has a single polygon
     if (case_6)
     {
         typedef multi_polygon<polygon_2d> polygon_set;
         polygon_set ps1, ps2, ps3;

         ps1.push_back(BIGpoly);
         ps2.push_back(T1);
         ps2.push_back(T2);
         ps2.push_back(T3);
         ps2.push_back(T4);
         ps2.push_back(T5);

         union_inserter<polygon_2d>(ps1, ps2, std::back_inserter(ps3));
         if (isDump) DumbPPMPrint("c:\\case6.ppm", ps3.begin(), ps3.size());
         if (isDump) DumbPPMPrint("c:\\case6_A.ppm", ps1.begin(), 
ps1.size());
         if (isDump) DumbPPMPrint("c:\\case6_B.ppm", ps2.begin(), 
ps2.size());
     }

     //Case 7: using multi_polygon (PASS)
     // both list has one polygon (intersecting)
     if (case_7)
     {
         typedef multi_polygon<polygon_2d> polygon_set;
         polygon_set ps1, ps2, ps3;

         ps1.push_back(BIGpoly);
         ps2.push_back(T5);

         union_inserter<polygon_2d>(ps1, ps2, std::back_inserter(ps3));
         if (isDump) DumbPPMPrint("c:\\case7.ppm", ps3.begin(), ps3.size());
         if (isDump) DumbPPMPrint("c:\\case7_A.ppm", ps1.begin(), 
ps1.size());
         if (isDump) DumbPPMPrint("c:\\case7_B.ppm", ps2.begin(), 
ps2.size());
     }

     //Case 8: using multi_polygon (FAIL)
     // Different number of polygons in the lists
     if (case_8)
     {
         typedef multi_polygon<polygon_2d> polygon_set;
         polygon_set ps1, ps2, ps3;

         ps1.push_back(BIGpoly);
         ps1.push_back(T1);
         ps2.push_back(T2);
         ps2.push_back(T3);
         ps2.push_back(T4);
         ps2.push_back(T5);

         union_inserter<polygon_2d>(ps1, ps2, std::back_inserter(ps3));
         if (isDump) DumbPPMPrint("c:\\case8.ppm", ps3.begin(), ps3.size());
         if (isDump) DumbPPMPrint("c:\\case8_A.ppm", ps1.begin(), 
ps1.size());
         if (isDump) DumbPPMPrint("c:\\case8_B.ppm", ps2.begin(), 
ps2.size());
     }

     //Case 9: using multi_polygon (FAIL)
     // 2nd list has a single polygon
     if (case_9)
     {
         typedef multi_polygon<polygon_2d> polygon_set;
         polygon_set ps1, ps2, ps3;

         ps1.push_back(BIGpoly);
         ps1.push_back(T1);
         ps1.push_back(T2);
         ps1.push_back(T3);
         ps1.push_back(T4);
         ps2.push_back(T5);

         union_inserter<polygon_2d>(ps1, ps2, std::back_inserter(ps3));
         if (isDump) DumbPPMPrint("c:\\case9.ppm", ps3.begin(), ps3.size());
         if (isDump) DumbPPMPrint("c:\\case9_A.ppm", ps1.begin(), 
ps1.size());
         if (isDump) DumbPPMPrint("c:\\case9_B.ppm", ps2.begin(), 
ps2.size());
     }

     //Case 10: using multi_polygon (PASS)
     // both list has one polygon (non-intersecting)
     if (case_10)
     {
         typedef multi_polygon<polygon_2d> polygon_set;
         polygon_set ps1, ps2, ps3;

         ps1.push_back(BIGpoly);
         ps2.push_back(T4);

         union_inserter<polygon_2d>(ps1, ps2, std::back_inserter(ps3));
         if (isDump) DumbPPMPrint("c:\\case10.ppm", ps3.begin(), 
ps3.size());
         if (isDump) DumbPPMPrint("c:\\case10_A.ppm", ps1.begin(), 
ps1.size());
         if (isDump) DumbPPMPrint("c:\\case10_B.ppm", ps2.begin(), 
ps2.size());
     }

     //Case 11: using multi_polygon (FAIL)
     // one list has same polygon twice
     if (case_11)
     {
         typedef multi_polygon<polygon_2d> polygon_set;
         polygon_set ps1, ps2, ps3;

         ps1.push_back(BIGpoly);
         ps2.push_back(T4);
         ps2.push_back(T4);

         union_inserter<polygon_2d>(ps1, ps2, std::back_inserter(ps3));
         if (isDump) DumbPPMPrint("c:\\case11.ppm", ps3.begin(), 
ps3.size());
         if (isDump) DumbPPMPrint("c:\\case11_A.ppm", ps1.begin(), 
ps1.size());
         if (isDump) DumbPPMPrint("c:\\case11_B.ppm", ps2.begin(), 
ps2.size());
     }

     //Case 12: using multi_polygon (FAIL)
     //A: using same list twice. Its a mess
     //B: keeping one of the list empty. Returns empty.
     if (case_12)
     {
         typedef multi_polygon<polygon_2d> polygon_set;
         polygon_set ps1, ps2, ps3;

         ps1.push_back(BIGpoly);
         ps1.push_back(T1);
         ps1.push_back(T2);
         ps1.push_back(T3);
         ps1.push_back(T4);
         ps1.push_back(T5);

         union_inserter<polygon_2d>(ps1, ps1, 
std::back_inserter(ps3));    //A
         //union_inserter<polygon_2d>(ps1, ps2, 
std::back_inserter(ps3));  //B
         if (isDump) DumbPPMPrint("c:\\case12.ppm", ps3.begin(), 
ps3.size());
         if (isDump) DumbPPMPrint("c:\\case12_A.ppm", ps1.begin(), 
ps1.size());
         //if (isDump) */DumbPPMPrint("c:\\case12_B.ppm", ps2.begin(), 
ps2.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  = 256;   //pixel width of image
     unsigned int imgheight = 256;   //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)

     //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, weight;

     std::vector<polygon_2d >::iterator poly;

     weight = 255/n;
     if (weight < 101) weight = 101;

     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

             point_xy<float> point(xpos, ypos);

             poly = it;
             for (i = 0; i < n; i++, poly++)
             {
                 if( within( point, (*poly) ) )
                 {
                     val0 += weight;
                     val1 += weight;
                     val2 += weight;
                 }
             } //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

[boost] [GGL][Polygon][Union] Union of multi_polygon returns unexpected

Mohammad Morshed Alam Helal