Как разделить область, составленную из маленьких квадратов, на большие прямоугольники?

Question

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

В более практическом объяснении: я рисую сетку, которая представлена ​​числом квадратов, и я хочу найти способ объединить столько смежных квадратов в прямоугольники, сколько возможно, чтобы сократить затраченное время на велосипеде через каждый квадрат и рисование его.

Максимальная эффективность не нужна, скорость важнее.

Приложение: По-видимому, то, что я ищу, кажется техникой, называемой тесселяцией. Теперь мне нужно только найти хорошее описание для этого конкретного случая.

Приложение 2: Граница квадратов "1" будет нерегулярной, а в некоторых случаях даже не связана, так как распределение квадратов "1" будет совершенно случайным. Мне нужно, чтобы эти неправильные формы были определены и разбиты на правильные прямоугольники.

Правильный ответ: Чтобы получить наилучший баланс между скоростью и эффективностью, оптимально использовать данные сетки для заполнения четырехугольного дерева, причем каждый узел имеет значение состояния либо пустое / частично заполненное / заполненное .

Answer 1

Взгляните на эту статью из портала Доктора Добба о поиске максимального прямоугольника в вашей ситуации. Это очень подробное обсуждение чрезвычайно эффективного алгоритма, и я думаю, что повторное его повторение, возможно, решит вашу проблему.

Answer 2

Поскольку вы не ищете минимальное количество квадратов, я бы предложил использовать компромисс, который по-прежнему сохраняет ваш алгоритм простым.

Какое наилучшее решение зависит от ваших данных, но одна простая альтернатива - просто собрать ящики вдоль одной строки. То есть:

0 0 1 1 1 0 0 0 1 1 1 1 0

Результатом будет:

skip 2
draw 3
skip 3
draw 4
skip 1

Это уменьшит количество вызовов для рисования ящиков без необходимости кэширования (т.е. вы можете создавать свои ящики на лету).

Если вы хотите создать большие коробки, я бы предложил алгоритм обратного отслеживания, где вы найдете первую 1 и попытаетесь расширить коробку во всех направлениях. Составьте список полей и снимите 1: s, как вы их использовали.

Answer 3

Я сделал нечто похожее для быстрой и грязной воксельной визуализации 3d-блоков с OpenGL.

Я начал с верхнего левого ящика и сохранил пустой / заполненный флаг. Затем я попытался расширить прямоугольник вправо, пока не нажму на коробку с другим флагом. Я сделал то же самое в направлении вниз.

Нарисуйте прямоугольник, если он заполнен.

Если есть оставшиеся блоки, рекурсивно повторите процедуру для всех трех оставшихся прямоугольников, вызванных последним прямоугольником, которые находятся справа, снизу и справа внизу:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 4

Мне пришлось решить аналогичную проблему, мой алгоритм поддерживает зубчатые массивы, я тщательно протестировал и прокомментировал это, но это медленнее, чем предложение Джоэля-ин-Гё: https://stackoverflow.com/a/13802336

Answer 5

Итак, вы ищете прямоугольную границу квадратов 'ON'?
Вы хотите внутреннюю или внешнюю границу?
то есть. Должна ли граница иметь только квадраты «ON» или вы хотите, чтобы прямоугольник содержал все квадраты «ON» в группе?