Voronoi diagram

Voronoi tesselációja

Természet	Algoritmus
Alosztály	Pontszám , diagram
Névre hivatkozva nevezték el	Georgy Voronoi

A matematika , a Voronoi diagram egy mozaik (szeletelés) a sík sejtekbe (szomszédos területeket) diszkrét pontok halmaza az úgynevezett „mag”. Minden sejt egyetlen csírát foglal magában, és a síkban lévő pontok halmazát alkotja, amely közelebb van ehhez a csírához, mint bármely máshoz. A sejt bizonyos módon képviseli a csíra „befolyási zónáját”.

A diagram nevét Gueorgui Voronoï (1868-1908) orosz matematikusnak köszönheti . Az osztály is nevezik bomlás Voronoi , mozaik vagy mozaik Dirichlet .

Általánosabban, ez jelenti a bomlási egy metrikus tér a sejtekbe (szomszédos régiók), által meghatározott távolságok egy diszkrét halmaza tárgyak a térben, általában diszkrét ponthalmaz. A síkban a sejteket Voronoi sokszögeknek vagy Thiessen sokszögeknek , az űrben pedig Voronoi polihedráknak nevezzük .

Történelem

Az informális használata Voronoi diagramok vezethető vissza Descartes a 1644 a Principia philosophiae illusztrálására egy csillagászati jelenség. Dirichlet használt 2 vagy 3 dimenziós Voronoi diagramok tanulmányában négyzetes formák az 1850 ( Dirichlet 1850 ).

A 1854 , brit orvos John Snow használt Voronoi diagram azt mutatja, hogy az emberek többsége, akik meghaltak a Soho kolera járvány volt a Broad Street vízszivattyú sejt, így tovább éltek. Közel ez a szivattyú, mint bármely más szivattyút. Így bebizonyította, hogy a fertőzés forrása ez a szivattyú volt.

Voronoi rajzok elnevezett orosz matematikus Georgy Fedoseevich Voronoi (vagy Voronoy), aki meghatározott és tanulmányozta az általános helyzet dimenziója n , 1908-ban Voronoi ábrák amelyeket a geofizikai és meteorológiai adatok elemzéséhez származó térbeli eloszlása (mint a csapadék mérés) között az úgynevezett Thiesseni sokszögek, amelyeket Alfred H. Thiessen  amerikai meteorológusról neveztek el (in) .

Meghatározás

Az affin síkba helyezzük magunkat . Legyen S a sík n pontjának véges halmaza ; az S elemeit központoknak, helyeknek vagy akár csíráknak nevezzük. R2{\ displaystyle \ mathbb {R} ^ {2}}

Felhívjuk a Voronoi régió - vagy Voronoi cella - kapcsolódó eleme p az S , a pontok halmaza, amelyek közelebb állnak p , mint bármely más pontján S  :

VorS(o)={x∈R2 / ∀q∈S ‖x-o‖≤‖x-q‖}{\ displaystyle \ mathrm {Vor_ {S}} (p) = \ {x \ in \ mathbb {R} ^ {2} \ / \ \ forall q \ in \ mathrm {S} \ \ xp \ | \ leq \ | xq \ | \}}

ahol || x - p || jelöli az x és p közötti távolságot .

Ha hívjuk H ( p , q ) a félig tartalmazó síkra p által határolt függőleges felezővonal a szegmens [ PQ ] , van

H(o,q)={x∈R2 / ‖x-o‖≤‖x-q‖}{\ displaystyle \ mathrm {H} (p, q) = \ {x \ in \ mathbb {R} ^ {2} \ / \ \ | xp \ | \ leq \ | xq \ | \}} VorS(o)=⋂q∈S∖{o}H(o,q){\ displaystyle \ mathrm {Vor_ {S}} (p) = \ bigcap _ {q \ in \ mathrm {S} \ hátsó perjel \ {p \}} \ mathrm {H} (p, q)}

A 2. dimenzióban könnyű megrajzolni ezeket a partíciókat. Azon a tényen alapul, hogy két különböző csíra Voronoi-sejtjei közötti határ szükségszerűen azon a merőleges felezőn helyezkedik el, amely elválasztja ezt a két csírát. Valójában ennek a merőleges felezőnek a pontjai egyenlő távolságra vannak a két csírától, így nem tudjuk megerősíteni, hogy a Voronoi egyik vagy másik cellájában helyezkednek el. Csírahalmaz esetében tehát a Voronoi-diagramot úgy állítjuk össze, hogy meghatározzuk az egyes csírapárok merőleges felezőit. A merőleges felező egy pontja ekkor a Voronoi-határhoz tartozik, ha legalább két csírától egyenlő távolságban van, és e pont és a halmaz másik csírája között nincs kisebb távolság.

