次の要件が満たされるように、100 ～ 200 個のバブル ラベルを自動的に配置したいと考えています。
これに役立つライブラリ/アルゴリズムはありますか? (できれば JavaScript または PHP)
(画像内のラベルの配置はこれらの要件を満たしていません)
これはどう？
ツール内で D3 を使用している場合は、「力ベース」のラベル配置アルゴリズムを使用できると思います。ソリューションはもともとMax Planck Research Networksに属していましたが、既に既製の Javascript の例がここにあります: D3 での力ベースのラベル配置
JavaScript、html、およびcssを使用していると思いますか？いずれにせよ、2 つのアプローチが頭に浮かびます。
まず、最適化問題として定式化します。各ラベルの理想的な位置を計算する必要があります。これは、バブルのサイズ、目的の位置 (つまり、上、下、左、右)、およびラベルのサイズ (フォントと長さの両方) に基づきます。次に、座標をパラメータ化する必要があります。たとえば、N がラベルの数である 2N 要素のリストにします。次に、ある位置 (遺伝的アルゴリズムを使用している場合は母集団) でラベルを初期化し、コスト関数を必要とする最適化アルゴリズムを適用する必要があります。これは、一連のラベル位置が理想からどれだけ離れているか、および重複などのルールに違反するものに基づいています。
または、物理の問題にします。固定リンクを使用して、各ラベルをバブルに「添付」します。すべてのラベルとすべてのバブルに反発力を与え、グローバルでより強力な重力を追加します (望ましい上/左/右/下方向)。平衡に達するまで、短い物理シミュレーションを行います。数学はあまり難しくないはずです。
これは、線形計画問題として定式化できます。特定の制約 (要件) に従って、関数 (解の「重み」または「良さ」を表す) を最大化または最小化したい。要件を値として形式化する必要があります。このようなもの：
Variables:
x1 = 1 if Labels overlap, 0 otherwise
x2 = some measure of "how much" a label overlaps a bubble
x3 = distance from label to bubble //Label should be close to bubble
x4 = distance between ideal and actual label position
x5 = difference between actual and ideal font size
minimize x1 + 10*x2 + x3 + 20*x4 + 5*x5
subject to constraints:
x1 = 0 // labels can never overlap
x2 < /* maximum amount a label is allowed to overlap a bubble */
...
x5 < 6 // font size does not vary by more than +/- 6 pts.
係数と制約を作成しました。それらを使用して、どの機能が最も重要であるかに基づいて結果を調整できます。係数は、要件の値を増加させます (この場合、f4最も重み付けされているため、「最も重要」です。制約は、違反できないハード リミットです。
これはよく知られた問題であるため、多くの方法を使用して解決できるようになりました。シンプレックス アルゴリズムが一般的です。Cormen et.には全章があります。これらの問題について。
この問題に対して実際にJavaでアプローチを見つけました。これは実際に機能し、Force Directed Map Labelingと呼ばれ、オープンソースのアカデミー体験です。
ドキュメントとプロジェクトのソース コードは次のとおりです: Force Directed Map Labeling
残念ながら、Javascript や PHP ですぐに利用できるこのソリューションを見つけるのは難しいと思います。ただし、ソリューションの設計に役立つように、問題を（ルールに基づいて）小さなサブ問題に分割できると思います。
どのルールが最も重要かを特定します。あなたが提供したグラフの外観から、ルール 1 と 2 が読みやすさを最大に改善すると思います。
これらのルールに従って配置を決定するには、テキストと吹き出しの境界コンテナーを計算し、交差をテストします。交差点では、交差点のない場所に移動します。見つからない場合は、オーバーラップが最小限のスペースを使用してください。
これにより、左上、右下などの加重配置ヒューリスティックを作成して、ラベルを「優先」位置に配置することもできます。
通常は近くにあり、重複する可能性がある 2 つのラベルを持つ 2 つのバブルを使用して、配置アルゴリズムの小さな部分を書き出そうとします。この小さなサブセットで機能するように配置アルゴリズムを一般化できる場合は、より多くのバブルで前進できるはずです。
また、おそらく、kd ツリーまたは別の空間分割データ構造の順序で何かを使用して、回避する最近傍を見つけることができます。
このスレッドは、いくつかのアプローチをカバーするのに非常に適しています。全体的に最良の方法のように思われるため、複数の焦点を持つフォース レイアウトを使用しています。
どうですか
label.substring(0, Math.sqrt(bubbleValueOrRadius))
これは、protovis.js の例の 1 つで見つかりました。