# Boost :

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)

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