Általánosíthatjuk a fogalmat egy d e euklideszi távolsággal felruházott E euklideszi térre . Legyen S az E n pontjának véges halmaza . A meghatározás:

VorS(o)={x∈E / ∀q∈S d(x,o)≤d(x,q)}{\ displaystyle \ mathrm {Vor_ {S}} (p) = \ {x \ in \ mathrm {E} \ / \ \ forall q \ in \ mathrm {S} \ \ mathrm {d} (x, p) \ leq \ mathrm {d} (x, q) \}}

A két pont egy és b a S , a beállított Π ( a , b ) egyenlő távolságú pontok egy , és b egy affin hipersíkot (affin altér CO-dimenzió 1). Ez hipersíkot a határ közötti pontok halmaza közelebb a mint b , és a pontok halmaza közelebb b , mint egy .

Π(o,q)={x∈E / d(x,o)=d(x,q)}{\ displaystyle \ Pi (p, q) = \ {x \ in \ mathrm {E} \ / \ \ mathrm {d} (x, p) = \ mathrm {d} (x, q) \}}

Jelölje H ( a , b ) a fél-által határolt tér e hipersíkot tartalmazó egy , azt akkor tartalmazza az összes pontok közelebb egy , mint a b . A Voronoi társított régióban egy ezután a kereszteződésekben a H ( a , b ) , ahol b végighalad S \ { a } .

H(o,q)={x∈E / d(x,o)≤d(x,q)}{\ displaystyle \ mathrm {H} (p, q) = \ {x \ in \ mathrm {E} \ / \ \ mathrm {d} (x, p) \ leq \ mathrm {d} (x, q) \ }} VorS(o)=⋂q∈S∖{o}H(o,q){\ displaystyle \ mathrm {Vor_ {S}} (p) = \ bigcap _ {q \ in \ mathrm {S} \ hátsó perjel \ {p \}} \ mathrm {H} (p, q)}

A Voronoi-diagram általánosítása

Megoldani bizonyos problémákat, Shamos bevezeti a fogalom Voronoi rajza ponthalmaz A (részhalmaza S ), V (A) által meghatározott:

V(NÁL NÉL)={x∈E/ ∀o∈NÁL NÉL,∀q∈S∖NÁL NÉL,d(x,o)<d(x,q)}{\ displaystyle \ mathrm {V} (\ mathrm {A}) = \ bal \ {x \ in \ mathrm {E} / \ \ forall p \ in \ mathrm {A}, \ forall q \ in \ mathrm {S } \ setminus \ mathrm {A}, \ mathrm {d} (x, p) <\ mathrm {d} (x, q) \ jobb \}}

Így V (A) a pontok halmaza, amelyek közelebb vannak egymáshoz pont A mint bármely tárgy nem tekinti A .

Ha H ( i , j ) -nek nevezzük azt a félsíkot, amelyet az [ ij ] szakasz merőleges felezője határol és amely i-t tartalmaz , akkor:

V(NÁL NÉL)=⋂én∈NÁL NÉL,j∈S∖NÁL NÉLH(én,j){\ displaystyle \ mathrm {V} (\ mathrm {A}) = \ bigcap _ {i \ in \ mathrm {A}, j \ in \ mathrm {S} \ setminus \ mathrm {A}} \ mathrm {H} (i, j)}

Az általánosított Voronoi régiók tehát domborúak, de üresek lehetnek. Ezután Shamos meghatározza a k- sorrendű Voronoi-diagramokat (1 ≤ k <kártya (S)) az általánosított Voronoi-sejtek egyesülésével, amelyet a k összes részhalmaza alkot :

Vk(S)=⋃NÁL NÉL⊂S,vs.nál nélrd(NÁL NÉL)=kV(NÁL NÉL){\ displaystyle \ mathrm {V} _ {k} (\ mathrm {S}) = \ bigcup _ {\ mathrm {A} \ subset \ mathrm {S}, \ mathrm {card} (\ mathrm {A}) = k} \ mathrm {V} (\ mathrm {A})}.

Az V (A) régiók alkotják a V k (S) partícióját .

