Boost logo

Geometry :

Subject: [Fwd: [boost] [GGL][Polygon][Union] Union of multi_polygon returns unexpected]
From: Mateusz Loskot (mateusz)
Date: 2010-02-05 16:46:37


Hi,

Barend, I know you're taking action on this, but are you
going to add these cases to the unit tests?
If not, I would do it.

Mat

-------- Original Message --------
Subject: [boost] [GGL][Polygon][Union] Union of multi_polygon returns
unexpected
Date: Fri, 05 Feb 2010 15:44:40 +0100
From: Mohammad Morshed Alam Helal <helal_at_[hidden]>
Reply-To: boost_at_[hidden]
To: boost_at_[hidden]
References: <4B60719F.10906_at_[hidden]>

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

_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost

-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org

Geometry list run by mateusz at loskot.net