Rovinný přímkový graf - Planar straight-line graph

Příklad rovinný přímkový graf

v výpočetní geometrie, a rovinný přímkový graf, ve zkratce PSLG, (nebo přímkový rovinný grafnebo rovinný přímkový graf) je termín používaný pro vkládání a rovinný graf v letadlo tak, že jeho okraje jsou mapovány do přímkových segmentů.[1] Fáryho věta (1948) uvádí, že každý rovinný graf má tento druh vkládání.

Ve výpočetní geometrii byly často nazývány PSLG rovinné členění, s předpokladem nebo tvrzením, že členění je spíše polygonální než zakřivené hranice.

PSLG mohou sloužit jako reprezentace různých mapy, např. geografické mapy v geografické informační systémy.[2]

Zvláštní případy PSLG jsou triangulace (polygon triangulace, bodová triangulace ). Triangulace množiny bodů jsou maximální PSLG v tom smyslu, že je nemožné přidat k nim rovné hrany při zachování rovinnosti grafu. Triangulace mají četné aplikace v různých oblastech.

PSLG lze považovat za zvláštní druh Euklidovské grafy. V diskusích zahrnujících euklidovské grafy jsou však primárním zájmem jejich metrické vlastnosti, tj. Vzdálenosti mezi vrcholy, zatímco pro PSLG jsou primárním zájmem topologické vlastnosti. U některých grafů, například Delaunayovy triangulace, jsou důležité metrické i topologické vlastnosti.

Zastoupení

Existují tři známé datové struktury pro reprezentaci PSLG, to jsou Okřídlený okraj datová struktura, Halfedge, a Čtyřlůžkový. Okřídlená datová struktura je nejstarší ze tří, ale manipulace s ní často vyžaduje komplikované rozlišování případů. Je to proto, že odkazy na hrany neukládají směr hrany a směry hran kolem plochy nemusí být konzistentní. Datová struktura halfedge ukládá obě orientace hrany a správně je propojuje, což zjednodušuje operace a schéma úložiště. Datová struktura Quadedge ukládá současně planární dělení i jeho duální rozdělení. Jeho záznamy se skládají výslovně pouze z okrajových záznamů, čtyři pro každý okraj, a ve zjednodušené formě je vhodný pro ukládání PSLG.[3]

Problémy z hlediska PSLG

  • Umístění bodu. Pro bod dotazu najděte, ke které ploše PSLG patří.
  • Překryv mapy. Najděte překrytí dvou PSLG (map), což je dělení roviny dvěma současně vloženými PSLG. V GIS je tento problém známý jako „tematická mapa překrytí ".

Viz také

Reference

  1. ^ Franco P. Preparata a Michael Ian Shamos (1985). Výpočetní geometrie - úvod. Springer-Verlag. 1. vydání: ISBN  0-387-96131-3; 2. tisk, opraveno a rozšířeno, 1988: ISBN  3-540-96131-3; Ruský překlad, 1989: ISBN  5-03-001041-6.
  2. ^ Nagy, George; Wagle, Sharad (červen 1979), „Zpracování geografických dat“, ACM Computing Surveys, 11 (2): 139–181, doi:10.1145/356770.356777
  3. ^ Příručka datových struktur a aplikací, D. P. Mehta a S. Sahni, 2005, ISBN  1-58488-435-5, kapitola 17