4

正方形または長方形をランダムなサイズの正方形または長方形に分割して、重ならないようにしようとしています。

もちろん、他の人がこれを私が見つけた最高のスレッドであると尋ねまし た。正方形を小さな正方形/長方形で埋める方法は？

解決策は、ビンパッキングまたはある種のツリーマップのいずれかによるもののようです。

しかし、私が探しているのは、Java、Javacript、actionscript、さらにはCの実際のアルゴリズムです。

4

3 に答える 3

4

解決策は、「分割統治」手法を試すことです。反復1では、長方形があります。長方形を2つの小さい長方形に分割します。そのための方法は次のとおりです。長方形が100x50であるとします。0〜100（長方形の長さ）の間の乱数を選択します。乱数が20であるとします。次に、サイズが20x50と80x50の2つの小さい長方形に吐き出すことができます。これらの2つの新しい長方形には、同じ手順が再帰的に適用されます（したがって、反復2では4つの長方形が作成されます）。これをn回実行すると、2^n個の長方形が作成されます。また、各反復で、各長方形の長さ（垂直）または幅（水平）のどちらで唾を吐くかをランダムに選択できます。

それが役に立てば幸い！

于 2011-10-13T13:13:12.367 に答える
1

提供されたコードはkdツリーを作成します。これを使用して、長方形に線を描画し、長方形を小さな長方形に分割することができます。ツリーを取得したら、次のように使用して、リージョンを次の長方形に分割できます。

  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; 
}
于 2011-10-13T14:10:24.823 に答える
1

長さをランダムに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);
        }

    }

}
于 2011-10-13T14:25:32.050 に答える