Длина стороны единичного куба, учитывая, что необходимо использовать N единичных кубов для мозаичного изображения / заполнения трехмерного пространства заданного размера

Question

Каждый имеет трехмерное пространство с прямоугольной призмой, например, {xmin, xmax}, {ymin, ymax}, {zmin, zmax}. Цель состоит в том, чтобы использовать предопределенную "сетку" из не более N кубов для максимального разбиения трехмерного пространства. Он будет использовать не более N кубов, если N не может быть равномерно распределен в пространстве. Обратите внимание, что кубы расположены в центральных точках куба (т.е. это сетка), а не на краях куба.

Например, в простом случае N=30 и {0,3}, {0,3}, {0,3}. Правильный ответ - использовать кубы с длиной стороны 1, в этом случае 27 кубов будут использоваться в 3 рядах по 3 столбца из 3 стеков.

В более сложном случае с N=1000 и {0, 100}, {0, 0}, {0, 50} очевидно, что у-измерение использует только 1 строку кубов (оно больше не может использовать), поэтому размеры z и x должны использовать 1000 кубов, расположенных в соотношении 2:1. 100/L * 50/L = 1000. Таким образом, длина стороны, вероятно, около 2,2361, потому что 22 x 1 x 45 = 990 - самое близкое, что мы собираемся получить к 1000 (альтернативно, мы минимизировали пространство, которое мы могли бы не накрываем наши кубические центры). Конечно, стороны должны быть целым числом кубов.

---

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

L, xe, ye, ze ∊ Positive Reals
N, x, y, z ∊ Natural Numbers
x*y*z ≤ N
(x-1)*L ≤ xe
(y-1)*L ≤ ye
(z-1)*L ≤ ze
x,y,z ≥ 1
L = min(i) { (xe*ye*ze) - ((x-1)*i*(y-1)*i*(z-1)*i) }

Я сделал так, чтобы это были x-1, y-1 и т. Д., Чтобы они могли выходить за пределы ширины точно и не более чем на 1 размер куба. Я не могу решить, правильно ли это делать во всех измерениях, или указать, что он должен выходить наружу не более чем в одном измерении (наименьшем?).

Answer 1

Главная идея

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

Упрощение проблемы

Предположим, что ваше пространство имеет размер dx, dy, dz, все ненулевые, и вы хотите использовать до N кубики.

Давайте выразим наши ограничения как:

найти Nx, Ny, Nz, L такой, что
- Nx * Ny * Nz ≤ N
- Nx * L ≤ dx
- Ny * L ≤ dy
- Nz * L ≤ dz
Минимизация "потерянного объема": (dx * dy * dz - L^3 * Nx * Ny * Nz)

Вы можете максимизировать Nx * Ny * Nz вместо. Также обратите внимание, что минимизация громкости без мозаики эквивалентна максимизации L^3 * Nx * Ny * Nz,

И последнее замечание: если ваше решение каким-либо образом оптимально (номер куба или объем мозаики), по крайней мере, одно из измерений будет иметь равенство N@ * L == d@в противном случае мы можем увеличить L,

Давайте предположим без ограничения общности, что dx это измерение, и давайте разделим все длины на dxтаким образом с a@ = d@ / dx за @ являющийся y а также z (а также ax = 1 если нужно). Тогда мы можем переписать проблему:

найти Nx, Ny, Nz, L такой, что
- Nx * Ny * Nz ≤ N
- Nx = дх / л
- Ny / Nx ≤ ay
- Nz / Nx ≤ az
Максимизация объема кубов: dx^3 * (Ny / Nx) * (Nz / Nx)

Следовательно, ваша проблема заключается в том, чтобы получить соотношения числа кубов на каждой стороне как можно ближе к соотношениям размеров, сохраняя при этом Nx * Ny * Nz ≤ N - так же, как вы инстинктивно приблизились к N = 1000 дело.

Предложение алгоритма: Вы можете, например, многократно увеличить Nx и установить N@ = floor(a@ * Nx) для @ in {y,z} в то время как Nx * Ny * Nz ≤ N, сохраняя лучшее решение.

Оптимальные решения

