Algorithmus zum visuell ansprechenden und intuitiven Verteilen von Etiketten

24

Kurze Version

Gibt es ein Entwurfsmuster für die Verteilung von Fahrzeugetiketten in nicht überlappender Weise, um sie so nah wie möglich an dem Fahrzeug zu platzieren, auf das sie sich beziehen? Wenn nicht, ist eine der von mir vorgeschlagenen Methoden praktikabel? Wie würden Sie das selbst umsetzen?

Erweiterte Version

In dem Spiel, das ich schreibe, habe ich eine Vogelperspektive meiner Luftfahrzeuge. Ich habe auch neben jedem der Fahrzeuge ein kleines Etikett mit Schlüsseldaten über das Fahrzeug. Dies ist ein Screenshot:

Zwei Fahrzeuge mit ihren Etiketten

Da die Fahrzeuge nun in unterschiedlichen Höhen fliegen könnten, könnten sich ihre Symbole überlappen. Ich möchte jedoch nicht, dass sich die Beschriftungen überschneiden (oder dass sich die Beschriftungen von Fahrzeug 'A' mit dem Symbol von Fahrzeug 'B' überschneiden).

Gegenwärtig kann ich Kollisionen zwischen Sprites erkennen und schiebe das anstößige Etikett einfach entgegen der Richtung des ansonsten überlappenden Sprites weg . Dies funktioniert in den meisten Situationen, aber wenn der Luftraum überfüllt ist, kann das Etikett sehr weit vom Fahrzeug weggeschoben werden, selbst wenn es eine alternative "intelligentere" Alternative gibt. Zum Beispiel bekomme ich:

  B - label
A -----------label
  C - label

Wo wäre es besser (= Etikett näher am Fahrzeug) zu bekommen:

          B - label
label - A
          C - label

EDIT: Es muss auch berücksichtigt werden, dass es neben dem Fall überlappender Fahrzeuge auch andere Konfigurationen geben kann, in denen sich die Fahrzeugkennzeichnungen überlappen können (die ASCII-Kunstbeispiele zeigen zum Beispiel drei sehr nahe Fahrzeuge, in denen das Etikett von Adas Symbol von überlappen würde Bund C).

Ich habe zwei Ideen, wie ich die gegenwärtige Situation verbessern kann, aber bevor ich Zeit damit verbringe, sie umzusetzen, habe ich mir überlegt, mich an die Community zu wenden, um Rat zu holen (schließlich scheint es ein "häufig genug auftretendes Problem" zu sein, dass ein Entwurfsmuster dafür existieren könnte).

Für das, was es wert ist, sind hier die zwei Ideen, an die ich gedacht habe:

Slot-isierung des Label-Space

In diesem Szenario würde ich den gesamten Bildschirm in "Slots" für die Etiketten unterteilen. In diesem Fall wird für jedes Fahrzeug immer das Etikett in das nächstgelegene Leerzeichen gesetzt (leer = keine anderen Sprites an dieser Stelle).

Spiralige Suche

Ab der Position des Fahrzeugs auf dem Bildschirm würde ich versuchen, das Etikett in zunehmenden Winkeln und dann in zunehmenden Radien zu platzieren, bis eine nicht überlappende Position gefunden wird. Etwas auf der ganzen Linie von:

try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...
Mac
quelle
1
Wie viele Flugzeuge können sich gleichzeitig überlappen?
Wangburger
1
@wangburger - Hätte nie gedacht, dass dies relevant ist (wäre interessiert, mehr über Ihre Gedanken zu erfahren), aber die Antwort lautet: Es hängt von der Spielstrategie des Spielers ab. Technisch gesehen könnten sich 24 Fahrzeuge auf der Welt überlappen, aber eine realistische Zahl in den meisten Spielbedingungen ist 3-4.
Mac
3
Ist es nicht verwirrender, wenn sich Beschriftungen relativ zur Ebene bewegen, als wenn sie sich überlappen, während sie für einen angemessenen Zeitraum statisch sind?
Maik Semder
3
Vielleicht interessieren Sie sich auch für de.wikipedia.org/wiki/… - dies ist kein einfaches Problem. Erwarten Sie nicht, eine perfekte Lösung zu finden.
Blecki
2
GraphViz ist eine Reihe von Werkzeugen zum visuell ansprechenden Erstellen von Diagrammen mit der Tendenz, Überschneidungen in Beschriftungen zu vermeiden. Es ist zwar möglicherweise nicht direkt verwendbar, Sie können jedoch möglicherweise Informationen aus der Dokumentation oder dem Quellcode zu den Algorithmen abrufen, mit denen die Diagramme erstellt werden. Sie scheinen zum Beispiel sowohl Modelle auf Energiebasis als auch Modelle auf Federbasis zu haben.
Lars Viklund

