Search

 
Problem Description
Here's a program illustrating an efficient
way to exactly cover a given rectangle reasonable shaped rectangles.
Background & Techniques
"Robot Rooms" implements an algorithm for exactly
covering a rectangular area with random rectangles meeting certain size and
shape constraints. The authors' 2001 paper "Data Set
Generation for Rectangular Placement Problems", C. L. Valenzuela and P. Y.
Wang, is available at
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3218
The paper slightly complex but well presented and requires no
more than high school math and a few hours of study to digest. It proves the
existence of exact rectangle coverings with rectangles that are constrained
by aspect ratio (are not too long and narrow) and by area ratio (restricts
range in size). The proofs provide the basis for an included algorithm
for generating random coverings.
It was just what a long time DFF viewer needed generate a random arrangement of
rectangles (rooms) for a Delphi investigation of intelligent robot behavior.
I helped him by providing a way to create "doorways" connecting adjacent
rooms. I found the problem so interesting that I independently implemented
the "room generator" algorithm as well.
The program allows user control of base size, aspect and area ratios, and number of
rooms to create. Two features used for debugging were retained : 1.)
an option to display text for generated rectangles and 2.) the random seed
used to generate each set of rooms. This can be useful for generating the
same set of rooms multiple times.
Notes for programmers
The paper referenced above proceeds step by step proving several theorems
working up to:
1. Theorems 1 through 4: Given an aspect ratio, ρ
(Greek letter Rho), representing
H/W of a rectangle, and a starting rectangle whose aspect ratio is between
1/ρ and ρ,
it is possible to subdivide the starting rectangle into an arbitrary number
of smaller rectangles, each of which meet the same aspect ratio criteria.
2.Theorem 5: Given an area ratio. ϒ
(Greek letter Upsilon), representing largest area divided by smallest area of a set of rectangles, it is possible
to subdivide any starting rectangle into an arbitrary number of
smaller rectangles, each set of which meet the area ratio criteria.
3. Theorem 6: Theorems 1 through 5 can apply to a starting rectangle meeting the
aspect ration initial condition. This allows arbitrary subdivision into as
many rectangles as desired, each meeting both Rho and Upsilon conditions and
cumulatively exactly covering the original rectangle.
The algorithm for implementing Theorem 6 :
 How to choose the rectangle to split next which will maintain the
area ratio condition , 
 The direction (or directions) in which to divide the rectangle
(horizontally or vertically), and the range of offsets from the
top or left end of an edge which will maintain both the aspect and area
ratio conditions.. 
Although the procedure described is recursive in nature, (each rectangle
has the same steps applied) it seemed natural to implement the solution as a
loop:
 While more rectangles are needed
 Select a rectangle to split
 Get area, m, of largest
rectangle 
 Make a list of rectangles whose
area is > 2m/ρ 
 Randomly select one. 

 Split it.
 If selected rectangle can be
split either Horizontally or Vertically, randomly choose one.
Otherwise just use the only valid direction. 
 For split direction chosen,
calculate the valid range of offsets. 
 Select random split point within
this range to define a new right or bottom edge. 
 Replace existing rectangle
definition with left or top rectangle and create a new
rectangle defining the right or bottom portion the split.



 End 
Everything else, as they say, is details.
The "door generator" portion of the
program makes vertical doorways by sorting the rectangles by increasing left edge X
offsets within top edge Y offsets and then checks top and bottom edge lines
with the following rectangles looking
for vertical edges which are colinear and overlap. Given two colinear
edges, function Overlap returns offsets of the overlapping portion. These overlap
line segments are candidates
for receiving a doorway if they are wider than the specified door width.
The same process, sorting by increasing Y coordinates within left edge offsets will find
candidates for horizontal doors.
Running/Exploring the Program
Suggestions for Further Explorations
Original Date: January 10, 2012 
Modified:
February 18, 2016 


