Как разбить 2D-пейзаж на наименьшее количество прямоугольников?

Question

world - это двумерный массив, заполненный 0 (AIR) или 1 (BLOCK).Задача состоит в том, чтобы разбить world на непересекающиеся прямоугольники, чтобы при склеивании этих прямоугольников вы получили исходный world.Количество прямоугольников должно быть сведено к минимуму (оно не должно быть наименьшим, если это сильно увеличит время вычислений, достаточно мало), а прямоугольники должны выглядеть больше как квадраты, а не как полосы (отношение длин сторон должнобыть ближе к 1, чем к 0).

Я смог придумать алгоритм, но у него есть некоторые проблемы.

Функция center_of_mass возвращает центр масс для прямоугольникаобласть, край.Если в области нет блоков, возвращается None.

def center_of_mass(grid, x1,y1, x2,y2):
    cx = 0
    cy = 0
    mass = 0
    for x in range(x1,x2+1):
        for y in range(y1,y2+1):
            if 0<=x<w and 0<=y<h and grid[x][y] == BLOCK:
                cx += x
                cy += y
                mass += 1
    if mass == 0:
        return None
    else:
        cx = round(cx/mass)
        cy = round(cy/mass)
        return cx, cy

Функция scom находит первый suitable center of mass (SCoM) в прямоугольной области:

if world[center_of_mass] is filled with a block, return coordinates from center_of_mass
else{
    split the grid into 4 rectangles with the division point at center_of_mass
    foreach rect in split_rectangles{
        if scom of rect != None{
            return center_of_mass(rect)
        }
    }
    if wasn't able to find a SCoM or the region is 0-sized, return None
}

def scom(grid, x1,y1, x2,y2):
    p = center_of_mass(grid, x1,y1, x2,y2)
    if p is None:
        return None
    else:
        cx, cy = p
        if grid[cx][cy] != BLOCK:
            if abs(x1-x2)==0 and abs(y1-y2)==0:
                return None
            else:
                px = x1 + (x2-x1)//2
                py = y1 + (x2-x1)//2
                r = [(x1,y1,px,py),(px+1,y1,x2,py),
                     (px+1,py+1,x2,y2),(x1,py+1,px,y2)]
                for rect in r:
                    x = scom(grid, *rect)
                    if x is not None:
                        return x
        else:
            return cx, cy

Следующая функция, stretch, принимает двумерную сетку grid и прямоугольник, который помещается в некоторый кусок блоков и пытается расширить этот прямоугольник во всех 4 направлениях, пока это не станет невозможным.Затем он возвращает развернутый прямоугольник.

def stretch(grid, x1, y1, x2, y2):
    can_grow = True
    while can_grow:
        can_grow = False
        for vec in ((1,0),(0,1),(-1,0),(0,-1)):
            for x,y in extension(x1, y1, x2, y2, vec):
                if (x>=w or x<0 or y>=h or y<0)\
                   or grid[x][y] == AIR or grid[x][y]>BLOCK:
                    break
            else:
                x1,y1,x2,y2 = add_to_rect(x1,y1,x2,y2, vec)
                can_grow = True
    return (x1, y1, x2, y2)

Функция apply_rect принимает угол grid и rect и заменяет все элементы сетки в данном прямоугольнике на указанное число.Числа разные, потому что я хочу визуализировать деление позже.

def apply_rect(grid, rect, n=MARKED):
    for x,y in all_points(*rect):
        grid[x][y] = n

Основная часть алгоритма такова:

По сути, я ищу подходящий центр масс, чтобы датьпрямоугольник много области, чтобы расти так, чтобы они в конечном итоге были более квадратными.Если вместо этого я просто отсканирую сетку, чтобы найти первую ячейку с блоком в ней, у меня будет много полос (я это проверил. Удивительно, но число прямоугольников обычно почти одинаково).

number_of_rects = 0
found = True

while found:
    found = True
    p = scom(world, 0,0, w-1,h-1)

    if p is None:
        found = False
    else:
        x,y = p

    if found:
        rect = stretch(world, x,y, x,y)
        number_of_rects += 1
        apply_rect(world, rect, number_of_rects+3)

Это был ввод:

И это был вывод:

Это почти то, что мне нужно.Однако есть две проблемы:

1. Вычисление занимает более 2 секунд.Если я дам алгоритму изображение размером 320х240, он даст ответ за 40 секунд.Алгоритм необходим в игре, где размер мира может быть 1000x800 или более.Я бы разделил мир на эти прямоугольники в начале и мог бы изменить некоторые регионы во время игры, когда игрок изменяет мир.Несколько минут, чтобы сделать это во время генерации мира, это слишком долго.Это просто проблема с Python или алгоритм неэффективен?

2.Левый угол состоит из квадратов размером с пиксель, а не из одной полосы.Как я могу это исправить?Очевидное решение состоит в том, чтобы сканировать крайний левый столбец и собрать все пиксели в разные прямоугольники.Однако, если бы я разделил игровой мир на более мелкие куски (например, блоки 32х32 или даже меньше) и вместо этого разделил бы эти кусочки на прямоугольники, квадратные спагетти слева могут нарушить эффективное деление. - исправлено.