discuss@lists.openscad.org

OpenSCAD general discussion Mailing-list

View all threads

Re: packing objects in 2 space

JB
Jordan Brown
Mon, Feb 14, 2022 7:25 PM

I should note that, in general, coming up with your own algorithm as I
did here is a bad idea.  For generic problems like this, smart people
have spent a lot of effort coming up with these algorithms.

For instance, here's a discussion of a similar problem:
https://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu

I was curious whether the algorithm that I was thinking of would work,
which is an entirely different motivation from just wanting to get the
problem solved.

I should note that, in general, coming up with your own algorithm as I did here is a bad idea.  For generic problems like this, smart people have spent a lot of effort coming up with these algorithms. For instance, here's a discussion of a similar problem: https://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu I was curious whether the algorithm that I was thinking of would work, which is an entirely different motivation from just wanting to get the problem solved.
JB
Jordan Brown
Mon, Feb 14, 2022 7:38 PM

On 2/14/2022 11:25 AM, Jordan Brown wrote:

Another piece of advice, though:  make sure that the problem that you're
trying to solve needs to be solved.

The author there writes that he wants to efficiently pack multiple
images into one image, and gives two examples, one larger with a bunch
of white space and the other smaller and packed more efficiently.

But his goal is to reduce the file size, not to reduce the dimensions of
the image per se... and image compression algorithms are really good at
squashing out large white areas.  I can't compare directly, because his
two examples and the accompanying text are all one image, but I cut the
two images out with Paint and saved them separately.  For a ~20K file,
there was a 300-byte difference in size, or about 1.5%.  That could have
been caused by the difference in exactly where I did the cuts.

I suspect that the simplest algorithms that he suggests (e.g. just
stacking the images side by side) would produce results nearly as good
as his much fancier algorithm, because the image compressor would get
rid of the white space.

On 2/14/2022 11:25 AM, Jordan Brown wrote: > For instance, here's a discussion of a similar problem: > https://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu Another piece of advice, though:  make sure that the problem that you're trying to solve needs to be solved. The author there writes that he wants to efficiently pack multiple images into one image, and gives two examples, one larger with a bunch of white space and the other smaller and packed more efficiently. But his goal is to reduce the file size, not to reduce the dimensions of the image per se... and image compression algorithms are really good at squashing out large white areas.  I can't compare directly, because his two examples and the accompanying text are all one image, but I cut the two images out with Paint and saved them separately.  For a ~20K file, there was a 300-byte difference in size, or about 1.5%.  That could have been caused by the difference in exactly where I did the cuts. I suspect that the simplest algorithms that he suggests (e.g. just stacking the images side by side) would produce results nearly as good as his much fancier algorithm, because the image compressor would get rid of the white space.