Voronoiho diagram - Voronoi diagram

20 bodů a jejich buňky Voronoi (větší verze níže )

v matematika, a Voronoiho diagram je rozdělit a letadlo do oblastí blízko každé z dané sady objektů. V nejjednodušším případě jsou tyto objekty konečně mnoho bodů v rovině (nazývají se semena, místa nebo generátory). Pro každé semeno existuje odpovídající oblast skládající se ze všech bodů roviny blíže k tomuto semenu než k jakémukoli jinému. Tyto oblasti se nazývají Voronoiho buňky. Voronoiův diagram množiny bodů je dvojí k jeho Delaunayova triangulace.

Voronoiův diagram je pojmenován po Georgy Voronoy, a také se nazývá a Voronoi mozaikování, a Voronoiův rozklad, a Voronoi oddílnebo Dirichletova mozaikování (po Peter Gustav Lejeune Dirichlet ). Voronoi buňky jsou také známé jako Thiessenovy polygony.^[1][2][3] Voronoiovy diagramy mají praktické a teoretické aplikace v mnoha oblastech, zejména v Věda a technologie, ale také v vizuální umění.^[4][5]

Nejjednodušší případ

V nejjednodušším případě, zobrazeném na prvním obrázku, dostaneme konečnou množinu bodů {str₁, ..., str_n} v Euklidovské letadlo. V tomto případě každý web str_k je prostě bod a jeho odpovídající Voronoiova buňka R_k se skládá z každého bodu v euklidovské rovině, jehož vzdálenost k str_k je menší nebo rovna jeho vzdálenosti od kteréhokoli jiného str_k. Každá taková buňka je získána z průsečíku poloprostory, a proto je (konvexní) mnohostěn^[6]. The úsečky Voronoiho diagramu jsou všechny body v rovině, které jsou ve stejné vzdálenosti od dvou nejbližších míst. Voronoijské vrcholy (uzly ) jsou body ve stejné vzdálenosti od tří (nebo více) míst.

Formální definice

Nechat ${ textstyle X}$ být metrický prostor s funkcí vzdálenosti ${ textstyle d}$. Nechat ${ textstyle K}$ být soubor indexů a nechat ${ textstyle (P_ {k}) _ {k v K}}$ být n-tice (objednaný sběr) neprázdného podmnožiny (stránky) v prostoru ${ textstyle X}$. Voronoiova buňka nebo oblast Voronoi, ${ textstyle R_ {k}}$související s webem ${ textový styl P_ {k}}$ je množina všech bodů v ${ textstyle X}$ jejichž vzdálenost do ${ textový styl P_ {k}}$ není větší než jejich vzdálenost od ostatních webů ${ textový styl P_ {j}}$, kde ${ textstyle j}$ je jakýkoli index odlišný od ${ textstyle k}$. Jinými slovy, pokud ${ textstyle d (x, , A) = inf {d (x, , a) uprostřed a v A }}$ označuje vzdálenost mezi bodem ${ textstyle x}$ a podmnožina ${ textový styl A}$, pak

$${ displaystyle R_ {k} = {x v X mid d (x, P_ {k}) leq d (x, P_ {j}) ; { text {pro všechny}} ; j neq k }}$$

Voronoiův diagram je jednoduše n-tice buněk ${ textstyle (R_ {k}) _ {k v K}}$. V zásadě se některé weby mohou protínat a dokonce shodovat (aplikace je popsána níže pro weby představující obchody), ale obvykle se předpokládá, že jsou disjunktní. Kromě toho je v definici povoleno nekonečně mnoho webů (toto nastavení má aplikace v geometrie čísel a krystalografie ), ale v mnoha případech se zvažuje pouze konečně mnoho stránek.

