|
|
Boost : |
Subject: [boost] [GGL][Polygon][Union] Union of multi_polygon returns unexpected
From: Mohammad Morshed Alam Helal (helal_at_[hidden])
Date: 2010-02-05 09:44:40
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 list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk