占有/占有されていない2D空間を効率的に格納する方法（挿入あり）

Question

XとYは、私に与えられた矩形のサイズによって決まるXのY空間を持っています。私は一度に1つのスペースに一定の大きさの向きのある四角形を挿入しています。それぞれの挿入は可能な限り左にあり、できるだけ遠くに（できるだけ（0,0）に近いように）挿入します。これを表現する最良の方法は何ですか？私はこれをPythonで実装しています。 thisの質問への一番の答えは役に立ちましたが、Python固有のアドバイスを期待していました。私は言語自体もかなり新しいです。

ありがとうございます！

Answer 1

矩形を効率的にパックしようとすると、いくつかの確立されたアルゴリズムがあります。以下は、Pythonの具体的な実装例です。algorithmです。私がPython versionを持っているライトマップを梱包する記事もあります（私はそれを自分で移植したのか、別の場所から持ってきたのか覚えていません）。

Answer 2

このように2次元空間で作業するには2つの選択肢があります。

1. リストのリスト。 [ [0, 0, ..., 0], [0, 0, ..., 0], ... [0, 0, ..., 0] ]外側のリストは「X」アクセス、内側のリストは「Y」アクセスです。それぞれのポイントはspace[x][y]です。あなたはspace = list(list(EMPTY for j in range(Y_size)) for i in range(X_size))または類似のものでそれを構築します。

   値を長方形のスペースパッチに設定するいくつかのフィラーアルゴリズムで、長方形をマスクします。

   for x in range(low, high): 
       for y in range (low, high): 
        space[x][y]= FILLED # or whatever object you're putting there. 
   

2. マッピング。 { (0,0): 0, (0,1): 0, ... (X,Y): 0 }。各ポイントはspace[x,y]です。 space = dict(((x,y), EMPTY) for x in range(X_size) for y in range(Y_size))でビルドします。

   ほぼ同じフィラーアルゴリズムで矩形をマスクします。構文をわずかに変更してください。

Answer 3

Quadtreesがよく使用されます。あなたが地域クワッドツリーをしたいように聞こえる。