Обратите внимание, что в случае, если ваши коэффициенты ay а также az рациональны, как в ваших примерах, точное решение минимизации может быть найдено довольно легко.

Давайте напишем a@ = n@ / m@ для @ in {y,z}, тогда мы можем найти точное решение, установив
Nx = lcm(my, mz) - наименьшее общее кратное из знаменателей. Обратите внимание, что в случае, когда dx, dy, dz все целые числа, это означает Nx = dx / gcd(dx, dy, dz),

Таким образом, если Nx^3 * ax * ay = lcm(my, mz) ^3 * ny * nz / (my * mz) ≤ Nэто решение также соответствует ограничению на N, Чтобы написать это полностью:

Nx = lcm(my, mz)
L  = dx / Nx
Ny = Nx * ay
Nz = Nx * az

В ваших примерах, для случая 3D, у вас есть ay = az = 1 и решение с Nx = Ny = Nz = 1и для двумерного случая мы имеем только размеры x, z с az = 1/2, это у вас есть решение с Nx = 2 а также Nz = 1

Теперь вы можете добавить больше кубов, потому что у вас Nx * Ny * Nz ≤ N ограничение. В частности, вы можете умножить каждую координату на floor(cbrt(N / (Nx * Ny * Nz))) который floor(cbrt(30 / 1)) = 3 в вашем первом случае, и floor(sqrt(1000 / 2)) = 22 в вашем 2D случае.

Подводя итоги к вашим примерам:

пробел ={3,3,3} N=30: Nx=3, Ny=3, Nz=3, L=1
пробел ={100, 50} N=1000: Nx=44, Nz=22, L=2,72727272...

Эвристический (ы)

Если мы не можем найти точный ответ, мы можем сделать обоснованное предположение. Чтобы не перебирать Nx значения, или просто чтобы иметь разумное начальное предположение.

Обратите внимание, что чем больше знаменатель, тем меньше интервалы между двумя дробями с одним и тем же знаменателем. Это не означает, что с учетом действительного числа, которое вы хотите аппроксимировать, точность вашего приближения пропорциональна размеру знаменателя, но средняя точность при аппроксимации большого числа действительных чисел будет лучше (следовательно, вы ' мы получили лучшую вероятность в одном случае).

Мы пытаемся максимизировать (Ny / Nx) * (Nz / Nx)Таким образом, из наших ограничений на ay а также az мы получаем (N@ + 1) / Nx ≥ a@отсюда N@ ≥ a@ * Nx - 1, Сейчас, Nx * Ny * Nz ≤ N таким образом, ограничение на Nx является:
Nx * (Nx * ay - 1) * (Nx * az - 1) ≤ N

Но мне лень это решать, поэтому давайте еще упростим еще: N@ ≥ a@ * Nx - 1 ≥ a@ * Nx
Таким образом:Nx * (Nx * ay) * (Nx * az) ≤ N

Таким образом, вы можете попробовать как первое предположение:

Nx = floor(crbt(N / (ay * az)))
L  = dx / Nx
Ny = floor(Nx * ay)
Nz = floor(Nx * az)

или (точно так же без a@):

Nx = floor(crbt(N * dx * dx / (dy * dz)))
L  = dx / Nx
Ny = floor(dy / L)
Nz = floor(dz / L)

Если вы хотите убедиться, что у вас есть оптимальное значение, вы можете попытаться выяснить, насколько упрощения ограничены Nx слишком много, так что увеличивайте его до Nx * Ny * Nz ≥ N и сохранить лучшую конфигурацию.

Точно так же разные значения Nx может позволить получить Nx * ay а также Nx * az ближе к их целой части, тратя таким образом меньше места. Вы могли бы уменьшить Nx пока не станет маленьким. Обратите внимание, что вы можете пропустить любое значение, которое делит значение Nx что ты уже пробовал.

Выбор "заполненного измерения" x

Остается выбор, какое направление будет x - инстинктивно я бы сказал, возьмите измерение, в котором ваше пространство самое большое, но это опять-таки только эвристика, и если вы хотите получить оптимальный ответ, вам придется попробовать все направления.

Тем не менее, на точных решениях, где соотношения размеров сторон рациональны, выбирая любую сторону как x будет делать, так как все размеры будут заполнены.