Általánosságban elmondható, hogy minden algoritmus egy nagyon egyszerű ötleten alapul, hogy szekvenciálisan adjunk hozzá pontokat egy részben megszerkesztett Delaunay-háromszöglethez. Formailag ez így néz ki.

Adott egy N pontból álló halmaz.

1. Az első három kiindulási pontra építünk egy háromszöget.

2. Az összes többi ponthoz tartozó n ciklusban hajtsa végre a 3-5.

3. A következő n-edik pontot adjuk hozzá a már megszerkesztett háromszögelési struktúrához az alábbiak szerint. Először is a pont lokalizált, azaz. van egy (korábban megszerkesztett) háromszög, amelybe a következő pont esik. Vagy ha a pont nem esik bele a háromszögelésbe, akkor a háromszög határán, a következő ponthoz legközelebb található háromszög található.

4. Ha egy pont egy korábban beillesztett háromszögelési csomópontra esik, akkor az ilyen pontot általában eldobjuk, ellenkező esetben a pont új csomópontként kerül be a háromszögelésbe. Sőt, ha a pont valamelyik élre esik, akkor azt két újra osztják, és az éllel szomszédos mindkét háromszöget szintén két kisebbre osztják. Ha egy pont szigorúan egy háromszög belsejébe esik, akkor három új pontra osztódik. Ha a pont kívül esik a háromszögelésen, akkor egy vagy több háromszög készül.

5. Az újonnan kapott háromszögek helyi ellenőrzése a Delaunay-feltételnek való megfelelés érdekében, és a szükséges rekonstrukciók elvégzése.

Az algoritmus vége.

Az alábbiakban több algoritmus részletes leírása található.

Mohó algoritmus

Az egyik első, aki a következő algoritmust javasolta a háromszögelés felépítéséhez.

Mohó módszer- ez egy olyan módszer, amelyben soha nem vonják vissza azt, amit már megcsináltak. Az algoritmus a következő lépéseket egymás után hajtja végre.

1. Az összes szerkezeti szegmens vége a kezdeti pontok halmazába kerül.

2. Az összes pontpárt összekötő szegmenseket generálunk, a szakaszokat hossz szerint rendezzük.

3. A szerkezeti vonalak összes szakaszát beillesztjük a háromszögelésbe.

4. A háromszögeléshez a szegmenseket szekvenciálisan kell kiválasztani a hosszúság szerint (rövidebbről hosszabbra) rendezett szegmenskészletből. Ha egy szakasz metszi a már beszúrt szegmenseket, akkor eldobjuk, ellenkező esetben bekerül a háromszögelésbe.

A 4. lépést addig ismételjük, amíg a szegmensek el nem fogynak.

Vegye figyelembe, hogy ha minden lehetséges szegmens különböző hosszúságú, akkor ennek az algoritmusnak az eredménye egyértelmű, ellenkező esetben az azonos hosszúságú szegmensek beillesztési sorrendjétől függ.

A háromszögelést mohónak nevezzük, ha mohó algoritmussal szerkesztik meg.

"Törlés és felépítés" algoritmus

Az Remove and Build nem hajt végre újraépítést. Ehelyett egy új csomópont (a) minden beillesztésekor azonnal törlődik minden olyan háromszög, amelyben az új csomópont (b) a körülírt körökön belülre esik. Ebben az esetben az összes eltávolított háromszög implicit módon sokszöget alkot. Ezt követően az eltávolított háromszögek helyére kitöltő háromszögletet készítünk úgy, hogy ehhez a sokszöghez új csomópontot kapcsolunk (c. ábra).

Rizs. 4. "Törlés és felépítés" algoritmus

Ez az algoritmus az összes szükséges háromszöget egyszerre építi fel, ellentétben a szokásos iteratív algoritmussal, ahol egy csomópont beillesztésekor ugyanannak a háromszögnek több rekonstrukciója is lehetséges. Itt azonban egy távoli sokszög kontúrjának kinyerésére szolgáló eljárás kerül előtérbe, amelynek hatékonyságától függ az algoritmus teljes sebessége. Általában a használt adatszerkezettől függően ez az algoritmus kevesebb időt tölthet, mint egy újraépítéssel rendelkező algoritmus, és fordítva.

Algoritmus "Build by breaking"

A szerkezeti szegmensek beillesztésére szolgáló „Build by Breaking” algoritmus a legegyszerűbb megvalósítani és a legstabilabb működésben.

Ebben a beillesztett szegmens mentén a háromszögek mentén egymás után haladva meg kell találni a háromszögelési élekkel való metszéspontjait. Ezeken a metszéspontokon új háromszögelési csomópontokat kell elhelyezni, a meglévő éleket és háromszögeket részekre bontani. Ezt követően minden újonnan épített háromszögnél ellenőrizni kell a Delaunay állapotot, és szükség esetén újra kell építeni anélkül, hogy a rögzített éleket érintené.

Rizs. 5. Algoritmus "Build by breaking"

Egyes esetekben ennek a beillesztési algoritmusnak a hátránya lehet, hogy nagyszámú további csomópontot és háromszögelési élt hoz létre. Ugyanakkor más esetekben ez a hátrány előnyt jelent, megakadályozva a hosszú, keskeny háromszögek kialakulását, ami különösen a terepmodellezés során értékelhető.

Ennek a beillesztési algoritmusnak egy másik előnye a későbbiekhez képest akkor jelenik meg, amikor olyan szerkezeti szegmenst próbálunk beilleszteni egy háromszögelésbe, amelyben az általa metszett élek között rögzített élek vannak. Az ilyen bordákat, mint az összes többit, egyszerűen két részre osztják.

Algoritmus a háromszög középpontjainak k-D fával való indexelésével

A háromszögközéppontok k-D-fával való indexelésével járó háromszögelési algoritmusban csak a háromszögek középpontjai kerülnek a k-D-fába (k = 2-vel). A régi háromszögek törlésekor el kell távolítani a k-D-fából a középpontjukat, újak készítésekor pedig hozzá kell adni.

A háromszögelésbe beszúrt aktuális pontot tartalmazó háromszög kereséséhez egy nem szabványos pontlekérdezést kell végrehajtani a k-D fán. A fán való keresésnek a gyökértől kell kezdődnie, és le kell mennie a levelekre. Ha az aktuális k-D-fa csomópont leszármazottai (a leszármazottakat körülvevő téglalap) nem fedik le az aktuális pontot, akkor a fa mentén a további leereszkedéshez ki kell választani a keresési ponthoz legközelebb eső leszármazottat.

Ennek eredményeként egy háromszöget találunk, amelynek középpontja közel lesz az adott ponthoz. Ha a talált háromszög nem tartalmaz adott pontot, akkor az egyszerű iteratív algoritmusból a szokásos háromszögkereső algoritmust kell használni a Delaunay-háromszögelés megalkotásához.

A megszerkesztett háromszögelés minőségének kvantitatív értékeléséhez kétféle kritériumot határozunk meg: topológiai és geometriai kritériumokat.

A topológiai kritérium egy halmazból származó pont legközelebbi szomszédjain alapul. Ideális esetben egy pontnak 6 szomszédja van egy kétdimenziós régióhoz, és 12 szomszédja egy háromdimenziós régióhoz. Topológiai becslést kapunk az (1) képlet segítségével, ahol a terület összes pontjának száma, a belső ponttal összekötött szomszédos pontok foka vagy száma.

A geometriai kritérium a tervezési háromszög alakú elem körüli beírt és körülírt körök közötti különbségen alapul. Geometriai becslést kapunk a (2) képlet segítségével, ahol a háromszögek száma, a beírt kör sugara, a körülírt kör sugara.

Algoritmusok háromszögelés felépítéséhez

A háromszögelés felépítésére számos algoritmus létezik. Eltérnek egymástól a munkaintenzitásban, a számítógépen történő végrehajtás összetettségében és az építési megközelítésben. További információ az algoritmusokról A.V. könyvében található. Skvorcova. Nézzünk néhány algoritmust.

Az elsők között javasolták mohó algoritmus háromszögelés építése. A Delaunay-háromszögelést mohónak nevezzük, ha mohó algoritmussal szerkesztik meg. A mohó algoritmus bonyolultsága néhány fejlesztésével együtt . Az ilyen nagy munkaintenzitás miatt a gyakorlatban szinte soha nem használják. Nézzük meg lépésről lépésre az algoritmust:

1. lépés. A rendszer létrehozza a forráspontpárokat összekötő összes lehetséges szegmens listáját, és szegmenshosszak szerint rendezi.

2. lépés. A legrövidebbtől kezdve a szegmenseket egymás után illesztjük be a háromszögelésbe. Ha egy szegmens nem metszi egymást más korábban beillesztett szegmensekkel, akkor beszúrásra kerül, ellenkező esetben eldobásra kerül.

Vegye figyelembe, hogy ha minden lehetséges szegmens különböző hosszúságú, akkor ennek az algoritmusnak az eredménye egyértelmű, ellenkező esetben az azonos hosszúságú szegmensek beillesztési sorrendjétől függ.

