layout - 在 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() 函数根据大小、位置和之前帧中发生的情况来确定是吞下对象还是被它吞下更好，以防止闪烁。