Keep It Simple, Stupid PerlMonks

### Challenge: 2D random layout of variable-sized rectangular units.

by BrowserUk (Pope)
 on Sep 03, 2006 at 03:22 UTC Need Help??
BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

#### Problem description:

Your going to lay a patio using brand of precast concrete "stone effect" pavers that come in a range of sizes:

a)300x300, b)450x300, c)450x450, d)600x450, e)600x600, f)600x300, g)750x600, h)750x750, i)900x600.

To achieve the most natural effect, the advice is to lay a combination of sizes of paver in 'random layout'. The industry rules of thumb for achieving a good effect are:

1. The more sizes used the better.
2. There should be roughly equal numbers areas* of each size used.
3. There should be no 4-corner joints.
4. Contiguous straight runs of joint should be minimised, and under no circumstances should any single straight run stretch for more than half the width of the area in the direction it runs.

One final, if obvious, golden rule is that you should work out the pattern of choice before ordering the pavers.

#### The challenge

Write a program that takes the width x length of the patio in question, ( and optionally the list of sizes of paver, though these can be hard coded as above), and generates random patterns that comply with the rules of thumb above.

The program should produce one random layout per run.

The output should be in some form that can be used as input to another program to display the layout graphically. I'm not going to specify the format, but it might be something like:

```   X,    Y  TYPE
0,    0,  c
450,    0,  g
1050,    0,  a
1350,    0,  i
...

Many other formats are possible, including a Data::Dumper dump of the internal data structure used.

The size of the patio as input can be 'rounded up' in either or both dimensions to the next of the greatest common divisor (GCD) of the list of sizes. (This puts all cuts to be made in the actual patio at one of the four edges). For example. The GCD of the 9 sizes above is 150mm. This forms a minimum grid for the layout. If the patio size entered was 8.65 x 4.1, then this would be round up to

```0.15 * ( 1 + int( 8.65 / 0.15 ) ) x 0.15 * ( 1 + int( 4.1 / 0.15 ) )
8.7 x 4.2

#### Other rules

None. I have ideas about how I will approach the problem, but I don't want to influence the creativity.

There is no rush. I will not be looking at other peoples solutions till I've had a go myself, and not until at least next Sunday. If you have questions, please mark the post with (Qs) in the title so I'll know to look and answer.

There is no 'best layout'; or 'right answer'; nor prize. It's just a real world problem that I encountered recently that I thought deserved a programic solution, but found quite hard to tackle when I sat down to try it. I hope that others will find it interesting also.

I will attempt to produce the graphic display program (probably using GD). I will also attempt to make it verify layouts against the rules above.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re: Challenge: 2D random layout of variable-sized rectangular units.
by zentara (Archbishop) on Sep 03, 2006 at 17:56 UTC
UPDATE Sep04,2006 Fixed an error in the second point of the patio rectangle, where I didn't account for the y offset. The patio rectangle will then be bigger.

Well, I figure this is more of an "artistic" endeavor, than 1 of pure mathematical fitting. So of course, I made a Tk visualizer, which allows you do drag pavers from stacks of 99, and rotate them 90 degrees with a right click. Postscript saving included. In order to get a convenient scaling of cm-to-pixel, I've scaled it to cm.

I'm not really a human, but I play one on earth. Cogito ergo sum a bum
heh... nice job++ :)

It really needs a "snap-to-edge" feature though. Especially for somebody as clumsy with a mouse as me ;)

Thanks, I made it as simple as I could. I'm thinking about an improved version, with "snap-to" edges, and 45 degree rotations, so you can get more artistic with the layout.

I'm not really a human, but I play one on earth. Cogito ergo sum a bum
Re: Challenge: 2D random layout of variable-sized rectangular units.
by punch_card_don (Curate) on Sep 03, 2006 at 14:18 UTC
Not a very Perlish answer, but perhaps helpful to a fellow Perl user in real life:

If this an actual real-life project in your backyard, I would just make a point of buying from a store that takes returns. Choose 5 or 6 sizes and buy approximately equal surface areas of each size to equal patio size + ~20%. Lay them out randomly following the rules. You'll spend less time, and get more exercise, working it out on your hands and knees in real time than you'll spend writing a progrma that produces a set of coordinates that almost noone can actually follow. Then, use the time you've saved to enjoy your new patio with your kids.

Like I said, not Perlish, but Perl-coders' real lives are more important than Perl itself. Call me crazy.

Forget that fear of gravity,
Get a little savagery in your life.

I already laid my patio this summer using 300x300 slate pavers. The problem came up whilst researching what to use, and I thought it interesting enough to consider it a perlish (going on) winter project.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Ah - good man.