V konkrétním případě, kdy je prostor a konečně-dimenzionální Euklidovský prostor, každé místo je bod, existuje konečně mnoho bodů a všechny jsou odlišné, pak jsou buňky Voronoi konvexní polytopes a mohou být reprezentovány kombinačním způsobem pomocí jejich vrcholů, stran, dvourozměrných ploch atd. Někdy se indukovaná kombinatorická struktura označuje jako Voronoiův diagram. Obecně však nemusí být buňky Voronoi konvexní nebo dokonce spojené.

V obvyklém euklidovském prostoru můžeme formální definici přepsat obvyklými termíny. Každý polygon Voronoi ${ textstyle R_ {k}}$ je spojen s bodem generátoru ${ textový styl P_ {k}}$.Nechat ${ textstyle X}$ být množinou všech bodů v euklidovském prostoru. Nechat ${ textový styl P_ {1}}$ být bodem, který generuje jeho oblast Voronoi ${ textstyle R_ {1}}$, ${ textový styl P_ {2}}$ který generuje ${ textstyle R_ {2}}$, a ${ textový styl P_ {3}}$ který generuje ${ textstyle R_ {3}}$, a tak dále. Poté, jak vyjádřil Tran et al^[7]„všechna místa ve Voronoiově polygonu jsou blíže k bodu generátoru tohoto polygonu než kterýkoli jiný bod generátoru ve Voronoiho diagramu v euklidovské rovině“.

Ilustrace

Pro jednoduchou ilustraci zvažte skupinu obchodů ve městě. Předpokládejme, že chceme odhadnout počet zákazníků daného obchodu. Pokud jsou všechny ostatní stejné (cena, produkty, kvalita služeb atd.), Je rozumné předpokládat, že si zákazníci vyberou svůj preferovaný obchod jednoduše podle vzdálenosti: půjdou do nejbližšího obchodu. V tomto případě Voronoiova buňka ${ displaystyle scriptstyle R_ {k}}$ daného obchodu ${ displaystyle scriptstyle P_ {k}}$ lze použít k poskytnutí hrubého odhadu počtu potenciálních zákazníků, kteří do tohoto obchodu (který je modelován bodem v našem městě).

U většiny měst lze vzdálenost mezi body měřit pomocí známéhoEuklidovská vzdálenost:

${ displaystyle ell _ {2} = d left [ left (a_ {1}, a_ {2} right), left (b_ {1}, b_ {2} right) right] = { sqrt { left (a_ {1} -b_ {1} right) ^ {2} + left (a_ {2} -b_ {2} right) ^ {2}}}}$

nebo Vzdálenost na Manhattanu:

${ displaystyle d left [ left (a_ {1}, a_ {2} right), left (b_ {1}, b_ {2} right) right] = left | a_ {1} - b_ {1} right | + left | a_ {2} -b_ {2} right |}$.

Odpovídající Voronoiovy diagramy vypadají odlišně pro různé metriky vzdálenosti.

Voronoiovy diagramy 20 bodů pod dvěma různými metrikami

Euklidovská vzdálenost

Vzdálenost na Manhattanu

Vlastnosti

• The duální graf pro Voronoiův diagram (v případě a Euklidovský prostor s bodovými místy) odpovídá Delaunayova triangulace pro stejnou sadu bodů.
• The nejbližší dvojice bodů odpovídá dvěma sousedním buňkám ve Voronoiově diagramu.
• Předpokládejme, že nastavení je Euklidovské letadlo a je dána skupina různých bodů. Pak dva body sousedí na konvexní obal kdyby a jen kdyby jejich Voronoiovy buňky sdílely nekonečně dlouhou stranu.
• Pokud je prostor a normovaný prostor a je dosažena vzdálenost ke každému místu (např. když je web a kompaktní sada nebo uzavřená koule), pak může být každá Voronoiova buňka reprezentována jako spojení liniových segmentů vycházejících z míst.^[8] Jak je tam znázorněno, tato vlastnost nemusí nutně platit, když není dosaženo vzdálenosti.
• Za relativně obecných podmínek (prostor je možná nekonečně dimenzionální rovnoměrně konvexní prostor, může existovat nekonečně mnoho stránek obecné formy atd.) Voronoiovy buňky mají určitou vlastnost stability: malá změna v tvarech stránek, např. změna způsobená nějakým překladem nebo zkreslením, přináší malou změnu v tvar buněk Voronoi. Toto je geometrická stabilita Voronoiho diagramů.^[9] Jak je zde ukázáno, tato vlastnost obecně neplatí, i když je prostor dvourozměrný (ale nerovnoměrně konvexní a zejména neeuklidovský) a stránky jsou body.

