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

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

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

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

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

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

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


area geometry 2d rectangles
person Mithaldu    schedule 02.11.2008    source источник
comment
Максимальная эффективность не нужна, важнее скорость. - Хм? Я предполагаю, что вы имеете в виду, что мне не нужно абсолютное минимальное количество прямоугольников, просто что-то, что делает хорошее приближение, быстро...?   -  person Roger Lipscombe    schedule 02.11.2008
comment
О, и вы доказали, что циклическое прохождение каждого квадрата является узким местом вашей производительности?   -  person Roger Lipscombe    schedule 02.11.2008
comment
Что касается приближения, то да. Я в основном ищу наиболее сбалансированное решение с точки зрения эффективности и скорости. Кроме того, да, я на 100% уверен, что зацикливание является узким местом из-за того, что Perl намного медленнее, чем сам OpenGL.   -  person Mithaldu    schedule 02.11.2008
comment
Ваши данные статичны? т.е. стоит кешировать?   -  person Peter Olsson    schedule 02.11.2008
comment
В зависимости от использования он меняется примерно каждые 3-30 минут. На самом деле этот алгоритм будет применяться при создании другого кеша. Конечная цель — получить ограничительную рамку для проверки окклюзии во время 3D-рендеринга.   -  person Mithaldu    schedule 02.11.2008

Ответы (5)


arrow_upward
2
arrow_downward

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

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

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

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

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333
person Daniel Rikowski    schedule 02.11.2008
comment
Да, это то, что я буду делать, если кто-то другой не придумает лучшее решение. :) - person Mithaldu; 02.11.2008

arrow_upward
3
arrow_downward

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

person Joel in Gö    schedule 03.04.2009

arrow_upward
1
arrow_downward

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

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

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, как вы их использовали.

person Peter Olsson    schedule 02.11.2008
comment
Да, это почти то, что я ищу. Я уже думал о том, чтобы сделать это в 1-мерном пространстве, но надеялся, что кто-то уже потратил время на размышления о том, как сделать это в 2-х измерениях. - person Mithaldu; 02.11.2008

arrow_upward
0
arrow_downward

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

person Martin Beckett    schedule 02.11.2008
comment
Добавлено объяснение в качестве дополнения 3. Спасибо за помощь в разъяснении. :) - person Mithaldu; 02.11.2008

arrow_upward
0
arrow_downward

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

person gouessej    schedule 03.03.2016