Of course, once it's developed, you could always sell this program to the paver company for them to use as a marketing tool....

Forget that fear of gravity,
Get a little savagery in your life.
Re: Challenge: 2D random layout of variable-sized rectangular units.
by bart (Canon) on Sep 03, 2006 at 18:30 UTC
In your proposed format for the output, you forgot one thing: rectangular paves can be oriented either horizontally or vertically — thus, rotated over 90°.

Unless you prefer all rectangles to be oriented in the same direction?

The orientation (where it matters Ie. for non-square units), can be derived from the information I listed. If you substract the next unit's X-offset from this unit's X-offset, you have the dimension in the X orientation. Combined with the type letter, this is sufficient.

But you are right. An indication of orientation would be a useful addition.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Challenge: 2D random layout of variable-sized rectangular units.
by pengvado (Acolyte) on Sep 05, 2006 at 20:54 UTC
Interesting problem. Here's my attempt at a random layout generator, using a simple exponential-time backtracking algorithm.

It enforces "no 4-corner joints", but does not enforce "no long straight runs".

The areas covered by each tile type are not necessarily equal: The randomization code looks like they might be equal by number instead of by area, but small tiles fit in more places and so have a higher representation in the final layout.

And a sample output:
```+----+-+----+--+-+----+-+--+---+---+---+--+-+---+--+-+---+--+
|    | |    |  | |    | |  |   |   |   |  | |   |  | |   |  |
|    | |    +-++-+    +-+  |   |   +---+-++-+-+-+  +-+   |  |
|    +-+    | |  |    | +--+   |   |     |    | |  | |   +--+
+-+--+ +---++++--+    | |  +---+   |     |    | +-++-+   |  |
| |  | |   | |   +---++-+  |   |   |     |    +-+ |  |   |  |
+-+--+++-+-+ |   |   |  +--+   +-+-+-+---++---+ +-+-++---++-+
|     |  | | +--++--++--+  |   | |   |    |   | |   |     | |
|     |  | +-+  |   |   |  |   +-+   |    |   +-+   |     +-+
|     |  +-+ |  +-+-+   |  +-+-+ |   |    |   | |   |     | |
+---+-+--+ | |  | | |   +--+ | +-+   +---++--++-+   +--+-++-+
|   |    +-+ +--+++-++--+  | | | |   |   |   |  |   |  | |  |
|   |    | +-+   |   |  +--+-+++-++--+   |   |  +---+  | +--+
+---+    | | |   |   |  |     |   |  |   |   +--+   +--+-+  |
|   +-+--+++-+   |   |  |     |   +--+   |   |  +-+-+    +--+
|   | |   |  |   |   +--+     |   |  +---+   |  | | |    |  |
+---+++---++-+---+   |  +---+-+   |  |   +--+++-+ +-+    +--+
|    |     |     +---+  |   | +-+-+  |   |  | | | | |    |  |
|    |     |     |   +--++-++-+ | +-++-+-++-+ | +-+ +---+++-+
|    |     |     |   |   | |  | | | |  |  | | | | | |   | | |
+----+-----+-----+---+---+-+--+-+-+-+--+--+-+-+-+-+-+---+-+-+

Excellent++. The first attempt to tackle the challenge!

I'm resisting looking at how your code works whilst I complete my attempt. More in a week or so once I've finished my attempt.

I like your output format, though it does present problems for supplying on to other programs, but then it is a pretty good visualisation as is.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Challenge: 2D random layout of variable-sized rectangular units.
by traveler (Parson) on Sep 03, 2006 at 18:04 UTC
You should include any grout line and try to make it uniform. You may not have used grout in your previous project, but for a "stone effect", you may want a fixed (1cm?) grout line around all pavers, but not necessarily along the edges.

(No, I am not trying to add a mathematical complication, just a nicer appearance.)

For the purposes of this exercise, the "grout lines" can be ignored as the nominal sizes of the pavers are actually slightly larger on each dimension to accomodate the pointing. Ie. Just as bricks are nominally sold as being 225 x 112.5 x 75 but actually measure 215 x 102.5 x 65 to accomodate 10mm of mortar.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Errrm, This rule is too simplistic and will result in laying pattern that will not fit together. The algorithm needs to be much more complicated. You have to dynamically adjust the grouting or gap to cater for the different slab sizes. Imagine a very simple arrangement where you have 3 1x1 (flags/pavers/slabs) next to each other, then compare the length against a 1x3 flag and you see the problem, with a 1 cm jointing gap one row is 3 units + 2 cms and the other is just 3 units and they do not fit. We have developed a tool which actually achieves this. For further information contact us at: Nick Deakin Bloom Media UK Ltd http://www.bloommedia.co.uk/services/creative_graphic_design/multimedia_and_3d/index.shtml
Re: Challenge: 2D random layout of variable-sized rectangular units.
by GrandFather (Sage) on Sep 05, 2006 at 23:01 UTC

The following code uses a backtracking technique that gets very slow with increasing size. It precludes long edges, but doesn't check for four tile corners. It attempts to achieve an even distribution of tile areas.

A very stripped down version of Zentra's Tk code is used to display the result and the tile list and placement is also printed.

Update: various bugs fixed and a constant added to control maximum allowed edge length as a fraction of width or height.

Update: the code doesn't scale as poorly as I expected with larger areas to be paved. I guess because it doesn't actually have to do much back tracking until fitting the last tiles so the last couple of "rows" may get relaid multiple times, but hardly ever more than that. The kMaxFrac constant I added can be set to much smaller values than the 0.5 criteria provided by BrowserUK for a maximum edge of half the width or height. In fact it could probably be set in terms of the GCD and be independent of the patio size.

Sample output:

```Rounded dimensions are 1500 mm x 1200 mm
X,    Y,    Type
0,    0,    1 (300 x 300)
300,    0,    3 (450 x 450)
750,    0,    2 (300 x 450)
1050,    0,    2 (450 x 300)
0,    300,    1 (300 x 300)
1050,    300,    3 (450 x 450)
300,    450,    2 (300 x 450)
600,    450,    2 (450 x 300)
0,    600,    1 (300 x 300)
600,    750,    2 (300 x 450)
900,    750,    4 (600 x 450)
0,    900,    6 (600 x 300)

