衝突を避けるために長方形をレイアウトする（アルゴリズムのヘルプ）

Question

私は、（大）水平スクロールビューと、それに配置したい四角形の束を持っています。各矩形は、所望の水平位置を有するが、必要に応じてその位置から一定量（定数、K）まで変化させることができる。長方形は重なり合ってはいけません。長方形の垂直位置は任意です（もちろん、ビューの高さに制限されます）。

理想的には、矩形のサイズを可変にしたいと思っています...それが不可能かどうかは、大きさを1次元で変えることができると思います。

ここでは、ある程度の垂直方向のスペースしかなく、理想から水平方向にKピクセルしか移動できないため、すべての矩形を描くことができない可能性があります。これに対処するため、各矩形は優先度（P）を持ち、優先度の低いものは最初に省略する必要があります。 （あなたはそれが曖昧ではないと仮定することができます、そして、あなたはいつもより高い優先順位を持っているどんな2つの四角形のどちらが高いかを知ることができます）。

私は概念的アルゴリズムの後のものですが、 iPad上では数千（> 1000、ただし<00）の長方形が考慮されます。理想的には、ユーザーがズームレベルを変更するたびに再実行するのに十分な速さが必要ですが、それが簡単でない場合は、位置をキャッシュすることができます。オブジェクトはタイムライン上の写真です。イベントが発生したときに、それらを近づけたいと思っています。私は、その上にもっと多くを得るために近づくつもりです。

私はthisのようなアルゴリズムを見てきましたが、交差していないトリックはありますが、各アイテムが一定量までしか移動できないという考えはありません。明らかに後者の制約がなければ、すべてのアイテムを表示することができるので、どのポイントにも長方形を表示することはできません。

上記の問題を解決することが難しい場合は、より実用的なアイデアの提案を歓迎します。他のすべてが失敗した場合、私は常に優先順位順に何かを行うことができます。可能であれば、それぞれのアイテムを必要な場所にレンダリングします。垂直方向にシフトしない場合は、水平方向に許容範囲までシフトします。次のものに移ります。優先順位は、おそらく最適以下の解決策が見つかることを意味しますが、最も重要な項目に向かって重み付けされます。

Answer 1

これは私がこれを行うことができると考える一つの方法です。

ステップ1は、新しい黄色の矩形を配置できるすべての場所を把握することです。一般性を失うことなく、これを矩形の左上隅のすべての可能なX-Y位置のリストとして格納することができます。当然のことながら、リストには何百万ものエントリが含まれているような巨大な開始領域のために、スペースを節約するために、このリストを矩形領域のセットの形で保存しましょう。

たとえば、X = 0〜X = 2999のピクセルがあり、Y = 0〜Y = 999のピクセルがあり、新しい長方形の幅が300ピクセルと高さが150ピクセルの場合、左上隅（X、Y）=（0,0）から（2699,849）までの任意の位置に表示できます。それを4つ組の[0、0、2699、849]として保存しましょう。

既存の（赤い）矩形を画面に配置すると、新しい（黄色の）矩形が重なって表示されるため、これらの可能性のいくつかが除外されます。たとえば、赤い四角形[1100、200、1199、299]がある場合、黄色の四角形は、（X、Y）=（801,51）から（1199,29）までの任意の位置に左上隅を持つことができません。包括的です。

したがって、[0、0、2699、849]を同じ領域をカバーする4つの矩形のゾーンで置き換えます。これを行うには多くの方法がありますが、ここでは[0,0,1199,50]、[1200,0,299,2699]、[0,51,800,849]、[801,300,2699,849 ]。

さらに赤い四角形を画面に追加してください。 1つが追加されるたびに、リストからより多くの可能性を引きます（これは通常、より多くのより小さな「セーフゾーン」を含むリストになります）。 （これは1000 +の長方形のフルスクリーンでは非常に時間がかかることがありますが、あなたが言及した[XK、0、X + K、H]スペースから始めれば、1000 +はこれをオーバーラップさせ、計算ははるかに速くなるでしょう）。このコードは、フェンスポストのエラーがたくさんあるので、非常に注意して単体テストを重ねて書いてください。

最終的な結果は、新しい黄色の四角形の左上隅が配置される可能性がある、四角形のゾーンのリストの形式で表示される可能性のある場所の完全なリストです。

ステップ2：このリストを調べ、最も望ましい場所を選択します。理想的な垂直線と実際に交差する矩形のゾーンが優先されます。しかし、それは存在しない可能性があります。この場合、左にあるゾーンと理想ラインの右にあるゾーンの中から最も好ましいオプションを選択するのはあなた次第です。ヒントとして、それぞれのゾーンの1つの角だけを考慮する必要があります（右側のゾーンの左上隅、左側のゾーンの右上隅）。