Break up a square or rectangle into a large number of randomly sized squares or rectangles

Question

I'm trying to break up a square or rectangle into a large number of randomly sized squares or rectangles so that none are overlapping.

Ok of course others have asked this the best thread I found is How to fill a square with smaller squares/rectangles?

The solution seems to be either through bin packing or some sort of tree map.

But what I'm looking for is the actual algorithm in Java, Javacript , actionscript or even C.

Answer 1

The provided code creates a k-d tree. You can use this to draw lines on your rectangle that will divide it into smaller rectangles. After you've got your tree you can use it as follows to divide your region up into these rectangles:

1. Pick the node at the root of the tree.
2. Draw a vertical line through this point.
3. Choose it's left child, draw a horizontal line through this point on the left side of the line you just drew through it's parent (this line stops at the line you just drew).
4. Choose it's right child, draw a horizontal line through this point on the right side of the line you just drew through it's parent (this line also stops at the line you drew through the parent).
5. Do this recursively, switching between vertical and horizontal lines at each level of the tree.

Code:

int MAX_HEIGHT = 100;
int MAX_WIDTH = 100;
int NUM_POINTS = 6;


// Generate random list of points
List<Point> pointList = new List<Point>();

Random rand = new Random();

for(int i = 0; i < NUM_POINTS ; i++)
{
    pointList.add(new Point(rand.nextInt(MAX_HEIGHT), rand.nextInt(MAX_WIDTH));
}

BinaryTree tree = CreateKDTree(pointList, 0);


// Recursive function for creating a K-D Tree from a list of points
// This tree can be used to draw lines that divide the space up
// into rectangles.
public BinaryTree CreateKDTree(List<Point> pointList, int depth)
{
    // Have to create the PointComparator class that just selects the
    // specified coordinate and sorts based on that
    Coordinate coord= depth % 2 == 0 ? X_COORDINATE : Y_COORDINATE
    Collections.sort(pointList, new PointComparator(coord));

    int median = pointList.size() / 2;

     // unfortunately Java doesn't have a BinaryTree structure so
     // you have to create this too
    BinaryTree node = new BinaryTree(pointList[median]);

    if(pointList.size() == 1) return node;

    if(median > 0)
        node.left(CreateKDTree(pointList.subList(0, median), depth + 1);

    if(median + 1 < subList.size())
        node.right(CreateKDTree(pointList.subList(median + 1, subList.size()), depth + 1);

    return node; 
}

Answer 2

A solution would be to try the "Divide and Conquer" technique. In iteration 1 you have a rectangle. Divide the rectangle in two smaller ones. A way to do that is the following . Lets say the rectangle is 100x50 .Choose a random number between 0-100 (the length of the rectangle).Lets say the random number is 20. Then you can spit your rectangle in two smaller ones with sizes 20x50 and 80x50. For these 2 new rectangles apply recursively the same procedure.(hence in iteration 2 you will have 4 rectangles). Do that n -times and you will have 2^n rectangles. Also in each iteration you could randomly choose if the spitting should be done by the length (vertical) or width (horizontal) of each rectangle.

hope it helps!

Answer 3

Randomly divide the length into x parts

Now, randomly divide each smaller rectangle individually into y parts

Here's some ActionScript code (written in notepad, you'll have to check for errors). It takes the width and height of the input rectangle and returns an array with the vertices of the divided rectangles

private function divRect(w:Number, h:Number):Array {
    var rw:Number=0, rh:Number=0;
    var wa:Array=[0], rv:Array=[];
    while(rw < w) {
        var r:Number=Math.random() * (w-rw);
        wa.push(r+rw);
        rw+=r;
    }

    for(var i:int=1; i<wa.length; i++) {
        while(rh < h) {
            var o:Object={x: wa[i-1], x2: wa[i]};
            var s:Number=Math.random() * (h-rh);
            o.y=rh;
            rh+=s;
            o.y2=rh;
            rv.push(o);
        }

    }

}