Opened 8 years ago

Last modified 3 years ago

#5103 new Bugs

Boost Polygon: The union of these two polygon return an empty result.

Reported by: thai@… Owned by: Andrii Sydorchuk
Milestone: To Be Determined Component: polygon
Version: Boost 1.53.0 Severity: Problem
Keywords: Bug Cc:

Description

main.cpp

#include <boost/polygon/polygon.hpp>
#include <iostream>
namespace gtl = boost::polygon;
using namespace boost::polygon::operators;

// points_array_A_1 (-92810838,3618230) (-94606872,1822196) (-94999302,2214626) (-93203268,4010660) (-92810838,3618230) 
int points_array_A_1[] = {-92810838,3618230,-94606872,1822196,-94999302,2214626,-93203268,4010660,-92810838,3618230};
int points_array_A_1_size =5;

// points_array_B_1 (-95269304,222758) (-95260668,419862) (-95234760,615696) (-95192088,808228) (-95132906,996442) (-95057214,1178814) (-94966028,1354074) (-94860110,1520444) (-94739968,1676908) (-94606618,1822450) (-94999048,2214880) (-95165164,2033778) (-95314770,1838706) (-95446850,1631442) (-95560388,1413510) (-95654368,1186434) (-95728282,951992) (-95781368,711962) (-95813626,468376) (-95824294,222758) (-95269304,222758) 
int points_array_B_1[] = {-95269304,222758,-95260668,419862,-95234760,615696,-95192088,808228,-95132906,996442,-95057214,1178814,-94966028,1354074,-94860110,1520444,-94739968,1676908,-94606618,1822450,-94999048,2214880,-95165164,2033778,-95314770,1838706,-95446850,1631442,-95560388,1413510,-95654368,1186434,-95728282,951992,-95781368,711962,-95813626,468376,-95824294,222758,-95269304,222758};
int points_array_B_1_size =21;


namespace{
	class Output //for printing debug info
	{
	public:
		template<class T>
		static void Print(const gtl::polygon_data<T>& polyData)
		{
			gtl::polygon_data<T>::iterator_type pit = polyData.begin();
			gtl::polygon_data<T>::iterator_type pit_end = polyData.end();
			while(pit!=pit_end)
			{
				gtl::point_data<T> p = (*pit++);
				std::cout<<"("<<p.x()<<","<<p.y()<<")";
				std::cout<<" ";
			}
		}

		template<class T>
		static void Print(std::vector<gtl::polygon_data<T> >& polygonVec)
		{
			int size = polygonVec.size();
			for(int i=0;i<size;i++)
			{
				gtl::polygon_data<T>& poly = polygonVec[i];
				std::cout<<"Polygon "<<i+1<<": ";
				Output::Print(poly);
				std::cout<<std::endl;
			}
		}
	};
}

static void AddPolygonData(std::vector<gtl::polygon_data<int> >& group, int* points_array, int size)
{
	//convert c array to boost polygon data
	if(size>0)
	{
		gtl::polygon_data<int> poly_data;
		std::vector<gtl::point_data<int> > poly_points(size);
		int pi=0;
		for(int i=0;i<size;i++)
		{
			int i1 = i*2;
			int i2 = i1+1;
			poly_points[i]=gtl::point_data<int>(points_array[i1],points_array[i2]);
		}
		poly_data.set(poly_points.begin(),poly_points.end());
		group.push_back(poly_data);
	}
}

void testBooleanOps()
{
	//lets declare ourselves a polygon set
	using namespace gtl; //because of operators
	typedef std::vector<polygon_data<int> > PolygonVec;
	PolygonVec group_A;
	PolygonVec group_B;
	PolygonVec group_U;

	//load group A;
	AddPolygonData(group_A,points_array_A_1,points_array_A_1_size);

	//load group B;
	AddPolygonData(group_B,points_array_B_1,points_array_B_1_size);

	
	std::cout<<"union\n";
	//the result of the union is tore in group U;
	assign(group_U, group_A + group_B);
	Output::Print(group_U);
}

int main() {
 
	testBooleanOps();
    return 0;
}

Attachments (3)

TestBoost.Bug.cpp (3.2 KB) - added by thai@… 8 years ago.
show the union of these two polygon will return an empty result
Boost crash reproducer.zip (10.2 KB) - added by vvolosyuk@… 5 years ago.
This project illustrates the problem I noticed working with BOOST:Polygon. It does two union operations: the first union should join two overlapping CCW directed polygons, but results into an empty polygons. This operation uses a polygon received after a couple of boost polygon union operations. I did some clean up work on it to remove extra segments that looks like cuts. If I use the polygon without cleaning the union results in crash (the second polygon union call)
Poly_test.cpp (1.8 KB) - added by z@… 5 years ago.
simple test program that shows union of two polygons fails to return anything

