4

それぞれに幅と高さを定義したいくつかの抽象的な形状があるとしましょう (簡単にするために、それらを長方形にしましょう)。定義された幅と高さの単一のキャンバス (HTML5 キャンバスとは限らない単なる用語) にできるだけ多くのそれらを配置するにはどうすればよいですか?

明らかに、これはある種の制約充足問題ですが、どこから始めればよいかわかりません (ブルート フォースを除く)。グーグルは無関係な結果を表示するだけです（おそらく、何を検索すればよいかわからないためです）。良いアルゴリズムとは何か、またはこれを行うアルゴリズムを作成する良い方法は何か?

フィズがいい例です。図形 (この場合は円) はグループで表示され、互いに重ならず、互いの邪魔にならないようにします。私の使用例は、1 回限りのポジショニング取引です。もう 1 つの例は、特定の境界内にできるだけ効率的に配置するSpriteRightです。

4

3 に答える 3

1

あなたの問題は、有限領域に対する制約論理プログラミング ( ) から利益を得ることができます。

Prolog の制約処理: Packing squaresに対する質問と回答を考えてみましょう。いくつかの方法が示されていますが、そのうちの 1 つは専用の配置制約を使用して、2D で重なり合わない四角形のレイアウトを見つけます。

clpfd を使用すると、パッキングの制約に加えて、追加の制約を適用することもできます。をサポートする無料 ( SWIやYAPなど) と商用 ( SICStus など)の両方の実装があります。

于 2015-04-15T09:43:15.977 に答える
0

JavaScript と HTML5 キャンバスを使用したオープン ソースの例を見つけました。長方形はランダムに生成されてからパックされます。ただし、著者は効率性については主張していません。

有望そうな記事も見つけました。

于 2012-02-14T14:48:31.427 に答える
0

http://www.aimms.com/downloads/application-examples/circle-packingも ご覧ください。ここでは、数学的プログラミング/モデリングを使用して、サークル パッキングの問題を解決します。他のバリアントも定義できます。Constraint Programming ( http://www.aimms.com/cp ) には、特別なビンパッキング制約が存在します。

一般に、数理計画法は、このような問題にアプローチするための優れた方法です。

于 2012-02-17T11:15:20.423 に答える