4

Let's say I have some abstract shapes defined each with a width and height (let's make them rectangles for the sake of simplicity). How can I place as many of them as possible on a single canvas (just a term, not necessarily HTML5 canvas) of a defined width and height?

Obviously this is some sort of constraint satisfaction problem, but I don't really know where to start (besides brute force). Googling just turns up unrelated results (probably because I don't know what to search for). What would be a good algorithm or what would be a good way to go about creating an algorithm to do this?

Fizz is a good example. Shapes (circles, in this case) appear in groups and don't overlap each other and they stay out of each other's way. My use case is more of a one time positioning deal. Another example is SpriteRight, which places as efficiently as possible within certain boundaries.

3 Answers3

1

Your problem could profit from constraint logic programming over finite domains ().

Consider the question and answers to Prolog constraint processing: Packing squares. It shows several methods, one of which uses dedicated placement constraints to find a layout of non-overlapping rectangles in 2D.

clpfd also enables you to enforce additional constraints in addition to the packing constraint. There are both free (e.g., SWI and YAP) and commercial (e.g., SICStus) implementations which support .

Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
0

I found an open source example with JavaScript and HTML5 canvas. Rectangles are randomly generated and then packed. The author, however, makes no claims as to efficiency.

I also found an article which looks promising.

0

You could also look at http://www.aimms.com/downloads/application-examples/circle-packing. Here mathematical programming/modeling is used to solve the circle-packing problem. Other variants can also be defined. Special bin-packing constraints exist in Constraint Programming, http://www.aimms.com/cp.

In general, mathematical programming is a good way to approach such problems.

GdL
  • 1