Представьте себе мир, основанный на кубах (например, Minecraft, Trove или Cube World), где все состоит из кубов одинакового размера, и все кубы одного типа .
Цель состоит в том, чтобы представить мир с наименьшим количеством прямоугольных прямоугольников (объединяя кубы, но сохраняя выпуклую форму (или прямоугольную форму)). Мой алгоритм преуспевает в этом, но его производительность слишком медленная для его предназначения. Есть ли более быстрые алгоритмы?
Псевдо-C # -код для моего алгоритма в основном:
struct Coordinate { int x,y,z; }; //<-- integer based grid
HashSet<Coordinate> world; // <-- contains all the cubes
//width, height, and length represent how many cubes it spans
struct RectangularBox { Coordinate coord; int width,height,length; }
void Begin()
{
List<RectangularBox> fewestBoxes = new List<RectangularBox>();
while(world.Count > 0)
{
RectangularBox currentLargest = ExtractLargest();
fewestBoxes.Add(currentLargest);
world.RemoveRange(currentLargest.ContainedCubes());
}
//done; `fewestBoxes` contains the fewest rectangular boxes needed.
}
private RectangularBox ExtractLargest()
{
RectangularBox largestBox = new RectangularBox();
foreach (Coordinate origin in world)
{
RectangularBox box = FindMaximumSpan(origin);
if (box.CalculateVolume() >= largestBox.CalculateVolume())
largestBox = box;
}
return largestBox;
}
private RectangularBox FindMaximumSpan(Coordinate origin)
{
int maxX, maxY,maxZ;
while (world.Contains(origin.Offset(maxX, 0, 0))) maxX++;
while (world.Contains(origin.Offset(0, maxY, 0))) maxY++;
while (world.Contains(origin.Offset(0, 0, maxZ))) maxZ++;
RectangularBox largestBox;
for (int extentX = 0; extentX <= maxX; extentX++)
for (int extentY = 0; extentY <= maxY; extentY++)
for (int extentZ = 0; extentZ <= maxZ; extentZ++)
{
int lengthX = extentX + 1;
int lengthY = extentY + 1;
int lengthZ = extentZ + 1;
if (BoxIsFilledWithCubes(origin, lengthX, lengthY, lengthZ))
{
int totalVolume = lengthX * lengthY * lengthZ;
if (totalVolume >= largestBox.ComputeVolume())
largestBox = new RectangularBox(origin, lengthX, lengthY, lengthZ);
}
else
break;
}
return largestBox;
}
private bool BoxIsFilledWithCubes(Coordinate coord,
int lengthX, int lengthY, int lengthZ)
{
for (int gX = 0; gX < lengthX; gX++)
for (int gY = 0; gY < lengthY; gY++)
for (int gZ = 0; gZ < lengthZ; gZ++)
if (!world.Contains(coord.Offset(gX, gY, gZ)))
return false;
return true;
}
По сути, для каждого блока в мире, он сначала находит, сколько константных блоков есть в каждом из трех положительных измерений (+ X, + Y, + Z). И затем он как бы заполняет этот объем и проверяет, какая из них самая большая, не пропустив ни одного блока.
Обновление: так как я, казалось, подразумевал, что это было для движка рендеринга игры, я просто хочу уточнить, это не для движка рендеринга игры; это для файлового конвертера; нет графического интерфейса
источник
Ответы:
Вы можете использовать тот факт, что когда
возвращает true, тогда нет необходимости проверять
BoxIsFilledWithCubes(c,x+1,y,z)все эти кубы в координатном диапазоне "(c, x, y, z)" снова. Вам нужно только проверить эти кубики с новой x-координатойc.x + (x+1). (То же самое верно дляy+1илиz+1). В более общем смысле, разделив прямоугольник на два меньших прямоугольника (для которых вы, возможно, уже знаете, заполнены ли они кубиками или не заполнены оба), вы можете применить здесь метод «разделяй и властвуй», который становится быстрее, чем ваш. оригинальный подход при кешировании промежуточных результатов.Для этого вы начинаете
BoxIsFilledWithCubes(c,x,y,z)рекурсивную реализацию , например:и затем используйте памятку (как это обсуждается здесь ), чтобы избежать повторных вызовов
BoxIsFilledWithCubesс теми же параметрами. Обратите внимание, что вам придется очистить кэшworldнапоминания, когда вы примените изменение к своему контейнеру, например, с помощьюworld.RemoveRange. Тем не менее, я думаю, это сделает вашу программу быстрее.источник
Создайте октодерево с листовым узлом размером с ваш ящик. Проходя через октри, вы можете дешево объединить узлы. Полностью заполненные узлы тривиальны для слияния (новое поле = родительский aabb), в то время как для частично заполненных узлов вы можете использовать вариант текущего алгоритма для проверки возможности слияния.
источник
Похоже, что вы, по крайней мере, O (n ^ 2) (см. Большие обозначения O ), когда вы перебираете все блоки в мире в «Begin ()», а затем для каждого блока вы перебираете все блоки в мире в ExtractLargest ( ). Таким образом, мир с 10 несвязанными коробками займет в 4 раза больше времени, чем мир с 5 несвязанными коробками.
Поэтому вам нужно ограничить количество блоков, на которые должна смотреть ExtractLargest (), для этого вам нужно использовать некоторый тип пространственного поиска , так как при работе в 3d вам может понадобиться трехмерный пространственный поиск. Однако сначала начните с понимания двумерного пространственного поиска.
Затем подумайте, будет ли у вас когда-нибудь много блоков поверх друг друга, если нет, то двухмерного пространственного поиска, который охватывает только x, y, может быть достаточно для сокращения вашего цикла.
Octree / quadtree - один из вариантов, но есть много других вариантов разделения пространства ,
Но вы можете просто использовать двумерный массив списков ( пространственный индекс сетки ), где все поля, которые охватывают точку (a, b), находятся в массиве [a, b] .list. Но, скорее всего, это привело бы к слишком большому массиву, так как насчет массива [mod (a, 100), mob (b, 100)]. List? Все зависит от того, на что похожи ваши данные .
(Я видел, как сеточное решение очень хорошо работает в реальной жизни.)
Или сделайте то, что говорит Уилберт, с октодеревом с размером листа aabb, равным размеру вашего блока, но позже вам, скорее всего, придется найти блок, на который указывает мышь пользователя, и т. Д., Снова случай пространственного поиска.
( Вы должны решить, пытаетесь ли вы заставить это программное обеспечение работать или вы пытаетесь понять, как стать лучшим программистом и, следовательно, больше заинтересованы в обучении, чем в быстром решении. )
источник