高速最小距離と各矩形パッキング2Dビンアルゴリズム及び点

Question

これはbin packing problemに類似しているが、いくつかの変更を有します。私が持っているもの

は、注釈付きデータの時系列である、と私はチャートを描画するとき、私は全体的な注釈付きの点からの距離を最小限に抑える位置に注釈を配置します。 ：

このチャート、（無償盗まれた）が、私が何をしたいのかを示しています。

私はこれが最適化問題であることを知っていますが、どこから始めたらいいのか分かりません。私が最初にやっていたことは、それを対応するxに配置し、yを上下に動かして利用可能な場所を見つけて、描画された領域を保存することでした。それがうまくいく間に、実際に利用可能なスペースを最大限に活用するわけではありません。もっと良いものがあるかどうかは疑問です。

これまたは類似の問題を攻撃する既知のアルゴリズムがあるかどうか疑問に思っていますか？

注意事項を追加しました：それが最適である必要はありませんが、それは絶対に速くする必要があります。これはレンダリング中に行われるため、UIの実行中にブロックされます。

Answer 1

この難しい問題には、さまざまなアプローチがあります。私はautomatic label placementのWikipediaの記事から始めることをお勧めします。 force-based algorithms for graph drawingの領域からいくつかのアイデアを得ることもできます。

Answer 2

私はそれが簡単な「ファーストフィット」アルゴリズムを使用してラベルを配置するための任意の順序で開始しthis-好きだろう。結果を、各注釈付きポイントからの距離の二乗の和のようなものでスコア化します。私は遠く離れているものを除いて、それらのすべてが本当に近くになるのを避けるために、距離を二乗するだろう。

最初の解決策があるしきい値よりも低い場合は、それを使用して次に進みます。そうでない場合は、最悪のフィット（注釈付きポイントから最も離れたラベル）を取り、それらを配置順に上に移動してやり直します。あなたは十分に良い解決策を得るか、時間を使い果たすまで、これを繰り返すことができます。その場合、多くのベストな解決策を取って行きます。