气泡图标签位置的算法？ （在JavaScript preferably） [英] Bubble chart label placement algorithm? (preferably in JavaScript)

问题描述

我想自动放置100-200泡沫标签，这样满足以下要求：

I'd like to automatically place 100-200 bubble labels so that the following requirements are met:

• 标签不能重叠
• 标签应该preferably不重叠气泡
• 标签应接近泡沫
• preferred标签位置（左上，上，下，右等）应尊重在一定程度上
• 字体大小可以改变

是否有任何有用的库/算法呢？ （preferably的JavaScript或PHP）

Are there any helpful libraries / algorithms for this? (preferably JavaScript or PHP)

（图像中的标签位置不符合这些要求）的

推荐答案

这可归结为一个线性规划问题。你想最大化或最小化功能（重新presenting的权重或解决方案的善）受到一定的制约（你的要求）。您需要正式的要求值。事情是这样的：

This can be formulated as a Linear Programming problem. You want to maximize or minimize a function (representing the "weight" or "goodness" of the solution) subject to certain constraints (your requirements). You'll need to formalize your requirements as values. Something like this:

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 加权大多数，因此最重要的约束，不能违背硬性限制。

I made up the coefficients and the constraints, you can use them to tune the result based on which features are most important to you. Coefficients increase the value of a requirement (in this case, f4 is weighted most so it 'most important'. The constraints are hard limits that cannot be violated.

由于这是一个众所周知的问题，则可以使用现在许多方法解决。单纯形法是受欢迎的。有一个在 Cormen等一整章。人有关这些问题。

Since this is a well-known problem, you can now solve it using a number of methods. The Simplex algorithm is popular. There is a whole chapter in Cormen et. al about these problems.

这篇关于气泡图标签位置的算法？ （在JavaScript preferably）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！