android - 在 map 上排列标签，使其不重叠

Question

在我的 (Android) 应用程序中，我正在显示一张 map ，上面有一些标记的对象。当对象彼此非常接近时，标签会重叠，如本示例图片(底部三个对象)所示:

我想用一条指向它们位置的线来显示标签，例如这里:

但是，我想不出一种有效的算法来计算线条所需的角度，以使所有标签都不重叠。 map 也可以缩放，而标签大小不变；因此，所需的角度将随缩放级别而变化。

是否有任何计算成本不那么高的算法(即，我不需要在每一帧计算所有对象之间的碰撞)可以在这里帮助我？或者我应该预先计算一些东西并将其与应用程序一起发送吗？ (对象总是固定的)

Answer 1

一些建议:

1. 使用空间分区数据结构(k-D 树、四叉树)进行碰撞检测。这将避免强力碰撞计算。

2. 将 1. 与简单的贪心策略(以提高效率)结合起来:按优先级对标签进行排序(例如，大城市优先)。对于应显示的每个标签，尝试多个位置(例如项目符号的左侧、右侧、顶部、底部)并选择第一个有效的位置(如果有)(并呈现标签)。

3. 对于其引用点(子弹)在当前缩放级别在空间上非常接近的标签:仅对子弹进行第一遍(碰撞检测和可能的渲染)。使用 1. 应该可以检测到彼此靠近的项目符号并准备一个伪标签，它将项目符号的所有文本标签组合在一起(使用所需的基于行的布局类型)并且可以使用(使用一些变体，如水平或垂直分组)，碰撞检测 + 渲染 channel 为 2。

使用这种方法，实际上并没有调整线之间的角度以避免碰撞。相反，计算是为了避免组标签内的重叠，并结合典型的碰撞检测来避免与其他标签重叠。