Iteratív algoritmus Egy nagyon egyszerű ötleten alapulnak, hogy egymás után adjunk hozzá pontokat egy részben megszerkesztett Delaunay-háromszöglethez. Ennek az algoritmusnak a bonyolultsága egy olyan háromszög keresésének bonyolultságából áll, amelyhez a következő lépésben egy pontot adunk, az új háromszögek létrehozásának összetettségéből, valamint a háromszögelési struktúra megfelelő rekonstrukcióinak összetettségéből a nem kielégítő eredmény miatt. az eredményül kapott háromszögelés szomszédos háromszögpárjainak ellenőrzése a Delaunay-feltétel teljesüléséhez. Nézzük meg lépésről lépésre az algoritmust:

1. lépés. Az első három kiindulási pontra építünk egy háromszöget.

2. lépés. Az összes többi pontra vonatkozó ciklusban a 3-5.

3. lépés A következő i-edik pont hozzáadódik a már megszerkesztett háromszögelési struktúrához az alábbiak szerint. Először is a pont lokalizált, azaz. van egy (korábban megszerkesztett) háromszög, amelybe a következő pont esik. Vagy ha a pont nem esik bele a háromszögelésbe, akkor a háromszög határán, a következő ponthoz legközelebb található háromszög található.

4. lépés. Ha egy pont egy korábban beillesztett háromszögelési csomópontra esik, akkor az ilyen pontot általában eldobjuk, ellenkező esetben a pont új csomópontként kerül be a háromszögelésbe. Sőt, ha a pont valamelyik élre esik, akkor azt két újra osztják, és az éllel szomszédos mindkét háromszöget szintén két kisebbre osztják. Ha a pont szigorúan egy háromszög belsejébe esik, akkor három újra oszlik. Ha a pont kívül esik a háromszögelésen, akkor egy vagy több háromszög készül.

5. lépés. Az újonnan kapott háromszögek helyi ellenőrzése a Delaunay-feltételnek való megfelelés érdekében, és elvégzik a szükséges rekonstrukciókat.

Új háromszögek készítésekor két helyzet lehetséges: a hozzáadott pont vagy a háromszögelésen belülre, vagy azon kívülre esik. Az első esetben új háromszögeket szerkesztenek, és rögzítik az algoritmus által végrehajtott műveletek számát. A másodikban további háromszögeket kell létrehozni az aktuális háromszögelésen kívül, és számuk a legrosszabb esetben egyenlő lehet? 3. Az algoritmus minden lépése során azonban nem adunk több háromszöget, ahol a kezdőpontok teljes száma. Ezért mindkét esetben a háromszögek felépítésére fordított teljes idő az.

Lánc algoritmus az egyik első hatékony háromszögelési algoritmus egy síkgráf szabályosságának és monoton sokszögek háromszögelésének eljárásán alapul. Ennek az algoritmusnak az összetettsége, hogy hol van a kezdeti szegmensek száma. Nézzük meg lépésről lépésre az algoritmust:

1. lépés. A kezdeti szerkezeti szegmensek halmazából összefüggő síkgráfot alkotunk (4. ábra, a).

2. lépés. A gráf szabályosított, azaz. új élek kerülnek hozzáadásra, amelyek nem metszenek másokat, így a gráf minden csúcsa szomszédos lesz legalább egy felette és egy alatta lévő csúcsgal. A rendszerezés két menetben történik, függőleges lapos sepréssel. Az első lépésben alulról felfelé az összes csúcsot egymás után megtaláljuk, ahonnan nem emelkednek ki felfelé vezető élek. Például (4. ábra, b) ez a B csúcs. Vízszintes vonal húzásával megtaláljuk az AD és EF gráf legközelebbi éleit, amelyeket bal és jobb oldalon metszi. Ekkor a DEHG négyszögben megtaláljuk a legalsó csúcsot, és húzunk bele egy élt B-ből. Hasonló módon hajtjuk végre a második lépést felülről lefelé (4.c ábra). E lépés eredményeként a síkgráf minden egyes tartománya monoton sokszöggé válik.

3. lépés A grafikon minden régióját háromszögekre kell osztani. Ehhez használhatja a két háromszögelés nem konvex egyesítésére szolgáló algoritmust (4. ábra, d).

4. ábra A láncháromszögelési algoritmus működési vázlata: a) - kezdeti szakaszok; b - a gráfszabályozás alulról felfelé haladása; c) - átjárás fentről lefelé; d) - monoton sokszögek háromszögelése

Láncolt algoritmus megvalósításához a legjobb olyan adatstruktúrákat használni, amelyekben az élek kifejezetten vannak ábrázolva, például „Dupla élek” vagy „Csomópontok, élek és háromszögek”.

A láncalgoritmus hátránya, hogy semmit nem lehet előre megmondani a kapott háromszögelés formájáról. Ez nem optimális háromszögelés, nem mohó és nem korlátozott Delaunay-háromszögelés. A láncalgoritmus nagyon hosszú megnyúlt háromszögeket tud előállítani.

Az eredményül kapott háromszögelés minőségének javítása érdekében ellenőrizheti az összes szomszédos háromszögpárt, amelyeket nem választ el szerkezeti él a Delaunay-feltételhez, és szükség esetén rekonstrukciókat végezhet. Az eredmény egy Delaunay-háromszögelés lesz, korlátozásokkal.

A háromszögelés egy modellezett objektum felületének közelítése a tőle bizonyos meghatározott értéket meg nem haladó távolságra elhelyezett háromszög alakú lemezekkel 6. Minden háromszög alakú lemezt össze kell kapcsolni. Tetejük a felszínen fekszik. Egy háromszög alakú lemezkészlettel könnyebb dolgozni, mint egy általános felülettel. A háromszög alakú lemezeket háromszögeknek nevezzük. Háromszög esetén gyorsan kiszámítható egy adott pont távolsága vagy egy adott térbeli metszéspont. Az arcok háromszögelése a geometriai modell vizuális észlelése érdekében történik, így a háromszögek oldalai úgy vannak kiválasztva, hogy a szem ne vegye észre a töréseket.

Amikor geometriai objektumokat háromszögekkel jelenítünk meg a felületek parametrikus síkjain, a test lapjainak térbeli háromszögezését úgy kell megszerkeszteni, hogy kiszámítjuk a térben lévő pontok tömbjét és a test lapjaira vonatkozó normálok tömbjét ezeken a pontokon egy tömb segítségével. kétdimenziós pontok A testek gyors megjelenítéséhez a felületüket háromszög alakú lemezekkel közelítik meg, amelyek a test lapjaival kölcsönhatásba lépő fénysugarak viselkedését határozzák meg. Az előző fejezetekben és ebben a fejezetben a hangszínrajzok háromszögelés segítségével készültek.

A felületi háromszögelés eredményeképpen egy paraméteres síkon egy kétdimenziós pontokból álló tömböt és egy egész számokból álló hármastömböt szeretnénk elérni, amelyek az elsőként említett tömb pontjainak számai. Így minden háromszöget három csúcsszám képvisel a paramétertömbben. A parametrikus tartomány minden kétdimenziós pontjára számítható a felületen egy térbeli pont és a benne lévő felületnormál. A térbeli pontok és normálok a 2D ponttömbhöz hasonló tömbökben tárolhatók.

Nézzünk meg néhány háromszögelési módszert. Sík felületekre vannak olyan költséghatékony háromszögelési eljárások, amelyeknél a háromszögeket a felület határpontjaiban építik fel, és nincs szükség a paraméteres tartományon belüli pontok keresésére.

Delaunay háromszögelés.

Nézzünk néhány területet a gépen. Konvexnek nevezünk egy területet, ha a határa mentén haladva csak egy irányba kell fordulni (csak balra vagy csak jobbra). A Delaunay algoritmus használható konvex síkrégiók háromszögelésére. Ezt az algoritmust közvetlenül nem tudjuk majd szabad formájú felületek háromszögelésére alkalmazni, de háromszögek készítésére fogjuk használni a módszerét.

Rizs. 9.7.1. Konvex régió adott pontokkal belül

Adjunk meg egy zárt szaggatott vonallal határolt konvex kétdimenziós tartományt és ezen belül egy ponthalmazt (9.7.1. ábra).

A megadott területet háromszögekre kell felosztani, amelyek csúcsai a területen belüli adott pontok és az azt határoló szaggatott vonal csúcsai. A háromszögek nem fedhetik át egymást, és oldalaik csak a csúcsokban metszhetik egymást.

Egy meghatározott terület kitöltésére több különböző háromszöghalmaz is létrehozható. A háromszögek száma minden esetben egyenlő -vel, ahol K a határoló vonallánc csúcsainak száma, I a területen belüli adott pontok száma.

Rizs. 9.7.2. A Delaunay-algoritmus harmadik pontjának kiválasztása

Egy régió háromszögelése Delaunay-háromszögelés lesz, ha az egyes háromszögek körül leírt körön belül nincsenek más háromszögek csúcsai. A Delaunay-háromszögelés olyan háromszögeket épít fel, amelyek a lehető legközelebb vannak az egyenlőszögekhez (nem teszi lehetővé az indokolatlanul megnyúlt háromszögek felépítését).

