CGAL Performance - Work In Bulk

A performance tip when using CGAL 2D Boolean Operations: you'll get much better performance if you can perform multiple operations at once.

I wrote code that did something like this:

for each polygon
my_area.difference(polygon)

That snippet took 36 minutes to run. So I rewrote it like this:

vector all;
for each polygon
all.push_back(polygon)
Polygon_set_2 sub_area.join(all.begin(),all.end());
my_area.difference(sub_area);

New running time: 3 minutes. Why the huge speedup? Well, every time you do a boolean operation between two polygons, the underlying arrangements are merged using a "sweep" algorithm, which is an efficient way to merge two big piles of lines. The sweep operation's time is O(NlogN) which is very good for this kind of thing, but N is the sum of the edges in both polygon sets.

If the area we are subtracting from is very complex, this means that for each subtraction we do an operation based on the big polygon's area. Ouch!

The second snippet wins in two ways:

• We do only one operation against "my_area", so if my_area is complex we eat the cost of going through the area only once.
• A "join" on a range of polygons is very fast because CGAL will divide and conquer in groups, to minimize the total number of operations. That is, a join on a range is faster than a join on each individual item.

If you run a profiler like Shark on CGAL and see "sweep_line_2" taking all the time, use techniques like the one above to cut down the total number of merges. It can make a huge difference!