algorithm - サークル内にオブジェクトを配布する

Question

重複の可能性：
正方形を円に詰める方法は？

さまざまなサイズの長方形を円の中に収める必要があるという問題があります。すべての長方形は、互いに重なり合うことなく、また円をオーバーフローすることなく、円に収まる必要があります。

長方形が円の中に収まると仮定すると、それらを円の中に分散させるアルゴリズムをどのように開発するでしょうか？

私が考えることができるのは、長方形をランダムに何度も分散させ、条件が満たされているかどうかをテストすることです（ブルートフォース）。

Answer 1

これは古典的な制約問題であり、ブルートフォースはそれを行う1つの方法ですが、ヒューリスティックなどを使用してアルゴリズムをソリューションに導くのに役立つ他の方法があります。より良いアルゴリズムについては、GoogleScholarのようなものでいくつかの制約プログラミングとビンパッキングペーパーを調べる必要があります。

ウィキペディアの概要は次のとおりです。http： //en.wikipedia.org/wiki/Packing_problem

Answer 2

他の人が述べているように、最適な解決策（たとえば、最小の面積または均一な分布）はNP困難である可能性があります。それでも、ニーズに応じて、さまざまなサイズの長方形を他の長方形にパックするための優れたアルゴリズムがいくつかあります。例：CSSスプライトを構築するための高速最適化長方形パッキングアルゴリズム：

This article describes a fast algorithm to pack a series of rectangles of varying widths and heights into a single enclosing rectangle, with no overlap and in a way that minimizes the amount of wasted space in the enclosing rectangle. [...] shows step by step how the algorithm arrives at the optimal enclosing rectangle.

Note that in the above procedure the bounding rectangle is allowed to vary (nor am I convinced that the solution is the optimal enclosing rectangle). You can approximate a circle by breaking it up into discrete rectangles.

While not a complete solution to what you are looking for, I think this may be a good first step.