Kiegyensúlyozottnak nevezhető. A Delaunay-háromszögelés akkor lesz egyedi, ha nincs négy csúcs ugyanazon a körön.

Nézzük a Delaunay-háromszögelést. A régiót határoló vonallánc csúcsait és a régión belüli adott pontokat a háromszögelés csúcsainak nevezzük. A háromszögek oldalait éleknek nevezzük. Az élek közül kijelöljük a határoló vonallánc szegmenseit, amelyeket határéleknek nevezünk. Orientáljuk az összes határélt úgy, hogy a konvex tartomány minden éltől balra legyen. Legyen szükség egy háromszög megszerkesztésére, amelynek oldala az AB határél, az ábrán látható. 9.7.2.

Az A, B csúcsokon és minden olyan csúcson keresztül, amely nem esik egy egyenesen velük, kör rajzolható. A háromszög harmadik csúcsaként a V csúcsot választjuk, a megfelelő kör nem tartalmaz más csúcsokat az AB szakaszhoz képest, amelyen a V pont található Határélre általános esetben egy ilyen csúcs lehet találhatók. Nevezzük a legközelebbinek. Az A, B és V pontokon átmenő kör középpontja az AB, BV és VA szakaszok felezőpontjaira vonatkozó merőlegesek metszéspontjában található. A kör középpontjának helyzetét az AB élre merőleges, egyenlő hosszúságú és az AB él közepén átmenő MN szakasz t paramétere fogja jellemezni.

Rizs. 9.7.3. Delaunay háromszögelési folyamat

Az AB szakasztól balra fekvő összes csúcs esetén a legközelebbi csúcsnak van a legkisebb t paramétere. A legközelebbi csúcsnak megfelelő kör nem tartalmaz további csúcsokat az AB szakasztól balra. Leírjuk az A, B és V csúcsokat kétdimenziós sugárvektorokkal. Az AB és BV szakaszok felezőpontjainak sugárvektorai egyenlőek lesznek

Az egyenes t paraméterének értéke, amely megfelel az A, B és V pontokon átmenő kör középpontjának rajta lévő pozíciójának, egyenlő

Az AB szakasz bal oldalához legközelebb eső csúcsnál a t paraméternek van egy minimális értéke.

Állítsuk be az összes határélt úgy, hogy a háromszögezendő terület mindegyiktől balra legyen. A háromszögek felépítését bármely határéltől kezdjük. Keressük meg neki a legközelebbi csúcsot, amelynek megfelelő köre nem tartalmaz más csúcsot. Keressük meg a legközelebbi V csúcsot az AB határélhez. Ezután megszerkesztjük az ABV háromszöget, és az AB élt átvisszük az inaktív kategóriába. Meghívjuk azokat az inaktív éleket és csúcsokat, amelyek nem vesznek részt a háromszögelési algoritmusban. Ha a határélek között nincs BV él, akkor a VB szakaszon új határélt építünk. Ha a határélek között van BV él, akkor azt és a B csúcsot átvisszük az inaktív kategóriába. Ha nincs VA él a határélek között, akkor az AV szakaszon új határélt építünk. Ha a határélek között van VA él, akkor azt és az A csúcsot átvisszük az inaktív kategóriába. A háromszögelési folyamat az ábrán látható. 9.7.3.

Rizs. 9.7.4. Delaunay háromszögelés

A háromszögelést akkor fejezzük be, amikor minden csúcs és él inaktívvá válik. Egy adott terület háromszögelésének eredményét az ábra mutatja. 9.7.4.

Háromszögelés korrekciós módszerrel.

Nézzük meg egy adott felület háromszögletét a paraméterek meghatározásához. Osszuk fel a felületi paraméterek meghatározására szolgáló tartományt kétdimenziós vonalakkal ellátott négyszögletes cellákra. Vegyük egyenlőnek a szomszédos egyenesek közötti paraméteres távolságokat a (9.4.7) képlet szerint

Vegyük egyenlőnek a szomszédos egyenesek közötti paraméteres távolságokat a (9.4.8) képlet szerint

Ha minden téglalap alakú cellában átlót építünk, akkor a felület háromszögezését kapjuk (a követelményeknek megfelelő háromszöghalmazt kapunk). ábrán. A 9.7.5 a forgásfelület háromszögelését mutatja be a leírt módszerrel.

Tekintsük egy tetszőleges határú felület háromszögezését. A háromszögelési módszert a fent leírt felületi háromszögelés határkontúrokkal történő korrekciójára építjük fel, a paraméterek meghatározására szolgáló téglalap alakú területtel.

Rizs. 9.7.5. Téglalap tartományú felület háromszögelése paraméterek meghatározásához

Leírjuk a felület határát a paraméterdefiníciós tartományban több nem metsző kétdimenziós kontúrral (2.12.7). Az egyik kontúr külső, és tartalmazza a többi kontúrt. Az egyes kontúrok pozitív irányához azt az irányt vesszük, amely mentén haladva a felületdefiníciós terület mindig a kontúrtól balra van, ha a felületnormál felé nézünk. Szerkesszünk sokszögeket a felületdefiníciós terület határkontúrjainak pozitív irányban. Határpoligonok készítéséhez valamilyen változó lépéssel végig kell haladni a felület határvonalain, és ki kell tölteni egy kétdimenziós pontokból álló tömböt, amelyek koordinátái a felületi paraméterek. Egy parametrikus síkon lévő pontokból fogunk sokszöget építeni, de az egyik pontból a másikba való mozgás lépését a térgeometria határozza meg, mégpedig abból a feltételből, hogy a szomszédos pontok közötti görbe ív elhajlása nem nagyobb, mint egy adott érték. A (9.4.4) képlet segítségével kiszámítjuk a felületi határvonal kontúrgörbéjének sokszög felépítéséhez szükséges paraméteres lépéseket.

Minden sokszög kétdimenziós pontok rendezett halmazából áll. A sokszög minden szakasza kétdimenziós egyenes szakasznak tekinthető, amely két szomszédos pontra épül. Az ilyen területeket határélként fogjuk használni, és a sokszögek pontjait, amelyeken az élek alapulnak, háromszögelési csúcsként fogjuk használni. Mivel a felületi paraméterek meghatározására szolgáló terület a határoló sokszögek bal oldalán található, az egyes határháromszögelési élekhez háromszögek készítésekor az éltől balra lévő háromszög harmadik csúcsát kell keresni.

Határozzuk meg, hogy mely csomópontok fekszenek a határpoligonokon belül, és melyek a határokon vagy a felületdefiníciós területen kívül. Ezen információk felhasználásával két csoportba rendezzük a téglalap alakú rácscellákat. Az első csoportba azok a cellák tartoznak, amelyek teljes egészében azon a területen belül helyezkednek el, ahol a felületi paramétereket meghatározzák (a cellák nem érinthetik a határpoligonokat). A második csoportba tartoznak a fennmaradó cellák (amelyek a felületdefiníciós területen kívül helyezkednek el, vagy határoló sokszögekkel metszik őket).

Rizs. 9.7.6. Befejezetlen felületi háromszögelés

Az első csoport minden celláján belül egy átló segítségével két háromszöget készítünk. Így egy befejezetlen háromszögelést kapunk. Az ábrán látható egy példa háromszögek megalkotására az első csoport celláiban a körvonalakkal határolt forgásfelülethez. 9.7.6.

A második csoport celláinak nem metszett oldalain határéleket készítünk, és úgy irányítjuk őket, hogy a megfelelő cella az éltől balra legyen. Az első csoport cellái köré zárt szaggatott vonalat (esetleg több zárt vonalat) építünk úgy, hogy ezen haladva a terület háromszögekre nem tagolt része a felületnormál felé nézve bal oldalon legyen. Ennek a szaggatott vonalnak az egyenes szakaszait is fogjuk határélként használni. Minden élt egyenlőnek fogunk tekinteni. A háromszögelés befejezéséhez háromszögeket kell alkotnunk a határélek között. Minden élhez keresünk egy csúcsot, amely attól balra fekszik, és felhasználható háromszög megszerkesztésére. Csúcsot csak azon csúcsok között fogunk keresni, amelyek az éllel egy cellában vannak. A csúcs kiválasztásához a fent leírt Delaunay-módszert használjuk, amelyet az ábra szemléltet. 9.7.2. Ha találunk ilyen csúcsot, akkor ellenőrizni kell, hogy a háromszög két új éle metszi-e valamelyik határélt. Keressük meg az AB határélhez a legközelebbi V csúcsot, és ellenőrizzük, hogy a BV és VA szakaszok nem metszenek-e más határéleket. Ezután megszerkesztjük az ABV háromszöget, és átvisszük az AB élt az inaktív kategóriába. Ha a határélek között nincs BV él, akkor a VB szakaszon új határélt építünk, ha viszont van BV él a határélek között, akkor azt és a B csúcsot átvisszük az inaktív kategóriába. Ha a határélek között nincs VA él, akkor az AV szakaszon új határélt építünk, ha viszont van VA él a határélek között, akkor azt és az A csúcsot átvisszük az inaktívak kategóriájába.

