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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

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

Answer 3

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

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

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

Приведет к:

skip 2
draw 3
skip 3
draw 4
skip 1

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

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

Answer 4

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

Answer 5

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