3

I am looking for a sound algorithm that would randomly place a given number of rectangles of the same size into a bigger rectangle (canvas).

I see two ways to do it:

  1. create an empty array that will contain the rectangles already placed on canvas. start with the empty canvas. in a loop, pick a position at random for a new rectangle to be placed. check if the array has a rectangle that overlaps with the new rectangle. if it does not, put the new rectangle in to the array and repeat the loop. otherwise, pick a new position, and rerun the check again. and so on. This might never terminate (theoretically) I think. I do not like it.

  2. use a grid and place rectangles into the cells randomly. This might still look like a grid placement. I do not like it either.

any better ways to do it? "better" meaning more efficient, or more visually "random" than the grid approach. better in any respect.

Ciro Santilli OurBigBook.com
  • 347,512
  • 102
  • 1,199
  • 985
akonsu
  • 28,824
  • 33
  • 119
  • 194
  • Possible duplicate (this one deals with non-uniform rectangles): http://stackoverflow.com/questions/716558/place-random-non-overlapping-rectangles-on-a-panel – nodakai Mar 08 '12 at 05:08
  • the question linked discusses optimal 2D packing – akonsu Mar 08 '12 at 05:10
  • If the rectangles are not rotated (so parallel with X- and Y-axis), then you could use quad-trees to find overlaps with other rectangles in a faster way. – Patrick Mar 08 '12 at 05:30

3 Answers3

1

Here is a simple heuristic. It will be non-overlapping and random.

Place a rectangle randomly. Then, calculate the intersections of extensions of the the two parallel edges of the first rectangle with the edges of the canvas. You will obtain four convex empty regions. Place other rectangles in these empty regions one-by-one independently and calculate the similar divisions for placements. And try to put the remaining rectangles in empty regions.

You can try different strategies. You can try to place the rectangles close to the corners. Or, you can place them around the center of the regions. We cannot discuss optimality because you introduced randomness.

delete_this_account
  • 2,376
  • 7
  • 23
  • 31
0

I create internal room-like dungeons using the following method.

1) Scatter N points at random, but not within a few pixels of each other. 2) For each point in turn, expand if possible in all four directions. Cease expanding if you hit another rectangle. 3) Cease the algorithm when no rooms can expand.

The result is N rectancles with just a few rectangular small spaces.

Code is in the binary image library

https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/dungeongenerator3.c #

Malcolm McLean
  • 6,258
  • 1
  • 17
  • 18
0

You might find Quadtrees or R-trees useful for your purpose.

Murat Derya Özen
  • 2,154
  • 8
  • 31
  • 44