Delaunay triangulatsioon

Delaunay triangulatsioon (hääldus: delo'nee) on matemaatika ja arvutusgeomeetria mõiste. See on defineeritud kui punktihulga P triangulatsioon pinnal nii, et moodustatavate kolmnurkade sees ei oleks ühtegi punkti ning kolmnurkade tipud ühtivad punktidega.

Delaunay triangulatsioon on nimetatud nõukogude teadlase Boriss Delaunay järgi, kes tegeles selle teemaga alates 1934. aastast. Delaunay triangulatsioon maksimeerib kolmnurkade väikseima nurga, mille läbi välditakse liiga kitsaid kolmnurki.

Delaunay triangulatsiooni ei ole samal sirgel asuvate punktide jaoks. Kui punkti ümber kujutletud ringjoonel on 4 või rohkem punkti (näiteks ringi sisse kujuteldava ruudu diagonaalidel), pole Dealunay triangulatsioon enam üheselt määratud. Sel juhul rahuldavad mõlemad võimalikud triangulatsioonid Delaunay tingimust: tekivad kolmnurgad, mille sisemused jäävad tühjaks.

Võttes arvesse punkte ühendavad ringjooned, saab Delaunay triangulatsiooni defineerida ka kolme- ja enamamõõtmelistele punktihulkadele. Üldistused on võimalikud ka väljapoole eukleidilisi ruume. Sellistel juhtudel on aga võimalik, et Delaunay triangulatsiooni ei eksisteeri või ei ole see ühene.

Kuna lõplike elementide meetod (inglise keeles finit element method) ja piirielementide meetod (boundary element method) muutuvad järjest populaarsemaks, kasvab põhjus arendada automaatseid võrestiku moodustamise meetodeid. Vaatamata paljudele võrestiku moodustamise meetoditele, on võimalik, et nende abil loodud võrestikud tulevad moondunud ja kasutamatud. Selle probleemi lahenduseks on olemas meetodid, mille abil olemasolevat võret parandada. Näiteks võib tuua silumise, mille käigus kontrollitakse üle punkti kuuluvus kolmnurkadesse ja vajadusel muudetakse seda. Seeläbi väheneb võrestiku moone. Venitatud võrestiku meetod on aga selline, kus pärast moonete vähendamist jääb alles enam-vähem regulaarne võrestik, mida saab kiiresti ja kergesti muuta vastavaks Dealunay triangulatsiooni tingimustele.

Seotus Vornoi diagrammiga

Lisaks Delaunay triangulatsioonile kasutab punkte ühendavaid ringjooni ka Vornoi tessalatsioon. Vornoi tessalatsiooni käigus ühendatakse mainitud ringide keskpunktid ja saadakse seeläbi hulknurgad.

D-mõõtmeline Delaunay triangulatsioon

Eukleidilises ruumis moduleeritakse d–mõõtmelise juhu jaoks Delaunay triangulatsiooniks vajalik punkte ühendav hüpersfäär ja selle sees olev üldistatud vajalike mõõtmetega tetraeeder (simplex), mille sisse ei jää ühtegi punkti. On teada, et eksisteerib üheselt määratud Delaunay triangulatsioon punktihulgale P, kui ei eksisteeri k-pinda, kus on k+2 punkti, ega k-sfääri, kus oleks k+3 punkti, kusjuures 1 ≤ k ≤ d – 1. Kolmemõõtmelisel juhul tähendaks see, et ei eksisteeri kolme punkti sirgjoonel, nelja punkti ringjoonel ega viit punkti samal sfääril.

Delaunay triangulatsiooni leidmise d–mõõtmelises eukleidilises ruumis saab muuta punktihulga konveksse keha leidmiseks d+1-mõõtmelises ruumis, andes igale punktile lisakoordinaadi väärtusega |p|², leides seejärel alumise poole konvekssele kehale ja kaardistades selle tagasi d–mõõtmeliseks ruumiks, kustutades viimase koordinaadi. Kuna konveksne keha on üheselt määratud, on seetõttu ka tekkiv Delaunay triangulatsioon üheselt määratud, seda aga ainult juhul, kui konveksse keha kõik tahud on mitmemõõtmelised tetraeedrid. Kui see tingimus ei ole täidetud, on võimalik selline tulemus saada vaid siis, kui algsetest punktidest d+2 asetsevad samal d–mõõtmelisel hüpersfääril.

Omadused

Tähistame n-iga punktide arvu ja d-ga ruumi mõõtmete arvu.

Kõikide mitmemõõtmeliste tetraeedrite ühendus on kokku punktide konveksne keha.

Delaunay triangulatsioon koosneb O(n^(d / 2)) mitmemõõtmelisest tetraeedrist.

Kui pinnal (d=2) on b diagonaali samal konvekssel kehal, siis punktide iga triangulatsioon koosneb maksimaalselt 2n-2-b kolmnurgast ja ühest välisest tahust (lähemalt vaata artiklist Euleri karakteristikud).

Pinnal on igal punktil keskmiselt 6 ümbritsevat kolmnurka. See reegel kehtib üksnes siis, kui punkte on palju.

Delaunay triangulatsioon maksimeerib väikseimat nurka. Võrreldes teiste triangulatsioonidega, on Delaunay triangulatsiooni väikseim nurk vähemalt sama suur kui ülejäänud triangulatsioonide väikseim nurk. See ei tähenda aga, et suurim nurk kindlasti minimeeritaks.

Delaunay kolmnurkade ümberringjoon ei sisalda ühtegi punkti peale nende, mis moodustavad antud punktide Delaunay kolmnurga.

Kui ringjoon ühendab vaid kahte triangulatsioonipunkti, saab selle kaudu teada triangulatsioonikolmnurga ühe serva.

Iga Delaunay triangulatsiooni kolmnurk vastab d+1-mõõtmelisse ruumi projekteeritud konveksse keha tahule ja vastupidi.

Lähim tee kahe punkti b ja p vahel on neid ühendavat triangulatsioonikolmnurga serva pidi.

Visuaalne Delaunay triangulatsiooni definitsioon ja pööre

Ülaltoodud tingimustest saab järeldada, et vaadates kahte kolmnurka ABD ja BCD, mille ühine külg on BD, saab kontrollida nende vastavust Delaunay triangulatsioonile, liites kokku nurgad tippude A ja C juures. Kui summa on väiksem või võrdne sirgnurgaga (selle suurus on 180°), siis vastavad kolmnurgad Delaunay triangulatsiooni tingimustele. Kui summa on aga suurem, saab probleemi lahendada, vahetades ühist külge, mis eespool kirjeldatud juhul oleks külje BD vahetamine AC vastu. See omadus on äärmiselt oluline, kuna laseb kasutada pööret. Kui kaks ühise küljega kolmnurka ei vasta Delaunay triangulatsiooni tingimustele, saab vahetada nende ühist külge.

Pööre on Delaunay triangulatsiooni juures tihti kasutatav meetod.

Algoritmid

Kui on vaja kindlaks teha, kas punkt asetseb Delaunay kolmnurga ümberringjoones, või salvestada andmeid kolmnurkade ja nende servade jaoks, sõltuvad paljud algoritmid, mida kasutatakse Delaunay triangulatsiooni arvutamiseks, operatsioonide sooritamise kiirusest ja andmestruktuuride efektiivsusest.

Kahemõõtmelisel juhul on üks võimalus kontrollida, kas punkt D asetseb punktide A, B ja C ümberringjoones, determinant, mille väärtus on positiivne siis ja ainult siis, kui D asetseb antud ümberringjoones.

${\begin{vmatrix}A_{x}&A_{y},&A_{x}^{2}+A_{y}^{2},&1\\[6pt]B_{x}&B_{y},&B_{x}^{2}+B_{y}^{2},&1\\[6pt]C_{x}&C_{y},&C_{x}^{2}+C_{y}^{2},&1\\[6pt]D_{x}&D_{y},&D_{x}^{2}+D_{y}^{2},&1\end{vmatrix}}={\begin{vmatrix}A_{x}-D_{x},&A_{y}-D_{y},&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\[6pt]B_{x}-D_{x},&B_{y}-D_{y},&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\[6pt]C_{x}-D_{x},&C_{y}-D_{y},&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}>0$

Pöörde algoritmid

Nagu juba mainitud, saame Delaunay triangulatsiooni tingimustele mittevastavate kolmnurgapaaride pöördel määratud tingimustele vastavad kolmnurgad. Sellest omadusest järeldub, et Delaunay triangulatsiooni jaoks saab teha kõigepealt suvalise triangulatsiooni ja siis servi pöörata, kuni kõik kolmnurgad vastavad Delaunay triangulatsiooni tingimustele. Kahjuks võib sellise lähenemise jaoks vaja minna O(n²) pööret ning samuti ei laiene see meetod kolmele või enamale mõõtmele.

Lisamine

Kõige tõhusam viis Delaunay triangulatsiooni sooritamiseks on korduvalt ühekaupa tipupunkte lisada, taasluues kolmnurgad graafiku osade kaupa. Kui kolmnurga tipp v lisatakse, jagatakse ümbritsevate punktide vahele ära kolmnurgad ja seejärel kontrollitakse nurkade suurusi. Vajadusel rakendatakse pööret. Kuid on võimalus, et iga punkti lisamisel tuleb pöörata kõiki kolmnurki, seega triangulatsiooni kogu ajakulu oleks O(n²).

Tuleb aga välja, et kui lisada punkte suvalises järjekorras, on iga punkti lisamisel vaja sooritada pööre keskmiselt O(1) kolmnurgas – alati see aga ei tööta ja mõnikord võib olla vaja sooritada palju rohkem pöördeid.

Seega on punkti lisamise meetoditel arenemisruumi. Me saame alles hoida pöörete ajalugu: iga kolmnurga juures säilitatakse viitu punktidele, mis seda kolmnurka muutsid. Leidmaks kolmnurka, millesse lisati punkt v, alustame põhikolmnurgast ja leiame viitade abil, mis viitavad kolmnurgale, kuhu punkt sai lisatud, punkti v, kui leiame kolmnurga, mida ei ole veel muudetud. Keskmiselt on sellegi tegevuse keerukus O(log₁₀n). Kõigi punktide korral võtab see kokku aega O(n log₁₀n). Olgugi et seda meetodit saab üldistada kõrgemate dimensioonide jaoks, nagu on tõestanud Herbert Edelsbrunner ja Nimish Shah, kasvab ajakulu eksponentsiaalselt isegi juhul, kui lõpptriangulatsioon on väike.

Boyeri-Watsoni algoritm pakub aga teistsugust lähenemist lisamismeetodile. See on alternatiiviks pöörde meetodile, kui lisatakse ükshaaval uusi punkte. Selle meetodi jaoks kustutatakse ära uue punkti ümbruses olevad ümberringjooned, misläbi jääb sellesse kohta tähekujuline avaus, kuhu seejärel luuakse uuesti triangulatsioonikolmnurgad, lähtudes Delaunay triangulatsiooni nõuetest.

Jaga ja valitse algoritm

Algoritmi "Jaga ja valitse" (divide and conquer) on kahemõõtmelistel pindadel välja töötanud Der-Tsai Lee ja Bruce Schachter, seejärel täiustasid seda Leonidas Guibas ja Jorge Stolfi, hiljem ka Rex Dwyer. Selles algoritmis jagatakse tipud rekursiivselt kaheks. Delaunay triangulatsioon leitakse iga osa jaoks ja seejärel ühendatakse osad omavahel mööda jagamisjoont. Sobivate võtete abil saab seda teha ajaga O(n), seega kulub kogu triangulatsioonile aega O(n log₁₀n).

Mõne jaotuse korral, näiteks ühtlane juhuslik jaotus, saab teadlikult valida tippude jagamise koha, mille abil saab algoritmi kiirendada väärtuseni O(n log₁₀log₁₀n), säilitades siiski küllalt hea täpsuse.

On tõestatud, et meetod "jaga ja valitse" on kõige kiirem meetod Delaunay triangulatsiooni saamiseks.

Nihkejoon

Fortune'i algoritm kasutab nihkuva joone (sweepline) tehnikat, kus üle punktihulga nihkub punktikaupa edasi joon, milleni triangulatsioon on juba tehtud. Selle meetodiga saab planaarsel juhul saavutada keerukuse O(n log₁₀n).

Nihkekeha

Nihkekeha (sweephull) meetod on kiire hübriidtehnika kahemõõtmelise Delaunay triangulatsiooni jaoks, mis kasutab radiaalselt levivat nihkekeha (see on loodud järjestikku radiaalselt sorteeritud kahemõõtmelistest punktihulkadest, mille abil saadakse mittekattuv triangulatsioon) koos iteratiivse kolmnurgapöördega. Empiiriline tulemus täpsele integraal-aritmeetilisele algoritmile kulutab aega ligikaudu poole O(keha) jagu ja sellele on saada vabavaralised rakendused programmeerimiskeeltes C++ ja C#.

Kasutusvaldkonnad

Eukleidiline minimaalse ulatusega puu (Euclidean minimum spanning tree – EMST ) punktihulga jaoks on Delaunay triangulatsiooni alamhulk. Tänu viimasele on EMST leidmine arvutuslikult lihtsustatud ja tõhusam.

Maastiku või teiste sarnaste pindade modelleerimisel on Delaunay triangulatsiooni abil võimalik määratud punktidega leida kergesti kasutatav võre pinna manipuleerimiseks, kuna välditakse liiga kitsaid kolmnurki ka saadakse ebaregulaarne võrgustik, mis kujutab reaalseid pindasid paremini.

Delaunay triangulatsiooni abil saab hinnata punktide tihedust, kasutades Delaunay tesselatsiooni väljahindajat (Delaunay Tesselation field estimator).

Tihti kasutatakse Delaunay triangulatsiooni, et konstrueerida võrestikku füüsikaliste simulatsioonide jaoks, nagu näiteks lõplike elementide meetod või lõpliku mahu meetod (finite volume method), kuna Delaunay triangulatsioonil on nurga suurusele piirangud ja välja on töötatud mitu küllalt kiiret arvutuslikud meetodid triangulatsiooni leidmiseks. Võrestiku numbrilise stabiilsuse saavutamiseks kasutatakse näiteks Rupperti algoritmi.