在二维空间中排列物体的标签，避免重叠。

Question

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

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

它们仍应尽可能靠近对象，并且不应该显示任何突然的抖动运动，只要对象本身平稳移动即可。

我不知道如何做到这一点，是否有算法可以解决这个问题？

- Tomas Andrle

Answer 1

我建议使用物理学。将标签通过弹簧固定在物体上，并对每个标签施加排斥力，使它们避免靠近其他物体（和它们的标签），但不包括所描述的那个物体。

- macbirdie

Answer 2

我使用了几乎是暴力的方法来解决这个问题

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

需要循环多次执行此操作，因为对象在吞噬其他对象时会变大，因此必须再次进行碰撞检查（新的重叠可能会在循环中出现）。但是，由于我处理的对象数量较多，不要超过3个周期。

should_swallow()函数根据大小、位置和前几帧发生的情况来确定是最好吞噬一个对象还是被其吞噬，以防止闪烁。

- Tomas Andrle

Answer 3

标记的放置： 您可以确定最紧密的正方形，将其闭合在对象上，然后从正方形的右侧垂直地落下一个垂线到对象上。将标签放置在这个交点处。

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

避免突然移动： 这是难点，因为如果仅在检测到碰撞时更改标签位置，则会出现抖动。简单的方法是在检测到碰撞时合并它们，并且只要存在碰撞，就保持合并状态。更困难的方法是移动标签。为了使其平滑，您需要预先检测出可能出现在几帧之后的任何碰撞，并开始在某条轨迹上移动标签，以避免任何碰撞。

- Prashast