faster, less optimal algorithms?

[joefutrelle]

My use case involves large numbers of rectangles (e.g., 10k) which I want to pack as quickly as possible, even if the packing isn't optimal.

I've taken the advice in the documentation to use one of the faster algorithms, and that was an improvement from the one I started with, but I'm looking for something at least 10x faster (my application is interactive).

So my questions are: is this a feature anyone else would use? And if so, is there some guidance available as to how to plug an additional algorithm into this library? I would be happy to contribute if this would be useful to others, otherwise I'll roll my own.

[secnot]

I think that 10k rectangles is a rare use case, but before looking for a solution i need a little more information.

are all the rectangles packed into a single or multiple bins?
What algorithm are you using currently?
What Bin selection heuristic ?
Online or Ofline?
what is the size of the rectangles compared with the bins? ie.- the bin is larger than the rectangle
what is the max acceptable wasted space per bin?

In general a little more detailed description of the problem

[joefutrelle]

Thanks for your response!.

• Multiple equal-sized bins
• I'm using "GuillotineBafSlas", SORT_AREA, no rotation
• Offline
• The vast majority of the rectangles are significantly smaller than the bin size, and based on some experimentation with various datasets I believe that most of the time is spent packing the small ones
• No clear idea how much wasted space is acceptable, would want to balance that with latency

The number of rectangles in each dataset ranges from 1 to about 10k with the average being around 5k.

[secnot]

Instead of packing each rectangle individually try to group several rectangles and pack their bounding box, then substitute it by the original rectangles once packed. It is very effective when the rectangles are much smaller than the bin, specially if the size of each group and the shape of the bounding box is selected carefully. You could go from packing 5k rectangles to packing 500 easily.

Another option is to split the bin in 2, 4 or 8 parts and pack each one individually by a different process using multiprocessing. Or just create the rectangle groups in parallel

If your application is iterative you could break the groups apart if any rectangle inside is accessed/removed.

There are a couple of faster and/or simpler algorithms, but the solutions for some inputs can be terrible, or the implementation too complex . I would try the another approach first.

Hope it helps

[joefutrelle]

Your first suggestion sounds promising, but I'm having trouble understanding it. Once I select a group of rectangles, how can I compute a bounding box for them, without packing them?

[secnot]

Create a bin with the width you are looking for, and several times the height required to pack all the rectangles that form the group, and then pack all the rectangles. Once finished compute the bounding box from the rectangles, or use the bin with and the highest rectangle top as the bounding box dimensions.

Select the width so the shape of the resulting group has the aspect ration you want, If the sum of the areas of the group is A, and the width used is W, then the height will be approximately H=0.7A/W, if the packing is good the constant will be bigger, smaller if it's bad.

If you have many rectangles with the same dimensions you could pack together those rectangles,
and place them "manually" in groups of 4, 8 ... etc

[joefutrelle]

Thanks, that's clear.

It seems to me that the speed increase would come from having fewer rectangles to pack at once. Could a simplified version of your approach work where I would just determine ahead of time which group of rectangles goes in each bin (using some simple, inexact, non-optimal heuristic based on area) and then pack each bin separately? Any rectangles that don't fit into a given bin can just be added to the next group, and if the heuristic is tuned right that will rarely happen and instead I'll just have some additional wasted space per bin, which is not a problem for my app.

[secnot]

The idea is to reduce the number of rectangles, if you create the groups beforehand and keep them unchanged you can reuse the bounding box in several packings saving calculations, only discarding a group when several of its rectangles are deleted. But anything that reduces the number of rectangles per bin will be an improvement.

In the end you will have to play with all the options and try to find one that works for your problem. If it is impossible you could implement an algorithms that keeps track of empty spaces in the bin, and allows adding and deleting rectangles interactively, but they are prone to fragmentation and wasted space.

[joefutrelle]

I have been exploring using Numba for this problem and have a working GuillotineBaf implementation running about 10x faster than the one in this library. Unfortunately I had to refactor your code in some rather inelegant ways to limit it to operations that Numba supports.

Here's the implementation.