在 2D 空间中排列对象的标签而不重叠

Question

我需要将文本标签附加到在屏幕上随机分布并不断移动的对象。

标签的默认和理想位置是在它所引用的对象的右侧。 我需要一种方法来动态地重新排列（或可能合并）标签，以便它们永远不会相互重叠或与其他对象重叠。

它们仍应尽可能靠近物体，并且在物体本身平稳移动的情况下，不应表现出任何突然的急速运动。

我不知道该怎么做，有类似的算法吗？

Answer 1

我建议使用物理学。 用弹簧将标签贴在物体上，并对每个标签施加排斥力，这样它们就可以避免靠近其他物体（及其标签），但不包括它们所描述的物体。

Answer 2

放置标签：
您可以找出闭合物体的最紧密的正方形，然后从正方形的右侧向物体垂下一条垂线。 将标签放置在该交叉点处。

检测碰撞：
存储标签的坐标，在显示最终缓冲区之前，您可以使用坐标检测标签的碰撞。

避免突然的动作：
这是困难的部分，因为如果仅在检测到碰撞时才更改标签的位置，那么就会出现抖动。 简单的方法是在检测到碰撞时以及只要碰撞存在就将它们合并。 更困难的方法是移动标签。 为了使这一过程顺利进行，您必须事先检测可能出现在前面几帧的任何碰撞，并开始在某些轨迹上移动标签以避免任何碰撞。

Answer 3

我使用相当强力的方法解决了这个问题

for each object as a
    for each colliding object as c
        if should_swallow(a, c)
            swallow(a, c)

，并在一个循环中多次执行此操作，因为对象在吞噬其他对象时会增长，因此必须再次进行碰撞检查（新的重叠可能会在循环中出现）。 不过，根据我正在处理的对象数量，永远不要超过 3 个周期。

should_swallow() 函数根据大小、位置以及前一帧中发生的情况来确定是吞掉物体更好还是被它吞掉，以防止闪烁。