Voronoi diagram

A síkon egy véges S ponthalmaz Voronoi-diagramja a sík egy olyan partícióját ábrázolja, amelyben ennek a partíciónak minden területe olyan pontokat alkot, amelyek közelebb vannak az S halmaz egyik eleméhez, mint bármelyikhez. a halmaz másik eleme [1] .

Nevét Georgij Feodosevics Voronojról kapta , aki 1908-ban tanulmányozta az általános n -dimenziós esetet [2] . Más néven: Voronoi csempe, Voronoi csempe, Dirichlet csempe .

Történelem

Az ilyen szerkezetek használatát először 1644-ben Descartes -nak tulajdonítják. Dirichlet kétdimenziós és háromdimenziós Voronoi-diagramokat használt a másodfokú formákkal foglalkozó munkájában 1850-ben.

Tulajdonságok

Szoros kapcsolata van, és egy az egyben megfelel a Delaunay-háromszögelésnek . Ugyanis, ha olyan élekkel kapcsolunk össze pontokat, amelyek Voronoi régiói határosak egymással, akkor a kapott gráf egy Delaunay-háromszöglet lesz.

Építési algoritmusok

Egy egyszerű algoritmus

Tekintsük néhány pontpárt és . $p$ $q$

Ez a merőleges a síkot két félsíkra és -ra osztja , és a p pont Voronoi területe az egyikben, a pont területe pedig a másikban található. A Voronoi pont tartománya egybeesik az összes ilyen félsík metszéspontjával : $H_{{pq}}$ $H_{{qp}}$ $q$ $V_{p}$ $p$ $H_{{pq}}$

$V_{p}=\bigcap \limits _{q\in S/\{p\}}H_{pq}$ .

Így a feladat megoldása egy ilyen metszéspont kiszámítására redukálódik minden pontra . Az algoritmus számítási komplexitással megvalósítható [3] . $p$ $O(n^{4})$

Fortune algoritmusa

Az algoritmus egy söprő vonal használatán alapul. A seprővonal egy függőleges egyenes vonalat ábrázoló segédobjektum. Az algoritmus minden lépésében egy Voronoi-diagram készül egy söprő vonalból álló halmazhoz, amely balra mutat. Ebben az esetben a Voronoi-terület, az egyenes és a pontterületek határa parabolák szakaszaiból áll (mivel az adott ponttól és az egyenestől egyenlő távolságra lévő pontok helye parabola ). Az egyenes vonal balról jobbra halad. Minden alkalommal, amikor áthalad egy másik ponton, ez a pont hozzáadódik a diagram már megszerkesztett szakaszához. A pontok diagramhoz bináris keresési fával történő hozzáadása összetettsége , összes pont , és a pontok -koordináta szerinti rendezése elvégezhető -ben , így a Fortune algoritmus számítási összetettsége . $O(\log n)$ $n$ $x$ $O(n\log n)$ $O(n\log n)$

Rekurzív algoritmus

A rekurzív algoritmus fő ötlete a dinamikus programozási módszer használata . A kezdeti ponthalmazt két részhalmazra osztjuk, és mindegyikhez készítünk egy Voronoi-diagramot, majd a kapott diagramokat egyesítjük. A halmaz felosztása a síkot két félsíkra osztó egyenessel történik úgy, hogy mindkét félsík megközelítőleg ugyanannyi pontot tartalmazzon. A és halmazok Voronoi-diagramjainak uniója időben végrehajtható , így az algoritmus számítási bonyolultsága . $S$ $S_{1}$ $S_{2}$ $S$ $S_{1}$ $S_{2}$ $Tovább)$ $O(n\log n)$

Általánosítások

Egy Voronoi-diagram kézenfekvő módon definiálható egy tetszőleges euklideszi tér ponthalmazára, amely nem feltétlenül kétdimenziós. A következő állítás érvényes: -dimenziós térben egy ponthalmaz -dimenziós Delaunay-háromszögelésének egyszerűségeinek száma elérheti a -t . Ezért a kettős Voronoi diagram tárolásához szükséges memóriaköltségek azonos nagyságrendűek. $k$ $k$ $n$ $O(n^{{\lceil {\frac k2}\rceil }})$

Voronoi-diagram definiálható egy nem euklideszi metrikával rendelkező térhez. Ebben az esetben azonban előfordulhat, hogy a szomszédos Voronoi régiók közötti határok nem elsőrendű sokaságok (például a Manhattan távolság használatakor ).

Az S halmaz nem csak pontokból állhat, hanem bármely olyan objektumból is, amelyre a sík tetszőleges pontjától való távolságot meghatároztuk. Ebben az esetben az S halmaz elemeit helyeknek nevezzük. Példa erre a Voronoi poligon diagram , ahol a helyek a sokszög csúcsai és élei. Az ilyen diagramokat középtengelyek készítésére használják, és széles körben használják képelemzési problémákban. A Voronoi-sokszögdiagram régióinak határa a szakaszok és a parabolák uniója.

Alkalmazás

A Voronoi partíciót a számítástechnikai anyagtudományban használják szintetikus polikristályos aggregátumok létrehozására. Számítógépes grafikában is használják a felületek véletlenszerű felosztására.

A Gold módszere (vagy "területlopási módszer") egy függvény interpolációja 2D-ben, amelyet például a geodéziában használnak. Az összes pontról egy Voronoi-diagram készül, amely után hozzáadjuk a kívánt pontot. Az új cella "kiválasztja" a területet a meglévők közül; minél több területet vettünk kölcsön ( x i , y i , z i ), annál nagyobb az együttható ezen a ponton.

A Voronoi-partíciót arra is használjuk, hogy megtaláljuk a kromatikus szám felső becslését a 2-es vagy 3-as dimenziójú euklideszi térhez ( Nelson-Erdős-Hadwiger probléma ). Itt a sík Voronoi-sokszögekre való felosztása adott rácsra figyelembe vett. A legjobb becslést mind a 2-, mind a 3-dimenziós terekre kaptuk, ha szimmetrikus partíciót vettünk figyelembe. Például egy sík hatszögekkel való burkolása (ebben az esetben a hatszög egy Voronoi-sokszög).

Lásd még

Linkek

A Fortune's Algorithm archiválva : 2008. június 13. a Wayback Machine -nél
Fortune Algorithm Visualizer

Források

↑ F. Preparata, M. Sheimos. Számítógépes geometria: Bevezetés. Archív másolat 2011. április 23-án a Wayback Machine -nél - M .: Mir, 1989. Pp. 295
↑ G. F. Voronoi. Nouvelles applications des paramètres continus à la théorie de formesatiques (francia) // Journal für die reine und angewandte Mathematik. - 1908. - Kt. 134 . - 198-287 o .
↑ Voronoi diagram . MAXimal (2009. január 26.). Letöltve: 2021. június 8. Az eredetiből archiválva : 2021. június 8. (Orosz)