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

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

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