CGAL::join return wrong result

[Alison-97]

Issue Details

The CGAL::join function should return the union of the polygons, and subtract any polygons with counter-clockwise points. The following test initially passed in CGAL 4.11 but upon upgrading to CGAL 5.5, one of the points is missing in the resulting polygon, and hence yielding a wrong result for area.

Source Code

CGAL 4.11 - Area is 100; the polygon shape is same as the original input CGAL 5.5 - Area is 75; one of the point (10, 10) is missing

#include <CGAL/Polygon_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <list>
#include <CGAL/Boolean_set_operations_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Polygon_2<K>                                  Polygon_2;
typedef CGAL::Polygon_with_holes_2<K>                       Polygon_with_holes_2;
typedef CGAL::Point_2<K>                                    Point_2;


void TwoPolyUnion()
{
	Polygon_2 p;
	p.push_back(Point_2(0, 0));
	p.push_back(Point_2(10, 0));
	p.push_back(Point_2(10, 10));
	p.push_back(Point_2(0, 10));

	Polygon_2 p1;
	p1.push_back(Point_2(0, 10));
	p1.push_back(Point_2(10, 10));
	p1.push_back(Point_2(10, 5));
	p1.push_back(Point_2(0, 5));

	Polygon_2 p2;
	p2.push_back(Point_2(0, 10));
	p2.push_back(Point_2(10, 10));
	p2.push_back(Point_2(10, 5));
	p2.push_back(Point_2(0, 5));

	std::list<Polygon_2> polies;

	polies.push_back(p);
	polies.push_back(p1);
	polies.push_back(p2);

	std::list<Polygon_with_holes_2> input;
	for (auto it = polies.begin(); it != polies.end(); it++)
	{
		Polygon_with_holes_2 holes;
		for (auto pit = it->vertices_begin(); pit != it->vertices_end(); pit++)
			holes.outer_boundary().push_back(*pit);
		input.push_back(holes);
	}

	std::list<Polygon_with_holes_2> polyHoles;
	CGAL::join(input.begin(), input.end(), std::back_inserter(polyHoles));

	Polygon_with_holes_2 polyhole = *polyHoles.begin();
	Polygon_2 finalPoly;

	for (const Point_2& p : polyhole.outer_boundary().vertices()) {
		std::cout << p << std::endl;
		finalPoly.push_back(p);
	}

	std::cout << "AREA: " << finalPoly.area();

}

int main()
{
	TwoPolyUnion();
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Windows 11 version 21H2, 64 bits
• Compiler: Visual Studio 2022
• Release or debug mode: Debug
• CGAL version: 5.5
• Boost version: 1_65_1

[sloriot]

Could you please check that with Exact_predicates_exact_constructions_kernel it is not working as expected?

[Alison-97]

I've tried using Exact_predicates_exact_constructions_kernel but unfortunately the results are still the same.