Antworten:

14

Im Wesentlichen ähnelt dieses Problem einem Problem der Kollisionsvermeidung. Ja, die Flugzeuge können in verschiedenen Höhen fliegen, aber ihre Beschriftungen befinden sich alle auf derselben "Höhe".

Es gibt Algorithmen wie Unaligned Collision Avoidance , die für Sie einen Schritt in die richtige Richtung darstellen. Natürlich sind die Etiketten für Ihre Situation an ihre Ebenen "angebunden", so dass sie einen begrenzten Bewegungsbereich haben.

Wenn Sie sich das Beflockungsverhalten ansehen , möchten Sie die erste "Regel" der Beflockung implementieren: Abstoßung über kurze Entfernungen. Anstatt jedoch in die von den nächsten Nachbarn entfernte Richtung zu "steuern", verwenden Sie den Vektor "away" als Platzierungsort für Ihr Etikett.

Beispielsweise:

Bildbeschreibung hier eingeben

Der große schwarze Kreis stellt Ihren Einflussbereich dar, der grüne Kreis stellt die gültigen Platzierungen für das Etikett dar, der mittlere grüne Punkt ist die Ebene, die Sie gerade betrachten, und der kleine grüne Punkt ist der Punkt auf dem Kreis, der für die Platzierung des Etiketts ausgewählt wurde.

Jetzt könnten die schwarzen Punkte entweder andere Bezeichnungen oder andere Ebenen darstellen. Ich bin mir nicht sicher, welches am besten funktioniert. Wenn es sich um andere Labels handelt, kann man das besser vermeiden, aber ich bin mir nicht sicher. Offensichtlich sind die "Kraft" -Pfeile die Richtungsvektoren zwischen Ihrer aktuellen Ebene und den "Einflussobjekten". Schließlich ist die Box das Etikett.

Wenn Sie also Ihr Beispiel oben verwenden, würde dies ungefähr so ​​aussehen:

            - label
           / 
          B 
label - A
          C 
           \
            - label

Wenn Sie diese Methode verwenden, müssen Sie einige Sonderfälle erstellen, z. B. drei Ebenen, die vertikal ausgerichtet sind:

          - label       label -
          |                   |
          B                   B
  label - A                   A - label
          C                   C
          |                   |
          - label       label -

Alle drei Beschriftungen können von rechts nach links umkehren, je nachdem, wie Ihre Beschriftungsecken definiert sind. Grundsätzlich müssen Sie nur auf die Winkel um den Kreis achten, in denen Ihre Beschriftungen umschalten können, von welcher Ecke sie gezeichnet werden: 0, 90, 180, 270.

Bildbeschreibung hier eingeben

Ich denke am Ende würde das irgendwie ordentlich aussehen, wenn man beobachtet, wie sich die Labels ausweichen. Wenn es zu ablenkend wird, können Sie möglicherweise für weniger häufige Bewegungen auf die nächsten 10 Grad runden.

Tut mir leid für die seltsamen Details, die meisten Dinge, über die ich nachgedacht habe, als ich ein Radialmenü für mein Spiel erstellt habe, aber ich denke, in dieser "dynamischen" Form würde es ziemlich gut funktionieren.

MichaelHouse
quelle
1
Eigentlich hat mein Beispiel nicht einmal Ebenen berücksichtigt, die direkt übereinander liegen, da ihre x- und z-Koordinaten genau übereinstimmen (aber wenn Sie Floats verwenden, passiert dies wahrscheinlich nicht). Die Beispiele, die ich gegeben habe, beziehen sich auf Flugzeuge in der Nähe. Außerdem können Sie sich, wie gesagt, die schwarzen Punkte im obigen Bild als andere Bezeichnungen vorstellen.
MichaelHouse
1
Oh, anscheinend haben Sie Ihren Kommentar entfernt?
MichaelHouse
1
Was ich mit meinem vorherigen [schlecht formulierten und daher jetzt entfernten] Kommentar gemeint habe, war, dass Sie ein Szenario haben könnten, in dem ein Etikett von anderen nicht beweglichen (dh Fahrzeugen) Sprites "gefangen / umgeben" wird. In diesem Fall sollte das Etikett möglicherweise außerhalb des umschließenden Kreises "springen", aber mir ist nicht genau klar, wie dies geschehen soll. Übrigens: Ich dachte ursprünglich, dass der grüne Punkt Ihres Bildes mehrere übereinander gestapelte Flugzeuge waren, aber nach Ihrem Kommentar wurde mir klar, dass ich falsch lag ... Entschuldigung!).
Mac
1
Ah ich sehe. Dann würden Sie die schwarzen Punkte als Ebenen UND Bezeichnungen behandeln. Wenn die durch die erste Iteration gefundene Position nicht gut ist, verdoppeln Sie den Radius und überprüfen Sie erneut. Oder Sie haben bereits einen Vektor, der von der Mehrheit der Masse abweicht. Sie können dem folgen, bis Sie einen Ort finden, der funktioniert. Ich denke jedoch, dass die erste Methode bessere Ergebnisse erzielen würde.
MichaelHouse
9

