10

I've been searching far and wide on the seven internets, and have come to no avail. The closest to what I need seems to be The cutting stock problem, only in 2D (which is disappointing since Wikipedia doesn't provide any directions on how to solve that one). Another look-alike problem would be UV unwrapping. There are solutions there, but only those that you get from add-ons on various 3D software.

Cutting the long talk short - what I want is this: given a rectangle of known width and height, I have to find out how many shapes (polygons) of known sizes (which may be rotated at will) may I fit inside that rectangle.

For example, I could choose a T-shaped piece and in the same rectangle I could pack it both in an efficient way, resulting in 4 shapes per rectangle

enter image description here

as well as tiling them based on their bounding boxes, case in which I could only fit 3

enter image description here

But of course, this is only an example... and I don't think it would be much use to solving on this particular case. The only approaches I can think of right now are either like backtracking in their complexity or solve only particular cases of this problem. So... any ideas?

LWolf
  • 188
  • 1
  • 2
  • 7
  • 1
    Re-post this on http://math.stackexchange.com/. You'll get interesting solutions from both places. – Jacob May 21 '11 at 15:53
  • Also, this isn't really the cutting-stock problem. More like packing arbitrary polygons in a minimum area rectangle. – Jacob May 21 '11 at 15:57
  • 1
    [This paper](http://www.waset.org/journals/waset/v11/v11-19.pdf) looks interesting. – Jacob May 21 '11 at 15:58
  • That paper is indeed interesting +1 – LWolf May 22 '11 at 18:39
  • 1
    @Jacob Unfortunately, that link is now dead. Can you share the title, author of the paper? – zipzit Jun 09 '16 at 14:32
  • @zipzit [Optimizing Allocation of Two Dimensional Irregular Shapes using an Agent Based Approach by Ramin Halavati, Saeed B. Shouraki, Mahdieh Noroozian, and Saman H. Zadeh](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=97E827964A807463F89BCE721E3E26CD?doi=10.1.1.193.4085&rep=rep1&type=pdf) – LWolf Jun 17 '16 at 14:28
  • 1
    @LWolf Many thanks, impressive paper.. oops, that should be `waste` not `waist` on the output table. The whole thing is based on obtaining "friends".. Almost sounds like a packing algorithm developed by the folks at Facebook. I'm not sure I could duplicate the code from that write up but its a nice approach. Thx! – zipzit Jun 17 '16 at 15:32

2 Answers2

2

Anybody up for a game of Tetris (a subset of your problem)?

This is known as the packing problem. Without knowing what kind of shapes you are likely to face ahead of time, it can be very difficult if not impossible to come up with an algorithm that will give you the best answer. More than likely unless your polygons are "nice" polygons (circles, squares, equilateral triangles, etc.) you will probably have to settle for a heuristic that gives you the approximate best solution most of the time.

One general heuristic (though far from optimal depending on the shape of the input polygon) would be to simplify the problem by drawing a rectangle around the polygon so that the rectangle would be just big enough to cover the polygon. (As an example in the diagram below we draw a red rectangle around a blue polygon.)

Rectangle around polygon

Once we have done this, we can then take that rectangle and try to fit as many of that rectangle into the large rectangle as possible. This simplfies the problem into a rectangle packing problem which is easier to solve and wrap your head around. An example of an algorithm for this is at the following link:

An Effective Recursive Partitioning Approach for the Packing of Identical Rectangles in a Rectangle.

Now obviously this heuristic is not optimal when the polygon in question is not close to being the same shape as a rectangle, but it does give you a minimum baseline to work with especially if you don't have much knowledge of what your polygon will look like (or there is high variance in what the polygon will look like). Using this algorithm, it would fill up a large rectangle like so:

enter image description here

Here is the same image without the intermediate rectangles:

enter image description here

For the case of these T-shaped polygons, the heuristic is not the best it could be (in fact it may be almost a worst case scenario for this proposed approximation), but it would work very well for other types of polygons.

Jason Moore
  • 3,294
  • 15
  • 18
  • umm.. thanks for the effort, but although this would be easy to approach, it isn't exactly what I'm looking for... also, even if I simplify the initial problem by choosing a less complex polygon, unless that polygon is a square (or triangle or circle), I'm back to square one. What I need here is accuracy, not speed... (of course, the answer shouldn't take more than ten minutes to compute on worst case scenario) – LWolf May 22 '11 at 18:32
2

consider what the other answer said by placing the t's into a square, but instead of just leaving it as a square set the shapes up in a list. Then use True and False to fill the nested list as the shape i.e. [[True,True,True],[False,True,False]] for your T shape. Then use a function to place the shapes on the grid. To optimize the results, create a tracker which will pay attention to how many false in a new shape overlap with trues that are already on the grid from previous shapes. The function will place the shape in the place with the most overlaps. There will have to be modifications to create higher and higher optimizations, but that is the general premise which you are looking for.

Adam Moyer
  • 21
  • 2