Automatické umístění štítku - Automatic label placement

Automatické umístění štítku, někdy nazývané umístění textu nebo umístění jména, zahrnuje počítačové metody automatického umístění štítků na mapu nebo graf. To souvisí s typografický design těchto štítků.

Typické rysy zobrazené na geografickém mapa jsou prvky čáry (např. silnice), prvky oblasti (země, pozemky, lesy, jezera atd.) a prvky bodů (vesnice, města atd.). Kromě geografického přesného zobrazení prvků mapy je zásadně důležité umístit názvy, které tyto prvky identifikují, a to tak, aby čtenář okamžitě věděl, který název popisuje daný prvek.

Automatické umístění textu je jedním z nejobtížnějších, nejsložitějších a časově nejnáročnějších problémů při vytváření map a GIS (Geografický informační systém). Jiné druhy počítačem generované grafiky - jako grafy, grafy atd. - vyžadují také dobré umístění štítků, nemluvě o technických výkresech a profesionálních programech, které tyto výkresy a grafy vytvářejí tabulky (např. Microsoft Excel ) nebo výpočetní softwarové programy (např. Mathematica ).

Naivně umístěné štítky se příliš překrývají a výsledkem je mapa, kterou je obtížné nebo dokonce nemožné číst. GIS proto musí umožňovat několik možných umístění každého štítku a často také možnost změny velikosti, otáčení nebo dokonce odebrání (potlačení) štítku. Poté vybere sadu umístění, která se bude minimálně překrývat, a bude mít další žádoucí vlastnosti. Problém je u všech, kromě těch nejtriviálních nastavení NP-tvrdé.

Algoritmy založené na pravidlech

Algoritmy založené na pravidlech se snaží napodobit zkušeného lidského kartografa. Po staletí kartografové vyvinuli umění mapování a umístění štítků. Například zkušený kartograf několikrát opakuje názvy silnic na dlouhých silnicích, místo aby je umístil jednou, nebo v případě Ocean City znázorněného bodem velmi blízko břehu by kartograf umístil štítek „Ocean City“ přes země zdůraznit, že se jedná o pobřežní město.[1]

Kartografové pracují na základě přijatých konvencí a pravidel, jako jsou ta, která rozvedl švýcarský kartograf Eduard Imhof v roce 1962.[2] Například New York, Vídeň, Berlín, Paříž nebo Tokio se musí objevit na mapách zemí, protože se jedná o štítky s vysokou prioritou. Jakmile je umístíte, umístí kartograf další nejdůležitější třídu štítků, například hlavní silnice, řeky a další velká města. V každém kroku zajišťují, že (1) je text umístěn tak, aby jej čtenář snadno přidružil k prvku, a (2) štítek se nepřekrývá s textem, který je již umístěn na mapě.

Lokální optimalizační algoritmy

Nejjednodušší chamtivý algoritmus umístí po sobě následující štítky na mapu na pozice, které mají za následek minimální překrytí štítků. Jeho výsledky nejsou dokonalé ani pro velmi jednoduché problémy, ale jsou extrémně rychlé.

Mírně složitější algoritmy spoléhají na místní optimalizaci, aby dosáhly lokálního optima funkce vyhodnocení umístění - v každé iteraci se umístění jednoho štítku přesune na jinou pozici a pokud to vylepší výsledek, přesun se zachová. Poměrně dobře funguje pro mapy, které nejsou příliš hustě označeny. Mírně složitější variace zkuste přesunout 2 nebo více štítků současně. Algoritmus končí po dosažení místního optima.

Jednoduchý algoritmus - simulované žíhání - přináší dobré výsledky s relativně dobrým výkonem. Funguje to jako lokální optimalizace, ale může to udržet změnu, i když to zhorší výsledek. Šance na zachování takové změny je , kde je změna hodnotící funkce a je teplota. Teplota se postupně snižuje podle harmonogram žíhání. Když je teplota vysoká, simulované žíhání provádí téměř náhodné změny umístění štítku, přičemž je možné uniknout z místní optimum. Později, když doufejme, že bylo nalezeno velmi dobré místní optimum, chová se podobně jako lokální optimalizace. Hlavními výzvami při vývoji simulovaného žíhacího řešení je volba dobré vyhodnocovací funkce a dobrého harmonogramu žíhání. Příliš rychlé chlazení obecně zhorší řešení a příliš pomalé chlazení sníží výkon, ale plán je obvykle poměrně složitý algoritmus s více než jedním parametrem.

