title: Finding unoccupied bounding boxes in an image given a set of occupied boxes
body: <p>Following up on <a href="https://stackoverflow.com/questions/60527008/generate-random-number-but-exclude-multiple-ranges-without-looping">my previous post that handled this problem in 1-D</a>, 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.</p>
  
  <p>So far I have the following function from my previous question:</p>
  
  <pre class="lang-py prettyprint-override"><code>def random_exclude(low: int, high: int, exclude: List[Tuple[int]]) -&gt; 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 &lt; l:
        return r
      else:
        r+=h
    return r
  </code></pre>
  
  <p>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)</p>
  
  <pre><code>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) -&gt; 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
  </code></pre>
  
  <p>Given that I've defined the Rectangle class to be as follows:</p>
  
  <pre class="lang-py prettyprint-override"><code>class Rectangle:
      def __init__(self, x: int, y: int, w: int, h: int) -&gt; None:
          self.x = x
          self.y = y
          self.w = w
          self.h = h
  
      def intersects(self, other: "Rectangle") -&gt; bool:
          if self.x &lt;= other.x &lt;= self.x+self.w:
              return True
          elif self.y &lt;= other.y &lt; self.y+self.h:
              return True
          else:
              return False
  </code></pre>
  
  <p>This is the test case that I came up with that breaks my previous attempt:</p>
  
  <pre class="lang-py prettyprint-override"><code>high = 50
  size = 9
  r1 = Rectangle(10, 10, high, high)
  print(random_bound_box(0, 0, high, high, size, size, [r1]))
  </code></pre>
  
  <p>Note, while <a href="https://stackoverflow.com/questions/4373741/how-can-i-randomly-place-several-non-colliding-rects">this question</a> is relevant, it does not consider the situation where there are pre-existing boxes already placed within the image.</p>