배치와 연결 (1) - 빈 공간 찾아서 상자 배치하기


빈 공간 찾아서 상자 놓기

위 그림과 같은 너비 10, 높이 10의 평면에 세 개의 파란색 상자가 놓여져 있습니다.

이 평면에 특정한 너비와 높이를 갖는 새로운 상자를 놓을 위치를 찾는 방법을 소개합니다.




1) 평면 공간 만들기

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches

width, height = 10, 10
canvas1 = np.zeros((height, width))
rect_info = [(2, 4, 3, 2), (3, 1, 4, 2), (6, 5, 3, 4)]

print('Before Placement:')
print(canvas1)
Before Placement:
[[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]

np.zeros() 함수를 사용해서 너비 (width)/높이 (height)가 10이고 모두 0을 갖는 NumPy 어레이 canvas1을 만들었습니다.

rect_info는 이 평면에 놓여질 사각형 상자 정보 ((x, y, w, h))의 리스트입니다.




2) 상자 배치하기

def draw_rect(canvas, rectangles):
    for i, (x, y, w, h) in enumerate(rectangles):
        canvas[y:y+h, x:x+w] = i + 1

draw_rect(canvas1, rect_info)

print('After Placement:')
print(canvas1)
print(rect_info)
After Placement:
[[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 2. 2. 2. 2. 0. 0. 0.]
 [0. 0. 0. 2. 2. 2. 2. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 1. 1. 0. 0. 0. 0. 0.]
 [0. 0. 1. 1. 1. 0. 3. 3. 3. 0.]
 [0. 0. 0. 0. 0. 0. 3. 3. 3. 0.]
 [0. 0. 0. 0. 0. 0. 3. 3. 3. 0.]
 [0. 0. 0. 0. 0. 0. 3. 3. 3. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]
[(2, 4, 3, 2), (3, 1, 4, 2), (6, 5, 3, 4)]

drawRect()는 2차원 어레이 (canvas)와 사각형 상자 정보를 입력받아서 배치하는 함수입니다.

세로 방향을 높이로, 가로 방향을 너비로 표시되도록 했습니다.




3) 새 상자 놓을 위치 찾기

new_rect = [0, 0, 4, 4]

def find_place(canvas, rectangle):
    w_rect, h_rect = rectangle[2], rectangle[3]
    options = []
    for i in range(height - h_rect + 1):
        for j in range(width - w_rect + 1):
            if not np.any(canvas[i:i+h_rect, j:j+w_rect]):
                options.append((j, i))

    rand = np.random.randint(len(options))
    return options[rand]

new_x, new_y = find_place(canvas1, new_rect)
new_rect[0:2] = new_x, new_y

rect_info.append(tuple(new_rect))
print(rect_info)
[(2, 4, 3, 2), (3, 1, 4, 2), (6, 5, 3, 4), (1, 6, 4, 4)]

new_rect는 새롭게 놓을 상자의 정보입니다. 너비 높이가 4이고, x, y 위치는 우선 0으로 지정했습니다.

find_place()함수는 평면 공간에서 새로운 상자를 놓을 수 있는 위치의 후보를 찾아서 그 중 하나의 위치를 반환합니다.

not np.any(canvas[i:i+h_rect, j:j+w_rect])는 평면 공간 i, j의 위치에서 새로운 상자의 너비와 높이만큼의 공간이 비어있는지 확인합니다.

options는 새로운 상자를 놓을 수 있는 위치들의 후보를 갖는 리스트입니다.

np.random.randint() 함수를 사용해서 임의의 성분을 반환하도록 하고,

rect_info 리스트에 새로운 상자의 정보를 튜플의 형태로 변환해서 추가합니다.




4) 새 상자 배치하기

draw_rect(canvas1, rect_info)

print('After New Placement:')
print(canvas1)
print(rect_info)
After New Placement:
[[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 2. 2. 2. 2. 0. 0. 0.]
[0. 0. 0. 2. 2. 2. 2. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 1. 1. 1. 0. 0. 0. 0. 0.]
[0. 0. 1. 1. 1. 0. 3. 3. 3. 0.]
[0. 0. 4. 4. 4. 4. 3. 3. 3. 0.]
[0. 0. 4. 4. 4. 4. 3. 3. 3. 0.]
[0. 0. 4. 4. 4. 4. 3. 3. 3. 0.]
[0. 0. 4. 4. 4. 4. 0. 0. 0. 0.]]
[(2, 4, 3, 2), (3, 1, 4, 2), (6, 5, 3, 4), (1, 6, 4, 4)]

새 상자를 포함해서 다시 평면에 상자를 배치했습니다.

네번째 상자가 빈 공간에 배치된 것을 볼 수 있습니다.




5) Matplotlib 시각화하기

plt.style.use('default')
plt.rcParams['figure.figsize'] = (6, 6)
plt.rcParams['font.size'] = 12

fig, ax = plt.subplots()
for (x, y, w, h) in rect_info:
    ax.add_patch(
        patches.Rectangle(
            (x, y), w, h,
            edgecolor='royalblue',
            facecolor='lightsteelblue',
            linewidth=0.5,
            fill=True))

ax.axis((0, 10, 10, 0))
ax.xaxis.tick_top()
plt.show()

위 코드는 네 개의 상자들의 정보를 갖는 리스트 rect_info를 Matplotlib를 사용해서 시각화합니다.

Matplotlib patches 모듈을 사용해서 도형 시각화하기 페이지를 참고하세요.

axis()를 사용해서 축의 범위를 지정하고, tick_top()으로 X축 눈금을 상단에 위치하도록 했습니다.

결과는 아래와 같습니다.


빈 공간 찾아서 상자 놓기




전체 코드는 아래와 같습니다.

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches

width, height = 10, 10
canvas1 = np.zeros((height, width))
rect_info = [(2, 4, 3, 2), (3, 1, 4, 2), (6, 5, 3, 4)]

print('Before Placement:')
print(canvas1)

def draw_rect(canvas, rectangles):
  for i, (x, y, w, h) in enumerate(rectangles):
      canvas[y:y+h, x:x+w] = i + 1

draw_rect(canvas1, rect_info)

print('After Placement:')
print(canvas1)
print(rect_info)

new_rect = [0, 0, 4, 4]

def find_place(canvas, rectangle):
  w_rect, h_rect = rectangle[2], rectangle[3]
  options = []
  for i in range(height - h_rect + 1):
      for j in range(width - w_rect + 1):
          if not np.any(canvas[i:i+h_rect, j:j+w_rect]):
              options.append((j, i))

  rand = np.random.randint(len(options))
  return options[rand]

new_x, new_y = find_place(canvas1, new_rect)
new_rect[0:2] = new_x, new_y

rect_info.append(tuple(new_rect))
# print(rect_info)

draw_rect(canvas1, rect_info)

print('After New Placement:')
print(canvas1)
print(rect_info)

plt.style.use('default')
plt.rcParams['figure.figsize'] = (6, 6)
plt.rcParams['font.size'] = 12

fig, ax = plt.subplots()
for (x, y, w, h) in rect_info:
  ax.add_patch(
      patches.Rectangle(
          (x, y), w, h,
          edgecolor='royalblue',
          facecolor='lightsteelblue',
          linewidth=0.5,
          fill=True))

ax.axis((0, 10, 10, 0))
ax.xaxis.tick_top()
plt.show()


이전글/다음글