31

我想自动放置 100-200 个气泡标签，以便满足以下要求：

  • 标签不应重叠
  • 标签最好不要与气泡重叠
  • 标签应靠近气泡
  • 应在一定程度上尊重首选标签位置（左上、上、下、右等）
  • 字体大小可以变化

有没有对此有用的库/算法？（最好是 JavaScript 或 PHP）

（图片中的标签放置不符合这些要求）

在此处输入图像描述

4

9 回答 9

9

这个怎么样？

一种高效的散点图标注算法

于 2011-04-29T22:48:28.230 回答
5

我想你正在使用 javascript、html 和 css？无论如何，我想到了两种方法。

首先是将其表述为一个优化问题。您需要计算每个标签的理想位置。这将基于气泡的大小、所需的位置（即上、下、左、右）和标签的大小（字体和长度）。然后你需要参数化你的坐标，例如到一个包含 2N 个元素的列表中，其中 N 是标签的数量。然后，您需要在某个位置初始化标签（如果使用遗传算法，则为种群）并应用需要成本函数的优化算法。这将基于一组标签位置与理想位置的距离，以及任何违反规则的情况，例如重叠。

或者，让它成为一个物理问题。通过一些刚性链接将每个标签“附加”到其气泡上。给每个标签和每个气泡一个排斥力，并添加一个全局和更强的重力（在首选的上/左/右/下方向）。进行简短的物理模拟，直到达到平衡。数学应该不会太难。

于 2011-05-06T00:22:30.613 回答
5

我认为如果您在工具中使用 D3，则可以使用“基于力”的标签放置算法。该解决方案最初属于Max Planck Research Networks，但已经有一个现成的 Javascript 示例，这里：D3 中基于强制的标签放置

于 2013-08-05T15:56:58.617 回答
4

这可以表述为线性规划问题。您希望在某些约束（您的要求）下最大化或最小化一个函数（代表解决方案的“权重”或“优度”）。您需要将您的要求形式化为值。像这样的东西：

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中有一整章。关于这些问题。

于 2011-05-02T17:54:20.293 回答
3

也许可以使用一些帮助工具包，如下所示：

于 2011-05-06T20:18:06.807 回答
1

不幸的是，我认为很难在 Javascript 或 PHP 中找到这个现成的解决方案。但是，我确实认为您的问题可以分解为小的子问题（根据您的规则），以帮助您设计解决方案。

我会确定您的哪些规则最重要。从您提供的图表的外观来看，我会说规则 #1 和 #2 将最大程度地提高可读性。

为了根据这些规则确定位置，我将计算文本和气泡的边界容器并测试相交。交叉路口后，移动到没有交叉路口的位置。如果找不到，请使用重叠最少的空间。

这将允许您还为左上角、右下角等创建加权放置启发式方法，以帮助将标签放置在“首选”位置。

我会尝试使用两个带有两个标签的气泡写出一小部分放置算法，这两个标签通常很接近并且可能会重叠。如果您可以概括您的放置算法以适用于这个小子集，那么您应该可以继续使用更多气泡。

此外，也许您可​​以使用 kd-tree 或其他空间分区数据结构的顺序来定位最近的邻居以避免。

于 2011-05-02T16:54:29.400 回答
1

我在 Java 中找到了一种实际上可以解决这个问题的方法，称为 Force Directed Map Labeling，是一种开源学院体验。

这是文档+项目源代码：Force Directed Map Labeling

于 2013-12-11T16:50:25.763 回答
0

怎么样

label.substring(0, Math.sqrt(bubbleValueOrRadius))

我在 protovis.js 示例之一中发现了这一点。

于 2011-08-04T01:32:01.227 回答
0

这个线程很好地涵盖了一些方法。我正在使用具有多个焦点的力布局，因为它似乎是最好的整体方法。

于 2016-02-11T04:18:26.620 回答