Historie a výzkum

Neformální použití Voronoiho diagramů lze vysledovat až k Descartes v roce 1644. Peter Gustav Lejeune Dirichlet použil ve své studii kvadratických forem v roce 1850 dvourozměrné a trojrozměrné Voronoiovy diagramy. britský lékař John Snow použil Voronoiův diagram v roce 1854 k ilustraci toho, jak většina lidí, kteří zemřeli v Vypuknutí cholery na Broad Street žil blíže k infikovaným Broad Street pumpa než na jakékoli jiné vodní čerpadlo.

Voronoiovy diagramy jsou pojmenovány po Georgy Feodosievych Voronoy který definoval a studoval generála n-rozměrný případ v roce 1908.^[10] Voronoiovy diagramy, které se používají v geofyzika a meteorologie analyzovat prostorově distribuovaná data (například měření srážek) se podle amerického meteorologa nazývají Thiessenovy polygony Alfred H. Thiessen. Další ekvivalentní názvy pro tento koncept (nebo jeho konkrétní důležité případy): Voronoi polyhedra, Voronoi polygony, domény vlivu, Voronoiho rozklad, Voronoiho teselace, Dirichletova teselace.

Příklady

Toto je výseč Voronoiho diagramu náhodné sady bodů ve 3D poli. Obecně platí, že průřez 3D Voronoiho mozaikování není 2D Voronoiho mozaikování sám. (Buňky jsou všechny konvexní mnohostěn.)

Voronoi mozaikování pravidelné mříže bodů ve dvou nebo třech dimenzích vede k mnoha známým mozaikování.

• 2D mřížka poskytuje nepravidelné voštinové mozaikování se stejnými šestiúhelníky s bodovou symetrií; v případě pravidelné trojúhelníkové mřížky je pravidelná; v případě obdélníkové mřížky se šestiúhelníky zmenšují na obdélníky v řádcích a sloupcích; A náměstí mřížka dává pravidelné mozaikování čtverců; Všimněte si, že obdélníky a čtverce lze také generovat jinými mřížemi (například mřížka definovaná vektory (1,0) a (1 / 2,1 / 2) dává čtverce). Vidět tady pro dynamický vizuální příklad.
• A jednoduchá kubická mříž dává kubický plástev.
• A šestihranný uzavřený mřížka dává mozaikování prostoru s lichoběžníková kosočtverec.
• A kubický střed mřížka dává mozaikování prostoru s kosočtverečná dodekahedra.
• A centrovaný na tělo mřížka dává mozaikování prostoru s zkrácená oktaedra.
• Rovnoběžné roviny s pravidelnými trojúhelníkovými mřížemi zarovnanými s navzájem středy dávají šestihranný hranolový plástev.
• Určité tetragonální mřížky zaměřené na tělo dávají mozaiku prostoru s rhombo-hexagonální dodekahedra.

Pro množinu bodů (X, y) s X v diskrétní sadě X a y v diskrétní sadě Y, dostaneme obdélníkové dlaždice s body, které nemusí být nutně v jejich středech.

Voronoiovy diagramy vyššího řádu

I když je normální Voronoiova buňka definována jako množina bodů nejblíže jednomu bodu v S, an nVoronoiova buňka tého řádu je definována jako množina bodů majících konkrétní množinu n body v S jako jeho n nejbližší sousedé. Voronoiovy diagramy vyššího řádu také dělí prostor.

