泡泡圖標籤放置算法？（優選在JavaScript）

我想自動放置100-200氣泡標籤，使得滿足以下要求：泡泡圖標籤放置算法？（優選在JavaScript）

標籤應不重疊
標籤應優選不重疊的氣泡
標籤應接近氣泡
優選的標記位置（左上，上，下，右等）應遵守，以在一定程度上
字體大小可以變化

這是否有任何有用的庫/算法？（最好的JavaScript或PHP）

（貼標籤的圖像中不符合這些要求）

enter image description here

2011-04-29 dani

優秀的問題。我會提供一個bouty，但在圖表中閱讀「每千人口的謀殺案」讓我閉嘴，忘掉「賞金」一詞。 – 2011-04-29 22:20:27

安德拉斯，圖片僅僅作爲一個帶有標籤的散點圖的例子。我從這裏拿走它：http://flowingdata.com/2010/11/23/how-to-make-bubble-charts/。對不起，如果它不是一個合適的示例圖像 - 我沒有太注意實際指標繪製。 – dani 2011-04-30 10:02:54

我認爲這個問題的範圍過於寬泛。 – 2011-05-02 17:19:38

這可以表示爲線性規劃問題。您希望最大化或最小化受某些約束（您的要求）約束的功能（表示解決方案的「重量」或「良好」）。您需要將您的需求正式化爲值。事情是這樣的：

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加權最大，因此它是「最重要的」）。約束是不能違反的嚴格限制。

由於這是一個衆所周知的問題，您現在可以使用多種方法解決它。 Simplex算法很受歡迎。關於這些問題，Cormen et. al有一整章。

來源

2011-05-02 17:54:20

指定權重似乎非常合理。然而我想知道如何在JavaScript中實現所描述的單純形算法。謝謝。 – dani 2011-05-04 08:02:02

Downvoted，因爲問題不能被定義爲線性規劃問題。你的約束x1不是線性的，它是二元的，這是一個決策問題。這很難。如果寫下相交/非相交的方程式，您會注意到，約束條件不是線性的。 – Sebastian 2013-11-15 11:38:59

這個怎麼樣？

An Efficient Algorithm for Scatter Chart Labeling

來源

2011-04-29 22:48:28

感謝您的鏈接優秀的論文。我有一個讀通過，但它可能很難適應JavaScript和上面列出的標準的算法。如果您有更多的「適用」資源可供分享，他們會非常感激。 – dani 2011-05-01 09:51:32

Upvoted，因爲我寫了這個算法。 – Sebastian 2013-11-15 11:36:22

@dani我同意這個算法在JavaScript中不易實現。但是這表明了問題的嚴重性。該算法允許將標籤放置在與其氣泡相距一定距離的位置，只要連接線可以在沒有相交的情況下繪製即可。如果你不允許這樣做，問題就會變得更加容易。 – Sebastian 2013-11-15 11:42:26

不幸的是，我認爲這將是很難找到在Javascript或PHP一應俱全此解決方案。但是，我確實認爲你的問題可以分解成小的子問題（根據你的規則）來幫助你設計你的解決方案。

我想確定哪些規則最重要。從你提供的圖表看，我會說規則＃1和＃2將提供可讀性最大的改進。

要根據這些規則確定放置位置，我會計算文本和氣泡的邊界容器並測試相交。交叉路口時，移動到沒有交集的位置。如果找不到，請使用重疊最小的空格。

這將允許您還爲左上角，右下角等創建加權位置啓發式，以幫助將標籤放置在「首選」位置。

我會盡量寫出一小段使用兩個氣泡的貼裝算法，這兩個貼有兩個標籤，這兩個標籤通常很近並且可能會重疊。如果你可以概括你的放置算法爲這個小子集工作，你應該很好地向前移動更多的氣泡。

此外，也許你可以使用一些kd-tree或其他空間分區數據結構的順序來定位最近的鄰居以避免。

來源

2011-05-02 16:54:29 jsherer

我想你正在使用javascript，html和css？無論如何，想到兩種方法。

首先將其表述爲優化問題。您需要計算每個標籤的理想位置。這將基於氣泡的大小，期望的位置（即，上，下，左，右）和標籤的大小（字體和長度）。然後，您需要對座標進行參數化，例如，將其轉換爲2N個元素的列表，其中N是標籤的數量。然後，您需要在某個位置（或使用遺傳算法的羣體）初始化標籤，並應用需要成本函數的優化算法。這將基於一組標籤位置離理想有多遠，以及違反規則的任何事情，如重疊。

或者，讓它成爲一個物理問題。用一些固定的鏈接將每個標籤粘貼到其泡泡上。給予每個標籤和每個泡沫一個排斥力，並且增加一個全球性的和更強的graviational力量（在首選的頂部/左/右/下方向）。進行短暫的物理模擬，直至達到平衡。數學不應該太難。

來源

2011-05-06 00:22:30 zenna