Polygonální řetěz - Polygonal chain
v geometrie, a polygonální řetěz je spojená řada úsečky. Více formálně polygonální řetězec P je křivka specifikováno a sekvence bodů volal jeho vrcholy. Samotná křivka se skládá z úseček spojujících následné vrcholy.
název
Polygonální řetězec může být také nazýván a polygonální křivka,[1] polygonální cesta,[2] křivka,[3] po částech lineární křivka,[3] přerušovaná čára[4] nebo v geografické informační systémy, a linestring nebo lineární prsten.[5]
Variace
A jednoduchý polygonální řetěz je takový, ve kterém se protínají pouze po sobě jdoucí (nebo první a poslední) segmenty, a to pouze v jejich koncových bodech.
A uzavřený polygonální řetězec je ten, ve kterém se první vrchol shoduje s posledním, nebo alternativně, první a poslední vrcholy jsou také spojeny úsečkou.[6] Jednoduchý uzavřený polygonální řetězec v letadlo je hranice a jednoduchý mnohoúhelník. Výraz „polygon „se používá ve smyslu„ uzavřeného polygonálního řetězce “, ale v některých případech je důležité rozlišovat mezi polygonální oblast a polygonální řetězec.
Polygonální řetězec se nazývá monotónní, pokud existuje přímka L tak, aby každý řádek byl kolmý na L protíná řetězec maximálně jednou. Každý netriviální monotónní polygonální řetězec je otevřený. Pro srovnání: monotónní mnohoúhelník je polygon (uzavřený řetězec), který lze rozdělit na přesně dva monotónní řetězce.[7] Grafy po částech lineární funkce tvoří monotónní řetězce vzhledem k vodorovné linii.
Vlastnosti
Každá sada alespoň points obsahuje polygonální cestu minimálně hrany, ve kterých mají všechny svahy stejné označení. Toto je důsledek Erdős – Szekeresova věta.
Aplikace
Polygonální řetězce lze často použít k přiblížení složitějších křivek. V této souvislosti Algoritmus Ramer – Douglas – Peucker lze použít k nalezení polygonálního řetězce s několika segmenty, který slouží jako přesná aproximace.[8][9]
v kreslení grafu, polygonální řetězy se často používají k reprezentaci okrajů grafů ve výkresových stylech, kde by kreslení hran jako přímých segmentů způsobilo křížení, kolize hrany s vrcholem nebo jiné nežádoucí prvky. V této souvislosti je často žádoucí kreslit hrany s co nejmenším počtem segmentů a ohybů, aby se snížil vizuální nepořádek ve výkresu; nazývá se problém minimalizace počtu ohybů minimalizace ohybu.[10]
Polygonální řetězce jsou také základním datovým typem výpočetní geometrie. Například a umístění bodu algoritmus Závětří a Preparata pracuje rozkladem libovolně rovinné členění do uspořádané sekvence monotónních řetězců, ve kterých lze vyřešit problém s dotazem na místo v bodě binární vyhledávání; tato metoda byla později vylepšena, aby poskytla optimální časové hranice pro problém s umístěním bodu.[11]
S geografický informační systém, linestrings mohou představovat jakoukoli lineární geometrii a lze je popsat pomocí známý text označení jako LineString nebo MultiLineString.[5] Lineární kroužky (nebo LinearRing) jsou uzavřené a jednoduché polygonální řetězce používané k vytváření geometrií polygonů.
Viz také
- Řetěz (algebraická topologie), formální kombinace jednoduchostí, která v 1rozměrném případě zahrnuje polygonální řetězce
- Složená Bézierova křivka, zobecnění, které nahradí každou přímku polygonálního řetězce hladkou křivkou.
- Spojovací vzdálenost, počet segmentů nejkratšího řetězce, který spojuje dva body v mnohoúhelníku
- Kusová regrese
- Cesta (teorie grafů), analogický koncept v abstraktních grafech
- Mnohostěnný terén, 3D zobecnění monotónního polygonálního řetězce
- Číslo hůlky, invariant uzlu založený na reprezentaci uzlu jako uzavřeného polygonálního řetězce
- přejít, aplikace v geodetické
Reference
- ^ Gomes, Jonas; Velho, Luiz; Costa Sousa, Mario (2012), Počítačová grafika: Teorie a praxe, CRC Press, str. 186, ISBN 9781568815800.
- ^ Cheney, Ward (2001), Analýza pro aplikovanou matematiku, Postgraduální texty z matematiky, 208, Springer, str. 13, ISBN 9780387952796.
- ^ A b Boissonnat, Jean-Daniel; Teillaud, Monique (2006), Efektivní výpočetní geometrie pro křivky a povrchy, Springer, str. 34, ISBN 9783540332596.
- ^ Muggeo, Vito M. R. (květen 2008), "segmentovaný: balíček R, který se hodí pro regresní modely s přerušovanými vztahy" (PDF), R Novinky, 8 (1): 20–25
- ^ A b Otevřete geoprostorové konsorcium (2011-05-28), Herring, John R. (ed.), Standard implementace OpenGIS® pro geografické informace - jednoduchý přístup k funkcím - Část 1: Společná architektura, 1.2.1, Open Geospatial Consortium, vyvoláno 2016-01-15
- ^ Mehlhorn, Kurt; Näher, Stefan (1999), LEDA: Platforma pro kombinatorické a geometrické výpočty, Cambridge University Press, str. 758, ISBN 9780521563291.
- ^ O'Rourke, Josephe (1998), Výpočetní geometrie v jazyce C., Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, s. 1. 45, ISBN 9780521649766.
- ^ Ramer, Urs (1972), „Iterativní postup pro polygonální aproximaci rovinných křivek“, Počítačová grafika a zpracování obrazu, 1 (3): 244–256, doi:10.1016 / S0146-664X (72) 80017-0.
- ^ Douglas, David; Peucker, Thomas (1973), „Algoritmy pro snížení počtu bodů potřebných k reprezentaci digitalizované čáry nebo její karikatury“, Kanadský kartograf, 10 (2): 112–122, doi:10.3138 / FM57-6770-U75U-7727.
- ^ Tamassia, Roberto (1987), „Při vkládání grafu do mřížky s minimálním počtem ohybů“, SIAM Journal on Computing, 16 (3): 421–444, doi:10.1137/0216030.
- ^ Edelsbrunner, Herbert; Guibas, Leonidas J.; Stolfi, Jorge (1986), „Optimální umístění bodu v monotónním dělení“, SIAM Journal on Computing, 15 (2): 317–340, doi:10.1137/0215023.