Meghatározza a „ legtávolabbi pont Voronoi-diagramot” is . Ez a diagram az egyenlőtlenség irányának megfordításával készül

Vor¯S(o)={x∈E / ∀q∈S d(x,o)≥d(x,q)}{\ displaystyle {\ overline {\ mathrm {Vor}}} _ {\ mathrm {S}} (p) = \ bal \ {x \ in \ mathrm {E} \ / \ forall q \ in \ mathrm {S } \ \ mathrm {d} (x, p) \ geq \ mathrm {d} (x, q) \ jobb \}}

A p pont nyilvánvalóan nem a Vor S ( p ) cellában található , hanem az ellenkező oldalon van a halmaz „középpontja” szempontjából: a p pont a S pontja a Vor S- től legtávolabb ( p ) .

A legtávolabbi pontok diagramját teljes egészében az S konvex héja határozza meg . Nem tartalmaz zárt cellát.

Tehát a p ponttól legtávolabbi pontok halmaza az S többi pontjához közelebb eső pontok halmaza  :

Vor¯S(o)=⋃q∈∁S({o})VorS(q){\ displaystyle {\ overline {\ mathrm {Vor}}} _ {\ mathrm {S}} (p) = \ bigcup _ {q \ in \plement _ {\ mathrm {S}} (\ {p \}) } \ mathrm {Vor_ {S}} (q)}

ezért a legtávolabbi pontok diagramja megegyezik V n - 1 (S), n = kártyával (S) .

Tulajdonságok

A Voronoi régiók a féltér metszéspontjaként domború politopok . Az összes ilyen sokszög E partíció és az S halmaznak megfelelő Voronoi partíció .

Tétel  -  Legyen v a sík egy pontja. A Voronoi sokszög csúcsa akkor és csak akkor, ha egy három csírán áthaladó kör közepe, és nem tartalmaz más csírát a felszínén.

Demonstráció

Az v pont három Vor S ( p ) , Vor S ( q ) és Vor S ( r ) sejt metszéspontjában található , tehát egyenlő távolságra van p , q , r távolságtól , tehát v a pqr-re körülírt kör közepe . Ha egy másik mag lenne a lemezen, akkor v közelebb lenne ehhez a ponthoz, mint p , q és r , tehát nem lenne a három cella egyikében sem.

További tulajdonság, hogy a két legközelebbi pont a szomszédos cellákban található.

Kapcsolat a Delaunay-háromszögeléssel

A Voronoi diagramja diszkrét halmaz S pont a kettős grafikon a Delaunay háromszögelés társított S .

Váltás a Voronoi diagramról a Delaunay háromszögelésre

A Voronoi-diagram minden magja egy csúcsot képez a Delaunay-háromszögelésben. Ezeket a csúcsokat akkor és csak akkor köti össze egy él, ha a cellák szomszédosak.

DEL(S)={(o,q)∈S2 / VorS(o)∩VorS(q)≠∅}{\ displaystyle \ mathrm {DEL} (\ mathrm {S}) = \ {(p, q) \ in \ mathrm {S} ^ {2} \ / \ \ mathrm {Vor_ {S}} (p) \ cap \ mathrm {Vor_ {S}} (q) \ neq \ lakkozás \}}

Átváltás Delaunay háromszögeléséről a Voronoi diagramra

A Voronoi-diagram csúcsai a Delaunay-háromszög háromszögeinek körülírt köreinek középpontjai. A Voronoi-diagram szélei a Delaunay-háromszög széleinek merőleges felezőin vannak.

Ábra ábrázolás

Grafikusan a sejtek falai általában ábrázolva vannak, vagyis azok a pontok, amelyek egyenlő távolságra vannak legalább két centrumtól, és a cellákhoz tartozó központok. A cellát néha egyszínű, falral vagy anélkül ábrázolják, az egyes cellák között más színű (lásd a négy szín tétele ).

Analitikai szempontból, ha egy sejt félsíkok metszéspontja, ez a félsíkok egyenletrendszere lehet (lásd: Analitikai geometria> Félsík ):