Ha egy szakasz vagy VA más határéleket metsz, akkor keressük meg a legközelebbi csúcsot egy másik határélhez. A háromszögelés azután fejeződik be, hogy minden él és csúcs inaktívként lett besorolva.

Rizs. 9.7.7. Háromszögelés korrekciós módszerrel

ábrán. A 9.7.7 a felületi háromszögelést mutatja a háromszögek korrekciós módszerével határkontúrokkal metszett cellákban. ábrán. 9.7.8, a kapott háromszögelés segítségével maga a felület jelenik meg.

Ha a határoló sokszögek és a felület valamilyen szimmetriával rendelkeznek, akkor a korrekciós módszerrel végzett háromszögelés is hasonló szimmetriával rendelkezik.

Háromszögelés abszorpciós módszerrel.

Nézzünk egy másik háromszögelési módszert. Sebesség szempontjából alulmúlja a Delaunay-háromszögelést és annak módosításait. A háromszögelési eljárás megkezdéséhez a felület határát zárt sokszögek formájában kell ábrázolni. A háromszögelési folyamat során a felületi paraméterek alapján kell meghatároznunk a lépéseket. Ismert mozgási irány mellett ezeket a lépéseket a (9.4.6) képletek határozzák meg. A felületi paraméterek hozzávetőleges lépései az alábbiak szerint találhatók. Adjunk meg egy régiót a paramétersíkon egy bizonyos pont körül úgy, hogy ebben a tartományban bármely ponttól pontig terjedő térbeli szegmens ne legyen távolabb egy adott S értéknél a felülettől.

Ehhez kiszámítjuk a paraméterek megengedett növekményét a koordinátavonalak mentén

ahol a felület első és második másodfokú alakjának együtthatói a pontban. A kívánt régió határaként egy ellipszist veszünk, amelynek középpontja egy pontban van és féltengelyei . Ennek az ellipszisnek az egyenlete

Ha egy pontot akarunk találni a síkon egy pont mellett a és tengellyel bezárt szög irányában, akkor a paraméterei

Először vegyünk egy egyszerűbb esetet, amikor a felületi paraméterek területe egy külső kontúrra korlátozódik. A felület határát egy zárt sokszöggel közelítjük a parametrikus tartományon. A háromszögelés megalkotásánál a munkasokszöget használjuk, amelyet ebben az esetben a külső kontúr sokszögének veszünk. A sokszögpontokat hozzáadjuk a kapott kétdimenziós ponttömbhöz. A munkaterület szélétől háromszögeket építünk, szűkítve addig, amíg csak három pont marad a munkaterületen.

Keressünk a munkasokszögben egy csúcsot, amelynél befordul a régióba. Ilyen pont mindig létezik, és ennél kisebb a forgásszög. Jelöljük ezt a pontot O-val, paramétereit pedig A pont közelében egy vagy két háromszöget készítünk, a forgásszögtől függően. Ha a szög kisebb, akkor erre a három pontra építünk egy háromszöget (9.7.9. ábra). Ellenkező esetben két háromszöget építünk erre, két szomszédos és egy új pontot (9.7.11. ábra). Az új pontot P jelöli. A P pontot a B OS P paralelogramma átlóján keressük. Ha a paralelogramma csúcsa az ellipszis belsejében van (9.7.10. ábra), akkor P pontnak vesszük. Ellenkező esetben az ellipszis és a paralelogramma átlójának metszéspontját vesszük P pontnak. Ez utóbbi esetben egyáltalán nem szükséges az ellipszis és a szakasz metszéspontját keresni.

A P pont koordinátáit az O BC pontok koordinátái határozzák meg

Az OP szakasz vízszintessel bezárt szögét az egyenlőség határozza meg

(9.7.8)

Ezek az adatok lehetővé teszik a P pont ellipszishez viszonyított helyzetének meghatározását (9.7.5).

ábrán látható esetben. 9.7.9, készítsünk egy háromszöget (emlékezzünk a csúcsainak számaira) és töröljük az O pontot a munkaterületen. 9.7.11, megszerkesztünk két háromszöget, és a munkaterületen az O pontot helyettesítjük P ponttal, és az utóbbit elhelyezzük a kapott ponttömbben. ábrán. A 9.7.12. ábra azt a sokszöget mutatja, amelyet két háromszög felépítése és az O pont kiiktatása után kapunk. Mindkét esetben az O pontot eltávolítjuk a munkasokszögből, és a munkasokszög szűkül. Vegye figyelembe, hogy háromszögeket csak akkor lehet létrehozni, ha a munkaterület szűkítés után nem metszi önmagát.

Rizs. 9.7.9. Háromszög építése

Rizs. 9.7.10. Eredmény sokszög

Rizs. 9.7.11. Két háromszög felépítése

Rizs. 9.7.12. Eredmény sokszög

Az ilyen helyzeteket az ábra mutatja. 9.7.13. Akkor fordulhatnak elő, ha a megszerkesztett háromszögek oldalai metszik a munkaterület azon oldalait, amelyek nem szomszédosak. Mielőtt új háromszöget készítesz, mint az ábrán látható esetben. 9.7.9. ábrán látható esetben. 9.7.11, ellenőrizni kell, hogy a kapott sokszög nem metszi-e önmagát.

Ezenkívül a P pont helyzetének meghatározásakor fontos, hogy az kellő távolságra legyen a munkaterület többi pontjától, és ne kerüljön közel a terület pontjait összekötő szakaszokhoz. Ellenkező esetben a jövőben nehézségek merülhetnek fel a háromszögek építése során. Ezért, mielőtt szűkítené a munkasokszöget, ellenőrizze, hogy az eredményül kapott sokszög nem metszi-e egymást. Ha az O pont közelében lehetetlen háromszöget (háromszögeket) szerkeszteni, akkor ehelyett keressen egy másik pontot, ahol a sokszög jobban beburkol a kontúron, mint a többinél, és végezze el a leírt műveleteket.

Ezután a módosított munkaterülettel ugyanazokat a műveleteket hajtjuk végre, amelyeket az imént leírtunk. Keressünk a munkasokszögben egy olyan pontot, amelynél jobban megfordul a területen belül, mint más pontokon, ellenőrizzük, hogy van-e lehetőség a sokszög szűkítésére egy vagy két háromszög megszerkesztésével, és szűkítsük a sokszöget.

Rizs. 9.7.13. Ebben a sarokban nem építhet háromszöget.

Ezt a folyamatot folytatva kibővítjük a kétdimenziós pontok tömbjét és a háromszögek tömbjét, ugyanakkor szűkítjük a munkasokszöget, csökkentve az általa lefedett területet és pontjainak számát. Ezen műveletek bizonyos szakaszában egy három pontból álló működő sokszöget kapunk. Építsük meg ezeken a pontokon az utolsó háromszöget, távolítsuk el a munkaterületet és fejezzük be a háromszögelést. A leírt háromszögelési módszernél a munkaterület által határolt területet mintegy kiküszöböljük úgy, hogy háromszögeket vágunk le belőle.

Tekintsük azt az általános esetet, amikor a felületi paraméterek területét egy külső kontúr és több belső kontúr korlátozza, amelyek teljes mértékben a külső kontúron belül vannak. A felület határát a paraméteres tartomány zárt sokszögeivel közelítjük. Minden kontúrhoz megépítjük a saját sokszögünket. Csakúgy, mint a kontúrok esetében, a rájuk épített sokszögeknél is teljesülni kell a kölcsönös tájékozódási szabálynak. A belső sokszögek tájolásának ellentétesnek kell lennie a külső sokszög tájolásával. A háromszögelést a külső kontúrsokszöggel kezdjük. Helyezzük a pontjait a kétdimenziós pontokból álló tömbbe, és magát a sokszöget tegyük működővé.

A háromszögeket ugyanúgy fogjuk megszerkeszteni, mint egy egyszerűen összefüggő régió esetében. Keressük meg a munkaterületen az O pontot, ott ellenőrizzük a munkaterület szűkítésének lehetőségét, és szűkítsük a területet. Ha vannak belső kontúrok, nehezebb lesz ellenőrizni a munkaterület szűkítésének lehetőségét egy kiválasztott ponton. A háromszögek oldalainak a munkaterület oldalaival való metszéspontjának leírt ellenőrzésein kívül ellenőrizni kell a háromszögek oldalainak metszéspontját az összes belső sokszög oldalával.

Vizsgáljuk meg két háromszög felépítésének lehetőségét az O pontban (9.7.11. ábra), és állapítsuk meg, hogy az új P pont, miután megszerkesztettük, az egyik belső sokszög belsejébe esik, vagy elfogadhatatlan közelségbe kerül a szakaszaihoz. Ebben az esetben nem a P pontot fogjuk megszerkeszteni, hanem ezt a belső sokszöget belefoglaljuk a munkasokszögbe az 1. ábrán látható két háromszög megszerkesztésével. 9.7.14.

