Мне нужен метод, чтобы разделить трехмерное пространство на выровненные по случайной оси фигуры. На данный момент я делю 2d пространство для тестирования. Самый непосредственный подход, который я предложил, - определить прямоугольник размером (1, 1), а затем рекурсивно разделить все существующие прямоугольники на два неравных прямоугольника, чередующихся между осями X и Y.
Проблема здесь очевидна. Этот подход приводит к длинным линиям растяжения (отмечены красным)
То, что я хотел бы, это что-то более органично выглядящий (я включил пример)
Видите, никаких длинных прямых линий сверху вниз или слева направо.
Единственное ограничение заключается в том, что я могу ограничить минимальный размер прямоугольника, не влияя на детализацию размеров. т. е. если наименьший прямоугольник равен 1 квадратным сантиметрам, то наименьшее количество секунд не должно составлять 2 квадратных единицы.
Поэтому в идеале алгоритм должен соответствовать всем трем следующим ограничениям:
- Прямоугольники не бесконечно малы.
- Размеры прямоугольника не являются дискретным умножением наименьшего размера прямоугольника. т. е. если наименьший прямоугольник равен 3 квадратным единицам, то более крупные прямоугольники не ограничиваются 6, 9, 12 и т. д. квадратными единицами и вместо этого могут составлять 3,2 или 4,7).
- Алгоритм работает за полиномиальное время (нужно быстро вычислять).
Как видите, мне удалось избавить мир от этих артефактов. Идея очень похожа.
Неравномерная сетка (1):
Переговоры по оси х (2):
Переговоры по оси y (3):
Результат (4):
источник