Нахождение незанятых ограничивающих рамок на изображении по набору занятых рамок - PullRequest
Новая
       5

Нахождение незанятых ограничивающих рамок на изображении по набору занятых рамок

2 голосов
/ 04 марта 2020

В продолжение моего предыдущего поста, который рассматривал эту проблему в 1-D , я пытаюсь расширить решение в двух измерениях. Допустим, у меня есть изображение MxN с предопределенными ограничивающими прямоугольниками размеров (m1xn1, m2xn2, ... m_nxn_n). Как бы я go об эффективном поиске ящиков с заданным размером lxw.

Пока у меня есть следующая функция из моего предыдущего вопроса: 

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

Который я считаю ступенькой для функции, которую я пытаюсь построить (я связал ниже мою предыдущую попытку, которая приводила к ошибкам рекурсии из-за моего теста, описанного ниже) 

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

Учитывая, что я определил класс Rectangle для быть следующим: 

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

Это тестовый пример, который я придумал, который ломает мою предыдущую попытку: 

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

Обратите внимание, в то время как этот вопрос релевантный, он не учитывает ситуацию, когда уже существующие рамки уже размещены на изображении.

...