У меня есть приложение для рендеринга, которое отображает много-много кубов в трехмерной сетке.Это по своей сути неэффективно, так как каждый куб представляет 4 вершины, и часто кубы являются смежными, создавая одну поверхность, которая может быть представлена одним прямоугольником.
Для заполнения области я использую трехмерный массив, гдезначение 0 обозначает пустое пространство, а значение, отличное от 0, обозначает блок.
например (где X обозначает место размещения куба)
OOOXXXOOOO
OOXXXXXXXO
OOXXXXXXXO
OOXXXXOOOO
в настоящее время будет представлено как 21 кубили 252 треугольника, тогда как его можно легко представить в виде (где каждая буква обозначает часть прямоугольника)
OOOAAAOOOO
OOBAAACCCO
OOBAAACCCO
OOBAAAOOOO
, что представляет собой всего лишь 3 прямоугольника или 26 треугольников.
Типичный размер этих сеток составляет 128x128x128, поэтому ясно, что я бы выиграл от значительного увеличения производительности, если бы мог эффективно уменьшить фигуры до наименьшего количества прямоугольников за разумное время, но я застрял в идеях для алгоритма.
Использование Динамическое программирование - Самый большой квадратный блок будет одним из вариантов, но это не приведет коптимальный ответ, хотя, если решение слишком сложное для эффективного выполнения, тогда это должен быть путь.
В конце концов у меня будет несколько типов кубов (например, зеленый, коричневый, синий, на которые ссылаются, используя разныененулевые числа в массиве), поэтому, если возможно, будет полезна версия, которая будет работать с несколькими категориями.