3

I am a mason building a patio using random sized stones. I have a fixed number (in parentheses) of several different rectangular stones:

$18" \times 18" (17)$

$24"\times 12" (1)$

$18" \times 30" (17)$

$24"\times 18" (47)$

$18"\times 36" (10)$

$24"\times 30" (46)$

$12"\times 30" (51)$

The goal is to fit them into a $17'\times 23'$ patio without making a single cut. Is there an algorithm I can use? I do these types of jobs all of the time and we waste alot of stone, trying to reduce the overall waste by using an algorithm to calculate the ideal number of each size to use...

Inceptio
  • 7,881
Matt
  • 31
  • What is the relation between $x''$ and $x'$? – Inceptio Apr 03 '13 at 14:32
  • inches to feet, so 12"=1' – Matt Apr 03 '13 at 14:46
  • I've found an interesting introduction/explanation on "2D bin packing": http://codeincomplete.com/posts/2011/5/7/bin_packing/ Another link: http://www.joelverhagen.com/blog/2011/03/jim-scotts-packing-algorithm-in-c-and-sfml/ The general problem seems to be intractable. Therefore, heuristics are essential. – Axel Kemper Apr 03 '13 at 21:22
  • A related discussion: http://math.stackexchange.com/questions/4386/tiling-posters-on-a-wall/4388#4388 – Axel Kemper Apr 03 '13 at 21:25

2 Answers2

2

I've tried the Javascript implementation of http://pollinimini.net/demos/RectanglePacker.html

With the defined portfolio of stones, it is able to fill some 96% to 98% of the area depending on the sorting method chosen:

96% solution:

enter image description here

98% solution:

enter image description here

Here is my Javascript addition to define the available stones:

var b = []
var i = 0;
var bi = 0;
b[i++] = { w: 18, h: 18, n: 17 };
b[i++] = { w: 24, h: 12, n: 1 };
b[i++] = { w: 18, h: 30, n: 17 };
b[i++] = { w: 24, h: 18, n: 47 };
b[i++] = { w: 18, h: 36, n: 10 };
b[i++] = { w: 24, h: 30, n: 46 };
b[i++] = { w: 12, h: 30, n: 51 };

for (var j=0; j<b.length; j++) {
    for (var n=0; n<b[j].n; n++) {
        blocks[bi++] = { w: b[j].w, h: b[j].h };
    }
}

Below the line, this does not look like an "industry strength" solution for practical application to me. In a real building I would expect some obligatory requirements in terms of aesthetics. It is probably not enough to just fill 100% of the area, if it does not look "nice" in the end.

Axel Kemper
  • 4,943
0

Get Burr Tools, it's free. Divide all your values by 6, and sketch out the start on a large piece of grid paper, trying to be random.

When you're down to a hole and about 40 bricks left, toss that into the Burr Tools solver.

Ed Pegg
  • 20,955