Ahhoz, hogy az egyik belső sokszög pontjait belefoglaljuk a munkasokszögbe, a belső sokszög pontjai között megtaláljuk a munkasokszög C pontjához legközelebb eső pontot (az O ponttal szomszédos).

Szerkesszünk háromszögeket az OCF és CEF pontokban, valamint a munkaterület O és C pontjai között, illesszük be a belső sokszög pontjait, kezdve az F ponttal és az E ponttal végződve. Így az OS szakaszon megtörjük a munkaterületet, megtörjük a belső sokszög az EF szakaszon, és egyesítse őket az OF és az EU szakaszokkal.

Rizs. 9.7.14. Két háromszög felépítése

Rizs. 9.7.15. Külső és belső sokszögek összevonása

Az összevonás eredménye a ábrán látható. 9.7.15. Természetesen a külső és a belső sokszög összevonása előtt ellenőrizni kell ennek a műveletnek a helyességét.

Ezután a leírt módon tovább szűkítjük a munkaterületet, amíg egy másik belső terület közvetlen közelében nem találjuk magunkat, és be nem vonjuk a munkaterületbe. Ennek eredményeként az összes belső sokszög belekerül a munkapoligonba, amelyet az utolsó három pontra kell szűkíteni. Ennek eredményeként a felületi paraméterek meghatározására szolgáló teljes többszörösen összefüggő területet háromszögek borítják.

Rizs. 9.7.16. Ebben a sarokban nem építhet háromszöget.

Előfordulhatnak olyan helyzetek, amikor lehetetlen egyetlen háromszöget felépíteni az adott sokszögekre. ábrán. A 9.7.16. ábra egy két sokszöggel határolt területet mutat be, amelyek mindegyike négy szegmensből áll. A külső sokszög esetében nem folytathatjuk a háromszögelést, mert a belső sokszög útban van. Ebben az esetben a sokszög két szomszédos B és C pontját találjuk, amelyekre HRV háromszöget szerkeszthetünk. A P pont a BC oldal közepére vetül, és attól olyan távolságra van, hogy az új háromszög ne metszi a sokszögeket.

A háromszögelés egyéb módszerei.

A háromszögelésnek más módjai is vannak. Például a felületdefiníciós terület külső és belső kontúrjainak sokszögeinek megszerkesztése után más stratégia is választható a háromszögek megalkotásához. Egy másik lehetőség, hogy a külső és a belső sokszöget egy sokszögbe egyesítjük a háromszögelés megkezdése előtt. A paraméterdefiníciós területen belül egy bizonyos algoritmussal pontokat „vázolhat”, és Delaunay-háromszögelést hajthat végre ezek és a határkontúr sokszögek pontjai alapján. Vannak olyan algoritmusok, amelyek először nagy háromszögeket készítenek, majd felosztják kezelhető méretekre.

A test háromszögelése.

Egy test háromszögelése olyan háromszögek halmaza, amelyeket a test lapjainak háromszögelésével kapunk. Az egyes felületek háromszögelése abban különbözik a testlapok háromszögelésétől, hogy az utóbbi esetben a szomszédos felületek határpoligonjainak konzisztensnek kell lenniük (9.7.17. ábra).

Rizs. 9.7.17. Body Face Határ sokszög konzisztencia

A szomszédos lapok sokszögeinek metszetei, amelyek közös élek mentén haladnak el, akkor konzisztensek, ha pontjaik egybeesnek a térben.

A háromszögelés alkalmazása.

A háromszögelés eredményeként megszerkesztett háromszögek tónusképek készítésére szolgálnak. ábrán. A 9.7.18. és 9.7.19. ábra egy laptest homloklapjának háromszögeléseit mutatja, amelynek tónusképe a 2. ábrán látható. 6.5.1.

Rizs. 9.7.18. Testarc háromszögelése korrekciós módszerrel

A felületi paraméterek meghatározásának tartományának háromszögekre történő felosztása a (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) integrálokban használható testek geometriai jellemzőinek számításakor. . A numerikus integráció során a görbék paraméteres lépését a (8.11.5) képlet segítségével, a felületeknél a paraméteres lépéseket a (8.11.1) és (8.11.2) képletekkel kell kiszámítani.

A GRID modellek szabályos cellák modelljei.

Vezessük be a koordinátarendszert
És És
. Felhasználói készletek
és mintavételi lépések
.

,

- a pont fizikai koordinátái.

Kiszámoljuk
És
,
- bitrács.

- kvantált értékek. Igazi:

- algoritmus paraméter - pontok száma, - súly. Minél közelebb van a pont, annál nagyobb a súly.

- a távolság mértéke (1 vagy 2).

Normalizációs tényező:

Hogyan közelebb az 1-hez, annál több nagyobb súllyal bíró pontot vesz figyelembe.

Ez az IDW módszer - hosszú, minden t-hez meg kell találni a szomszédokat. A szomszédok halmaza hatékonyan megtalálható - a legközelebbi. Minden pont egy bizonyos magasságú „csapot” hoz létre. Sok múlik a pont meghatározásának szabálytalanságán;
vagy
azok. szektorokra és építési pontokra osztva a közelben.

Előny– egyszerűség

Hiba:

------Jegy 14. Ónmodell. Delaunay háromszögelési algoritmusok ------

1) Háromszögelés (ón).

Háromszögelés– függvény felépítése darabonkénti lineáris függvények halmaza formájában

Háromszögelés– interpoláció konvex tartományon belül.

Háromszögelés– síkgráf, amelynek minden belső éle háromszög; a tér ábrázolásának módja egymás melletti háromszögek formájában, átfedés nélkül. A háromszögelés többféleképpen is ponthalmazra épül.

Az optimális háromszögelés megalkotásához algoritmusra van szükség.

3 ponton áthaladó sík.

1) Keress egy háromszöget
;

2)
- megszerkeszteni a sík egyenletét.

Annak ellenőrzéséhez, hogy a pontok a háromszög belsejében vannak-e vagy sem, be kell cserélnie az értéket a vonalak egyenletébe - a háromszög élei. Ha mind a 3 egyenlet > 0, akkor belül.

Az előadás szerkezete:

Minden háromszögelés ugyanannyi háromszöget tartalmaz.

, Ahol – belső pontok száma,
- a pontok mennyisége.

Mohó háromszögelés.

Összekapcsoljuk az összes pontot élekkel, kiválasztjuk a minimumot, és hozzáadjuk a háromszögeléshez. Ezután vesszük a következő minimumot, amely nem metszi az előzőeket, stb. Az eredmény mohó háromszögelés.

Delaunay háromszögelés.

Egy tetszőleges háromszög köré körülírt kör belseje nem tartalmazza a többi háromszög pontjait. Az egyetlen módon épül fel.

A flip az élek áthelyezése. Lehetővé teszi, hogy a hagyományos háromszögelésről a Delaunay-háromszögelésre váltson. Annak ellenőrzéséhez, hogy egy pont egy körhöz tartozik-e: cserélje ki, ha< R, то внутри.

Delaunay állapot.

Három ponton átmenő kör egyenlete:

Ha kevesebb, mint nulla, akkor külső, egyébként - belső.

– Delaunay állapot.

Algoritmus a Delaunay-háromszögelés elkészítéséhez:

1) Pontok hozzáadása vizsgálat alatt– egy egyszerű iteratív algoritmus:

Van egy készlet
a háromszöghöz hozzáadva az építés megtörténik
háromszög hasítás
újjáépítés. A nulladik szakaszban adunk hozzá 3-4 fiktív pontot, ami nyilvánvalóan lefedi a borítékunkat, az összes benne lévő pontot. Ezután dobjuk a pontot, megnézzük, melyik háromszöget találja el, 3-ra osztjuk, minden háromszögnél ellenőrizzük a Delaunay-feltételt, és végrehajtjuk az élek átfordítását. A sávváltások átlagos száma három.

Elméleti bonyolultság

2) Gyorsítási módszerek. Statisztikailag függő pontok alapján. A magháromszög az a háromszög, amelybe az előző pont esett. Ezután összekötünk két pontot - az előzőt és az újat.

Az első pontból a másikba lépünk.

Küldje el a jó munkát a tudásbázis egyszerű. Használja az alábbi űrlapot

Diákok, végzős hallgatók, fiatal tudósok, akik a tudásbázist tanulmányaikban és munkájukban használják, nagyon hálásak lesznek Önnek.

Közzétéve: http://www.allbest.ru/

TANFOLYAM PROJEKT

ÉPÍTKEZÉSHÁROMSZOLGÁLTATÁSOKDELAUNAIS

Által fegyelem "StruktúrákÉsalgoritmusokfeldolgozásadat"

Tartalom

• Bevezetés
• 2.1 Mohó algoritmus
• 2.4 Algoritmus a háromszög középpontjainak indexelésévelk- D- fa
• 3.4 Ventilátor algoritmus
• 4. Szoftver rész
• Következtetés

Bevezetés

Ma, a 21. század elején az emberiség egy új civilizációba lép be – egy olyan civilizációba, amely a számítógépek behatolásával jár együtt az emberi tevékenység minden szférájába. Ezt a civilizációt információsnak, virtuálisnak, számítógépnek nevezik.

