Jednoduchý mnohoúhelník

Jednoduchý mnohoúhelník  je obrazec skládající se z neprotínajících se segmentů („stran“) spojených ve dvojicích tak, aby tvořily uzavřenou cestu. Pokud se strany protínají, mnohoúhelník není jednoduchý. Často je slovo „jednoduchý“ z výše uvedené definice vynecháno.

Výše uvedená definice poskytuje následující vlastnosti tvaru:

• Mnohoúhelník obklopuje oblast (nazývanou vnitřek), která má vždy měřitelnou plochu.
• Úsečky, které tvoří mnohoúhelník (nazývané strany, vzácněji hrany), se protínají pouze ve svých koncových bodech, které se nazývají vrcholy (nebo méně formálně „rohy“).
• V každém vrcholu se setkávají přesně dvě strany.
• Počet stran se vždy rovná počtu vrcholů.

Obvykle se vyžaduje, aby dvě strany, které se setkávají ve vrcholu, nesvíraly přímý (180°) úhel. Jinak jsou strany ležící na stejné přímce považovány za součást téže strany.

Matematici obecně používají termín "mnohoúhelník" pouze pro obrazce tvořené úsečkami, včetně vnitřku. Někteří však používají termín „polygon“ k označení plochého obrazce ohraničeného uzavřenou cestou sestávající z konečné sekvence segmentů (tj. uzavřené křivky ). V závislosti na použité definici může, ale nemusí být hranice součástí polygonu [1] .

Jednoduché mnohoúhelníky se také nazývají Jordanovy mnohoúhelníky , protože Jordanova věta může být použita k prokázání, že takové mnohoúhelníky rozdělují rovinu na dvě oblasti, uvnitř a vně. Mnohoúhelník v rovině je jednoduchý právě tehdy, pokud je topologicky ekvivalentní kružnici . Jeho vnitřek je topologicky ekvivalentní kruhu .

Slabě jednoduchý mnohoúhelník

Pokud množina neprotínajících se segmentů tvoří hranici domény v rovině, topologicky ekvivalentní kružnici, pak se tato hranice nazývá slabě jednoduchý polygon [2] . Na obrázku vlevo je ABCDEFGHJKLM podle definice slabě jednoduchý mnohoúhelník. Modrá představuje oblast, pro kterou je hranicí slabě jednoduchý mnohoúhelník. Tento typ slabě jednoduchých polygonů se může vyskytovat v počítačové grafice a CAD systémech jako počítačová reprezentace polygonálních oblastí s dutinami - pro každou dutinu je vytvořen "řez" pro připojení k vnější hranici. Podle obrázku je ABCM vnější hranicí ploché oblasti s dutinou FGHJ. Řez ED spojuje dutinu s vnějším obrysem a je přejížděn dvakrát ve slabě jednoduchém polygonovém znázornění.

Alternativní a obecnější definicí slabých jednoduchých mnohoúhelníků je limita posloupnosti jednoduchých mnohoúhelníků stejného kombinatorického typu, které se sbíhají ve Fréchetově vzdálenosti [3] . To formalizuje myšlenku, že prvky mnohoúhelníku se mohou dotýkat, ale ne křížit. Tento typ slabě jednoduchého mnohoúhelníku však nemusí nutně tvořit hranici oblasti, protože „vnitřek“ může být prázdný. Například v řetězovém obrázku je ABCBA slabě jednoduchý mnohoúhelník - lze jej považovat za „vytlačovací“ limit polygonu ABCFGHA.

Problémy s počítačem

Ve výpočetní geometrii některé důležité výpočetní problémy používají jednoduchý polygonový vstup. V každém z těchto úkolů je klíčové rozlišení mezi uvnitř a vně [4]

• Problém, zda bod patří k mnohoúhelníku, vyžaduje určení, zda je bod q uvnitř mnohoúhelníku P .
• Pro výpočet plochy mnohoúhelníku , tedy vnitřní plochy, jsou známé jednoduché vzorce .
• Oddíl mnohoúhelníku je množina elementárních jednotek (například čtverců), které se neprotínají a jejichž spojení tvoří mnohoúhelník. Úkolem rozdělení polygonu je najít oddíl, který je v určitém smyslu minimální. Například příčka s minimálním počtem jednotek nebo s minimální celkovou délkou stran.
  • Speciálním případem dělení mnohoúhelníku je problém triangulace mnohoúhelníku, což je rozdělení jednoduchého mnohoúhelníku na trojúhelníky. Ačkoli se konvexní mnohoúhelníky snadno triangulují, triangulace obecných jednoduchých mnohoúhelníků je obtížnější, protože se musíte vyhnout přidávání hran, které se protínají mimo mnohoúhelník. Bernhard Chazelle však v roce 1991 ukázal, že jakýkoli jednoduchý mnohoúhelník s n vrcholy lze triangulovat v optimálním čase Θ ( n ). Stejný algoritmus lze použít k určení, zda uzavřená přerušovaná čára tvoří jednoduchý mnohoúhelník.
• Booleovské operace na polygonech — různé booleovské operace na množině bodů definovaných vnitřními oblastmi polygonů.
• Konvexní obal jednoduchého polygonu lze vypočítat efektivněji než konvexní obal pro jiné druhy vstupů, jako je například sada bodů.
• Voronoiův diagram jednoduchého mnohoúhelníku
• Střední osa / topologická kostra / přímočará kostra jednoduchého mnohoúhelníku
• Rovnoběžná křivka jednoduchého mnohoúhelníku
• Minkowského součet pro jednoduché mnohoúhelníky

Viz také

• hvězdná oblast

Poznámky

1. ↑ Grünbaum, 2003 .
2. ↑ Dumitrescu, Toth, 2007 , str. 177.
3. ↑ Chang, Erickson, Xu, 2015 , str. 1655–1670
4. ↑ comp.graphics.algorithms FAQ Archivováno 13. února 2011 na Wayback Machine se seznamem řešení matematických problémů s 2D a 3D polygony.

Literatura

• Branko Grünbaum . Konvexní polytopy / Volker Kaibel, Victor Klee, Günter M. Ziegler. — 2. - New York, London: Springer-Verlag , 2003. - ISBN 0-387-00424-6 .
• Adrian Dumitrescu, Csaba D. Toth. STACS 2007: 24. výroční symposium o teoretických aspektech informatiky, Aachen, Německo, 22.–24. února 2007, sborník příspěvků / Wolfgang Thomas, Pascal Weil. — ilustrovaný. - Springer, 2007. - ISBN 3540709177 .
• Hsien-Chih Chang, Jeff Erickson, Chao Xu. Sborník z 26. výročního sympozia ACM-SIAM o diskrétních algoritmech (SODA'15). — 2015.

Odkazy

• Weisstein, Eric W. Jednoduchý polygon  ve Wolfram MathWorld .