Как разделить область, состоящую из маленьких квадратов, на большие прямоугольники?
Где мне искать алгоритмы, которые принимают 2-мерную сетку значений, равных 0 или 1, в качестве входных данных, а затем идентифицируют в ней все возможные неперекрывающиеся прямоугольники?
В более практическом объяснении: я рисую сетку, которая представлена несколькими квадратами, и я хочу найти способ объединить как можно больше смежных квадратов в прямоугольники, чтобы сократить время, затрачиваемое на циклическое прохождение каждый квадрат и его рисование.
Максимальный КПД не нужен, важнее скорость.
Приложение: По-видимому, то, что я ищу, похоже на технику, называемую тесселяцией. Теперь мне нужно только найти хорошее описание для этого конкретного случая.
Приложение 2: Граница квадратов «1» будет неправильной, а в некоторых случаях даже не соединенной, так как распределение квадратов «1» будет полностью случайным. Мне нужно, чтобы эти неправильные формы были идентифицированы и разбиты на правильные прямоугольники.
Правильный ответ: Для достижения наилучшего баланса между скоростью и эффективностью оптимально использовать данные сетки для заполнения дерева квадратов с каждым узлом, имеющим значение статуса либо пустой / частично заполненный / заполненный.
О, и вы доказали, что циклическое прохождение каждого квадрата является узким местом для вашей производительности?
Что касается приближения, да, это так. Я в основном ищу наиболее сбалансированное решение по соотношению эффективности и скорости. Кроме того, да, я на 100% уверен, что цикличность является узким местом из-за того, что Perl намного медленнее, чем сам OpenGL.
Ваши данные статичны? Т.е. стоит кешировать?
В зависимости от использования он меняется примерно каждые 3-30 минут. Фактически, этот алгоритм будет применяться при создании другого кеша. Конечная цель - получить ограничивающую рамку, которая будет использоваться при проверках окклюзии во время 3D-рендеринга.
Ответы 5
Итак, вы ищете прямоугольную границу квадратов ON?
Вы хотите внутреннюю или внешнюю границу?
т.е. Должна ли граница содержать только квадраты «ON» или вы хотите, чтобы прямоугольник содержал все квадраты «ON» в группе?
Добавлено объяснение в виде приложения 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: s, как вы их использовали.
Да, это в значительной степени то, что я ищу. Я уже думал о том, чтобы сделать это в одном измерении, но надеялся, что кто-то уже потратил время на размышления о том, как сделать это в двух измерениях.
Я сделал нечто подобное для быстрой и грязной воксельной визуализации трехмерных блоков с помощью OpenGL.
Я начал с верхнего левого поля и сохранил флаг пустой / заполненный. Затем я попытался расширить прямоугольник вправо, пока не наткнулся на прямоугольник с другим флагом. Я сделал то же самое в направлении вниз.
Нарисуйте прямоугольник, если он залит.
Если есть оставшиеся блоки, рекурсивно повторите процедуру для всех трех оставшихся прямоугольников, созданных последним прямоугольником, которые являются правым, нижним и нижним правым:
xxxx 1111
xxxx 1111
xxxx 1111
2222 3333
2222 3333
2222 3333
Да, это то, что я буду делать, если кто-то другой не предложит лучшее решение. :)
Взгляните на эта статья с портала доктора Добба, чтобы найти максимальный прямоугольник в вашей ситуации. Это очень подробное обсуждение чрезвычайно эффективного алгоритма, и я думаю, что итеративное его повторение, возможно, решит вашу проблему.
Мне пришлось решить аналогичную проблему, мой алгоритм поддерживает зубчатые массивы, я тщательно тестировал и прокомментировал его, но он медленнее, чем предложение Джоэла-ин-Го: https://stackoverflow.com/a/13802336
«Максимальная эффективность не нужна, важнее скорость». - Хм? Я предполагаю, что вы имеете в виду: «Мне не нужно абсолютное минимальное количество прямоугольников, просто что-то, что дает хорошее приближение, быстро» ...?