Modify

Opened 7 years ago

Last modified 2 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@… 7 years ago.
show the union of these two polygon will return an empty result
Boost crash reproducer.zip (10.2 KB) - added by vvolosyuk@… 4 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@… 4 years ago.
simple test program that shows union of two polygons fails to return anything

Download all attachments as: .zip

Change History (9)

Changed 7 years ago by thai@…

Attachment: TestBoost.Bug.cpp added

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

comment:1 Changed 5 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 4 years ago by vvolosyuk@…

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

Changed 4 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 4 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 4 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 2 years ago by mhilferink@…

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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as new The owner will remain Andrii Sydorchuk.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.