Diagram Woronoja

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Komórki Woronoja dla losowego zbioru punktów na płaszczyźnie

Diagram Woronoja, tesselacja Dirichleta, tesselacja Woronoja lub komórki Woronoja (ang. Voronoi diagram) – podział płaszczyzny, nazwany tak na cześć twórcy Gieorgija Woronoja (termin tesselacja Dirichleta pochodzi od nazwiska Petera Dirichleta).

W przypadku przestrzeni dwuwymiarowej, dla danego zbioru punktów, dzieli się płaszczyznę na obszarów, w taki sposób, że każdy punkt w dowolnym obszarze znajduje się bliżej określonego punktu ze zbioru punktów, niż od pozostałych punktów

Definicja formalna[edytuj | edytuj kod]

Niech będzie skończonym zbiorem punktów należących do przestrzeni euklidesowej Elementy zbioru nazwiemy centrami, środkami lub zalążkami.

Obszarem Woronoja lub komórką Woronoja przypisaną pewnemu elementowi zbioru nazwiemy zbiór punktów znajdujących się bliżej punktu niż każdego innego elementu ze zbioru

gdzie jest odległością.

Weźmy dwa punkty i należące do zbioru W przestrzeni dwuwymiarowej (płaszczyzna) zbiór punktów jednakowo odległych od i od jest prostą zwaną symetralną odcinka

Prosta ta jest granicą między zbiorem punktów mniej oddalonych od punktu niż od punktu a zbiorem punktów mniej oddalonych od punktu niż od punktu

Niech będzie półpłaszczyzną ograniczoną prostą i zawierającą punkt Zawiera więc ona wszystkie punkty bliższe punktowi niż punktowi

Komórką (obszarem) Woronoja przypisaną punktowi jest intersekcja (część wspólna) wszystkich półpłaszczyzn gdzie zastępuje kolejno każdy punkt ze zbioru

Komórki Woronoja będąc intersekcją półpłaszczyzn są wielobokami wypukłymi. Zbiór tych wieloboków rozbija dwuwymiarową przestrzeń euklidesową i jest diagramem Woronoja odpowiadającym zbiorowi

Omówiony podział płaszczyzny na komórki Woronoja można również zastosować w przestrzeni trójwymiarowej. Prosta zastąpiona będzie wówczas płaszczyzną a półpłaszczyzna półprzestrzenią ograniczoną płaszczyzną Przestrzenne komórki Woronoja są wielościanami wypukłymi.

Generalizując, w przestrzeni euklidesowej -wymiarowej, jest hiperpłaszczyzną afiniczną (wymiaru ), a dowolna komórka Woronoja będąc intersekcją półprzestrzeni wymiaru N, ograniczonych hiperpłaszczyznami jest wielokomórką wypukłą.

Diagram Woronoja (na czerwono) i triangulacja Delone

Diagram Woronoja jest grafem dualnym triangulacji Delone, którą można zresztą łatwo otrzymać na podstawie diagramu Woronoja: dwa punkty i tworzą krawędź grafu wtedy i tylko wtedy, gdy komórki Woronoja przyporządkowane tym punktom przystają do siebie:

Linki zewnętrzne[edytuj | edytuj kod]