Voronoiovy diagramy vyššího řádu lze generovat rekurzivně. Generovat n^th- objednejte si Voronoiův diagram ze sadyS, začněte s (n − 1)^th-objednejte diagram a nahraďte každou buňku generovanou X = {X₁, X₂, ..., X_n−1} s Voronoiho diagramem generovaným na scéněS − X.

Nejvzdálenější Voronoiův diagram

Pro sadu n poukazuje na (n − 1)^th-řádkový Voronoiův diagram se nazývá nejvzdálenější Voronoiův diagram.

Pro danou sadu bodů S = {str₁, str₂, ..., str_n} diagram Voronoi s nejvzdálenějším bodem rozděluje rovinu na buňky, ve kterých je stejný bod P je nejvzdálenější bod. Bod z P má buňku v nejvzdálenějším Voronoiově diagramu právě tehdy, je-li vrcholem konvexní obal z P. Nechat H = {h₁, h₂, ..., h_k} být konvexní trup P; pak je nejvzdálenější Voronoiův diagram dělení roviny na k buňky, jeden pro každý bod v H, s vlastností, že bod q leží v buňce odpovídající místu h_i právě když d (q, h_i)> d (q, str_j) pro každého str_j ∈ S s h_i ≠ str_j, kde d (str, q) je Euklidovská vzdálenost mezi dvěma body str aq.^[11][12]

Hranice buněk v nejvzdálenějším Voronoiově diagramu mají strukturu a topologický strom, s nekonečným paprsky jako jeho listy. Každý konečný strom je isomorfní se stromem vytvořeným tímto způsobem z nejvzdálenějšího Voronoiho diagramu.^[13]

Zobecnění a variace

Jak vyplývá z definice, lze Voronoiovy buňky definovat pro jiné metriky než euklidovské, například Mahalanobisova vzdálenost nebo Vzdálenost na Manhattanu. V těchto případech však mohou být hranice Voronoiových buněk komplikovanější než v euklidovském případě, protože ekvidistantní lokus pro dva body nemusí být podprostorem codimension 1, a to ani v dvourozměrném případě.

Přibližný Voronoiův diagram množiny bodů. Všimněte si smíšených barev ve fuzzy hranici buněk Voronoi.

A vážený Voronoiův diagram je ten, ve kterém je funkce dvojice bodů k definování Voronoiho buňky funkcí vzdálenosti upravenou pomocí multiplikativní nebo aditivní váhy přiřazené bodům generátoru. Na rozdíl od případu Voronoiových buněk definovaných pomocí vzdálenosti, která je a metrický, v tomto případě mohou být některé z buněk Voronoi prázdné. A schéma napájení je typ Voronoiho diagramu definovaného ze sady kruhů pomocí vzdálenost výkonu; lze jej také považovat za vážený Voronoiův diagram, ve kterém je váha definovaná od poloměru každé kružnice přidána k na druhou euklidovská vzdálenost ze středu kruhu.^[14]

Voronoiův diagram ${ displaystyle n}$ body v ${ displaystyle d}$-rozměrný prostor může mít ${ textstyle O (n ^ { lceil d / 2 rceil})}$ vrcholy, které vyžadují stejnou mez pro množství paměti potřebné k uložení jejího explicitního popisu. Voronoiovy diagramy proto často nejsou možné pro střední nebo vysoké rozměry. Prostorově efektivnější alternativou je použití přibližné Voronoiovy diagramy.^[15]

Voronoiovy diagramy také souvisejí s jinými geometrickými strukturami, jako je střední osa (který našel uplatnění v segmentaci obrazu, optické rozpoznávání znaků a další výpočetní aplikace), rovná kostra, a zónové diagramy. Kromě bodů používají tyto diagramy jako semena čáry a mnohoúhelníky. Rozšířením diagramu o úsečky, které se připojují k nejbližším bodům na semenech, se získá plošné rozdělení prostředí.^[16] Tuto strukturu lze použít jako a navigační síť pro hledání cest ve velkých prostorech. Navigační síť byla zobecněna tak, aby podporovala 3D vícevrstvá prostředí, jako je letiště nebo vícepodlažní budova.^[17]