DWIM is Perl's answer to Gödel
Re: Challenge: 2D random layout of variable-sized rectangular units.
by Anonymous Monk on Sep 03, 2006 at 09:19 UTC
What do you mean by 4-corner joints?

I think that these are places where two straight lines intersect:

```         |
|
---------+----------
|
|

These are aesthetically inacceptable as too much structure becomes apparent. So only T-intersections are allowed.

```         |
|
---+-----+----------
|
|
Re: Challenge: 2D random layout of variable-sized rectangular units.
by aquarium (Curate) on Sep 03, 2006 at 12:05 UTC
if you were describing a real world scenario then....areas of particular pattern/size tiles are already known, as there's design involved. that precludes having to write a computed solution. although go ahead if you find this interesting.
the hardest line to type correctly is: stty erase ^H
Re: Challenge: 2D random layout of variable-sized rectangular units.
by BloomMedia on Mar 29, 2007 at 16:14 UTC
We have a working solution to this problem. That allows for the following functions. a) Rounding a target area to nearest slab width without cutting. b) Generating a random patterns using any size slabs, flags or pavers. In addition, repeating patterns can be generated and slabs at the edge or replaced for the correct sizes to minimise cutting. In both cases a bill of quantities is generated c) The random pattern generator avoids cross jointing where 4 corner slab meet. d) Avoids placing an adjacent slab of the same size directly next to each other. e) A GUI for actually planning a scheme with marking out tools, ability to add other garden landscaping features, circles, octagons, sheds etc, slab cutting tools to create organic shapes. f) View either a ouline view, laying pattern view or actual product view. g) All objects in the scene can be passed to a 3d Viualization environment to allow a user to walk around the scheme. Similar in operation to http://www.marshalls.co.uk/transform/garden_visualiser/ However, we use a much better and quicker rendering environment not the Shockwave technology and our proprietary planning tools are a lot easier to use. We have also developed photographic visualisation tools for this market, an example can be seen at: www.brett.co.uk/picturethis Any Software Developers, Web Design Agencies or Interlocking Block Paving Manufactures are welcome to contact us to discuss using these technologies under license. Nick Deakin System Architect Bloom Media ndeakin@bloommedia.co.uk direct line +44 (0) 113 20 50 892 More info at http://www.bloommedia.co.uk/services/creative_graphic_design/multimedia_and_3d/index.shtml

Create A New User
Node Status?
node history
Node Type: perlquestion [id://570906]
Approved by Popcorn Dave
Front-paged by McDarren
help
Chatterbox?
 [erix]: I recognise the makings of a fine argument [LanX]: lanx wonders ... how likely is it to talk >95% BS without intention? [erix]: "gigantic amounts of data" is also not SQLite (imho) talexb wonders why sqlite2 was deprecated in favour of sqlite3. [erix]: looks like a fork, rather, no? LanX /me /me

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (12)
As of 2017-07-28 15:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (431 votes). Check out past polls.