triangulaatioiden

Triangulaatioiden käsite viittaa geometriassa alueen tai pistejoukon jakamiseen kolmioiksi. Tämä jaottelu toteutetaan käyttämällä vierekkäisiä pisteitä yhdistäviä viivoja siten, ettei syntyviä kaavoja tai viivoja ristiä toisiaan. Tämän seurauksena muodostuu joukko harvoin päällekkäisiä kolmioita, jotka kattavat tarkasteltavan tilan.

Polygon triangulation on yleisin muoto triangulaatioista. Annettu yksinkertainen monikulmio, jolla on n kärkeä, voidaan jakaa n-2 kolmioon diagonaaleilla, jotka eivät leikkaa toisiaan. Polygon triangulationia tutkitaan sekä matemaattisena ilmiönä että käytännön sovelluksena muun muassa grafiikassa ja geometriassa. Yleensä monikulmio on mahdollista trianguloida riippumatta sen muodon monimutkaisuudesta.

Erityisiä triangulaatioita käytetään eri tarkoituksiin. Delaunay-triangulaatio on tärkeä erityistapaus, jossa kunkin kolmion ympäryttyhjiö (ympärysympyrä) ei sisällä muita syötteen pisteitä, ja jossa triangulaation reunat pyritään tekemään mahdollisimman suuriksi, mikä yleensä estää kapeita kolmiota. Toisaalta rajoitetut (constrained) triangulaatiot pakottavat tiettyjä diagonaaleja mukaan, jotta annettu rakenne säilyy osana triangulaatiota. Kolmiot- ja triangulaatioita käsittelevät edelleen myös 3D-tilanteet, kuten tetrahedralisaatiot kuutioissa.

Algoritmeja triangulaatioihin on lukuisia. Polygon triangulaatiossa yleinen ear clipping -menetelmä etenee etsimällä korvia (ulomaisia kolmioita, joiden toinen kärki on monikulmion reunalla), poistamalla niitä ja toistaen. Delaunay-triangulaation rakentamiseen käytetään esimerkiksi Bowyer–Watson- tai inkrementaalialgoritmeja. Monimutkaisuus vaihtelee, mutta useimmat käytännön sovellukset painottavat sekä tarkkuutta että suorituskykyä.

Sovelluksia on runsaasti: verkkomäähystys ja elementtimenetelmät, tietokonigrafiikka ja 3D-mallinnus, maantieteelliset tiedotjärjestelmät sekä maaston digitaaliset mallit. Triangulaatioiden avulla voidaan muodostaa tehokkaita, hallittavia verkkoja monimutkaisistakin aineistoista.