Расстановка меток для объектов в 2D-пространстве без наложения

Question

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

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

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

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

Answer 1

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

Answer 2

Я решил это, используя почти грубую силу

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

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

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

Answer 3

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

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

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