Aplikace

Humanitní vědy

• v klasická archeologie resp historie umění symetrie socha hlavy se analyzuje, aby se určil typ sochy, ke které mohla useknutá hlava patřit jako v případě slavné Sabouroffova hlava pomocí vysokého rozlišení Mnohoúhelníková síť.^[18][19]

Přírodní vědy

Voronoi teselace se objevuje radiálním růstem ze semen směrem ven.

• v biologie Voronoiovy diagramy se používají k modelování řady různých biologických struktur, včetně buňky^[20] a kostní mikroarchitektura.^[21] Voronoi teselace skutečně fungují jako geometrický nástroj k pochopení fyzických omezení, která řídí organizaci biologických tkání.^[22]
• v hydrologie „Voronoiovy diagramy se používají k výpočtu srážek v oblasti na základě řady bodových měření. V tomto použití se obecně označují jako Thiessenovy polygony.
• v ekologie Voronoiovy diagramy se používají ke studiu růstových vzorů lesů a lesních vrchlíků a mohou být také užitečné při vývoji prediktivních modelů pro lesní požáry.
• v výpočetní chemie K výpočtu se používají buňky Voronoi definované polohami jader v molekule atomové náboje. To se provádí pomocí Hustota deformace Voronoi metoda.
• v astrofyzika „Voronoiovy diagramy se používají ke generování adaptivních vyhlazovacích zón na obrázcích a ke každému z nich přidávají toky signálu. Hlavním cílem těchto postupů je udržovat relativně konstantní odstup signálu od šumu na všech obrázcích.
• v výpočetní dynamika tekutin, Voronoiho mozaikování množiny bodů lze použít k definování výpočetních domén použitých v konečný objem metody, např. jako v kosmologickém kódu pohybujícího se oka AREPO.^[23]
• v výpočetní fyzika, Voronoiovy diagramy se používají k výpočtu profilů objektu s Stínograf a protonová rentgenografie v Fyzika vysoké hustoty energie.^[24]

Zdraví

• v lékařská diagnóza, modely svalové tkáně, založené na Voronoiho diagramech, mohou být použity k detekci neuromuskulárních onemocnění.^[22]
  

  Původní diagram Johna Snowa
• v epidemiologie „Voronoiovy diagramy lze použít ke korelaci zdrojů infekcí v epidemiích. Jednu z raných aplikací Voronoiových diagramů implementovala John Snow studovat Vypuknutí cholery z roku 1854 na Broad Street v Soho v Anglii. Ukázal korelaci mezi obytnými oblastmi na mapě centrálního Londýna, jejichž obyvatelé používali konkrétní vodní čerpadlo, a oblastmi s největším počtem úmrtí v důsledku vypuknutí.^[25]

Inženýrství

• v polymerní fyzika „Voronoiovy diagramy lze použít k vyjádření volných objemů polymerů.
• v věda o materiálech, polykrystalické mikrostruktury v kovových slitinách jsou běžně reprezentovány pomocí Voronoiho teselace. Při růstu ostrovů se Voronoiův diagram používá k odhadu rychlosti růstu jednotlivých ostrovů ^{[26][27][28][29]}. v fyzika pevných látek, Wigner-Seitzova buňka je Voronoiho mozaikování tělesa a Brillouinova zóna je Voronoiova mozaikování vzájemnosti (vlnové číslo ) prostor krystalů, které mají symetrii vesmírné skupiny.
• v letectví, Voronoiovy diagramy jsou superponovány na oceánské vykreslovací grafy k identifikaci nejbližšího letiště pro odklon za letu (viz ETOPS ), jak letadlo postupuje v letovém plánu.
• v architektura, Voronoiovy vzory byly základem pro vítězný vstup pro přestavbu Centrum umění Gold Coast.^[30]
• v územní plánování, Voronoiovy diagramy lze použít k vyhodnocení systému zóny nákladního nakládání.^[31]
• v hornictví „Voronoiove polygony se používají k odhadu zásob cenných materiálů, minerálů nebo jiných zdrojů. Průzkumné vrty se používají jako sada bodů v polygonech Voronoi.
• v povrchová metrologie, Voronoi mozaikování lze použít pro drsnost povrchu modelování.^[32]

