Разбейте квадрат или прямоугольник на большое количество квадратов или прямоугольников произвольного размера

Question

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

Хорошо, конечно, другие задали этот вопрос, лучшая нить, которую я нашел, это Как заполнить квадрат меньшими квадратами / прямоугольниками?

Решение, похоже, заключается либо в упаковке бина, либо в какой-то карте дерева.

Но то, что я ищуэто фактический алгоритм в Java, Javacript, actionscript или даже C.

Answer 1

Решением было бы попробовать метод «Разделяй и властвуй».В итерации 1 у вас есть прямоугольник.Разделите прямоугольник на два меньших.Способ сделать это заключается в следующем.Допустим, прямоугольник равен 100x50. Выберите случайное число от 0 до 100 (длина прямоугольника). Допустим, случайное число равно 20. Затем вы можете разбить свой прямоугольник на два меньших с размерами 20x50 и 80x50.Для этих 2 новых прямоугольников применяется рекурсивно та же процедура (следовательно, в итерации 2 у вас будет 4 прямоугольника).Сделайте это n раз, и у вас будет 2 ^ n прямоугольников.Также в каждой итерации вы можете произвольно выбирать, следует ли выполнять разбрызгивание по длине (по вертикали) или ширине (по горизонтали) каждого прямоугольника.

надеюсь, это поможет!

Answer 2

Случайно разделить длину на x частей

Теперь случайным образом разделите каждый меньший прямоугольник по отдельности на y частей

Вот некоторый код ActionScript (написанный в блокноте, вам придется проверять наличие ошибок). Он принимает ширину и высоту входного прямоугольника и возвращает массив с вершинами разделенных прямоугольников

private function divRect(w:Number, h:Number):Array {
    var rw:Number=0, rh:Number=0;
    var wa:Array=[0], rv:Array=[];
    while(rw < w) {
        var r:Number=Math.random() * (w-rw);
        wa.push(r+rw);
        rw+=r;
    }

    for(var i:int=1; i<wa.length; i++) {
        while(rh < h) {
            var o:Object={x: wa[i-1], x2: wa[i]};
            var s:Number=Math.random() * (h-rh);
            o.y=rh;
            rh+=s;
            o.y2=rh;
            rv.push(o);
        }

    }

}

Answer 3

Предоставленный код создает дерево k-d . Вы можете использовать это для рисования линий на вашем прямоугольнике, которые разделят его на меньшие прямоугольники. После того, как вы получили свое дерево, вы можете использовать его следующим образом, чтобы разделить ваш регион на следующие прямоугольники:

1. Выберите узел в корне дерева.
2. Нарисуйте вертикальную линию через эту точку.
3. Выберите его левого потомка, нарисуйте горизонтальную линию через эту точку на левой стороне линии, которую вы только что нарисовали, через ее родителя (эта линия останавливается на линии, которую вы только что нарисовали).
4. Выберите правильного потомка, нарисуйте горизонтальную линию через эту точку справа от линии, которую вы только что нарисовали, через своего родителя (эта линия также останавливается на линии, которую вы нарисовали через родителя).
5. Делайте это рекурсивно, переключаясь между вертикальными и горизонтальными линиями на каждом уровне дерева.

Код:

int MAX_HEIGHT = 100;
int MAX_WIDTH = 100;
int NUM_POINTS = 6;


// Generate random list of points
List<Point> pointList = new List<Point>();

Random rand = new Random();

for(int i = 0; i < NUM_POINTS ; i++)
{
    pointList.add(new Point(rand.nextInt(MAX_HEIGHT), rand.nextInt(MAX_WIDTH));
}

BinaryTree tree = CreateKDTree(pointList, 0);


// Recursive function for creating a K-D Tree from a list of points
// This tree can be used to draw lines that divide the space up
// into rectangles.
public BinaryTree CreateKDTree(List<Point> pointList, int depth)
{
    // Have to create the PointComparator class that just selects the
    // specified coordinate and sorts based on that
    Coordinate coord= depth % 2 == 0 ? X_COORDINATE : Y_COORDINATE
    Collections.sort(pointList, new PointComparator(coord));

    int median = pointList.size() / 2;

     // unfortunately Java doesn't have a BinaryTree structure so
     // you have to create this too
    BinaryTree node = new BinaryTree(pointList[median]);

    if(pointList.size() == 1) return node;

    if(median > 0)
        node.left(CreateKDTree(pointList.subList(0, median), depth + 1);

    if(median + 1 < subList.size())
        node.right(CreateKDTree(pointList.subList(median + 1, subList.size()), depth + 1);

    return node; 
}