Nach einigem Überlegen entschied ich mich schließlich für die Implementierung der spiralförmigen Suchmethode , die ich in der ursprünglichen Frage kurz beschrieben hatte.

Der Grund dafür ist, dass die Methode des Byte56 für bestimmte Bedingungen eine spezielle Behandlung benötigt, während die spiralförmige Suche dies nicht tut, und dass sie sehr kompakt codiert . Auch bei der Spriralling-Suche wird der Schwerpunkt darauf gelegt , den nächstgelegenen Ort zum Fahrzeug zu finden, um das Etikett anzubringen. Dies ist IMO der Hauptfaktor, um die Karte lesbar zu machen.

Bitte stimmen Sie seiner Antwort jedoch weiterhin zu, da sie nicht nur nützlich, sondern auch sehr gut geschrieben ist!

Hier ist ein Screenshot des Ergebnisses, das mit dem Spiralcode erzielt wurde:

Bildbeschreibung hier eingeben

Und hier ist der Code, der - obwohl nicht in sich geschlossen - eine Vorstellung davon gibt, wie einfach die Implementierung ist:

def place_tags(self):
    for tag in self.tags:
        start_angle = tag.angle
        while not tag.place() or is_colliding(tag):  #See note n.1
            tag.angle = (tag.angle + angle_step) % 360
            if tag.angle == start_angle:
                tag.radius += radius_step
        tag.connector.update()                       #See note n.2

Hinweis 1 - tag.place()Gibt True zurück, wenn sich das Tag vollständig im sichtbaren Bereich des Bildschirms / Radars befindet. Diese Zeile lautet also: "Schleife weiter, wenn sich das Tag außerhalb des Radars befindet oder etwas anderes überlappt ..."

Anmerkung 2 - tag.connector.updateist die Methode, mit der die Linie zwischen dem Flugzeugsymbol und dem Etikett mit den Textinformationen gezogen wird.

Mac
quelle
Gut gemacht, das ist in der Tat sehr kompakt. Danke für das Lob. Auch danke, dass Sie uns mitgeteilt haben, was Sie getan haben. Dies ist immer nützlich, wenn Sie später nach Antworten suchen. Auf dem Screenshot sieht es so aus, als würde es sehr gut funktionieren! Stellen Sie sicher, dass Sie Ihre Antwort akzeptieren, da es das ist, was Sie letztendlich gemacht haben.
MichaelHouse
@Byte56 - Danke für das "Retro-Lob";) Ich warte auf die Auswahl der Antwort als angenommen, da ich auch Ihre Lösung noch codieren und das Ergebnis vergleichen möchte. Zum einen vermute ich, dass Ihre Lösung zu längerem, aber auch schnellerem Code führen könnte. Außerdem würde ich gerne sehen, wie sich die beiden in überfüllten Lufträumen vergleichen lassen ... also besteht immer noch die Möglichkeit, dass ich den Code mit Ihrem Algorithmus veröffentlichen kann. Beobachten Sie diesen Raum! ;)
Mac
@ Byte56 - Ich habe versucht, Ihren Algorithmus zu implementieren. Es funktionierte gut und schnell in niedrigen Dichten, aber sobald der Speicherplatz voll war, hatte ich Probleme, eine einfache Implementierung zu finden, die bestimmte Situationen bewältigen würde, in denen ein Etikett einen Block anderer Etiketten "überspringen" oder von Nicht- bewegliche (dh Flugzeugsymbol) Sprites. Ich markiere diese Antwort dann als ausgewählt, aber nochmals: Vielen Dank für die Zeit und den Beitrag! :)
Mac