{nál nél1x+b1y⩾vs.1nál nél2x+b2y⩾vs.2⋯{\ displaystyle \ left \ {{\ begin {matrix} a_ {1} x + b_ {1} y \ geqslant c_ {1} \\ a_ {2} x + b_ {2} y \ geqslant c_ {2} \ \\ cdots \ end {mátrix}} \ right.}

A Voronoi diagram számítógépes ábrázolásához John Burkardt azt javasolta, hogy négyféle típusú fájlt használjon:

• s x y : az S halmaz pontja, az ( x , y ) koordináták  ;
• v x y : Voronoi sokszög csúcsa ( csúcsa ) koordinátákkal ( x , y )  ;
• l a b c : egyenes (sokszög szélét hordozó), ax + egyenlet = c = egyenlet  ;
• e l v1 v2 : Szélén egy sokszög, által leírt index L annak könyv vonal és az indexek v 1 és v 2 a csúcsok, amelyek a végei; ha egy index egyenlő –1, akkor ez azt jelenti, hogy a csúcs „a végtelenben” van (félegyenes, vagy egyenes, ha mindkét csúcs –1).

Algoritmusok

Green és Sibson algoritmusa

A Green és Sibson algoritmus inkrementális algoritmus a Voronoi diagram kiszámításához. A Voronoi-diagramot úgy tartja fenn, hogy egyesével összeadja a pontokat. A komplexitás van . O(nem2){\ displaystyle O (n ^ {2})}

Shamos és Hoey algoritmus

Shamos és Hoey 1975-ben megmutatták, hogy ki lehet számítani a sík n pontjának halmazának Voronoi diagramját az O időben ( n log n ) . Indukcióval használják ezt az érvelést  : tegyük fel, hogy az S halmazt két részhalmazra oszthatjuk fel, azonos n / 2 kardinalitással , függőleges vonallal elválasztva: a bal oldali pontok G halmaza és a jobb D pontok . Ezen részhalmazok (V (G) és V (D) megfelelő diagramjai ismertek és összevonhatók. Ez az algoritmus Shamos és Hoey .

Így van egy osztó és meghódító algoritmusunk , amelynek bonyolultsága O ( n log n ) .

Szerencsés algoritmus

A Fortune algoritmus (1987, Bell Labs AT & T) aszimptotikusan optimálisnak bizonyult. Ez az O ( n log n ) a időben és O ( n ) a memóriát .

Az általános elképzelés szerint a síkot balról jobbra kell függőleges vonallal söpörni (ez egy sweep line algoritmus ); fokozatosan építjük a Voronoi-diagramot. A probléma az, hogy a már elkészített diagram, a vonaltól balra, attól a ponttól függ, amely ettől a vonaltól jobbra helyezkedik el, és ezért még nem vették figyelembe. A Fortune úgy oldja meg ezt a problémát, hogy figyelembe vesz egy parabolikus frontot, amely kissé "lemarad" a söpörési vonal mögött, oly módon, hogy az elől balra látható ábra a végső diagram.

Bowyer-Watson algoritmus

A Bowyer-Watson algoritmus kiszámít egy Delaunay-háromszöget , majd a duálhoz léphetünk, hogy megszerezzük a Voronoi-diagramot.

Alkalmazások

A Voronoi-diagramokat számos mezőben használják, vagy sok névvel feltalálják. Gyakran avatkoznak be, amikor az ember a teret befolyásoló zónákra kívánja felosztani. Néhány példa :

Csillagászat

• a csillagpopulációk térszerkezeteinek felosztása  ;

Biológia és orvostudomány

• a rákos sejtek diagnózisa  ;

Gazdaság és adminisztráció

• a területi szervezet esetében , ha a pontok erőforrásoknak felelnek meg, a Voronoi-cellák optimálisan megfelelnek az ezen erőforrások által kiszolgált területeknek, figyelembe véve, hogy a hozzáférési erőfeszítések arányosak a távolsággal légvonalban, és hogy a népsűrűség egységes; például az iskolai térkép elkészítése  ;
• geomarketing;

Földrajz

• az optimális földrajzi adatok rekonstrukciója, például repülési szimulátor számára;
• a tájak, különösen a mezőgazdasági tájak szimulálása (a Voronoi sejtek összehasonlíthatók a vetemények parcelláival);

Számítástechnika

• mozaik hatást szoftver a képszerkesztő  ;

Matematika

• kettős geodéziai kupola építése  ;
• számos geometriai probléma megoldása, gyakran téroptimalizálási alkalmazásokkal ( logisztika , területrendezés , létesítmény elhelyezése ):
  • keresse meg a legközelebbi szomszédokat ,
  • legnagyobb üres kör probléma ,
  • utazó eladó problémája ,
  • a domború burok meghatározása ,
  • minimális kör probléma ,
  • a városi szállítási területekre irányuló szolgáltatás jellemzése;

Fizika és kémia

• mikrostruktúrák, például egyes acélok modellezése  ;
• a folyadékok porózus közegben történő keringésének szimulálása, különösen a természetes elemek módszerével  ;
• a kristálytanban a Wigner-Seitz sejt és a Brillouin zóna meghatározása  ;
• a kémiai termodinamikában az állapotfüggvények modellezése  ;

Technológiák

• pálya számítások a mobil robotikában;
• detektálás vezeték nélküli kommunikációs rendszerekben (különösen a mobiltelefon- telefon fogalma ).

Megjegyzések és hivatkozások

Megjegyzések

1. Lásd: Convex set> Convexes metszéspontjai

Hivatkozások

1. Principia philosophiae 1644 , latin kiadás AT VIII-1; Paul Picot francia fordítása, Descartes átdolgozta, A filozófia alapelvei , 1647. , AT-IX.
2. (in) Steven Johnson , The Ghost térkép: The Story of London legborzasztóbb Epidemic - és hogyan Megváltozott Tudomány, városok és a modern világ , New York, Riverhead Könyvek,2006, 299  p. ( ISBN  1-59448-925-4 ) , p.  195–196
3. Georges Voronoï , „  Folyamatos paraméterek új alkalmazásai a másodfokú formák elméletéhez. Első tézis. A tökéletes pozitív másodfokú formák néhány tulajdonságáról.  », Journal für die Reine und Angewandte Mathematik , vol.  1908 N o  133,1908, P.  97–178 ( online olvasás )
4. Georges Voronoï , „  Folyamatos paraméterek új alkalmazásai a másodfokú formák elméletéhez. Első tézis. A tökéletes pozitív másodfokú formák néhány tulajdonságáról.  », Journal für die Reine und Angewandte Mathematik , vol.  1908 N o  134,1908, P.  198–287 ( online olvasás )
5. (en) Michael Ian Shamos , Számítási geometria: PhD értekezés , Yale Egyetem ,1975
   en) Michael Ian Shamos és Dan Hoey , „Legközelebbi problémák” , a 16. éves IEEE szimpózium folytatásaként a számítástechnika alapjairól , Los Angeles, IEEE Computer Society Press,1975( online olvasható ) , p.  151-162
6. Voronoi és Delaunay számítások , Florida Állami Egyetem
7. Franck Hétroy, „  Egy kis algoritmikus geometria, 4.2 Voronoıono: inkrementális konstrukció  ” , az ENSIMAG- on .
8. (a) Steven Fortune , "  A Sweepline Algoritmus voronoj-cella  " , Algorithmica , Springer-Verlag, vol.  1,1987, P.  153-174
9. (in) Lopez, C., Zhao, C.-L., Magniol, S., Chiabaut, N. and Leclercq, L. "  A teherautók parkolásához szükséges hajózás mikroszkópos szimulációja intézkedést jelent a teherterhelés zónájának kezelésére  " , Fenntarthatóság, 11 (5), 1276 ,2019. február 28( online olvasás )
10. (in) Yongjian Yang Hirofumi Tokunaga, Madoka Ono Kazutaka Hayashi és John C. Mauro, "  Az alkáli-alkáliföldfém-szilikát üvegek moláris térfogatának megértése a Voronoi polyhedra analízissel  " , Scripta Materialia  (in) , vol.  166,2019. június, P.  1–5 ( DOI  10.1016 / j.scriptamat.2019.02.041 ).

Lásd is

Bibliográfia

• [Dirichlet 1850] (de) Johann Peter Gustav Dirichlet , „  Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen  ” , Journal für die Reine und angewandte Mathematik ,1850
• [Aurenhammer 1991] (en) Franz Aurenhammer , „  Voronoi diagramok: egy alapvető geometriai adatszerkezet felmérése  ” , ACM Computing Surveys , vol.  23, n o  3,1991. szeptember, P.  345–405 ( online olvasás )

Kapcsolódó cikkek

• Navigációs háló
• Delaunay háromszögelés
• Lloyd-Max algoritmus
• A természetes elemek módszere
• Treemap
• Laguerre diagram  (in)

Külső linkek

• Stéphane Bessy, „  Geometriai algoritmusok: a kurzus algoritmusai  ” , a LIRMM-en (konzultáció 2017. január 30-án )