ElméletiInformatika- matematikai tudományág, amely matematikai módszereket használ az információk feldolgozásának, továbbításának és felhasználásának modelljeinek felépítésére és tanulmányozására. Matematikai logikán alapul, és olyan szakaszokat tartalmaz, mint az algoritmusok és automaták elmélete, az információelmélet és a kódolás elmélete, a formális nyelvek és nyelvtanok elmélete, a műveletek kutatása és mások.

Az elméleti számítástechnika egyik területe a számítási geometria , amely algoritmusok és programok segítségével számítógépes geometriai problémák megoldására dolgoz ki módszereket.

Számítástechnikageometria a számítástechnikának a geometriai problémák megoldására szolgáló algoritmusokat tanulmányozó ága. Ilyen problémák találhatók a számítógépes grafikában, az integrált áramkörök tervezésében, a műszaki eszközökben stb. Az ilyen problémák kiindulási adatai lehetnek egy síkon lévő pontok, szegmensek, sokszögek stb. A számítástechnikában meglehetősen gyakran találkozunk geometriai problémákkal, mivel ezek megoldására a számítógép nagyon kényelmes és gyors eszköz, mivel a kézi számítás itt abszolút nem alkalmazható.

CélmunkaÉsfeladatokat: tanulmányozza a Delaunay-háromszögelés elkészítésének egyik iteratív algoritmusát.

1) Tanulmányozza a Delaunay-háromszögelési probléma alapvető definícióit és tételeit;

2) Tekintsük a háromszögelés felépítésére szolgáló iteratív algoritmusok fő típusait;

3) Valósítsa meg a „Delete and Build” algoritmust a Delaunay-háromszögelés elkészítéséhez.

1. A Delaunay-háromszögelés általános leírása

A háromszögelés felépítésének problémája.

Delaunay a számítási geometria egyik alapvető eleme. Számos egyéb probléma is felmerül a számítógépes grafikában és a földrajzi információs rendszerekben felületek modellezésére és térbeli problémák megoldására. A Delaunay-háromszögelés megalkotásának feladatát először 1934-ben vetette fel Borisz Nyikolajevics Delaunay szovjet matematikus munkájában.

HáromszögelésDelaunay egy síkon lévő S pontok halmazára a DT (S) háromszögelést úgy nevezzük, hogy egyetlen S-ből induló A pont sem található egy olyan körön belül, amely a DT (S)-ből származó háromszög köré van írva úgy, hogy egyik csúcsa sem A pont.

1.1 A téma szakirodalmának elemzése

SkvorcovA.BAN BEN.HáromszögelésDelaunayÉsnekiAlkalmazás. /SzkvorcovA.BAN BEN. -Tomszk: KiadóHangerő. Un-ta,2002 . - 128s. Ez az oktatóanyag a kurzusprojekt fő része. Részletesen leírja a Delaunay-háromszögeléshez kapcsolódó elméleti információkat, és különféle definíciókat és tételeket ad.

Vannak olyan részek is, amelyek részletesen leírják a háromszögelések felépítésére szolgáló algoritmusokat, megadják azok összehasonlító jellemzőit és az algoritmusok összetettségét.

Mit kölcsönzött: alapanyag, elméleti információk, definíciók, rajzok.

PopovVAL VEL.A.SzámítástechnikamódÉsprogramozás. /PopovVAL VEL.A. -Moszkva: KiadóMSU,2008, - 24s. Ez a módszertani útmutató segédirodalmi forrás. Egyes algoritmusokat matematikai oldalról írunk le, konstrukciós képleteket számolunk, és van leírás az euklideszi térben történő háromszögelésről is.

Mit kölcsönzött: Delaunay-háromszögelés matematikai leírása, konstrukció az euklideszi téren

MedvegyevN.N.MódszerVoronoi - DelaunayVkutatásszerkezeteknem kristályosrendszerek/ RAS,Novoszibirsk: KiadóCORAS,2000, - 214 Val vel. A Voronoi és Delaunay módszerek leírásának szentelt könyv nem kristályos rendszerekben.

Mit kölcsönzött: Delaunay-háromszögelések tulajdonságai, Delaunay-háromszögelés definíciója.

1.2 Alapvető definíciók és tulajdonságok

Háromszögelés egy sík gráf, amelynek belső területei mind háromszögek.

Tulajdonságok:

· A Delaunay-háromszögelés egy az egyhez felel meg a Voronoi-diagramnak ugyanarra a ponthalmazra.

· Következésképpen: ha nincs négy pont ugyanazon a körön, a Delaunay-háromszögelés egyedi.

· A Delaunay-háromszögelés maximalizálja a minimális szöget az összes megszerkesztett háromszög összes szöge között, elkerülve ezzel a „vékony” háromszögeket.

· A Delaunay-háromszögelés maximalizálja a beírt gömbök sugarának összegét.

· A Delaunay-háromszögelés minimalizálja a diszkrét Dirichlet funkciót.

· A Delaunay-háromszögelés minimalizálja a minimális környezeti gömb maximális sugarát.

· A Delaunay-háromszögelés a síkon rendelkezik a háromszögek körül leírt körök sugarainak minimális összegével az összes lehetséges háromszögelés között.

1. ábra Háromszögelés.

Konvex háromszögelés olyan háromszögelés, amelynél az összes háromszöget körülvevő minimális sokszög konvex. A nem konvex háromszögelést nevezzük nem domború.

A feladat Építkezés háromszögelés Által adott toborzás kétdimenziós pontokat Az a probléma, hogy adott pontokat nem metsző szakaszok kötnek össze úgy, hogy háromszögelés alakuljon ki.

Azt mondják, a háromszögelés kielégít feltétel Delaunay , ha a megadott háromszögelési pontok egyike sem esik a szerkesztett háromszög köré körülírt körbe.

Háromszögeléshívottháromszögelés Delaunay , ha domború és kielégíti a Delaunay-feltételt.

2. ábra Delaunay-háromszögelés.

1.3 Delaunay üres labda módszer. Építés általános esetben

Használjunk egy üres labdát, amelyet úgy mozgatunk, hogy a méretét úgy változtatjuk meg, hogy érintse az (A) rendszer pontjait, de mindig üres maradjon.

Tehát helyezzünk el egy üres Delaunay golyót az (A) pontrendszerben. Ez mindig lehetséges, ha elég kicsi labdát választasz. Kezdjük növelni a sugarát úgy, hogy a labda közepét a helyén hagyjuk. Egy ponton a labda felülete találkozik az (A) rendszer valamely pontjával. Ez mindenképpen meg fog történni, mert a rendszerünkben nincsenek végtelenül nagy üregek. Tovább növeljük az üres golyó sugarát, hogy az i pont a felületén maradjon. Ehhez el kell mozgatnia a labda közepét az i pontból. Előbb-utóbb a labda a felületével elér egy másik pontot a rendszerben (A).

3. ábra - Kétdimenziós pontrendszer Delaunay csempézése

A Delaunay szimplexek hiányosságok és átfedések nélkül töltik ki a teret.

Egyetlen szimplex leírt gömbje sem tartalmazza magában a rendszer többi pontját.

Legyen ez a j pont. Tovább növeljük labdánk sugarát, mindkét pontot a felületén tartva. A labda növekedésével eléri a rendszer valamely harmadik pontját, a k pontot. A kétdimenziós esetben az „üres körünk” ebben a pillanatban rögzül, azaz. Lehetetlenné válik a sugarának további növelése, miközben a kör üresen marad. Ugyanakkor azonosítunk egy három pontból (i, j, k) álló elemi kétdimenziós konfigurációt, amely egy bizonyos háromszöget határoz meg, amelynek sajátossága, hogy az (A) rendszernek nincs más pontja a körülírt körön belül. A háromdimenziós térben a labdát nem három pont határozza meg. Növeljük tovább a sugarát úgy, hogy mindhárom pontot a felületén találjuk. Ez addig lehetséges, amíg a labda felülete nem találkozik a rendszer negyedik pontjával. Ezt követően az üres labda mozgása és növekedése lehetetlenné válik. A talált négy pont (i,j,k,l) ​​határozza meg a tetraéder csúcsait, amelyre az a jellemző, hogy körülírt gömbjén belül nincs más pontja az (A) rendszernek. Az ilyen tetraédert Delaunay szimplexnek nevezik.

A matematikában szimplex egy adott dimenziójú tér legegyszerűbb alakja: tetraéder - háromdimenziós térben; háromszög - két dimenzióban. A rendszer tetszőleges három (négy) pontja, amelyek nem helyezkednek el ugyanabban a síkban, mindig meghatároz egy bizonyos szimplexet. Ez azonban csak akkor lesz Delaunay szimplex, ha a leírt gömbje üres. Más szavakkal, a Delaunay-féle egyszerűsítéseket az (A) rendszer pontjainak speciális megválasztása határozza meg.

