Arrange labels for objects in 2D space without overlap

Question

I need to attach text labels to objects that are spread randomly across the screen and keep moving.

The default and ideal position for a label is on the right side of the object it refers to. I need a way to dynamically rearrange (or possibly merge) the labels so that they never overlap each other or other objects.

They should still be as close to the objects as possible and should not, provided that the objects themselves move smoothly, show any suddent jerky movement.

I have no idea how to do it, is there an algorithm for something like this?

Answer 1

I would suggest using physics. Attach the label to the object with a spring and apply a repelling force to every label so they avoid getting close to other objects (and their labels), excluding the one they describe.

Answer 2

Putting the label: You can figure out the tightest square which closes the objects and then drop a perpendicular from the right side of the square onto the object. Place the label at this point of intersection.

Detecting collision: Store the coordinates of the label and before you display the final buffer you can detect the collision of the labels using the coordinates.

Avoid sudden movements: This is the hard part because if you change the location of the labels only when collision is detected then there is going to be a jerk. The simple approach is to merge them when the collision is detected and for as long as a collision is there. The harder approach would be to move the labels. To make this smooth you will have to detect beforehand any collision that may appear some frames ahead and start moving your labels on some trajectory that would avoid any collision.

Answer 3

I solved this using pretty much brute force

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

and do this in a cycle several times because objects grow when they swallow other objects, so the collision check has to be done again (new overlaps may appear mid-cycle). Never hit more than 3 cycles though, with the number of objects I'm working with.

The should_swallow() function determines if it's better to swallow an objects or get swallowed by it, based on size, position and what happened in previous frames to prevent flicker.