Beschriftungen für Objekte im 2D-Raum ohne Überlappung anordnen

Question

Ich muss Textbeschriftungen an Objekten anbringen, die willkürlich über den Bildschirm verteilt sind und sich ständig bewegen.

Die Standard- und Idealposition für eine Beschriftung ist auf der rechten Seite des Objekts, auf das sie sich bezieht. Ich brauche eine Möglichkeit, die Beschriftungen dynamisch neu anzuordnen (oder möglicherweise zu verschmelzen), damit sie sich nicht gegenseitig oder andere Objekte überlappen.

Sie sollten sich noch so nah wie möglich an den Objekten befinden und keine plötzlichen ruckartigen Bewegungen zeigen, sofern sich die Objekte selbst gleichmäßig bewegen.

Ich habe keine Ahnung, wie man das macht. Gibt es einen Algorithmus für so etwas?

Answer 1

Ich würde vorschlagen, Physik zu verwenden. Befestigen Sie das Etikett mit einer Feder am Objekt und üben Sie auf jedes Etikett eine abstoßende Kraft aus, damit sie nicht in die Nähe anderer Objekte (und deren Etiketten) kommen, außer dem, das sie beschreiben.

Answer 2

Anbringen des Etiketts: Man kann das engste Quadrat ermitteln, das die Objekte umschließt, und dann eine Senkrechte von der rechten Seite des Quadrats auf das Objekt legen. Platzieren Sie das Etikett an diesem Schnittpunkt.

Erkennung von Kollisionen: Speichern Sie die Koordinaten des Etiketts, und bevor Sie den Endpuffer anzeigen, können Sie die Kollision der Etiketten anhand der Koordinaten erkennen.

Vermeiden Sie plötzliche Bewegungen: Dies ist der schwierigste Teil, denn wenn Sie die Position der Etiketten nur dann ändern, wenn eine Kollision erkannt wird, wird es zu einem Ruck kommen. Der einfache Ansatz besteht darin, sie zusammenzuführen, wenn die Kollision erkannt wird, und zwar so lange, wie eine Kollision besteht. Der schwierigere Ansatz wäre, die Beschriftungen zu verschieben. Um dies reibungslos zu gestalten, müssen Sie im Voraus eine Kollision erkennen, die einige Frames vor Ihnen auftauchen könnte, und die Beschriftungen auf einer Bahn verschieben, die eine Kollision vermeiden würde.

Answer 3

Ich habe das Problem mit ziemlich viel roher Gewalt gelöst

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

und führen Sie dies in einem Zyklus mehrmals durch, da Objekte wachsen, wenn sie andere Objekte verschlucken, so dass die Kollisionsprüfung erneut durchgeführt werden muss (neue Überschneidungen können mitten im Zyklus auftreten). Bei der Anzahl der Objekte, mit denen ich arbeite, komme ich jedoch nie auf mehr als 3 Zyklen.

Die Funktion should_swallow() bestimmt, ob es besser ist, ein Objekt zu verschlucken oder von ihm verschluckt zu werden, und zwar auf der Grundlage von Größe, Position und dem, was in den vorhergehenden Frames passiert ist, um Flimmern zu verhindern.