Egy Delaunay szimplexet szerkesztettünk, de ha az üres golyót különböző helyekre helyezzük, és ugyanazt az eljárást megismételjük, másokat is meghatározhatunk. Azt állítják, hogy az (A) rendszer összes Delaunay-egyszerűségének halmaza átfedések és hézagok nélkül tölti ki a teret, azaz. megvalósítja a tér felosztását, de ezúttal tetraéderekre. Ezt a partíciót hívják hasításDelaunay(3. ábra).

1.4 A Delaunay-háromszögelés alkalmazása

A Delaunay-háromszögelést gyakran használják az euklideszi térben. Az euklideszi minimális feszítőfa garantáltan a Delaunay-háromszögelésen fekszik, így egyes algoritmusok háromszögelést használnak. A Delaunay-háromszögelés révén az euklideszi utazó eladó probléma is megközelítőleg megoldott.

A 2D interpolációban a Delaunay-háromszögelés a lehető legvastagabb háromszögekre osztja fel a síkot, elkerülve a túl éles és túl tompa szögeket. Ezekkel a háromszögekkel például bilineáris interpolációt készíthet.

A geoinformatikában egy másik gyakran előforduló probléma a lejtős feltárások kialakítása. Itt meg kell határozni a lejtők domináns irányait kardinális irányban, és fel kell osztani a felszínt olyan régiókra, amelyekben egy bizonyos irány dominál. Mivel a felület vízszintes területein nincs értelme az expozíció meghatározásának, a vízszintes vagy enyhén lejtős területek külön régióhoz vannak hozzárendelve, pl.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

4. ábra. Példa a lejtős expozíció kiszámítására domborzati modell segítségével

A lejtős kitettség kiszámításának problémáját általában a Föld megvilágításának elemzésére használják. Ebben a tekintetben gyakran szükség van a Nap aktuális helyzetének további figyelembevételére, pl. Az expozíciót a háromszög normálja és a Nap iránya közötti irányként számítják ki.

Így minden háromszögelési háromszög osztályozható az adott régióhoz való tartozás elve szerint. Ezután már csak meg kell hívnia a régiókiválasztó algoritmust.

2. Építési algoritmusok leírása

Általánosságban elmondható, hogy minden algoritmus egy nagyon egyszerű ötleten alapul, hogy szekvenciálisan adjunk hozzá pontokat egy részben megszerkesztett Delaunay-háromszöglethez. Formailag ez így néz ki.

Adott Egy csomó tól től N pontokat.

1. Az első három kiindulási pontra építünk egy háromszöget.

2. Az összes többi ponthoz tartozó n ciklusban hajtsa végre a 3-5.

3. A következő n-edik pontot adjuk hozzá a már megszerkesztett háromszögelési struktúrához az alábbiak szerint. Először is a pont lokalizált, azaz. van egy (korábban megszerkesztett) háromszög, amelybe a következő pont esik. Vagy ha a pont nem esik bele a háromszögelésbe, akkor a háromszög határán, a következő ponthoz legközelebb található háromszög található.

4. Ha egy pont egy korábban beillesztett háromszögelési csomópontra esik, akkor az ilyen pontot általában eldobjuk, ellenkező esetben a pont új csomópontként kerül be a háromszögelésbe. Sőt, ha a pont valamelyik élre esik, akkor azt két újra osztják, és az éllel szomszédos mindkét háromszöget szintén két kisebbre osztják. Ha egy pont szigorúan egy háromszög belsejébe esik, akkor három új pontra osztódik. Ha a pont kívül esik a háromszögelésen, akkor egy vagy több háromszög készül.

5. Az újonnan kapott háromszögek helyi ellenőrzése a Delaunay-feltételnek való megfelelés érdekében, és a szükséges rekonstrukciók elvégzése.

Vége algoritmus.

Lent adott részletes leírás számos algoritmusok.

2.1 Mohó algoritmus

Az egyik első, aki a következő algoritmust javasolta a háromszögelés felépítéséhez.

Kapzsimódszer- ez egy olyan módszer, amelyben soha nem vonják vissza azt, amit már megcsináltak. Az algoritmus a következő lépéseket egymás után hajtja végre.

1. Az összes szerkezeti szegmens vége a kezdeti pontok halmazába kerül.

2. Az összes pontpárt összekötő szegmenseket generálunk, a szakaszokat hossz szerint rendezzük.

3. A szerkezeti vonalak összes szakaszát beillesztjük a háromszögelésbe.

4. A háromszögeléshez a szegmenseket szekvenciálisan kell kiválasztani a hosszúság szerint (rövidebbről hosszabbra) rendezett szegmenskészletből. Ha egy szakasz metszi a már beszúrt szegmenseket, akkor eldobjuk, ellenkező esetben bekerül a háromszögelésbe.

A 4. lépést addig ismételjük, amíg a szegmensek el nem fogynak.

Vegye figyelembe, hogy ha minden lehetséges szegmens különböző hosszúságú, akkor ennek az algoritmusnak az eredménye egyértelmű, ellenkező esetben az azonos hosszúságú szegmensek beillesztési sorrendjétől függ.

A háromszögelést hívják kapzsi , ha azt egy mohó algoritmus állítja össze.

2.2 "Törlés és felépítés" algoritmus

" Töröl És épít " nem történik változás. Ehelyett egy új csomópont (a) minden beillesztésekor azonnal törlődik minden olyan háromszög, amelyben az új csomópont (b) a körülírt körökön belülre esik. Ebben az esetben az összes eltávolított háromszög implicit módon sokszöget alkot. Ezt követően az eltávolított háromszögek helyére kitöltő háromszögletet készítünk úgy, hogy ehhez a sokszöghez új csomópontot kapcsolunk (c. ábra).

Rizs. 4. "Törlés és felépítés" algoritmus

Ez az algoritmus az összes szükséges háromszöget egyszerre építi fel, ellentétben a szokásos iteratív algoritmussal, ahol egy csomópont beillesztésekor ugyanannak a háromszögnek több rekonstrukciója is lehetséges. Itt azonban egy távoli sokszög kontúrjának kinyerésére szolgáló eljárás kerül előtérbe, amelynek hatékonyságától függ az algoritmus teljes sebessége. Általában a használt adatszerkezettől függően ez az algoritmus kevesebb időt tölthet, mint egy újraépítéssel rendelkező algoritmus, és fordítva.

2.3 "Build by breaking" algoritmus

A szerkezeti szegmensek beillesztésére szolgáló „Build by Breaking” algoritmus a legegyszerűbb megvalósítani és a legstabilabb működésben.

Ebben a beillesztett szegmens mentén a háromszögek mentén egymás után haladva meg kell találni a háromszögelési élekkel való metszéspontjait. Ezeken a metszéspontokon új háromszögelési csomópontokat kell elhelyezni, a meglévő éleket és háromszögeket részekre bontani. Ezt követően minden újonnan épített háromszögnél ellenőrizni kell a Delaunay állapotot, és szükség esetén újra kell építeni anélkül, hogy a rögzített éleket érintené.

Rizs. 5. „Build by breaking” algoritmus

Egyes esetekben ennek a beillesztési algoritmusnak a hátránya lehet, hogy nagyszámú további csomópontot és háromszögelési élt hoz létre. Ugyanakkor más esetekben ez a hátrány előnyt jelent, megakadályozva a hosszú, keskeny háromszögek kialakulását, ami különösen a terepmodellezés során értékelhető.

Ennek a beillesztési algoritmusnak egy másik előnye a későbbiekhez képest akkor jelenik meg, amikor olyan szerkezeti szegmenst próbálunk beilleszteni egy háromszögelésbe, amelyben az általa metszett élek között rögzített élek vannak. Az ilyen bordákat, mint az összes többit, egyszerűen két részre osztják.

2.4 Algoritmus a háromszög középpontjainak k-D fával való indexelésével

BAN BEN algoritmus háromszögelés Val vel indexelés központok háromszögek k-D- fa csak a háromszögek középpontja kerül a k-D-fába (k = 2 esetén). A régi háromszögek törlésekor el kell távolítani a k-D-fából a középpontjukat, újak készítésekor pedig hozzá kell adni.

A háromszögelésbe beszúrt aktuális pontot tartalmazó háromszög kereséséhez egy nem szabványos pontlekérdezést kell végrehajtani a k-D fán. A fán való keresésnek a gyökértől kell kezdődnie, és le kell mennie a levelekre. Ha az aktuális k-D-fa csomópont leszármazottai (a leszármazottakat körülvevő téglalap) nem fedik le az aktuális pontot, akkor a fa mentén a további leereszkedéshez ki kell választani a keresési ponthoz legközelebb eső leszármazottat.

Ennek eredményeként egy háromszöget találunk, amelynek középpontja közel lesz az adott ponthoz. Ha a talált háromszög nem tartalmaz adott pontot, akkor az egyszerű iteratív algoritmusból a szokásos háromszögkereső algoritmust kell használni a Delaunay-háromszögelés megalkotásához.

3. Algoritmusok hatékonyságának értékelése

Az algoritmus számítási bonyolultsága egy olyan függvény, amely meghatározza, hogy az egyes algoritmusok által elvégzett munka mennyisége mennyire függ a bemeneti adatok méretétől. A munka mennyiségét általában az idő és a tér elvont fogalmaiban mérik, amelyeket számítási erőforrásoknak neveznek. Az időt a probléma megoldásához szükséges elemi lépések száma, míg a helyet az adathordozón lévő memória vagy hely mennyisége határozza meg.

