2

Following up on my previous post that handled this problem in 1-D, I'm trying to extend the solution into two dimensions. Let's say I have an MxN image with predefined bounding boxes of sizes (m1xn1, m2xn2, ... m_nxn_n). How would I go about efficiently finding boxes with a given size lxw.

So far I have the following function from my previous question:

def random_exclude(low: int, high: int, exclude: List[Tuple[int]]) -> int:
  N = -low+sum([(l-h) for l,h in exclude])+high
  r = np.random.randint(low, N)
  for l, h in exclude:
    if r < l:
      return r
    else:
      r+=h
  return r

Which I think is a stepping stone for the function I am trying to build (I've linked below my prior attempt which was running into recursion errors due to my test case detailed below)

def random_bound_box(
        x_low: int, 
        y_low: int,
        x_high: int, # exclusive
        y_high: int, # exclusive
        w: int,
        h: int,
        restrictions: Optional[List[Rectangle]]=None) -> Rectangle:
    x = np.random.randint(x_low, x_high-w)
    y = np.random.randint(y_low, y_high-h)
    ret_rect = Rectangle(x, y, w, h)
    if restrictions and any(ret_rect.intersects(restrict_rect) for restrict_rect in restrictions):
        ret_rect = random_bound_box(x_low, y_low, x_high, y_high, w, h, restrictions)

    return ret_rect

Given that I've defined the Rectangle class to be as follows:

class Rectangle:
    def __init__(self, x: int, y: int, w: int, h: int) -> None:
        self.x = x
        self.y = y
        self.w = w
        self.h = h

    def intersects(self, other: "Rectangle") -> bool:
        if self.x <= other.x <= self.x+self.w:
            return True
        elif self.y <= other.y < self.y+self.h:
            return True
        else:
            return False

This is the test case that I came up with that breaks my previous attempt:

high = 50
size = 9
r1 = Rectangle(10, 10, high, high)
print(random_bound_box(0, 0, high, high, size, size, [r1]))

Note, while this question is relevant, it does not consider the situation where there are pre-existing boxes already placed within the image.

Adithya
  • 63
  • 1
  • 8
  • If I'm reading this correctly, the goal is to count the number of locations where a rectangle of size `WxH` can be placed within a larger rectangle of size `MxN`. The added restriction is that there is a list of rectangles `m[i] x n[i]` that must not overlap with `WxH` rectangle. First question: is that a correct statement of the problem? Second question: do the `m[i] x n[i]` rectangles overlap with each other? – user3386109 Mar 04 '20 at 21:12
  • The goal actually is to find a random such placement of a bounding box. The bounding boxes that are provided may overlap but the randomly generated ones may not. – Adithya Mar 04 '20 at 21:40
  • Right, but in keeping with the previous question, the first step is to count the number of valid locations. Then generate a random number from 0 to `count-1`. Finally, determine the location that corresponds to that random number. This can be done fairly easily if the dimensions of the outer `MxN` rectangle are small. Third question: what are the maximum values for `M` and `N`? – user3386109 Mar 04 '20 at 22:07
  • The images are usually of 480x960. and you're right about the approach. – Adithya Mar 04 '20 at 23:06

0 Answers0