Další třídou algoritmů přímého vyhledávání jsou různé evoluční algoritmy, např. genetické algoritmy.

Algoritmy rozděl a panuj

Jedna jednoduchá optimalizace, která je důležitá na skutečných mapách, je rozdělení sady štítků na menší sady, které lze vyřešit samostatně. Dva štítky jsou soupeři pokud se mohou překrývat v jednom z možných umístění. Tranzitivní uzavření tohoto vztahu rozděluje sadu štítků na možná mnohem menší sady. Na jednotně a hustě označených mapách bude obvykle jedna sada obsahovat většinu štítků a na mapách, pro které není označení jednotné, to může přinést velmi velké výkonnostní výhody. Například při označování mapy světa Amerika je označen nezávisle na Eurasie atd.

Algoritmy 2-uspokojivosti

Pokud lze problém s popisem mapy snížit na situaci, ve které má každý zbývající štítek pouze dvě potenciální polohy, do kterých jej lze umístit, lze jej efektivně vyřešit pomocí instance 2 - uspokojivost najít umístění a vyhnout se konfliktním dvojicím umístění; na tomto principu je založeno několik přesných a přibližných algoritmů umístění štítku pro složitější typy problémů.[3]

Další algoritmy

Algoritmy automatického umístění štítku mohou k vyhledání použít jakýkoli z těchto algoritmů maximální disjunktní sada ze sady potenciálních štítků. Lze použít i jiné algoritmy, jako jsou různá grafická řešení, celočíselné programování atd.

Poznámky

  1. ^ Slocum, Terry (2010). Tematická kartografie a geovizualizace. Upper Saddle River, NJ: Pearson. str. 576. ISBN  978-0-13-801006-5.
  2. ^ Imhof, Eduard, „Die Anordnung der Namen in der Karte“, Annuaire International de Cartographie II, Orell-Füssli Verlag, Curych, 93-129, 1962. Překlad do angličtiny: „Umístění jmen na mapách“ Americký kartograf, V.2 # 2 (1975), str. 128-144
  3. ^ Doddi, Srinivas; Marathe, Madhav V .; Mirzaian, Andy; Moret, Bernard M. E .; Zhu, Binhai (1997), „Mapové značení a jeho zobecnění“, Proc. 8. ACM-SIAM Symp. Diskrétní algoritmy (SODA), str. 148–157; Formann, M .; Wagner, F. (1991), "Balicí problém s aplikacemi pro psaní map", Proc. 7. ACM Symp. Výpočetní geometrie, s. 281–288; Poon, Chung Keung; Zhu, Binhai; Chin, Francis (1998), „Polynomiální časové řešení pro označování přímočaré mapy“, Dopisy o zpracování informací, 65 (4): 201–207, doi:10.1016 / S0020-0190 (98) 00002-7; Wagner, Frank; Wolff, Alexander (1997), „Praktický algoritmus značení map“, Výpočetní geometrie: Teorie a aplikace, 7 (5–6): 387–404, doi:10.1016 / S0925-7721 (96) 00007-7.

Reference

  • Freeman, H., Zpracování mapových dat a problém anotací, Proc. 3. skandinávská konf. o analýze obrazu, Chartwell-Bratt Ltd. Kodaň, 1983.
  • Ahn, J. a Freeman, H., „Program pro automatické umisťování jmen“, Proc. AUTO-CARTO 6, Ottawa, 1983. 444–455.
  • Freeman, H., „Umístění názvu počítače“, kap. 29, v Geografické informační systémy, 1, D.J. Maguire, M.F. Goodchild a D.W. Rhind, John Wiley, New York, 1991, 449–460.
  • Podolskaya N. N. Automatické algoritmy dekomplikace štítků pro interaktivní grafické aplikace. Informační technologie (ISSN 1684-6400), 9, 2007, s. 45–50. V ruštině: Подольская Н.Н. Алгоритмы автоматического отброса формуляров для интерак тивных графических приложений. Информационные технологии, 9. 2007, с. 45–50.
  • Kameda, T. a K. Imai. 2003. Umístění štítku mapy pro body a křivky. IEICE Transaction of Fundamentals of Electronics Communications and Computer Sciences. E86A (4): 835–840.
  • Ribeiro Glaydston a Luiz Lorena. 2006. Heuristika pro problémy s umístěním kartografických štítků. Počítače a geovědy. 32: 739–748.
  • Wagner, F., A. Wolff, V. Kapoor a T. Strijk. 2001. K řádnému umístění štítku stačí tři pravidla. Algorithmica. 30: 334–349.

externí odkazy