3.1 Egyszerű iteratív algoritmus

Egy egyszerű iteratív algoritmusban a következő háromszög keresése a következőképpen valósul meg. Minden olyan háromszöget veszünk, amely már beletartozik a háromszögelésbe (például véletlenszerűen kiválasztva), és a kívánt háromszöget a kapcsolódó háromszögek mentén történő egymást követő átmenetekkel keresi.

A legrosszabb esetben az összes háromszögelési háromszöget metszeni kell, így egy ilyen keresés bonyolultsága O(N). Átlagosan azonban csak O() átmeneti műveletekre van szükség az egyenletes négyzetes eloszlás eléréséhez. Így a legegyszerűbb iteratív algoritmus bonyolultsága a legrosszabb, és átlagosan -

3.2 Iteratív algoritmus háromszög indexeléssel

A háromszög keresésének bonyolultsága egy R-fában a legrosszabb esetben O(N), átlagosan pedig O(log N). Ebben az esetben 1-től N-ig háromszög található, amelyeket ezután ellenőrizni kell. Ezen túlmenően további időre van szükség a fastruktúra karbantartására – O (log N) minden egyes időháromszög összeállítása és törlése esetén. Ebből azt találjuk, hogy a háromszög indexeléssel rendelkező háromszögelési algoritmus bonyolultsága a legrosszabb esetben, és átlagosan - O (N log N).

3.3 Iteratív algoritmus a háromszög középpontjainak k-D-fával történő indexelésével

A k-D-fában egy pont keresésének bonyolultsága a legrosszabb esetben O(N), az átlagban pedig O(logN). Ezt követően használható a háromszög átmenet eljárás, amely legrosszabb esetben O N () munkaigényes lehet. A fa szerkezetének karbantartására további időt kell fordítani – O N (log) minden háromszög felépítésénél és eltávolításánál.

Ebből azt találjuk, hogy a háromszög középpontjainak indexelésével járó háromszögelési algoritmus bonyolultsága a legrosszabb esetben, és átlagosan - O (N log N).

3.4 Ventilátor algoritmus

A legyező háromszögelési algoritmusban (radiális sweeping sík algoritmus) először a kiindulási pontokból azt választjuk ki, amelyik a lehető legközelebb van az összes pont tömegközéppontjához. Ezután a fennmaradó pontok esetében kiszámítja a kiválasztott középponthoz viszonyított poláris szöget, és az összes pontot e szög szerint rendezi. Ekkor az összes pontot élekkel összekötjük a rendezett listában a központi ponttal és szomszédaival. Ezután a háromszögelést konvexre fejezzük be. És végül a háromszögelést teljesen rekonstruálják, hogy megfeleljen a Delaunay-feltételnek.

Egy ilyen algoritmus bonyolultsága átlagosan O N (). Az algoritmus körülbelül ugyanolyan sebességgel fut, mint az előző algoritmus.

4. Szoftver rész

A program a Microsoft Visual Studio 2012 fejlesztői környezetben készült. Az alkalmazás egy olyan ablak, amelyben a felhasználó tetszőlegesen hozzáadhat olyan pontokat, amelyek azonnal egy Delaunay-háromszögelésbe kapcsolódnak. A jobb oldalon az összes hozzáadott pont koordinátáinak listája látható.

fő. cpp - ablakfunkciók, a felhasználói felülettel való munkavégzés funkciói

delone. cpp - algoritmus és a vele való munkához szükséges funkciók

A program funkcióinak leírása:

void DrawPoint (int x, int y) - funkció egy pont rajzolásához az alkalmazás ablakában

void Triangulation() - a háromszögelés végrehajtására szolgáló funkció

void TriangulationIn () - a háromszögön belüli pontokkal végzett műveletek végrehajtására szolgáló funkció

void TriangulationOut () - funkció a háromszögön kívüli pontokkal végzett műveletek végrehajtására.

Az alkalmazás használatához a felhasználónak rá kell kattintania a kívánt területre, amely után a Delaunay háromszögelés megépül.

delaunay háromszögelési szoftver algoritmus

Rizs. 6. Program felület

Következtetés

Ebben a munkában egy olyan programot dolgoztak ki, amely alapján a Delaunay-háromszögelést megszerkesztik.

Valamennyi célt és célkitűzést is elértük, nevezetesen a Delaunay-háromszögelés megalkotásának egyik iteratív algoritmusát tanulmányoztuk; tanulmányoztam a Delaunay-háromszögelési probléma alapvető definícióit és tételeit; megvizsgáljuk a háromszögelés felépítésére szolgáló iteratív algoritmusok fő típusait; Megvalósítottak egy algoritmust a Delaunay-háromszögelés létrehozására.

Felhasznált irodalom jegyzéke

1. Skvortsov A.V. Delaunay-háromszögelés és alkalmazása. /Skvortsov A.V. - Tomszk: Tom kiadó. Egyetem, 2012. - 128 p.

2. Popov S.A. Számítási módszerek és programozás. /Popov S.A. - Moszkva: Moszkvai Állami Egyetemi Kiadó, 2008, - 24 p.

3. Medvegyev N.N. A Voronoi-Delaunay módszer a nem kristályos rendszerek szerkezetének vizsgálatában / RAS, Novoszibirszk: SB RAS Kiadó, 2009, - 214 p.

Közzétéve az Allbest.ru oldalon

Hasonló dokumentumok

Delaunay üres labda módszer. Egyszerű partíció (háromszögelés). A Delaunay-egyszerűségek kölcsönös elrendezésének sajátosságai. Algoritmus egy Delaunay-kör felépítéséhez. Programozási lehetőségek a Microsoft Windows Presentation Foundation technológiával.

tanfolyami munka, hozzáadva 2011.05.14


A "Surface" program lehetőségeinek tanulmányozása: izolinák, Voronoi-diagramok, profilok, interpolált gráfok, háromdimenziós vizualizáció, felületek készítésének módszereinek mérlegelése Delaunay háromszögelési módszerrel és rálátási zónák kiszámítására.

összefoglaló, hozzáadva: 2010.02.11


A kérdés elméleti kutatása és gyakorlati alkalmazása. Általános információk a grafikonokról. Dijkstra algoritmusa. A környezetben végzett munka jellemzői. Szoftver implementáció. Az algoritmus és a programstruktúra leírása. A szoftver leírása. Program szövege.

tanfolyami munka, hozzáadva 2007.11.27


Blokkdiagramok felépítése - digitális szűrőalgoritmusok grafikus ábrázolása. Struktúrák szintetizálásának lehetséges lehetőségei rekurzív szűrők példájával. Az ilyen szűrők differenciálegyenletének felépítése a rendszerfüggvény általános formában történő rögzítésével.

bemutató, hozzáadva 2013.08.19


A stratégiai rendszer tervezési megoldásának ismertetése, az objektumorientált elemzés és tervezés szakaszai. Az objektumok közötti kapcsolatok leírása. Szoftver implementáció, objektumállapotok modelljének felépítése. Felhasználói kézikönyv és programleírás.

tanfolyami munka, hozzáadva 2011.11.17


Az evolúciós algoritmusok főbb jellemzői. A genetikai algoritmusok megvalósításához használt szelekciós, mutációs, keresztezési algoritmusok leírása. A fitnesz függvény számítása. Szoftver implementáció. Tesztelés és használati útmutató.

tanfolyami munka, hozzáadva 2014.11.03


A számítógépes grafika fejlődésének szakaszai. Általános koncepció a háromdimenziós grafikáról. A vetítés építési folyamatának megszervezése. Drótmodell, nem arcfelületek levágása, forgatás. Képalkotás szoftveres megvalósítása. Komplex modellek felépítése.

tanfolyami munka, hozzáadva 2012.06.11


Szemantikus hálózatok, mint tudásreprezentációs modellek. Alapvető módszerek rendszerek gráfmodelljei hasonlóságának meghatározására. Módszer a szemantikai hálózatok hasonlóságának meghatározására szolgáló problémák megoldására komplexitásuk alapján. Algoritmusok fejlesztése és szoftveres megvalósítása.

szakdolgozat, hozzáadva: 2011.12.17


A szkennelési folyamat leírása egyszerűsített formában. A metamodell komponensek és lehetséges állapotaik leírása. Kezdeményezők és eredők, ekvivalencia osztályok. Műveletek folyamatokon: áthelyezés, redukció, kompozíció. Petri háló felépítése és tulajdonságai.

tanfolyami munka, hozzáadva 2011.06.13


Koncepcionális modell és szimulációs módszer felépítése. Matematikai modell változóegyenleteinek meghatározása és modellező algoritmus felépítése. A rendszer lehetséges fejlesztéseinek leírása és a végső modell az eredményekkel együtt.

Előző cikk: Mekkora a fénysebesség Következő cikk: Harmonikus rezgések Az oszcillációs frekvencia fizikai képlete