Geometrie

• A umístění bodu datovou strukturu lze postavit na Voronoiův diagram, aby bylo možné odpovědět nejbližší soused dotazy, kde člověk chce najít objekt, který je nejblíže danému bodu dotazu. Nejbližší sousední dotazy mají mnoho aplikací. Například byste mohli chtít najít nejbližší nemocnici nebo nejpodobnější objekt v a databáze. Velká aplikace je vektorové kvantování, běžně používaný v komprese dat.
• v geometrie, Voronoiovy diagramy lze použít k nalezení největší prázdný kruh uprostřed množiny bodů a v uzavírajícím mnohoúhelníku; např. vybudovat nový supermarket co nejdále od všech stávajících, ležící v určitém městě.
• Voronoiovy diagramy spolu s nejvzdálenějšími Voronoiovy diagramy se používají pro efektivní algoritmy pro výpočet kulatost množiny bodů.^[11] Voronoijský přístup se také používá při hodnocení kruhovitosti /kulatost při posuzování datové sady z a souřadnicový měřicí stroj.
• Moderní výpočetní geometrie poskytl efektivní algoritmy pro konstrukci Voronoiho diagramů a umožnil jejich použití v generování sítě, umístění bodu, shluková analýza, obráběcí plány a mnoho dalších výpočetních úkolů.^[33]

Informatika

• v síťování, Voronoiovy diagramy lze použít k odvození kapacity a bezdrátová síť.
• v počítačová grafika, Voronoiovy diagramy se používají k výpočtu geometrických vzorů tříštění / štěpení 3D. Používá se také k procedurálnímu generování organických nebo lávově vypadajících textur.
• Autonomní robotická navigace „Voronoiovy diagramy se používají k vyhledání jasných cest. Pokud jsou body překážkami, pak okraje grafu budou trasy nejdále od překážek (a teoreticky jakékoli kolize).
• v strojové učení, Voronoiovy diagramy se používají 1-NN klasifikace.^[34]
• v uživatelské rozhraní vývoj, lze Voronoiovy vzory použít k výpočtu nejlepšího stavu vznášení pro daný bod.^[35]

Občanská výchova a plánování

• v Melbourne, studenti vládních škol jsou vždy způsobilí navštěvovat nejbližší základní školu nebo střední školu, kde žijí, měřeno přímočarou vzdáleností. Mapa školních zón je tedy Voronoiův diagram.^[36]

Pekařství

• Ukrajinský cukrář Dinara Kasko používá matematické principy Voronoiho diagramu k vytvoření silikonových forem vyrobených pomocí 3D tiskárny pro tvarování jejích původních koláčů.

Algoritmy

Pro konstrukci Voronoiho diagramů je známo několik účinných algoritmů, a to buď přímo (jako samotný diagram), nebo nepřímo, počínaje Delaunayova triangulace a poté získat jeho dual.Direct algoritmy zahrnují Fortuneův algoritmus, an Ó (n log (n)) algoritmus pro generování Voronoiho diagramu ze sady bodů v rovině.Algoritmus Bowyer-Watson, an Ó (n log (n)) až Ó (n²) algoritmus pro generování Delaunayovy triangulace v libovolném počtu dimenzí, lze použít v nepřímém algoritmu pro Voronoiův diagram.

