Algorytm rozprowadzania etykiet w atrakcyjny wizualnie i intuicyjny sposób

Krótka wersja

Czy istnieje wzór projektowy do dystrybucji etykiet pojazdów w sposób nienakładający się na siebie, umieszczając je jak najbliżej pojazdu, którego dotyczą? Jeśli nie, to czy jakakolwiek metoda, którą sugeruję, jest wykonalna? Jak sam byś to wdrożył?

Rozszerzona wersja

W grze, którą piszę, widzę z lotu ptaka moje powietrzne pojazdy. Obok każdego pojazdu mam również małą etykietę z kluczowymi danymi na temat pojazdu. To jest zrzut ekranu:

Ponieważ pojazdy mogły latać na różnych wysokościach, ich ikony mogą się nakładać. Jednak nie chciałbym, aby ich etykiety nakładały się (lub etykieta z pojazdu „A” nie pokrywała się z ikoną pojazdu „B”).

Obecnie mogę wykryć kolizje między duszkami i po prostu odpycham obraźliwą etykietę w kierunku przeciwnym do pokrywającego się inaczej duszka . Działa to w większości sytuacji, ale gdy przestrzeń powietrzna jest zatłoczona, etykieta może zostać odsunięta bardzo daleko od pojazdu, nawet jeśli istnieje alternatywna „inteligentniejsza” alternatywa. Na przykład otrzymuję:

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

gdzie byłoby lepiej (= etykieta bliżej pojazdu), aby uzyskać:

          B - label
label - A
          C - label

EDYCJA: Należy również wziąć pod uwagę, że oprócz nakładających się pojazdów, mogą istnieć inne konfiguracje, w których etykiety pojazdów mogą się nakładać (przykłady ASCII-art pokazują na przykład trzy bardzo bliskie pojazdy, w których etykieta Aoznaczałaby ikonę Bi C).

Mam dwa pomysły, jak poprawić obecną sytuację, ale zanim poświęciłem czas na ich wdrożenie, pomyślałem o zwróceniu się do społeczności po poradę (w końcu wydaje się, że jest to „dość powszechny problem”, że może istnieć wzorzec projektowy).

Oto, co warto, oto dwa pomysły, o których myślałem:

Slot-isation przestrzeni na etykiety

W tym scenariuszu podzieliłem cały ekran na „miejsca” na etykiety. Wówczas każdy pojazd zawsze miałby etykietę umieszczoną w najbliższym pustym (pusty = brak innych duszków w tym miejscu).

Wyszukiwanie spiralne

Z położenia pojazdu na ekranie starałbym się umieszczać etykietę pod rosnącymi kątami, a następnie z rosnącymi promieniami, aż do znalezienia nie nakładającej się lokalizacji. Coś poniżej:

try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...

Zasadniczo ten problem jest podobny do problemu unikania kolizji. Tak, samoloty mogą latać na różnych wysokościach, ale ich etykiety są na tej samej „wysokości”.

Istnieją algorytmy, takie jak Unaligned Collision Avoidance , które byłyby dla ciebie krokiem we właściwym kierunku. Oczywiście w twojej sytuacji etykiety są „przywiązane” do swoich samolotów, więc mają ograniczony zakres ruchu.

Jeśli spojrzysz na zachowanie flokowania , chcesz wdrożyć pierwszą „zasadę” flokowania: odpychanie na krótki dystans. Jednak zamiast „sterować” w kierunku, który jest oddalony od najbliższych sąsiadów, użyjesz wektora „daleko” jako lokalizacji umieszczania etykiety.

Na przykład:

Duże czarne kółko reprezentuje obszar wpływu, zielone kółko oznacza prawidłowe rozmieszczenie etykiety, środkowa zielona kropka jest płaszczyzną, którą aktualnie rozważasz, mała zielona kropka to punkt na okręgu wybranym do umieszczenia etykiety.

Teraz czarne kropki mogą reprezentować albo inne etykiety, albo inne płaszczyzny. Nie jestem pewien, który z nich działałby najlepiej, możesz uzyskać lepsze unikanie, gdyby były to inne wytwórnie, ale nie jestem pewien. Oczywiście strzałki „siły” są wektorami kierunkowymi między twoją bieżącą płaszczyzną a „obiektami wpływu”. Wreszcie, pudełko to etykieta.

Więc korzystając z powyższego przykładu, myślę, że przyniosłoby to coś takiego:

            - label
           / 
          B 
label - A
          C 
           \
            - label

Przy użyciu tej metody istnieją sytuacje, w których należy wykonać specjalne przypadki, na przykład trzy płaszczyzny ustawione pionowo:

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

Wszystkie trzy etykiety mogą przerzucać flop od prawej do lewej, w zależności od sposobu zdefiniowania narożników etykiety. Zasadniczo musisz tylko uważać na kąty wokół koła, w których etykiety mogą zmieniać, z którego rogu są rysowane: 0, 90, 180, 270.

Myślę, że w końcu wyglądałoby to całkiem fajnie, obserwując, jak etykiety unikają się nawzajem. Jeśli robi się to zbyt rozpraszające, być może możesz zaokrąglić do najbliższych 10 stopni, aby rzadziej się poruszać.

Przepraszam za dziwne szczegóły, większość z tych rzeczy, o których myślałem, kiedy tworzyłem menu radialne dla mojej gry, ale myślę, że w tej „dynamicznej” formie zadziałałoby całkiem nieźle.

Po namyśle postanowiłem w końcu zastosować spiralną metodę wyszukiwania , którą krótko opisałem w pierwotnym pytaniu.

Uzasadnieniem jest to, że metoda Byte56 wymaga specjalnego traktowania w pewnych warunkach, podczas gdy spiralne wyszukiwanie nie, i koduje w naprawdę zwarty sposób . Ponadto wyszukiwanie spriralling podkreśla znalezienie bliższego miejsca dla pojazdu, aby umieścić etykietę, co IMO jest głównym czynnikiem zapewniającym czytelność mapy.

Proszę jednak nadal głosować za jego odpowiedzią, ponieważ jest ona nie tylko przydatna, ale także bardzo dobrze napisana!

Oto zrzut ekranu wyniku uzyskanego za pomocą spiralnego kodu:

A oto kod, który - choć nie jest samowystarczalny - daje wyobrażenie o tym, jak prosta jest implementacja:

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

Uwaga 1 - tag.place()zwraca True, jeśli znacznik znajduje się całkowicie w widocznym obszarze ekranu / radaru. Ta linia brzmi więc: „kontynuuj zapętlanie, jeśli tag znajduje się poza radarem lub nakłada się na coś innego ...”

Uwaga 2 - tag.connector.updateto metoda, która rysuje linię łączącą ikonę samolotu z etykietą / tagiem z informacją tekstową.