Algoritmus Bowyer-Watson - Bowyer–Watson algorithm
v výpočetní geometrie, Algoritmus Bowyer-Watson je metoda výpočtu Delaunayova triangulace konečné sady bodů v libovolném počtu rozměry. Algoritmus lze také použít k získání a Voronoiho diagram bodů, což je duální graf Delaunayovy triangulace.
Popis
Algoritmus Bowyer-Watson je inkrementální algoritmus. Funguje tak, že přidáváte body, jeden po druhém, k platné Delaunayově triangulaci podmnožiny požadovaných bodů. Po každém vložení budou odstraněny všechny trojúhelníky, jejichž kruhové kruhy obsahují nový bod, přičemž zůstane a hvězdicovitý polygonální díra, která se poté znovu trianguluje pomocí nového bodu. Použitím konektivity triangulace k efektivnímu lokalizování trojúhelníků, které lze odstranit, může algoritmus trvat O (N log N) operace k triangulaci N bodů, i když existují zvláštní zvrhlé případy, kdy to jde až NA2).[1]
První krok: Vložení uzlu do uzavírajícího „super“ trojúhelníku
Vložte druhý uzel
Vložte třetí uzel
Vložte čtvrtý uzel
Vložte pátý (a poslední) uzel
Odstraňte okraje s extrémy v super-trojúhelníku
Dějiny
Algoritmus je někdy známý jako Bowyerův algoritmus nebo Watsonův algoritmus. Adrian Bowyer a David Watson jej vymysleli nezávisle na sobě ve stejnou dobu a každý o tom publikoval článek ve stejném čísle Počítačový deník (viz. níže).
Pseudo kód
Následující pseudo kód popisuje základní implementaci Bowyer-Watsonova algoritmu. Jeho časová složitost je . Efektivitu lze zlepšit mnoha způsoby. Například připojení trojúhelníku lze použít k vyhledání trojúhelníků, které obsahují nový bod v jejich kruhovém kruhu, aniž by bylo nutné kontrolovat všechny trojúhelníky - tím můžeme snížit časovou složitost na . Předběžné výpočty obvodů mohou ušetřit čas na úkor dalšího využití paměti. A pokud jsou body rovnoměrně rozloženy, setřídí je podle vyplnění prostoru Hilbertova křivka před vložením lze také zrychlit umístění bodu.[2]
funkce BowyerWatson (pointList) // pointList je sada souřadnic definujících body, které mají být triangulovány triangulace := prázdný trojúhelník pletivo data struktura přidat super-trojúhelník na triangulace // musí být dostatečně velký, aby zcela obsahoval všechny body v pointList pro každý směřovat v pointList dělat // přidá všechny body jeden po druhém do triangulace badTriangles := prázdný soubor pro každý trojúhelník v triangulace dělat // nejprve najděte všechny trojúhelníky, které již nejsou platné kvůli vložení -li směřovat je uvnitř obvod z trojúhelník přidat trojúhelník na badTriangles polygon := prázdný soubor pro každý trojúhelník v badTriangles dělat // najít hranici polygonální díry pro každý okraj v trojúhelník dělat -li okraj je ne sdílené podle žádný jiný trojúhelníky v badTriangles přidat okraj na polygon pro každý trojúhelník v badTriangles dělat // odstranit je z datové struktury odstranit trojúhelník z triangulace pro každý okraj v polygon dělat // znovu trianguluje polygonální otvor novýTri := formulář A trojúhelník z okraj na směřovat přidat novýTri na triangulace pro každý trojúhelník v triangulace // hotové vkládání bodů, nyní vyčistit -li trojúhelník obsahuje A vrchol z originál super-trojúhelník odstranit trojúhelník z triangulace vrátit se triangulace
Reference
- ^ Rebay, S. Efektivní generování nestrukturované sítě pomocí Delaunayovy triangulace a Bowyer-Watsonova algoritmu. Journal of Computational Physics Volume 106, číslo 1, květen 1993, s. 127.
- ^ Liu, Yuanxin a Jack Snoeyink. „Srovnání pěti implementací 3D delaunayské mozaiky.“ Combinatorial and Computational Geometry 52 (2005): 439-458.
Další čtení
- Bowyer, Adrian (1981). „Computing Dirichlet tessellations“. Comput. J. 24 (2): 162–166. doi:10.1093 / comjnl / 24.2.162.
- Watson, David F. (1981). "Počítám n-dimenzionální delaunayská mozaikování s aplikací na voronské polytopy ". Comput. J. 24 (2): 167–172. doi:10.1093 / comjnl / 24.2.167.
- Efektivní triangulační algoritmus vhodný pro modelování terénu obecná vysvětlení s příklady zdrojových kódů v několika jazycích.
externí odkazy
- pyDelaunay2D : Didaktický Krajta implementace Bowyer-Watsonova algoritmu.
- Bl4ckb0ne / delaunay-triangulace : C ++ implementace Bowyer-Watsonova algoritmu.