Voroného diagram
V matematice Voroného (Thiessenův) diagram, nazvaný podle Georgije Voroného, někdy nazývaná Voroného teselace, Voroného dekompozice nebo Dirichletova teselace (podle Lejeune Dirichleta), je způsob dekompozice metrického prostoru určený vzdálenostmi k dané diskrétní množině objektů v prostoru, například diskrétní množinou bodů.
Nejjednodušším a nejběžnějším případem je rozdělení roviny podle dané množiny bodů M. Voroného diagram pro S je rozdělení roviny, která každému bodu b z M přidělí oblast V(b) tak, aby všechny body oblasti V(b) byly blíže k bodu b než k jakémukoliv jinému bodu z množiny M. Pro nalezení takového rozdělení se používá Fortunův algoritmus.
Jinou možností je aplikace přírůstkového (inkrementálního) algoritmu. Není tak efektivní jako jiné algoritmy, ale jeho princip je jednoduchý a intuitivní. Najdeme diagram pro nějaký jednoduchý případ (například vybereme dva nebo tři body z množiny generátoru) a pak postupně přidáváme po jednom zbylé body.
Voroného diagramy mají řadu využití v různých oborech, např. v geometrii, sociologii, chemii, hydrologii a dalších přírodních vědách, v urbanismu, architektuře. Mimo jiné se používají pro optimální rozdělení parcel, generování buněčných nebo krystalových struktur, pro voštinové struktury 3D tisku, v umění, ale třeba i ve fotbalu.
V meteorologii a hydrologii se Voroného diagramy používají pod názvem Thiessenovy polygony (pojmenováno po americkém meteorologovi Alfredu Thiessenovi). Slouží k vyhodnocení prostorových dat, zejména pro určení výšky srážky na dané území.
Externí odkazy
editovat
Obrázky, zvuky či videa k tématu Voroného diagram na Wikimedia Commons - Animace ruční tvorby Voroného diagramu
- Interaktivní kreslení diagramu (flash)
- Generování Voroného diagramu v AutoCADu
