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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

xxxx 1111 
xxxx 1111 
xxxx 1111 

2222 3333 
2222 3333 
2222 3333 

Answer 2

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

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 

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

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

Answer 4

Посмотрите this article from Dr Dobb's Portal на нахождение максимального прямоугольник в вашей ситуации. Это очень подробное обсуждение чрезвычайно эффективного алгоритма, и я думаю, что повторение его итеративно могло бы решить вашу проблему.

Answer 5

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