Ruppertsův algoritmus - Rupperts algorithm - Wikipedia

Vstup Ruppertova algoritmu
Vstupní rovinný přímkový graf
Výstup vyhovující Delaunayově triangulaci
Výstup vyhovující Delaunayově triangulaci
Příklad Ruppertova algoritmu

v generování sítě, Ruppertův algoritmus, také známý jako Delaunayovo upřesnění, je algoritmus pro vytváření kvality Delaunayovy triangulace. Algoritmus trvá a rovinný přímkový graf (nebo v dimenzi vyšší než dva a po částech lineární systém) a vrátí vyhovující Delaunayovu triangulaci pouze kvalitních trojúhelníků. Trojúhelník je považován za nekvalitní, pokud má poměr mezi poloměrem a nejkratší hranou větší než nějaký předepsaný práh. Objeven Jimem Ruppertem na počátku 90. let[1]„Ruppertův algoritmus pro generování dvourozměrné kvalitní sítě je možná první teoreticky zaručené propojení algoritmus být v praxi skutečně uspokojivý. “[2]

Motivace

Při provádění počítačových simulací, jako je výpočetní dynamika tekutin, jeden začíná modelem, jako je 2D obrys řezu křídla. Vstup do 2D Metoda konečných prvků musí být ve formě trojúhelníků, které vyplňují celý prostor, a každý trojúhelník musí být vyplněn jedním druhem materiálu - v tomto příkladu buď „vzduch“ nebo „křídlo“. Dlouhé, hubené trojúhelníky nelze přesně simulovat. je obecně úměrná počtu trojúhelníků, a tak člověk chce minimalizovat počet trojúhelníků a přitom stále používat dostatek trojúhelníků, aby poskytl přiměřeně přesné výsledky - obvykle pomocí nestrukturovaná mřížka Počítač používá Ruppertův algoritmus (nebo nějaký podobný síťový algoritmus) k převodu polygonálního modelu na trojúhelníky vhodné pro metodu konečných prvků.

Mezilehlé triangulace Ruppertova algoritmu

Popis algoritmu

Algoritmus začíná Delaunayovou triangulací vstupních vrcholů a poté sestává ze dvou hlavních operací.

  • Do trojúhelníku se vloží střed segmentu s neprázdnými diametrálními kruhy.
  • The circumcenter nekvalitního trojúhelníku se vloží do triangulace, pokud tento circumcenter neleží v diametrálním kruhu nějakého segmentu. V tomto případě je zasažený segment místo toho rozdělen.

Tyto operace se opakují, dokud neexistují žádné nekvalitní trojúhelníky a nebudou zasaženy všechny segmenty.

Pseudo kód

funkce Ruppert (bodů, segmenty, práh) je    T : = DelaunayTriangulation (bodů)    Q : = sada zasažených segmentů a nekvalitních trojúhelníků zatímco Q není prázdný: // Hlavní smyčka        -li Q obsahuje segment s: vložte střed s do T        jiný Q obsahuje nekvalitní trojúhelník t:            -li circumcenter z t zasahuje do segmentu s: přidat s na Q;            jiný: vložte circumcenter z t do T            skončit, pokud        skončit, pokud        Aktualizace Q    skončit chvíli    vrátit se Tkonec Ruppert.

Praktické využití

Bez modifikace je zaručeno, že Ruppertův algoritmus ukončí a vygeneruje kvalitní síť pro neakutní vstup a jakýkoli práh nízké kvality nižší než asi 20,7 stupňů. Pro uvolnění těchto omezení byla provedena různá malá vylepšení. Uvolněním požadavku na kvalitu v blízkosti malých vstupních úhlů lze algoritmus rozšířit tak, aby zvládl jakýkoli přímý vstup.[3] Zakřivený vstup lze také spojit pomocí podobných technik.[4]Ruppertův algoritmus lze přirozeně rozšířit do tří dimenzí, ale jeho výstupní záruky jsou o něco slabší kvůli čtyřstěnům typu pramene.

Ve volně dostupném balíčku Triangle je implementováno rozšíření Ruppertova algoritmu ve dvou dimenzích. Je zaručeno, že dvě varianty Ruppertova algoritmu v tomto balíčku budou ukončeny pro prahovou hodnotu nekvalitní asi 26,5 stupňů.[5] V praxi jsou tyto algoritmy úspěšné pro prahové hodnoty nízké kvality nad 30 stupňů. Jsou však známy příklady, které způsobují selhání algoritmu s prahovou hodnotou větší než 29,06 stupňů.[6]

Viz také

Reference

  1. ^ Ruppert, Jim (1995). "Algoritmus zdokonalení Delaunay pro kvalitní generování 2-dimenzionální sítě". Journal of Algorithms. 18 (3): 548–585. doi:10.1006 / jagm.1995.1021.
  2. ^ Shewchuk, Jonathan (12. srpna 1996). „Algoritmus upřesnění Rupperta Delaunaye“. Citováno 28. prosince 2018.
  3. ^ Miller, Gary; Pav, Steven; Walkington, Noel (2005). "Kdy a proč fungují algoritmy zpřesnění Delaunay". International Journal of Computational Geometry and Applications. 15 (1): 25–54. doi:10.1142 / S0218195905001592.
  4. ^ Pav, Steven; Walkington, Noel (2005). Delaunay zušlechťování rohovým bodáním. Sborník ze 14. mezinárodního kulatého stolu. str. 165–181.
  5. ^ Shewchuk, Jonathan (2002). "Delaunayovy zpřesňující algoritmy pro generování trojúhelníkové sítě". Výpočetní geometrie: Teorie a aplikace. 22 (1–3): 21–74. doi:10.1016 / s0925-7721 (01) 00047-5.
  6. ^ Rand, Alexander (2011). "Vylepšené příklady neukončení Ruppertova algoritmu". arXiv:1103.3903 [cs.CG ]..

externí odkazy