Random shape fill algorithm ?
Hi,
my current project calls for me to tile a rectangular area with a random pattern of rectangular and square shapes taken from a pre-existing list.
The size of each of the shapes in the array of squares and rectangles for tiling are known, as is the rectangular area they must fit into.
Has anybody come across an algorithm or example code ;) that might do this ?
Thanks for any guidance,
Paul
[434 byte] By [
pjohno] at [2007-11-11 7:21:45]
# 1 Re: Random shape fill algorithm ?
you need to choose two patterns randomly? Simply use srand() %2. IF the result is 0 it's a rectangle, otherwise it's a square.
Danny at 2007-11-11 21:02:30 >
# 2 Re: Random shape fill algorithm ?
Danny,
slightly different point. Its not about choosing between shapes as such. I have a rectangular area on the screen, that I need to fill with other shapes.
There are a number of other shapes to choose from to fill the rectangular area. The application currently selects one of these shapes at random and tries to fit it into the rectangle. Given a large enough rectangle this is easy. It then chooses another pattern from the list of shapes and tries to fit that one in with no overlap on the existing shape, (just with edges meeting) and so on.
I think some people refer to the process as tiling and others as packing, but either way, I cant find code to allow me to do it.
My current code goes into an infinite loop as more and more space in the rectangle is filled with shapes :(
Paul
pjohno at 2007-11-11 21:03:30 >
# 3 Re: Random shape fill algorithm ?
This sounds like a version of the "knapsack" np-complete problem. If the tiles are all different shapes and sizes that is?
do you KNOW its infinite loop or just sitting looking for a tile that fits (will complete when it gets lucky)?
Try this:
Sort the tile list by size (area?) or (longest leg?) and randomly choose until the area left is smaller than the largest tile left. Then begin to reduce your Tile set to only choose from tiles that can fit. If your smallest tile wont go, you are "done" (ok what now, nothing will fit, but if you have space un-tiled, is that ok?? if not you have to clear and do over or fill whats left with randomg tiles overlapping old somehow?).
jonnin at 2007-11-11 21:04:24 >
# 4 Re: Random shape fill algorithm ?
jonnin, I'll check into the knapsack idea. The tiles are a variety of rectangular and square shapes of differing sizes, but they they are all of either rectangle or square. I dont need to deal with other shapes like circles etc. The idea is that it is random pattern, so potentially I can have a rectangle in one of two different orientations, either horizontal or 'vertical'
Hair starting to pull out ...... :-)
Paul
pjohno at 2007-11-11 21:05:24 >
# 5 Re: Random shape fill algorithm ?
its still similar to that problem. The sorted tile list should get you close but has a couple of problems (its not random if you fill from say top to bottem because a large tile will never appear at the bottem, and if you fill randomly its a whole different set of problems), and you can be left with say a 1X1 untiled square (what now??). Of course the point of the problem might just be to introduce you to unsolvable problem theory ;)
(it may be solvable, depends on constraints & rules).
jonnin at 2007-11-11 21:06:33 >
