jquery - 2D 領域内の異なるサイズの重なり合わない四角形のランダムな位置を生成する

Question

2D 領域内の異なるサイズの重なり合わない四角形のランダムな位置を生成するアルゴリズムを探しています。例は次のとおりです。

四角形のランダムなサイズはa aと b b の間で、xy 座標に平行です。JQuery（JavaScript）を使用しています。

-- 四角形ごとに 2 つの独立した乱数 (x 座標と y 座標) を生成する場合、この場所の新しい四角形が他の既存の四角形と重なっていないかどうかを確認する必要があります。存在する場合は、この選択を無視して、新しい数字のペア (新しい場所) を生成します。したがって、これは良いアルゴリズムではない可能性があります--

誰か提案はありますか？ありがとう。

Answer 1

四分木または kd ツリーを使用して、サーフェスを細分割できます。空間インデックスも機能します。空間充填曲線と空間インデックスを探し、象限を見つける方法をクワッドキーまたはジオハッシュします。空間充填曲線が非常に複雑なので、r-tree も良いかもしれません。bing マップ クワッドキーの例を次に示します: http://msdn.microsoft.com/en-us/library/bb259689.aspx。次に、幅優先検索をランダムに使用できます。