union operation slow

[Arvin-huang1]

Hello, I ask a question again
The subjects is 10 horizontal rectangles and 10 vertical rectangles for examle.

Union operation is slowly when the number of horizontal and vertical rectangles increase to 1000.(my run time is 100s).
The union result is a polygon with single outline and a large number of holes(1000 * 1000), a lot of time is consumed in judge PointInPolygon.
Are there any improvement methods for this situation. thank you.

void testBandUnion() {
	int bandNums = 1000;
	int width = 5;
	int step = width * 2;
	int height = bandNums * step;
	Paths64 paths{};
	//add vertical band
	for (size_t i = 0; i < bandNums; i++)
	{
		Path64 path{};
		path.emplace_back(int64_t(i * step), int64_t(0));
		path.emplace_back(int64_t(i * step + width), int64_t(0));
		path.emplace_back(int64_t(i * step + width), int64_t(height));
		path.emplace_back(int64_t(i * step), int64_t(height));
		paths.push_back(path);
	}

	//add horizontal band
	for (size_t i = 0; i < bandNums; i++)
	{
		Path64 path{};
		path.emplace_back(int64_t(0), int64_t(i * step));
		path.emplace_back(int64_t(height), int64_t(i * step));
		path.emplace_back(int64_t(height), int64_t(i * step + width));
		path.emplace_back(int64_t(0), int64_t(i * step + width));
		paths.push_back(path);
	}

	PolyTree64 tree;
	clock_t time1 = clock();
	BooleanOp(ClipType::Union, FillRule::NonZero, paths, {}, tree);
	clock_t time2 = clock();
	std::cout << "run time(ms): " << double(time2) - double(time1) << std::endl;
}

[AngusJohnson]

Are there any improvement methods for this situation.

I suspect not, at least not without accepting a very imperfect union.

The best way to manage this would be to create an orthogonal clipper, but that would of course be a lot more work.
I could certainly consider creating an orthogonal clipper (that only clips polygons with axis aligned edges).
It would be a lot faster, but I doubt the user demand would justify the effort.

[stefanottili]

boost.polygon has optimized datastructures for 90 or 45 degree edges.
I’d be curious how it compares on your use case.

[Arvin-huang1]

I just give an special situation of small of less polygon union results in a large number of inner holes,They can be non-standard aligned edges, not orthogonal, also not a rectangle.