[FIXED] Algorithm for generating a non-overlapping rectangles

Issue

I'm working on a problem where I need to generate a rectangle (let's call it 'box') within a larger rectangle ('field'), ensuring that the box doesn't overlap with a smaller rectangle ('window') contained within the field. For simplicity, all the coordinates are integers greater or equal to 0.

Here's the specific problem:

• I have the coordinates of the lower left corner (LL) and upper right corner (UR) of both the field (light blue) and the window (white).
• The randomly generated box (dark blue) needs to be completely within the field but should have no common points and no overlaps with the window.

I've managed to solve the problem in the 2D case. However, my solution involved tedious consideration of all possible relations between the random coordinates of the box with respect to the field and the window.

Now, I'm looking for a more generalized and robust algorithm (if any) that can handle dimensions larger than 2. For instance, considering all possibilities in 3D would be extremely complex.

Could someone provide guidance or an algorithm for this generalized case? I'm implementing this in Python and using NumPy for numerical operations. Any insights or code snippets would be highly appreciated. Thank you!

Solution

The approach has two steps:

• Generate a random box that is inside the field -- this is trivial
• Verify that the box has no overlap with the window. This consists of the following check per dimension:
  • Get the extent of the window in the chosen dimension (you get a low and high coordinate)
  • Get the same for the box in the same dimension.
  • Check whether these two line segments are non-overlapping. If so, we can stop here: the box and the window have no overlap.
• If for none of the dimensions the condition was true, the box and window overlap.

Here is an implementation:

from random import randint 

def has_overlap(box1, box2):
    return all(
        high1 >= low2 and high2 >= low1
        for low1, high1, low2, high2 in zip(*box1, *box2)
    )

def generate_box_inside(field):
    return tuple(zip(*(
        sorted([randint(low, high), randint(low, high)])
        for low, high in zip(*field)
    )))

def generate_box(field, window):
    for _ in range(100):  # Make 100 attempts before giving up
        box = generate_box_inside(field)
        if not has_overlap(box, window):
            return box
        print("box", box, "overlaps window", window, "Retrying...")

    print("give up")

# Example run
field = ((0, 0), (100, 100))
window = ((70, 80), (120, 90))
box = generate_box(field, window)
if box:
    print("Found a suitable box", box)

You can replace all coordinate-tuples with 3D tuples, and it will work too. The condition is that the first tuple's coordinates are all less than the corresponding member of the second tuple (both for field and for window).

Answered By - trincot