How to randomly place rectangle inside a larger bounding rectangle without intersecting other rectangles inside

Question

Let us consider the case: there is an overall bounding rectangle (call this Rb) which contains a number of rectangles within it (call this set SRo). Now I would like to randomly position a new rectangle with known bounds (call this Rn) within the bounds of Rb without intersecting any of the rectangles in the set SRo

My current approach is rather brute force:

1. Generate random x-y coordinates for new rectangle
2. Check Rb contains Rn if it is placed at intended coordinates
3. Check Rn does not intersect any of rectangles inside set SRo

Anyone got any better idea?

Answer 1

Recursive subdivision is one simple and guaranteed finite-time solution, though it tends to look a little... non-uniform. The end result is reminiscent a bit of a mondrian painting and doesn't look exactly like random scattered rectangles. If that's still good enough for you, the algorithm is:

makeRects(x, y, width, height)
    if shouldSubdivide(width * height) then
        // pick which way to split it, tend towards making
        // the resulting pieces closer to square
        if random(width + height) < width then
            // split vertically
            var split = random(width)
            makeRects(x, y, split, height)
            makeRects(x + split, y, width - split, height)
        else
            // split horizontally
            var split = random(height)
            makeRects(x, y, width, split)
            makeRects(x, y + split, width, height - split)
        end
    else
        // not splitting the box, so just draw a rectangle inside it
        randomRect(x, y, width, height)
    end
end

// randomly inset the rect within the given bounds
randomRect(x, y, width, height)
    var insetWidth = random(width)
    var insetHeight = random(height)
    var insetX = random(width - insetWidth)
    var insetY = random(height - insetHeight)
    placeRect(x, y, width, height)
end

// determine if a rect of the given area should be
// subdivided, or if its small enough that we should
// stop here
shouldSubdivide(area)
    // return true or false. the smaller the area, the more
    // likely to be false. tune to taste...
end

random(max)
    // generate random value between 0 and max...
end

placeRect(x, y, width, height)
    // do whatever you want here to place the rect...
end

Answer 2

This sounds similar to a collision-detection problem. Look at "spacial partitioning" to sub-divide Rb, and find the set of open spaces in which Rn would fit. Randomly select one of those spaces, and place Rn randomly within it.

Answer 3

If don't run that algorithm too often (eg. just at startup-time) and there aren't thousands of rectangles, I'd probably just stick with the brute-force approach.

You could already eliminate a lot of unnecessary trial/error attempts, by combining step 1 and 2 into one step. To do this, just make sure you generate random x and y coordinates that are guaranteed to be inside Rb.

Example in pseudo-code, assumes that random() returns a value from 0-1 and that y-axis points down (screen-space).

y = Rb.minY + (random() * (Rb.height - Rn.height))
x = Rb.minX + (random() * (Rb.width - Rn.width))

Then check the rectangle position against all the already placed rectangles. If it intersects another rectangle, restart at step 1.

Depending on the generated random-values, this approach could need a lot of tries to be successful though. An optimization would be to divide your containing rectangle (Rb) into sections and increase a counter for each section that intersects a placed rectangle. Then pick random coordinates from sections with a low "rectangle-count" in step 1.

If you try to place a lot of rectangles into Rb (so that a big part of the area of Rb is covered), the brute-force approach is a very bad choice, since there's a very high probability that it will fail (endless loop).

Maybe also have a look at this answer over at stackoverflow for another approach.

Answer 4

Sounds like a fair implementation, there is no simple trick for avoiding doing a fair amount of checking. If you have got a performance problem then show us your code, otherwise just stick with it.

Answer 5

Depending on the layout of rectangles already inside, if you find that brute-force is taking too many iterations (i.e. that there are too few valid spaces to put a new rectangle after some point in time), an alternative might be to iterate through the entire bounding box, making a list of all valid positions where the new smaller box can go. Then, choose a random element from that list. Worst-case O(x*y) time, which is at least better than the random worst-case O(infinity).

Answer 6

I used a greedy approach:

• Rectangularize the overall (global) rectangle: create a grid from the sorted x & sorted y coordinates of all rectangles so far. So that will give you an irregular (but rectangular) grid.
• For each grid cell calculate the area, this gives you a matrix of areas.
• Use Kadanes 2D algorithm to find the sub matrix that gives you the maximum area (= the largest free rectangle)
• Place a random rectangle in that free space
• Repeat

This requires a conversion from your original coordinate space to/from the grid space but straightforward to do.

(Note that running Kadene directly on the original, global rectangle takes to long. Going via a grid approximation is plenty fast for my application)