Упорядочить метки для объектов в 2D пространстве без перекрытия

Question

Мне нужно прикрепить текстовые метки к объектам, которые распределены случайным образом по экрану и продолжают двигаться.

По умолчанию и идеальное положение для метки находится в правой части объекта, к которому он относится. Мне нужен способ динамически переставить (или, возможно, объединить) ярлыки, чтобы они никогда не перекрывали друг друга или другие объекты.

Они все равно должны быть как можно ближе к объектам, и не должны, при условии, что сами объекты движутся плавно, проявляют какое-либо отвратительное рывкое движение.

Я понятия не имею, как это сделать, есть ли алгоритм для чего-то подобного?

Answer 1

Я решил эту проблему, используя довольно много грубой силы

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

и сделать это в цикле несколько раз, потому что объекты растут, когда они глотают другие объекты, поэтому проверка на столкновение должно быть сделано снова (новые перекрытия могут появиться середина цикла). Никогда не делайте больше трех циклов, но с количеством объектов, с которыми я работаю.

Функция should_swallow() определяет, лучше ли проглотить объекты или проглотить их, исходя из размера, положения и того, что произошло в предыдущих кадрах, чтобы предотвратить мерцание.

Answer 2

Я бы предложил использовать физику. Прикрепите ярлык к объекту пружиной и примените силу отталкивания к каждой этикетке, чтобы они не приближались к другим объектам (и их меток), за исключением тех, которые они описывают.

Answer 3

Нанесение ярлыка: Вы можете найти самый плотный квадрат, который закрывает объекты, а затем отбрасывает перпендикуляр с правой стороны квадрата на объект. Поместите метку в эту точку пересечения.

Обнаружение столкновения: Сохраните координаты метки и перед отображением окончательного буфера вы можете обнаружить столкновение меток с использованием координат.

Избегайте резких движений: Это сложная часть, потому что если вы измените расположение меток только при обнаружении столкновения, тогда появится рывок. Простой подход - объединить их при обнаружении столкновения и до тех пор, пока существует столкновение. Более сложный подход заключается в перемещении этикеток. Чтобы сделать это гладким, вам придется заранее обнаружить любое столкновение, которое может показаться впереди, и начать перемещать ваши метки на какой-либо траектории, чтобы избежать любого столкновения.