algorithm - 円形の TreeMap をレイアウトするためのアルゴリズムは何ですか?

Question

標準のネストされた円形ツリーマップが与えられた場合、円を配置する場所をどのように計算しますか?

Answer 1

あなたの主な問題は次のように説明できます: " Given a set of circles of varying radius, how does one place them within a larger circle, so that none of them overlap"。

これは難しい問題ですが、手始めに力ずくで解決する方法を次に示します。

1. 円をサイズで並べ替える
2. 境界円の内側の縁に最大の円を配置します
3. 残りの円 (r1) については、次の操作を行います。
   1. すでに配置されている円のすべてのペア (r2、r3) (外側のものを含む) を反復処理します。
   2. 最初の円までの距離が r1+r2 で、2 番目の円までの距離が r1+r3 である (1 つまたは 2 つの) 点を見つけます。
   3. ここに新しい円を配置してみてください。

上記は、完全なパッキングでは、すべての円が少なくとも 2 つの他の円に接している必要があるという観察を使用しています。アルゴリズムを使用して完全な検索を提供することも、ランダムに反復して最初に利用可能なスポットを貪欲に選択することもできます。