Automatyczne umieszczanie etykiet
Automatyczne umieszczanie etykiet , czasami nazywane umieszczaniem tekstu lub umieszczaniem nazw , obejmuje komputerowe metody automatycznego umieszczania etykiet na mapie lub wykresie. Jest to związane z projektem typograficznym takich etykiet .
Typowymi obiektami przedstawianymi na mapie geograficznej są obiekty liniowe (np. drogi), terenowe (kraje, działki, lasy, jeziora itp.) oraz punktowe (wioski, miasta itp.). Oprócz przedstawienia obiektów mapy w sposób dokładny pod względem geograficznym, niezwykle ważne jest umieszczenie nazw identyfikujących te obiekty w taki sposób, aby czytelnik natychmiast wiedział, która nazwa opisuje który obiekt.
Automatyczne umieszczanie tekstu jest jednym z najtrudniejszych, najbardziej złożonych i czasochłonnych problemów w tworzeniu map i GIS (Geographic Information System) . Inne rodzaje grafiki komputerowej – jak wykresy , wykresy itp. – również wymagają dobrego umieszczenia etykiet, nie mówiąc już o rysunkach technicznych oraz profesjonalnych programów do tworzenia tych rysunków i wykresów, takich jak arkusze kalkulacyjne (np. Microsoft Excel ) czy programy obliczeniowe (np. Mathematica ).
Naiwnie umieszczone etykiety nadmiernie się nakładają, co powoduje, że mapa jest trudna lub wręcz niemożliwa do odczytania. Dlatego GIS musi umożliwiać kilka możliwych miejsc umieszczenia każdej etykiety, a często także opcję zmiany rozmiaru, obracania, a nawet usuwania (ukrywania) etykiety. Następnie wybiera zestaw miejsc docelowych, który powoduje najmniejsze nakładanie się i ma inne pożądane właściwości. Dla wszystkich, z wyjątkiem najbardziej trywialnych konfiguracji, problem jest NP-trudny .
Algorytmy oparte na regułach
Algorytmy oparte na regułach próbują naśladować doświadczonego kartografa. Przez stulecia kartografowie rozwinęli sztukę sporządzania map i umieszczania etykiet. Na przykład doświadczony kartograf powtarza nazwy dróg kilka razy dla długich dróg, zamiast umieszczać je raz, lub w przypadku Ocean City przedstawionego przez punkt bardzo blisko brzegu, kartograf umieściłby etykietę „Ocean City” nad ziemi, aby podkreślić, że jest to nadmorska miejscowość.
Kartografowie działają w oparciu o przyjęte konwencje i zasady, takie jak te wyszczególnione przez szwajcarskiego kartografa Eduarda Imhofa w 1962 roku. Na przykład Nowy Jork, Wiedeń, Berlin, Paryż czy Tokio muszą pojawiać się na mapach krajów, ponieważ są to etykiety o wysokim priorytecie. Po ich umieszczeniu kartograf umieszcza kolejną najważniejszą klasę etykiet, na przykład główne drogi, rzeki i inne duże miasta. Na każdym kroku dbają o to, aby (1) tekst został umieszczony w taki sposób, aby czytelnik łatwo skojarzył go z obiektem, oraz (2) etykieta nie pokrywała się z już umieszczonymi na mapie.
Lokalne algorytmy optymalizacji
Najprostszy algorytm zachłanny umieszcza kolejne etykiety na mapie w pozycjach, które powodują minimalne nakładanie się etykiet. Jego wyniki nie są doskonałe nawet w przypadku bardzo prostych problemów, ale jest niezwykle szybki.
Nieco bardziej złożone algorytmy polegają na optymalizacji lokalnej w celu osiągnięcia lokalnego optimum funkcji oceny rozmieszczenia – w każdej iteracji umieszczenie pojedynczej etykiety jest przesuwane na inną pozycję, a jeśli poprawi to wynik, ruch jest zachowywany. Działa dość dobrze na mapach, które nie są zbyt gęsto oznaczone. Nieco bardziej złożone odmiany spróbuj przenieść 2 lub więcej etykiet w tym samym czasie. Algorytm kończy się po osiągnięciu pewnego lokalnego optimum.
Prosty algorytm – symulowane wyżarzanie – daje dobre wyniki przy stosunkowo dobrych parametrach. Działa jak optymalizacja lokalna, ale może zachować zmianę, nawet jeśli pogorszy wynik. Szansa na zachowanie takiej zmiany jest , gdzie jest zmianą w ocenie , a to . Temperatura jest stopniowo obniżana zgodnie z harmonogramem wyżarzania . Gdy temperatura jest wysoka, symulowane wyżarzanie powoduje niemal przypadkowe zmiany w rozmieszczeniu etykiet, co pozwala uniknąć lokalnego optimum . Później, kiedy miejmy nadzieję, że zostanie znalezione bardzo dobre optimum lokalne, zachowuje się ono w sposób podobny do optymalizacji lokalnej. Głównymi wyzwaniami w opracowaniu rozwiązania do symulowanego wyżarzania jest wybór dobrej funkcji oceny i dobrego harmonogramu wyżarzania. Ogólnie rzecz biorąc, zbyt szybkie chłodzenie obniży jakość rozwiązania, a zbyt powolne obniży wydajność, ale harmonogram jest zwykle dość złożonym algorytmem z więcej niż jednym parametrem.
Inną klasą algorytmów wyszukiwania bezpośredniego są różne algorytmy ewolucyjne , np. algorytmy genetyczne .
Algorytmy typu „dziel i zwyciężaj”.
Jedną z prostych optymalizacji, która jest ważna na rzeczywistych mapach, jest podzielenie zestawu etykiet na mniejsze zestawy, które można rozwiązać niezależnie. Dwie etykiety są rywalami , jeśli mogą nakładać się na jedno z możliwych miejsc docelowych. Przechodnie domknięcie tej relacji dzieli zbiór etykiet na możliwie dużo mniejsze zbiory. Na mapach jednolicie i gęsto oznakowanych zazwyczaj pojedynczy zestaw będzie zawierał większość etykiet, a na mapach, dla których oznakowanie nie jest jednolite, może to przynieść bardzo duże korzyści wydajnościowe. Na przykład, przy oznaczaniu mapy świata, Ameryka jest oznaczana niezależnie od Eurazji itp.
Algorytmy 2-spełnialności
Jeśli problem z etykietowaniem mapy można sprowadzić do sytuacji, w której każda pozostała etykieta ma tylko dwie potencjalne pozycje, w których można ją umieścić, to można go skutecznie rozwiązać, wykorzystując przypadek spełnialności 2, aby znaleźć miejsce docelowe unikając wszelkich sprzecznych par miejsc docelowych; na tej zasadzie opiera się kilka dokładnych i przybliżonych algorytmów umieszczania etykiet dla bardziej złożonych typów problemów.
Inne algorytmy
Algorytmy automatycznego umieszczania etykiet mogą wykorzystywać dowolny z algorytmów do znajdowania maksymalnego zestawu rozłącznego ze zbioru potencjalnych etykiet. Można również zastosować inne algorytmy, takie jak różne rozwiązania grafów, programowanie całkowitoliczbowe itp.
Notatki
- Freeman, H., Przetwarzanie danych mapy i problem adnotacji, Proc. 3. konferencja skandynawska on Image Analysis, Chartwell-Bratt Ltd. Kopenhaga, 1983.
- Ahn, J. i Freeman, H., „Program do automatycznego umieszczania nazw”, Proc. AUTO-CARTO 6, Ottawa, 1983. 444–455.
- Freeman, H., „Umieszczanie nazw komputerów”, rozdz. 29, w Geographic Information Systems, 1, DJ Maguire, MF Goodchild i DW Rhind, John Wiley, Nowy Jork, 1991, 449–460.
- Podolskaya NN Algorytmy automatycznego usuwania konfliktów etykiet dla interaktywnych aplikacji graficznych. Technologie informacyjne (ISSN 1684-6400), 9, 2007, s. 45–50. W języku rosyjskim: Подольская Н.Н. Алгоритмы автоматического отброса формуляров для интерак тивных графических приложений. Информационные технологии, 9, 2007, с. 45–50.
- Kameda, T. i K. Imai. 2003. Rozmieszczenie etykiet na mapie dla punktów i krzywych. Transakcje IEICE dotyczące podstaw komunikacji elektronicznej i informatyki. E86A(4):835–840.
- Ribeiro Glaydstona i Luiza Loreny. 2006. Heurystyka dla problemów umieszczania etykiet kartograficznych. Komputery i nauki o Ziemi. 32:739–748.
- Wagner, F., A. Wolff, V. Kapoor i T. Strijk. 2001. Trzy zasady wystarczą do dobrego umieszczenia etykiety. Algorytmika. 30:334–349.