Lloydův algoritmus a jeho zobecnění prostřednictvím Algoritmus Linde – Buzo – Gray (aka k-znamená shlukování ), použijte konstrukci Voronoiho diagramů jako podprogram. Tyto metody se střídají mezi kroky, ve kterých jeden vytváří Voronoiův diagram pro sadu počáteční body, a kroky, ve kterých jsou počáteční body přesunuty na nová místa, která jsou v jejich buňkách centrálnější . Tyto metody lze použít v prostorách libovolné dimenze k iterativní konvergenci směrem ke specializované formě Voronoiho diagramu, zvané a Teselace Voronoi těžiště, kde byla místa přesunuta do bodů, které jsou zároveň geometrickými středy jejich buněk.

Softwarové nástroje

Před zobrazením výsledků vyžadují Voronoiovy diagramy výpočetní krok. Účinný nástroj by proto zpracovával výpočet v reálném čase, aby uživateli ukázal přímý výsledek. Existuje mnoho komerčních a bezplatných aplikací. Obzvláště praktickým typem nástrojů jsou webové nástroje. Webové nástroje jsou snadněji přístupné a odkazovatelné. Taky, SVG nativně podporovaný formát webu, umožňuje současně efektivní (GPU zrychlené) vykreslování a je standardním formátem podporovaným více CAD nástroje (např. Autodesk Fusion360).

• Voronátor je bezplatný nástroj (založený na reklamách), který působí na 3D objekty sítí k aplikaci Voronoi na jejich povrch. Ačkoli nástroj působí na 3D, zpracování voronoi je založeno na jeho 2D povrchu.
• rhill voronoi je open source JavaScriptová knihovna pro 2D generaci voronoi.
• stg voronoi je projekt github s jednoduchou webovou aplikací a přesto nabízí interaktivní prohlížení buněk voronoi při pohybu myší. Poskytuje také export SVG.
• websvg voronoi je responzivní webapp pro editaci a export voronoi v SVG. Umožňuje také exportovat a importovat souřadnice semen. Je založen na 2D a liší se od dříve zmíněných nástrojů tím, že poskytuje operaci zatahování buněk, která není založena na měřítku, ale na překladu hran. Hranu lze odstranit, pokud je spotřebována sousedními hranami.
• A. Beutel voronoi používá WebGL a kromě statického prohlížení poskytuje i animovaný pohyb buněk voronoi.

Budoucnost softwarových nástrojů

Ačkoli voronoi je velmi starý koncept, v současné době dostupné nástroje postrádají několik matematických funkcí, které by těmto programům mohly přidávat hodnoty. Příkladem může být použití jiné nákladové vzdálenosti než euklidovské a hlavně 3d voronoi algoritmy. Ačkoli nejde o softwarové nástroje samotné, první odkaz vysvětluje koncept 3d voronoi a druhým je knihovna 3d voronoi.

• 3D Voronoiovy diagramy a mediální osa
• Voro ++ C ++ knihovna pro výpočet 3D voronoi

Viz také

Poznámky

Reference

externí odkazy

• Interaktivní diagramy Voronoi a Delaunay v reálném čase se zdrojovým kódem
• Ukázka různých metrik
• Mathworld na Voronoiových diagramech
• Voronoiovy diagramy: Aplikace od archeologie po zoologii
• Voronoiovy diagramy v CGAL, Knihovna algoritmů výpočetní geometrie
• Další diskuse a fotogalerie o těžkých Voronoiových mozaikách
• Voronoiovy diagramy podle Ed Pegg, Jr. Jeff Bryant a Theodore Gray, Demonstrační projekt Wolfram.
• Voronoiův diagram na kouli, ve 3D a další
• Sestrojte Voronoiův diagram pomocí Mathematica
• Voronoi Teselace - Interaktivní Voronoi mozaikování s D3.js
• Interaktivní Voronoiův diagram a vizualizace interpolace přirozených sousedů (WebGL)