Download all attachments as: .zip

Change History (9)

Changed 8 years ago by thai@…

Attachment: TestBoost.Bug.cpp added

show the union of these two polygon will return an empty result

comment:1 Changed 6 years ago by Lucanus Simonson

Resolution: worksforme
Status: newclosed

This was apparently fixed a very long time ago or never a problem. My result: union Polygon 1: (-92810838,3618230) (-93203268,4010660) (-94999048,2214880) (-94999302,2214626) (-94999292,2214615) (-95165164,2033778) (-95314770,1838706) (-95446850,1631442) (-95560388,1413510) (-95654368,1186434) (-95728282,951992) (-95781368,711962) (-95813626,468376) (-95824294,222758) (-95269304,222758) (-95260668,419862) (-95234760,615696) (-95192088,808228) (-95132906,996442) (-95057214,1178814) (-94966028,1354074) (-94860110,1520444) (-94739968,1676908) (-94606618,1822450) (-92810838,3618230)

comment:2 Changed 5 years ago by vvolosyuk@…

Resolution: worksforme
Status: closedreopened
Version: Boost 1.45.0Boost 1.53.0

Changed 5 years ago by vvolosyuk@…

Attachment: Boost crash reproducer.zip added

This project illustrates the problem I noticed working with BOOST:Polygon. It does two union operations: the first union should join two overlapping CCW directed polygons, but results into an empty polygons. This operation uses a polygon received after a couple of boost polygon union operations. I did some clean up work on it to remove extra segments that looks like cuts. If I use the polygon without cleaning the union results in crash (the second polygon union call)

comment:3 Changed 5 years ago by z@…

I just want to follow up with this bug and add a simple test program (see below) that demonstrates that union of two polygons returns empty result.

Please note polygon A is a 45 degree and polygon B is an arbitrary with near 45 degree edge. I suspect that failure of polygon union has something to do with union of 45 degree polygon with a abutting arbitrary polygon that has near 45 degree edge. I also include an alternative polygon that has abutting near 45 degree edge and union of them seems to work. So the only difference between alternative and the original polygon is y-coordinate value of one of vertexes that has changed from 2214626 to 2214625.

#include <vector>
#include <boost/polygon/polygon.hpp>
using namespace boost::polygon::operators;

#define POLYGON_45

#ifdef POLYGON_45
int points_A_1[] = 
{ // 45 degree polygon
               -92810838,3618230,
               -94606872,1822196,
               -94999302,2214626,
               -93203268,4010660};
int points_A_1_size =4;

#else 
int points_A_1[] = 
{ // arbitrary polygon
               -92810838,3618230,
               -94606872,1822196,
               -94999302,2214625, // 2214626 -> 2214625, near 45 degree edge
               -93203268,4010660};
int points_A_1_size =4;

#endif

int points_B_1[] = 
{
               -94739968,1676908,
               -94606618,1822450,
               -94999048,2214880,
               -95165164,2033778};
int points_B_1_size =4;


int
main(int argc, char **argv)
{
    typedef boost::polygon::polygon_data<int>         Polygon;
    typedef boost::polygon::point_data<int>           Point;
    typedef boost::polygon::polygon_set_data<int>     PolygonSet;

    std::vector<Point> points;
    
    int count = points_A_1_size;
    for (int i = 0; i < count; ++i) {
        points.push_back(boost::polygon::construct<Point>(points_A_1[2 * i], points_A_1[2 * i+1]));
    }
    
    Polygon A;
    A.set(points.begin(), points.end());

    
    points.clear();
    count = points_B_1_size;
    for (int i = 0; i < count; ++i) {
        points.push_back(boost::polygon::construct<Point>(points_B_1[2 * i], points_B_1[2 * i+1]));
    }

    Polygon B;
    B.set(points.begin(), points.end());

    PolygonSet ps1, ps2, ps3;

    ps1 += A;
    ps2 += B;
    assign(ps3, ps1 + ps2);
    
    std::vector<Polygon> polygons;
    ps3.get(polygons);
    return 0;
}

Changed 5 years ago by z@…

Attachment: Poly_test.cpp added

simple test program that shows union of two polygons fails to return anything

comment:4 Changed 4 years ago by Andrii Sydorchuk

Thank you for your report. I was not able to reproduce the issue in neither of 3 reports.
Could you provide the compiler prompt and Boost libraries version?

comment:5 Changed 4 years ago by Andrii Sydorchuk

Owner: changed from Lucanus Simonson to Andrii Sydorchuk
Status: reopenednew

comment:6 Changed 3 years ago by mhilferink@…

This issue could have a similar cause as issue 11415. Was the compiler of the Reporter also MSVC?

Note: See TracTickets for help on using tickets.