Java: How to draw images on the smallest possible surface?

Question

Let's say I have 256 images with an average size of 70x150 (So, size if variable). And I have a Graphic-instance (Created from a BufferedImage with a given size) on which I want to draw the images. But I want to draw them at the lowest possible surface. So, not simply in a grid, but really puzzled in each other. But!: they may not overlap each other.

Maybe this something only a human brain can manage.
It is worth asking it, I think....

Thanks in advance,
Martijn

For example:

+------++------+
|      ||      |
| img1 || img2 |
|      |+------+
|      |+-----------------+
+------+|                 |
+---+   |                 |
| 3 |   |                 |
|   |   |    img 4        |
+---+   |                 |
        |                 |
        +-----------------+

I don't really understand your question. Are you asking how to find the smallest rectangle in a list of rectangle? Or howw to actually draw your example? Or whats the smallest size you can draw with a Graphic instance`? — RoflcoptrException, Dec 13 '10 at 19:14
I don't know the exact terminology to use, but this problem sounds a lot like a 2D version of the hard drive or memory space management problem: given a new file/data you want to store, where do you put it? Best fit, worst fit, first fit, etc. Maybe you could read up on that to get some ideas. — DGH, Dec 13 '10 at 19:15

score 3 · Answer 1 · edited May 23 '17 at 12:18

3

This question has been asked before: What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?

A good survey, from a previous answer, is available at: http://www.csc.liv.ac.uk/~epa/surveyhtml.html

edited May 23 '17 at 12:18

Community

1
1

answered Dec 13 '10 at 19:16

score 2 · Answer 2 · answered Dec 13 '10 at 19:23

Basically, you're asking for a solution to a knapsack problem.

There is none optimal algorithm for a Knapsack Problem of arbitrary size, since it's NP-hard problem.

There are plentiful of sub-optimal algorithms:

Greedy search algorithms.
Heuristic search space traveling algorithms, such as A* family
Stochastic search algorithms, such as simmulated annealing, genetic algorithms

Java: How to draw images on the smallest possible surface?

2 Answers2