Triangulace ventilátoru - Fan triangulation

Triangulace ventilátoru a konvexní mnohoúhelník

Triangulace ventilátoru a konkávní mnohoúhelník s jedinečným konkávním vrcholem.
A triangulace ventilátoru je jednoduchý způsob triangulovat mnohoúhelník výběrem vrcholu a nakreslením úhlopříček ke všem ostatním vrcholům mnohoúhelníku. Ne každý mnohoúhelník lze takto triangulovat, takže se tato metoda obvykle používá pouze pro konvexní polygony.[1]
Vlastnosti
Kromě vlastností všech triangulací mají trojúhelníkové ventilátory následující vlastnosti:
- Všechny konvexní polygony, ale ne všechny polygony, mohou být trojúhelníkovité.
- Polygony s pouze jedním konkávním vrcholem mohou být vždy vějířovitě trojúhelníkové, pokud jsou úhlopříčky kresleny z konkávního vrcholu.
- Je známo, zda polygon může být vějířově trojúhelníkován řešením Problém s uměleckou galerií, abychom zjistili, zda existuje alespoň jeden vrchol, který je viditelný z každého bodu mnohoúhelníku.
- Triangulace mnohoúhelníku s vrcholy používá úhlopříčky a generuje trojúhelníky.[2]
- Generování seznamu trojúhelníků je triviální, pokud je k dispozici uspořádaný seznam vrcholů, a lze jej vypočítat v lineárním čase. Jako takový není nutné explicitně ukládat seznam trojúhelníků, a proto mnoho grafických knihoven implementuje primitiva, která představují polygony založené na této triangulaci.[3]
- I když je tato triangulace vhodná pro řešení určitých problémů, jako např Rastrování nebo Detekce kolize, může být nevhodný pro jiné úkoly, protože vrchol původu akumuluje vysoký počet sousedů a vnitřní úhly triangulace jsou nerovnoměrně rozloženy.
Viz také
Reference
- ^ Loera, Ježíši; Rambau, Joerg; Santos, Francisco (2010). Triangulace: Struktury pro algoritmy a aplikace. Springer Science & Business Media. str.103. ISBN 9783642129711.
- ^ O'Rourke, Joseph (1998). Výpočetní geometrie v C (2. vyd.). Cambridge, Velká Británie: Cambridge University Press. ISBN 9780521649766. OCLC 38542796.
- ^ Segal, Mark (24. října 2016). „Grafický systém OpenGL: specifikace“ (PDF). Citováno 2. března 2017.