TEPLOV A.A., Bachelor, Moszkvai Állami Műszaki Egyetem, N.E. Bauman, Számítógépes Szoftverek és Információs Technológiák Tanszék, Moszkva, [e-mail védett]

MAIKOV K.A., a műszaki tudományok doktora, a Moszkvai Állami Műszaki Egyetem professzora, N.E. Bauman, Számítógépes Szoftverek és Információs Technológiák Tanszék, Moszkva, [e-mail védett]

Módosított algoritmus
Delaunay háromszögelés

Bemutatjuk a nagy teljesítményű és alacsony erőforrás-intenzitású Delaunay-háromszögelési módszerek összehasonlító elemzésének eredményeit. Az utólagos korszerűsítéshez szükséges prototípus választása a dinamikus háromdimenziós objektumok valós idejű, gyakorlatilag szükséges részletességgel történő megépítése kapcsán indokolt. Javasolunk egy algoritmust a háromszögelési pontok tömbjének intervallum-particionálására az eloszlási sűrűségnek megfelelően, amely lehetővé teszi a hardveres implementáció hibáinak elkerülését. A javasolt módosított Delaunay háromszögelési algoritmust elemeztem

Bevezetés

Az egyik szakasz, amely meghatározza a dinamikus 3D objektumok adott részletezettségi fokával történő építésének erőforrás-intenzitását, a háromszögelés. A gyakorlatban szükségessé válik a háromszögelési módszer prototípusának meghatározása, amely kielégíti a nagy teljesítmény és az alacsony erőforrás-intenzitás követelményét, utólagos módosítással egy adott problémacsoporthoz.

Kimutatás a megoldandó feladatokról

Számos gyakorlati problémára az jellemző, hogy olyan 3D objektumokat kell modellezni, amelyeket egy megfelelő pontkészlettel írnak le, ismeretlen eloszlási törvény mellett. Ilyen feladat például egy hegyvonulat vagy összetett és szabálytalan felszíni struktúrák modellezése, amelyek magasságát előzőleg távérzékeléssel határozzák meg. Ebben az esetben háromszögelést kell végrehajtani a kezdeti ponthalmazon, biztosítva a háromszögek legmagasabb "szabályossági fokát", amelyet az jellemez, hogy kizárják a "vékony" háromszögek felépítését a minimális összeg összegével. a körülírt körök sugarai.

A háromszögek "szabályossági fokának" problémáját egy olyan háromszögelés oldja meg, amely kielégíti a Delaunay-feltételt.

Az ismert Delaunay-háromszögelési algoritmusok a következő négy kategóriába sorolhatók: iteratív algoritmusok, fúziós algoritmusok, kétmenetes algoritmusok és lépésenkénti algoritmusok; ezeknek az algoritmusoknak a főbb jellemzőit az alábbiakban tárgyaljuk.

Iteratív algoritmusok a Delaunay-háromszögelés megalkotásához

Az iteratív algoritmusokban a pontok szekvenciális hozzáadását egy részlegesen megszerkesztett Delaunay-háromszöglethez valósítják meg. Az iteratív Delaunay-algoritmusok összetettsége O(N2) , a pontok egyenletes eloszlása ​​esetén pedig - O(N) . Az iteratív Delaunay-algoritmusok hátrányai az iteratív ciklusok nagy száma, a rendezési algoritmus függése a forrásadatok szerkezetétől, valamint az, hogy minden ciklusban ellenőrizni kell a Delaunay-feltételt. Az iteratív Delaunay-algoritmusok előnyei a könnyű implementáció és a hatékony rendezési algoritmus kiválasztásának gyorsasága egy adott bemeneti adatkészlet alapján.

Algoritmusok Delaunay-háromszögelés összevonással történő megalkotásához

Az összevonási algoritmusok a kezdeti ponthalmaz több részhalmazra való felosztását valósítják meg, amelyekben háromszögeléseket készítenek, majd számos megoldás egyesítése következik. Az összevonási algoritmusok összetettsége átlagosan O(N) . Az összevonási algoritmusok eleve redundánsak, mivel a „keskeny” sávokhoz konvex régiókat kell létrehozni, és ebből következően hosszú, „keskeny” háromszögek jönnek létre, amelyek összevonáskor újjáépülnek. Az egyesítő algoritmusok nagy sebességgel rendelkeznek, ami meghatározza gyakorlati előnyüket.

Kétmenetes algoritmusok a Delaunay-háromszögelés megalkotásához

A kétmenetes algoritmusok előnyös tulajdonsága, hogy az első ciklusban a Delaunay-feltétel figyelembevétele nélkül építenek fel valamilyen háromszögelést, amelyet a második szakaszban a Delaunay-feltételnek megfelelően módosítanak. A kétmenetes algoritmusok összetettsége átlagosan O(N) , legkedvezőtlenebb esetben pedig - O(N 2) . A kétmenetes Delaunay-algoritmusok hátránya, hogy minden sávhoz nagy számú válogatásra van szükség. Ugyanakkor ezt az algoritmust nagy teljesítmény jellemzi, mert a következő háromszöget, amely a háromszögelésbe esik, nem vetik alá a Delaunay-feltétel kielégítésére vonatkozó tesztnek, ami jelentős hardvererőforrást igényel.

Lépésről lépésre algoritmusok Delaunay-háromszögelés felépítéséhez

A lépésről lépésre történő felépítés algoritmusai csak olyan háromszögeket valósítanak meg, amelyek a végső háromszögelésben kielégítik a Delaunay-feltételt, ezért nem igényelnek újraépítést. Magas pontkoncentráció esetén a lépésről lépésre haladó cellás algoritmus használata nem megfelelő. Ennek az algoritmusnak a bonyolultsága átlagosan O(N), a legrosszabb esetben pedig O(N 2).

Prototípus kiválasztása Delaunay-háromszögelési módosításhoz

A dinamikus 3D objektumok valós idejű megalkotásának gyakorlati jellemzői olyan követelményeket határoznak meg a Delaunay háromszögelési algoritmusokkal szemben, mint a nagy teljesítmény és az alacsony erőforrás-felhasználás. Amint a fenti elemzési eredményekből következik, a vizsgált algoritmusok nem elégítik ki teljes mértékben ezeket a követelményeket. Ezért szükségessé válik egy olyan algoritmus megalkotása, amely nem függ a háromszögelési terület primitívekre való felosztásától, amelyek magának a háromszögelésnek a pontjait tartalmazzák, és nem igényli a Delaunay-feltétel ellenőrzését minden egyes iterációnál, amikor az aktuális háromszöget hozzáadjuk az eredeti háromszöghöz. .

A fenti összehasonlító elemzés eredményeiből az következik, hogy a kétmenetes Delaunay-háromszögelési algoritmusok, különösen a kétjáratú ventilátor-algoritmus csak részben felel meg a nagy sebesség és az alacsony erőforrás-felhasználás kritériumának.

Az ilyen típusú algoritmusokat azonban módosítani kell a valós idejű problémák esetén alkalmazható teljesítmény növelése érdekében. A kétmenetes ventilátor algoritmus redundáns a pontok tömegközéppontjának meghatározásában. A pont tömegközéppont koordinátájának OX vagy OY általi meghatározásakor, nagy számú pont esetén nem célszerű a számtani középértéket kiszámítani, és a pontok nagy koordinátáinál adattúlcsordulás léphet fel, ami hibához vagy programhibához vezet. Ezért tanácsos a háromszögelési pontok összes értékét felosztani intervallumokra az X tengely mentén Δх 1, Δх 2, Δх 3 ... Δх n, az Y tengely mentén pedig Δy 1, Δy 2, Δy 3 értékekkel. .. Δy n. Meg kell határozni a megfelelő intervallumokhoz tartozó pontok számát is az X és Y tengely mentén A kapott képletek a ponttömegek koordinátaközéppontjának meghatározásához a következők:

• x c - a tömegközéppont x-koordinátája;
• Δх i – i-edik intervallum az X-tengelyen;
• X max - a maximális érték az X tengely mentén az összes háromszögelési pont között;
• X min - a minimális érték az X tengely mentén az összes háromszögelési pont között;

• y c - a tömegközéppont y-koordinátája;
• n i az i-edik intervallum pontjainak száma;
• Δy i – i-edik intervallum az Y tengelyen;
• Y max - a maximális érték az Y tengely mentén az összes háromszögelési pont között;
• Y min - a minimális érték az Y tengely mentén az összes háromszögelési pont között.

A háromszögelés további szakaszai a klasszikus ventilátor-algoritmus szerint valósulnak meg. A kifejlesztett legyező alakú Delaunay-háromszögelési algoritmus sémája a 2. ábrán látható. egy.

A bemutatott sémában a legidőigényesebb lépések a rendezés és a konvex háromszögelési konstrukció szakaszai. Az összevonási algoritmust választottuk rendezési algoritmusnak, a Graham-algoritmust pedig a konvex háromszögelés felépítésének algoritmusának. Mindkét algoritmus elfogadható időn belül működik, és gyakorlati szempontból a legelőnyösebb képviselőik körében.

A módosított Fan Delaunay háromszögelési algoritmus elemzése

ábrán láthatóból. A diagram 1. ábrája azt mutatja, hogy a módosított ventilátor-algoritmus háromszögelési felépítési idejének értékét a következő kifejezés határozza meg:

• T 1 , T 2 az időértékek az intervallumok optimális számának kiszámításához az X és Y tengely mentén;
• T 3 , T 4 az X min és X max számítási idő értékei;
• T 5 , T 6 – Y min és Y max számítási időértékek;
• T 7, T 8 az X és Y tengely mentén az intervallumértékek kiszámításának időértékei;
• T 9 a tömb egyes pontjainak poláris szögének kiszámításához szükséges időérték az A(X c ,Y c) ponthoz képest;
• T 10 az A(X c ,Y c) ponthoz viszonyított polárszög szerinti összes pont összevonásával történő rendezés időértéke;
• T 11 a tömb egyes pontjaitól az A(X c ,Y c) pontig tartó él felépítési idejének értéke;
• T 12 - a konvex háromszögelés befejezéséhez szükséges idő értéke;
• T 13 a háromszögelési újraépítési idő értéke, amely kielégíti a Delaunay-feltételt;
• n pont koordinátaértékek tömbje.

Tekintsünk minden időfüggést külön-külön.

Az X és Y tengely mentén az intervallumok optimális számának meghatározásakor a Sturges-szabályt használjuk, amely szerint az n intervallumok számát a következőképpen definiáljuk:

• N a mennyiség megfigyelésének összes száma;
• [x] az x szám egész része.

Nyilvánvaló, hogy T 1 és T 2 időfüggésének állandó c 1 és c 2 reprezentációja van.

Az X min , X max , Y min , Y max értékek meghatározásának szakaszában a pszeudokód így fog kinézni:

Xmin ← M

ha i ← 1 hossz (M) – 1

Ha Xmin › M[i]

Xmin ← M[i]

Xmax ← M

ha i ← 1 hossz (M) – 1

IfXmax< M[i]

Xmax ← M[i]

Ymin ← M

ha i ← 1 hossz (M) – 1

Ha Ymin › M[i]

Ymin ← M[i]

Ymax ← M

ha i ← 1 hossz (M) – 1

Ha az Ymax< M[i]

Ymax ← M[i]

A fenti pszeudokódból jól látható, hogy az x vagy y maximális vagy minimális értékének megtalálásának ideje lineárisan függ O(N), ezért T 3 (n), T 4 (n), T 5 (n) ), T 6 (n) , O(N) időkarakterisztikával rendelkeznek.

Az X tengely mentén az intervallumértékek meghatározásának sémája a 2. ábrán látható. 2.

A fenti diagramból az O(N) lineáris időfüggés is látható, hiszen a ponttömb értékeinek teljes koordinátakészlete részt vesz az értékek meghatározásában. Az Y tengely mentén az intervallumok értékeinek meghatározására szolgáló séma hasonló szerkezettel és időbeli jellemzőkkel rendelkezik, ezért T 7 (n) és T 8 (n) időfüggése O (N).

ábrán látható a kezdeti ponttömb poláris szögének meghatározására szolgáló séma. 3.

A pszeudokódban ez a séma így nézne ki:

pontokért pontokért

# Ha a pont az I és IV kvadráns közötti koordinátatengelyen fekszik

Ha pont.x ≥ Xc és pont.y = Yc

Pont.szög ← 0

# Ha a pont szigorúan az első kvadránsban van

Ellenkező esetben, ha pont.x > Xc és pont.y > Yc

Alapozás ← |pont.x - Xc|

Pont.szög ← arctg(merőleges/alap)

# Ha a pont az I és II kvadráns közötti koordinátatengelyen fekszik

Egyébként ha pont.x = Xc és pont.y > Yc

Pont.szög ← p/2

# Ha a pont szigorúan a második kvadránsban van

Különben ha pont.x< Xc and point.y >Yc

Alapítvány ← |pont.y - Yc|

Pont.szög ← p/2 + arctg(merőleges/alap)

# Ha a pont a koordinátatengelyen fekszik a II és a III kvadráns között

Ha x pont< Xc and point.y = Yc

Pont.szög ← p

# Ha a pont szigorúan a harmadik kvadránsban van

Ha x pont< Xc and point.y >Yc

Alapozás ← |pont.x - Xc|

Merőleges ← |pont.y - Yc|

Pont.szög ← p + ív (merőleges/alap)

# Ha a pont a III és IV kvadráns közötti koordinátatengelyen fekszik

Ha pont.x = Xc és pont.y< Yc

Pont.szög ← 3p/2

# Ha a pont szigorúan a negyedik kvadránsban van

Ha pont.x > Xc és pont.y< Yc

Alapítvány ← |pont.y - Yc|

Merőleges ← |pont.x – Xc|

Pont.szög ← 3p/2 + arctg(merőleges/alap)

Nyilvánvaló, hogy a pontok kezdeti koordinátáinak poláris szögének meghatározására szolgáló idő jellemzője O(N), ezért T 9 (n) = O(N).

Amint az ábrán látható, az összevonási rendezés O(N) formájú időfüggő, ezért T 10 (n) = O(NlnN).

ábrán látható az eredeti tömb pontjait összekötő él felépítésének sémája. négy.

A fenti séma pszeudokódja így néz ki:

ha i ← 0 hosszra (pont) – 1

Döntetlen(Xc,Yc,pontok[i].x, pontok[i].y)

Az időbeli válasz is lineáris, ezért T 11 (n) = O(N).

Az így kapott háromszögelést egy konvexre a Graham-algoritmus szerint hajtjuk végre. Az eljárás bemeneti adatai a Q pontok halmaza, ahol |Q|≥3. Meghívja a Top(S) függvényt, amely visszaadja az S verem tetején lévő pontot anélkül, hogy annak tartalmát megváltoztatná. Ezenkívül a NextToTop(S) függvény is használatos, amely az S veremben található pontot adja vissza, egy pozícióval a felső pont alatt; verem S nem változik.

Graham (Q)

Legyen p 0 egy pontja a Q halmazból minimális koordinátájú.

Legyenek ‹p 1 , p 2 ,...,p N › a Q halmaz pontjai rendezve

A polárszög növekvő sorrendjében.

Push (p 0 ,S)

Push (p 1 ,S)

i=2 esetén N do

Míg a NextToTop(S), Top(S) és pi pontok által alkotott szög,

Alkoss egy nem balra fordulást

# ha az ezek által alkotott szaggatott vonal mentén haladunk

# pont, a mozgás közvetlenül vagy jobbra történik

Pop(S)

Push(pi,S)

vissza S

A Graham-eljárás futási ideje O(NlnN), ahol N=hossz(Q). Mennyire könnyű megmutatni, hogy a while ciklus O(N) időt vesz igénybe, a polárszögek rendezése pedig O(NlnN) időt vesz igénybe, innen ered a Graham-eljárás általános aszimptotikája, innen T 12 (n) = O(NlnN) ).

A Delaunay-feltételt kielégítő háromszögelésre jellemző újraépítési idő, amint az ábrán látható, O(N) lineáris függőséggel rendelkezik, így T 13 (n) = O(N).

Ha az összes talált időkarakterisztikát behelyettesítjük a (3) kifejezésbe, akkor a kapott időfüggés így fog kinézni:

T(n) = c1 +c2 +O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+ +O(NlnN) )+O(N)+O(NlnN)+O(N)

T(n) = O(NlnN)

A módosított Delaunay háromszögelési algoritmus időbeli jellemzőinek elméleti elemzése megerősíti a javasolt algoritmus hatékonyságát és nagy teljesítményét.

következtetéseket

A gyakorlatban megkívánt Delaunay-háromszögelési algoritmusok összehasonlító elemzése eredményeként kiderült, hogy a vizsgált módszerek nem felelnek meg a dinamikus háromdimenziós objektumok valós idejű, előre meghatározott részletezésű konstrukciós követelményeinek, ezért módosításuk gyakorlati igénye. Javasoljuk a ventilátor kétmenetes Delaunay háromszögelési algoritmusának módosítását, amelynek funkcionális jellemzője a háromszögelési pontok koordinátáinak tömegközéppontjának értékeinek kiszámítása úgy, hogy a ponttömböt részhalmazokra osztja fel a háromszögelési pontok mentén. X és Y tengely A módosított Delaunay háromszögelési algoritmus időbeli jellemzőinek elemzése. Ezek a számítások lehetővé teszik a teljesítmény jelentős javítását a tömegpont koordinátáinak meghatározásakor a pontok nagy tömbjén, és elkerülhető az adattúlcsordulás, és ezáltal a szoftveres implementáció hibái.

1. Knut D.E. A programozás művészete. 1. kötet. Alapvető algoritmusok. – M.: Williams, 2008. – 680 p.
2. Knut D.E. A programozás művészete. 3. kötet. Rendezés és keresés. – M.: Williams, 2008. – 800 p.
3. Mandelbrot B. A természet fraktálgeometriája. - M.: Számítástechnikai Kutatóintézet, 2002. - 656 p.
4. Skvortsov A. V. Delaunay háromszögelés és alkalmazása. - Tomszk: Tomszki Egyetem Kiadója, 2002. - 128 p.
5. Skvortsov A.V. A Delaunay-háromszögelés felépítése lineáris időben. - Tomszk: Tomszki Egyetem Kiadója, 1999. - P. 120-126.
6. Skvorcov A.V., Mirza N.S. Algoritmusok háromszögelés felépítéséhez és elemzéséhez. - Tomszk: Tomszki Egyetem Kiadója, 2006. - 168 p.
7. Thomas H. Cormen, Charles I. Leiseron, Ronald L. Rivest, Clifford Stein. Algoritmusok: szerkesztés és elemzés, 3. kiadás: Per. angolról. – M.: Williams, 2013. – 1328 p.
8. Shaydurov V.V. Multigrid végeselem-módszerek. – M.: Nauka, 1989. – 288 p.
9. Sturges H. (1926). Az óraköz megválasztása. J. Amer. stat. Társ., 21, 65-66.

Kulcsszavak: virtuális valóság, háromszögelés adott ponttömbön, Delaunay háromszögelés, dinamikus háromdimenziós objektumok építése.

A módosított Delaunay-féle háromszögelési algoritmus

Teplov A.A., Bachelor, MSTU Bauman, "Szoftver és Információs Technológia Tanszék", Moszkva, [e-mail védett]

Maikov K.A., a műszaki tudományok doktora, professzor, MSTU Bauman, "Szoftver és Információs Technológiák" Tanszék, Moszkva, [e-mail védett]

absztrakt: A Delaunay-féle háromszögelés gyakorlatilag népszerű, nagy teljesítményű és alacsony erőforrás-felhasználású módszereinek összehasonlító elemzésének eredményeit ismertetjük ebben a cikkben. A további korszerűsítés módszerének megválasztása azzal a céllal, hogy dinamikus 3D-s objektumok valós időben, bizonyos fokú részletességgel készüljenek. A szálas eljárás egyik fő lépése a Delaunay-féle háromszögelés kétmenetes algoritmusa módosul. Az algoritmus javaslata a háromszögelés cellatömbjének intervallum-particionálására az eloszlás sűrűségének megfelelően, lehetővé téve a hardveres implementáció hibáinak elkerülését.

kulcsszavak: virtuális valóság, háromszögelés adott cellatömbön, Delaunay-féle háromszögelés, dinamikus 3D objektumok építése.

Kapcsolatban áll

Á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 pontra vonatkozó n ciklusban hajtsa végre a 3-5. lépéseket.

3. A következő n-edik pontot hozzáadjuk 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ögelés határán van egy háromszög, amely a legközelebb van a következő ponthoz.

4. Ha a pont egy korábban beillesztett háromszögelési csomópontot érint, 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 élt érinti, akkor azt két újra osztjuk, és az éllel szomszédos mindkét háromszöget szintén két kisebbre osztjuk. Ha a pont szigorúan bármely háromszögön belül van, akkor három újra osztjuk. Ha a pont a háromszögelésen kívül van, akkor egy vagy több háromszög épül.

5. Az újonnan kapott háromszögek helyi ellenőrzése a Delaunay-feltételnek való megfelelés szempontjából és a szükséges átrendezések 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ő a következő algoritmust javasolta a háromszögelés felépítésére.

Mohó módszer Ez egy olyan módszer, amely soha nem vonja vissza azt, amit korábban már megtettünk. A következő lépéseket egymás után hajtjuk végre az algoritmusban.

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. Minden törésvonal-szegmens bekerül a háromszögelésbe.

4. A szegmensek szekvenciálisan kerülnek kiválasztásra a háromszögezéshez a hosszúság szerint rendezett szegmensekből (rövidebbről hosszabbra). Ha a szegmens metszi a már beillesztettek bármelyikét, 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.

Egy háromszögelést mohónak nevezünk, ha mohó algoritmussal épül fel.

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

A Delete and Build nem hajt végre újraépítést. Ehelyett egy új csomópont (a) minden beillesztésekor azonnal törlődik az összes háromszög, amelyben egy új csomópont (b) esik a leírt körökbe. Ebben az esetben az összes távoli háromszög implicit módon egy bizonyos sokszöget alkot. Ezt követően a törölt háromszögek helyére egy kitöltő háromszögelést épí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 felépíti, 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ének eljárása kerül előtérbe, az algoritmus teljes sebessége a hatékonyságától függ. Általában a használt adatszerkezettől függően ez az algoritmus kevesebb időt vehet igénybe, mint az újraépítésekkel végzett algoritmus, és fordítva.

Algoritmus "Build by breaking"

A szerkezeti szegmensek beillesztésére szolgáló "Build by breaking" algoritmus megvalósítása a legegyszerűbb és működése stabil.

Ebben a beillesztett szegmens mentén egymás után háromszögeken áthaladva 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öget ellenőrizni kell a Delaunay állapotra, é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 háromszögelési csomópontot és é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ésben értékelhető.

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

Algoritmus k-D háromszög középpontok indexelésével - fa

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

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ában. A fában történő keresésnek a gyökértől kell kezdődnie, és le kell mennie a levelekre. Ha a k-D-fa aktuális csomópontjának leszármazottai (a leszármazottakat körülölelő téglalap) nem fedik le az aktuális pontot, akkor a fa mentén történő további ereszkedéshez a keresési ponthoz legközelebb eső leszármazottat kell kiválasztani.

Ennek eredményeként találunk valami háromszöget, amelynek középpontja közel lesz az adott ponthoz. Ha a megadott pont nem esik a talált háromszögbe, akkor a Delaunay-háromszögelés elkészítéséhez a szokásos háromszögkereső algoritmust kell használni egy egyszerű iteratív algoritmusból.

A háromszögelés a szimulált 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 egymáshoz kell csatlakoztatni. 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 egyenes metszéspontja. Az arcok háromszögelése a geometriai modell vizuális észlelése érdekében történik, így a háromszögek oldalait úgy választjuk meg, 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 testlapok térbeli háromszögezését kell felépíteni úgy, hogy kiszámítjuk a térben lévő pontok tömbjét és a test lapjaihoz viszonyított normálok tömbjét ezeken a pontokon egy két- méretpontok A testek gyors megjelenítéséhez azok lapjait pontokra épített háromszög alakú lemezekkel közelítjük. A testfelületekkel kölcsönhatásba lépő fénysugarak viselkedésének meghatározásához a normálértékekre van szükség. Az előző fejezetekben és ebben a fejezetben a hangminták háromszögelés segítségével készültek.

A felületi háromszögelés eredményeképpen a paraméteres síkon egy kétdimenziós pontokból álló tömböt és egy egész számok hármasát szeretnénk elérni, amelyek az elsőként említett tömb pontjainak számai. Így minden háromszöget a 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ületi normális. 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íkfelületekre vannak olyan gazdaságos háromszögelési eljárások, amelyeknél a felület határpontjaiban háromszögeket építenek, és nem szükséges a paraméteres tartományon belüli pontokat keresni.

Delaunay háromszögelés.

Tekintsünk néhány területet a gépen. Egy régiót konvexnek nevezünk, ha a határa mentén haladva csak egy irányba kell fordulni (csak balra vagy csak jobbra). Használhatja a Delaunay algoritmust a konvex síkrégiók háromszögelésére. Ezt az algoritmust nem tudjuk közvetlenül alkalmazni a szabad formájú felületek háromszögezésére, de a háromszögek megalkotásának módszerét fogjuk használni.

Rizs. 9.7.1. Konvex terület 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ó vonallánc csúcsai. A háromszögek nem fedhetik át egymást, és oldalaik csak a csúcsokban metszhetik egymást.

Több különböző háromszög-készletet is létrehozhat, amelyek kitöltik a megadott területet. A háromszögek száma minden esetben , 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

A tartományi háromszögelés Delaunay-háromszögelés lesz, ha az egyes háromszögek körüli körülí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 nevezhetjük. A Delaunay-háromszögelés akkor lesz egyedi, ha nincs négy csúcs ugyanazon a körön.

Tekintsü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 háromszögelési csúcsoknak 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ároló éleknek nevezünk. Orientáljuk az összes határélt úgy, hogy a konvex tartomány minden éltől balra legyen. Legyen szükséges egy olyan háromszög megalkotása, amelynek oldala az ábrán látható AB határél. 9.7.2.

Egy kör megrajzolható az A, B csúcsokon és bármely olyan csúcson, amely nem esik egy egyenesen velük. A háromszög harmadik csúcsaként a V csúcsot választjuk, aminek megfelelően a kör nem tartalmaz más csúcsokat az AB szakaszhoz képest, amelyen a V pont található. Általános esetben egy ilyen csúcs határélre található. 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 húzódó merőlegesek metszéspontjában található. A kör középpontjának helyzetét az AB élre merőleges, vele 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 lévő összes csúcsnál 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ő helyzetének, egyenlő

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

Állítsa 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. Keresse meg a legközelebbi csúcsot, amelynek a megfelelő köre nem tartalmaz más csúcsokat. Keressük meg az AB határélhez a legközelebbi V csúcsot, majd készítsük el az ABV háromszöget és transzformáljuk az AB élt az inaktívak kategóriájába. Olyan inaktív éleket és csúcsokat fogunk hívni, 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ívak kategóriájába. Ha nincs VA él a határélek között, akkor az AV szakaszon egy ú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ívak kategóriájá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és akkor fejeződik be, amikor minden csúcs és él inaktívvá válik. ábra mutatja az adott terület háromszögelésének eredményét. 9.7.4.

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

Nézzük meg egy téglalap alakú paraméterdefiníciós tartományú felület háromszögelését. A felületi paraméterek definíciós tartományát osszuk fel kétdimenziós vonalakkal négyszögletes cellákra, amelyek egy téglalap alakú rácsot alkotnak. A szomszédos egyenesek közötti paraméteres távolságokat a (9.4.7) képlet szerint egyenlőnek vesszük

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

Ha minden téglalap alakú cellában átlót készí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ögezését mutatja a leírt módon.

Tekintsük egy tetszőleges határvonalú 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 egy téglalap alakú paraméterdefiníciós tartományban.

Rizs. 9.7.5. Téglalap alakú paramétertartományú felület háromszögelése

Legyen a felület határa a paraméterek meghatározásának tartományában 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ület definíciós területe mindig a kontúrtól balra van, ha a felület normálja felé nézünk. Építsünk sokszögeket a felületdefiníciós terület határkontúrjainak pozitív irányban. Határpoligonok felépítéséhez szükség van a felület határkontúrjaira valamilyen változó lépéssel végighaladni, és ki kell tölteni egy kétdimenziós pontokból álló tömböt, melynek koordinátái a felületi paraméterek. A parametrikus síkon lévő pontokból sokszöget fogunk építeni, de az egyik pontból a másikba való mozgás lépése a térgeometriából lesz meghatározva, vagyis abból a feltételből, hogy a szomszédos pontok közötti görbeív elhajlása legfeljebb adott értéket. A felület határkontúrjának görbéjének sokszög felépítésének paraméteres lépéseit a (9.4.4) képlet számítja ki.

Minden sokszög 2D pontok rendezett halmazából áll.A sokszög minden szakasza felfogható két szomszédos pontra épített 2D egyenes szakasznak. Az ilyen szakaszokat határélként fogjuk használni, és az élek alapjául szolgáló sokszögek pontjait használjuk háromszögelési csúcsként. Mivel a felületi paraméterek definíciós tartománya a határoló sokszögek bal oldalán található, a háromszögelés minden egyes határéléhez háromszögek megalkotásakor 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 mértékben a felületi paraméterek definíciós tartományába esnek (a cellák nem érinthetik a határpoligonokat). A második csoportba a többi cella tartozik (a felület definíciós területén kívül eső vagy határpoligonokkal metszett).

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

Az első csoport minden celláján belül az átló segítségével két háromszöget készítünk. Így egy befejezetlen háromszögelést kapunk. ábrán látható egy példa háromszögek létrehozására az első csoport celláiban kontúrokkal határolt forgásfelületre. 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 vonalláncot építünk (több zárt vonal is lehetséges) úgy, hogy ezen haladva a terület háromszögekre fel nem osztott része balra feküdjön, ha a felületi normális felé nézünk. Ennek a vonalláncnak az egyenes szakaszait a rendszer határoló élként is használja. Minden élt egyenlő jogúnak 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 felépítésére. Csúcsot csak azon csúcsok között fogunk keresni, amelyek ugyanabban a cellában vannak éllel. 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 más határéleket. Ezután megszerkesztünk egy ABV háromszöget, és az AB élt átvisszük az inaktívak kategóriájába. Ha a határélek között nincs BV él, akkor a VВ 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ívak kategóriájába. . Ha a határélek között nincs VA él, akkor az AV szakaszon új határélt konstruálunk, 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 a szakasz vagy a VA más határéleket metsz, akkor továbblépünk egy másik határél legközelebbi csúcsának megkeresésére. A háromszögelés az összes él és csúcs inaktív kategóriába való átvitele után fejeződik be.

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

ábrán. 9.7.7 szemlélteti a felület háromszögelését a háromszögek korrekciós módszerével határkontúrokkal keresztezett cellákban. ábrán. 9.7.8 a kapott háromszögelés segítségével magát a felületet jelenítjük meg.

Ha a határoló sokszögek és a felület szimmetriája van, akkor a korrekciós háromszögelés is hasonló szimmetriával rendelkezik.

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

Vegyü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 elindításához szükséges a felület határának ábrázolása zárt sokszögek formájában. A háromszögelés során meg kell határoznunk a lépéseket a felületi paramétereken. Ismert mozgási irány mellett ezeket a lépéseket a (9.4.6) képlet határozza 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 egy ponttól egy pontig tartó térbeli szakasz 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. Vegyünk egy ellipszist egy pontban és féltengelyekkel a kívánt terület határához. Ennek az ellipszisnek az egyenlete

Ha meg kell találni egy pontot a síkon a pont mellett a tengellyel és a tengellyel bezárt szög által megadott irányban, akkor annak paraméterei

Nézzünk először egy egyszerűbb esetet, amikor a felületi paraméterek területét egy külső kontúr korlátozza. 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 egy működő sokszöget fogunk használni, amelyhez ebben az esetben a külső kontúr sokszögét vesszük. A sokszög pontjai bekerülnek a kétdimenziós pontokból álló tömbbe. Háromszögeket építünk a munkasokszög széléből, szűkítve azt addig, amíg csak három pont marad a munkasokszögben.

Keresse meg a munkasokszögben azt a csúcsot, amelynél megfordul a területen belül. Ilyen pont mindig létezik, és a forgásszöge kisebb, mint . Jelöljük ki ezt a pontot az O-n keresztül, paramétereit pedig - keresztül. Ezen a ponton a forgásszögtől függően egy vagy két háromszöget készítünk. Ha a szög kisebb, akkor ezen a három ponton egy háromszöget készítünk (9.7.9. ábra). Ellenkező esetben két háromszöget készítünk az adott, két szomszédos és egy új ponton (9.7.11. ábra). Az új pontot P-vel jelöljük. A P pontot a B OS P paralelogramma átlóján fogjuk keresni. Ha a paralelogramma csúcsa az ellipszis belsejében van (9.7.10. ábra), akkor azt vesszük pont P. 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 VS pontok koordinátái határozzák meg

A VAGY szakasznak a 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 háromszöget (emlékezzünk a csúcsainak számára) és töröljük ki a munkasokszögből az O pontot. 9.7.11, készítsünk két háromszöget, és cseréljük ki a munkasokszög O pontját P pontra, és helyezzük el az utóbbit a kapott ponttömbben. ábrán. A 9.7.12 mutatja azt a sokszöget, 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ögek csak akkor építhetők, ha a szűkítés utáni munkasokszög 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 munkasokszög olyan oldalait, amelyek nem szomszédosak velük. Mielőtt új háromszöget hozna létre, mint az ábrán látható esetben. ábrán látható esetben a 9.7.9. 9.7.11, ellenőrizni kell, hogy az eredményül kapott sokszög nem metszi-e egymást.

Sőt, a P pont helyzetének meghatározásakor fontos, hogy az kellő távolságra legyen a munkasokszög többi pontjától, és ne kerüljön közel a sokszög 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 egy háromszög (háromszögek) nem építhető meg az O pont közelében, akkor helyette keressen egy másik pontot, ahol a sokszög jobban beburkol, mint a körvonalon belül, és ebben hajtsa végre a leírt műveleteket.

Ezután a módosított munkapoligonnal 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 a többi pontban, nézzük meg a sokszög szűkítésének lehetőségét egy-két háromszög megszerkesztésével, és szűkítsük a sokszöget.

Rizs. 9.7.13. Háromszögek nem megengedettek ebben a sarokban.

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. Ezekre a pontokra építsük fel az utolsó háromszöget, távolítsuk el a munkasokszöget és fejezzük be a háromszögelést. A leírt háromszögelési módszernél a munkasokszög á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 egészében a külső kontúron belül helyezkednek el. A felület határát a paraméteres tartomány zárt sokszögeivel közelítjük. Minden kontúrhoz saját sokszöget készítünk. Csakúgy, mint a kontúrok esetében, a rájuk épített sokszögeknél is teljesíteni kell a kölcsönös tájékozódási szabályt. A belső sokszögek tájolásának ellentétesnek kell lennie a külső sokszög tájolásával. Kezdjük el felépíteni a háromszögelést a külső kontúr sokszögével. Tegyük a pontjait a kétdimenziós pontokból álló tömbbe, és működtesse magát a sokszöget.

A háromszögeket ugyanúgy készítjük el, mint egy egyszerűen összefüggő régió esetében. Keressük meg a munkasokszögben az O pontot, nézzük meg a benne lévő munkasokszög szűkítésének lehetőségét, és szűkítsük a sokszöget. Ha vannak belső kontúrok, nehezebb lesz ellenőrizni a munkasokszög szűkítésének lehetőségét a kiválasztott pontban. A háromszögek oldalainak a munkasokszög oldalaival való metszéspontjának leírt ellenőrzésein kívül ellenőriznie 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 a megszerkesztett új P pont az egyik belső sokszög belsejébe, vagy annak szakaszaihoz elfogadhatatlan közelségbe kerül. . Ebben az esetben nem építjük fel a P pontot, hanem ezt a belső sokszöget foglaljuk bele a munkasokszögbe úgy, hogy két háromszöget készítünk, amint az ábra mutatja. 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).

Építsünk háromszögeket az OCF és CEF pontokra, és a munkasokszög O és C pontjai közé illesszük be a belső sokszög pontjait, kezdve az F ponttal és az E ponttal végződve. Így a munkasokszöget megtörjük a szakaszon. OS, törje meg a belső sokszöget az EF szegmensen, és egyesítse őket OF és EU szegmensekkel.

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ényét az ábra mutatja. 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.

Továbbá addig folytatjuk a munkasokszög szűkítését a leírt módon, amíg egy másik belső sokszög közvetlen közelében nem találjuk magunkat, és be nem vesszük a munkasokszögbe. 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 teljes többszörösen összefüggő tartománya háromszögekkel lesz borítva.

Rizs. 9.7.16. Háromszögek nem megengedettek ebben a sarokban.

Vannak helyzetek, amikor lehetetlen egyetlen háromszöget építeni az adott sokszögekre. ábrán. A 9.7.16 két sokszög által határolt területet mutat, amelyek mindegyike négy szakaszból áll. A külső sokszög esetében nem folytathatjuk a háromszögelést, mert a belső sokszög interferál. Ebben az esetben a sokszög két szomszédos B és C pontját találjuk, amelyekre VSR háromszöget készíthetü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.

Egyéb háromszögelési módszerek.

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ögének megszerkesztése után választhatunk más stratégiát a háromszögek megalkotásához. Alternatív megoldásként a külső és a belső sokszöget egy sokszögbe egyesítheti a háromszögelés megkezdése előtt. Lehetőség van a paraméterdefiníciós területen belüli pontok „megrajzolására” egy bizonyos algoritmus szerint, és ezek és a határkontúr sokszögek pontjai segítségével Delaunay-háromszögelést végezni. Vannak olyan algoritmusok, amelyek először nagy háromszögeket készítenek, majd felosztják őket elfogadható méretre.

A test háromszögelése.

A 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 lapok határpoligonjait össze kell hangolni (9.7.17. ábra).

Rizs. 9.7.17. A testlapok határoló sokszögeinek összhangja

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 a 9.7.19. ábrákon egy laptest homloklapjának háromszögelése látható, amelynek tónusképe a 3. á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 definíciós tartományának háromszögekre történő particionálása a (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) integrálokban használható a felület geometriai jellemzőinek számításakor. testek. A numerikus integráció során a görbék paraméteres lépését a (8.11.5) képlettel, a felületeknél a paraméteres lépést a (8.11.1) és (8.11.2) képletekkel kell kiszámítani.

A háromszögelés véges S ponthalmazra az S halmaz összes pontját behálózó CH(S) konvex hajótest háromszögelésének problémája. A vonalszakaszok nem metszik egymást a háromszögelés során - csak az S halmazhoz tartozó közös pontokban találkozhatnak. Mivel az egyenes A szegmensek háromszögeket zárnak be, éleknek tekintjük őket. ábrán. Az 1. ábra a háromszögelés két különböző változatát mutatja ugyanarra a ponthalmazra (az ábrákon megrajzolt köröket átmenetileg figyelmen kívül hagyjuk).

Rizs. egy

Adott egy S ponthalmaz, láthatjuk, hogy az S halmaz összes pontja felosztható határpontokra - azokra a pontokra, amelyek a konvex hajótest CH(S) határán vannak, és belső pontokra - amelyek a konvex belsejében helyezkednek el. hajótest CH(S). Az S háromszögelése eredményeként kapott élek osztályozása is lehetséges héj éleiés belső bordák. A hajótest élei magukban foglalják a domború CH(S) hajótest határa mentén elhelyezkedő éleket, a belső élek pedig az összes többi élt, amelyek a domború hajótest belsejében háromszöghálózatot alkotnak. Vegye figyelembe, hogy a héj minden éle két szomszédos határpontot köt össze, míg a belső élek két tetszőleges típusú pontot köthetnek össze. Különösen, ha egy belső él két határpontot köt össze, akkor ez a CH(S) konvex hajótest húrja. Vegye figyelembe azt is, hogy minden háromszögelési él két tartomány határa: minden belső él két háromszög között, minden héj éle pedig egy háromszög és egy végtelen sík között van.

Bármely ponthalmaz, néhány triviális eset kivételével, több módot is lehetővé tesz a háromszögelésre. Ugyanakkor van egy figyelemre méltó tulajdonság is: egy adott halmaz háromszögelési módja ugyanannyi háromszöget határoz meg, ami a tételből következik:

Tétel egy ponthalmaz háromszögeléséről. Tegyük fel, hogy az S pontok halmaza n>3 pontot tartalmaz, és nem mindegyik kollineáris. Ezenkívül a belőlük lévő i pontok belsőek (azaz a CH(S) konvex burkon belül helyezkednek el. Ekkor az S halmaz bármely háromszögelési módszeréhez pontosan n + i - 2 háromszöget kapunk.

A tétel bizonyításához először n-i határpont háromszögelését vesszük figyelembe. Mivel mindegyik egy konvex sokszög csúcsa, az ilyen háromszögelés (n - i) - 2 háromszöget eredményez. (Ezt nem nehéz ellenőrizni, sőt, kimutatható, hogy bármilyen háromszögelés tetszőleges m oldalú sokszög - konvex vagy nem konvex - m - 2 háromszöget tartalmaz). Most nézzük meg, hogy mi történik a háromszögeléssel, amikor hozzáadjuk a fennmaradó i belső pontokat, minden alkalommal egyet. Azt állítjuk, hogy minden ilyen pont összeadása a háromszögek számának kettővel való növekedéséhez vezet. Belső pont hozzáadásakor két helyzet adódhat, amint az az ábrán látható. 2. Először lehet, hogy a pont egy háromszög belsejében van, majd egy ilyen háromszöget három új háromszöggel helyettesítünk. Másodszor, ha a pont egybeesik a háromszögelés egyik élével, akkor az éllel szomszédos két háromszög mindegyikét két új háromszög helyettesíti. Ebből következik, hogy az összes r pont összeadása után a háromszögek teljes száma (n - i - 2) + (2i), vagy csak n + i - 2 lesz.

Rizs. 2

Ebben a részben egy olyan algoritmust mutatunk be, amellyel egy speciális háromszögelést hozhatunk létre, amely Delaunay-háromszögelésként ismert. Ez a háromszögelés jól kiegyensúlyozott abban az értelemben, hogy a kialakított háromszögek általában egyenlő szögűek. Például az ábrán látható háromszögelés. Az 1a. ábra a Delaunay-háromszögelés típusának tulajdonítható, és az 1a. Az 1b. ábrán látható háromszögelés több erősen megnyúlt háromszöget tartalmaz, és nem tulajdonítható a Delaunay típusnak. ábrán. A 3. ábra Delaunay-háromszögelési példát mutat be egy nagy számú pontból álló halmazra.

Rizs. 3

A Delaunay-háromszöglet kialakításához több új definícióra van szükségünk. Egy ponthalmazt kör alakúnak tekintünk, ha van olyan kör, amelyen a halmaz összes pontja fekszik. Egy ilyen kör egy adott ponthalmazra lesz körülírva. A háromszög körülírt köre átmegy mindhárom (nem kollineáris) csúcsán. Egy kört akkor mondunk pontoktól mentesnek egy adott S ponthalmazhoz képest, ha a körön belül nincsenek pontok az S halmazból, de az S halmazból származó pontok a pontoktól legmentesebb körön is elhelyezkedhetnek.

Egy S ponthalmaz háromszögelése Delaunay-háromszögelés lesz, ha az egyes háromszögek körülírt köre pontoktól mentes. ábrán látható háromszögelési diagramon. Az 1a. ábra két olyan kört mutat, amelyekben nyilvánvalóan nem találhatók más pontok (más háromszögekhez köröket rajzolhat, hogy megbizonyosodjon arról, hogy azok is mentesek a halmazban lévő pontoktól). ábra diagramján ezt a szabályt nem tartják be. 16 - egy másik háromszög egyik pontja a megrajzolt körön belülre került, ezért ez a grianguláció nem tartozik a Delaunay típusba.

Az S halmaz pontjairól két feltételezés tehető a háromszögelési algoritmus egyszerűsítésére. Először is, hogy egyáltalán létezhessen háromszögelés, fel kell tételeznünk, hogy az S halmaz legalább három pontot tartalmaz, és ezek nem kollineárisak. Másodszor, ahhoz, hogy a Delaunay-háromszögelés egyedi legyen, szükséges, hogy az S halmazból ne legyen négy pont ugyanazon a körülírt körön. Könnyen belátható, hogy ilyen feltevés nélkül a Delaunay-háromszögelés nem lesz egyedi, mert egy körülírt körön lévő 4 pont két különböző Delaunay-háromszögelést tesz lehetővé.

Algoritmusunk úgy működik, hogy folyamatosan háromszögenként építi fel az aktuális háromszögelést. Kezdetben az aktuális háromszögelés a héj egyetlen éléből áll, az algoritmus befejezése után az aktuális háromszögelésből Delaunay-háromszögelés lesz. Minden iterációnál az algoritmus egy új háromszöget keres, amelyhez kapcsolódik határ jelenlegi háromszögelés.

A határ meghatározása a következő Delaunay-háromszögelési élosztályozási sémától függ az aktuális háromszögeléshez képest. Mindegyik él lehet alvás, élő vagy halott:

• szunnyadó bordák: egy Delaunay-háromszögelési él nyugalmi állapotban van, ha még nem fedezte fel az algoritmus;
• élő bordák: az él él, ha megtalálható, de csak egy vele szomszédos régió ismert;
• elhalt bordák: egy él akkor tekinthető halottnak, ha megtalálható, és mindkét szomszédos régió ismert.

Kezdetben az egyetlen él, amely a konvex i ponthoz tartozik, él - egy határtalan sík csatlakozik hozzá, és az összes többi él alvó. Ahogy az algoritmus működik, az alvó élek élővé válnak, majd elhalnak. A határ minden szakaszban élő élek halmazából áll.

Minden iterációnál kijelöljük a határ bármely élét, és feldolgozásnak vetjük alá, ami abból áll, hogy egy ismeretlen régiót keresünk, amelyhez az e él tartozik. az e él és valamilyen v harmadik csúcs, akkor az e él halottá válik, mivel mindkét szomszédos terület ismert. A t háromszög másik két éle a következő állapotba kerül: alvóból élőbe vagy élőből halottba. Itt a v csúcsot hívjuk meg konjugált Ellenkező esetben, ha az ismeretlen tartomány végtelen sík, akkor az e él egyszerűen elhal. Ebben az esetben az e élnek nincs konjugált csúcsa.

ábrán. A 4. ábra az algoritmus működését mutatja, ahol a művelet fentről lefelé és fentről jobbra történik. A határ minden szakaszban vastag vonallal van jelölve.

Az algoritmus a delaunayTriangulate programban valósul meg. A program egy n pontból álló s tömböt kap, és visszaadja a Delaunay-háromszögletet reprezentáló háromszögek listáját. A megvalósítás a gyűrűlista osztályt és a Geometriai adatszerkezetek szakasz osztályait használja. Bármely szótár, amely támogatja a szükséges műveleteket, használható Szótár osztályként. Felülírhatja például a #define Dictionary RandomizedSearchTree-t.

Lista * (S pont, n int) ( p pont; lista *háromszögek = új lista ; Szótár határ(edgeCmp); Él *e = hajótestEdge(s, n); határbetét(e); while (!frontier.isEmpty()) ( e = border.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(határ, p, e->org); updateFrontier(határ, e ->dest, p); háromszögek->insert(triangle(e->org, e->dest, p)); ) delete e; ) return háromszögek; )

Rizs. négy

A háromszögelést alkotó háromszögek a háromszöglistába kerülnek. A határt a határ élő élek szótára ábrázolja. Minden él úgy van irányítva, hogy az ismeretlen (meghatározandó) régiója az éltől jobbra legyen. Az edgeCmp összehasonlító függvény a szótár megkeresésére szolgál. Összehasonlítja két él kezdőpontját, ha egyenlők, akkor a végpontjaikat összehasonlítja:

Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) return 1; if (a->org > b->org) return 1; if (a->dest< b->dest) return -1; if (a->dest > b->dest) return 1; visszatérés 0; )

Tehát hogyan változik a határ egyik lépésről a másikra, és hogyan változtatja meg az updateFrontier függvény a szegélyszótárt, hogy tükrözze ezeket a változásokat? Ha egy új t háromszöget csatolunk a határhoz, a háromszög három élének állapota megváltozik. A t háromszög határvonallal szomszédos éle halottá válik attól, hogy él. Az updateFrontier függvény figyelmen kívül hagyhatja ezt az élt, mivel a removeMin függvény meghívásakor már el kellett távolítani a szótárból. A háromszög két fennmaradó éle t megváltoztatja állapotát alvóról élőre, ha még nem írták be a szótárba, vagy élőből halottra, ha az él már benne van a szótárban. ábrán. Az 5. ábra mindkét esetet mutatja. Az ábrának megfelelően feldolgozzuk az af élő élt, és miután megállapítottuk, hogy a b pont konjugált hozzá, hozzáadjuk az afb háromszöget az aktuális háromszögeléshez. Ezután megkeressük a szótárban az élfb-t, és mivel még nincs ott, és először fedezik fel, állapota alvóból élővé változik. A szótár szerkesztéséhez elforgatjuk az fb élt úgy, hogy a mellette lévő ismeretlen terület jobbra legyen, és ezt az élt írjuk be a szótárba. Ekkor megtaláljuk a szótárban a ba élt - mivel benne van, így már él (a vele szomszédos ismert terület az abc háromszög). Mivel a számára ismeretlen területet, az afb háromszöget most fedezték fel, ez az él kikerül a szótárból.

Az updateFrontier függvény szerkeszti a határszótárt, amelyben az él állapota a pontról b pontra változik:

Rizs. 5

Érvénytelen frissítésFrontier(szótár &határ, &a pont, &b pont) ( Edge *e = new Edge (a, b); if (határ.find (e)) border.remove(e); else ( e->flip(); határ.beszúrás() e) ) )

A hullEdge függvény az s tömb n pontja között talál egy burok élt. Ez a funkció valójában az inicializálási lépést és az ajándékcsomagolási módszer első iterációját használja:

Él *hull Él (s pont, n int) ( int m = 0; for (int i = 1; i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }

A háromszög függvény egyszerűen létrehoz és visszaad egy sokszöget a paraméterként átadott három ponthoz:

Sokszög *háromszög (&a pont, &b pont, &c pont) ( Sokszög *t = új sokszög; t->beszúrás (a); t->beszúrás (b); t->beszúrás (c); t visszaadása; )

A megszerkesztett háromszögelés minőségének számszerűsítésére 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 2D-s régióhoz, és 12 szomszédja egy 3D-s régióhoz. Topológiai becslést kapunk az (1) képlet segítségével, ahol a régió összes pontjának száma, egy belső ponthoz kapcsolódó szomszédos pontok foka vagy száma.

A geometriai kritérium a számított háromszögelem körüli beírt és körülírt körök különbségén 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. Különböznek egymástól a munkaigényességben, a számítógépen történő megvalósítás összetettségében és az építési megközelítésben. Az algoritmusokról többet megtudhat A.V. könyvében. Skvorcova. Nézzünk néhány algoritmust.

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

1. lépés. A forráspont párokat összekötő összes lehetséges vonalszakasz listája létrejön, és a szakaszok hossza szerint rendeződik.

2. lépés A legrövidebbtől kezdve a szegmensek egymás után kerülnek be a háromszögelésbe. Ha a szegmens nem metszi egymást más korábban beszúrt 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 a háromszög megtalálásának bonyolultságából, amelyhez a következő lépésben pontot adunk, az új háromszögek létrehozásának bonyolultságából, valamint a háromszögelési struktúra megfelelő újraépítésének bonyolultságából áll, ami a nem kielégítő eredmény eredménye. az eredményül kapott háromszögelés szomszédos háromszögpárjainak ellenőrzése a Delaunay-feltételhez. Fontolja meg az algoritmust lépésről lépésre:

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 hajtsa végre a 3-5.

3. lépés A következő -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ögelés határán van egy háromszög, amely a legközelebb van a következő ponthoz.

4. lépés Ha egy pont eltalál egy korábban beillesztett háromszögelési csomópontot, 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 élt érinti, akkor azt két újra osztjuk, és az éllel szomszédos mindkét háromszöget szintén két kisebbre osztjuk. Ha a pont szigorúan bármely háromszögön belül van, akkor három újra osztjuk. Ha a pont a háromszögelésen kívül van, akkor egy vagy több háromszög épül.

5. lépés Megtörténik az újonnan kapott háromszögek helyi ellenőrzése a Delaunay-feltételnek való megfelelés szempontjából, és elvégzik a szükséges átrendezéseket.

Új háromszögek készítésekor két olyan helyzet lehetséges, amikor 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 az aktuális háromszögelésen kívül további háromszögeket kell építeni, és ezek száma a legrosszabb esetben azonos lehet? 3. Az algoritmus minden lépéséhez azonban legfeljebb háromszög adható hozzá, ahol a kezdőpontok teljes száma. Ezért mindkét esetben a háromszögek építésére fordított teljes idő az.

Lánc algoritmus Az egyik első hatékony háromszögelési konstrukciós algoritmus síkgráf-regulációs eljáráson és monoton poligon háromszögelésen alapul. Ennek az algoritmusnak az összetettsége, ahol a kezdeti szegmensek száma. Fontolja meg az algoritmust lépésről lépésre:

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 szabályozás két menetben történik, függőleges lapos söpréssel. Az első lépésben alulról felfelé sorra megkeressük az összes olyan csúcsot, ahonnan nincs felfelé vezető él. Például a (4. ábra, b) ponton ez a B csúcs. Vízszintes vonalat húzva megtaláljuk az AD és EF gráfok legközelebbi éleit, melyeket bal és jobb oldalon keresztez. Ezután keressük meg a DEHG négyszög legalsó csúcsát, és húzunk bele egy élt B-ből, hasonlóan a második lépést felülről lefelé (4. ábra, c). Ennek a lépésnek az eredményeként a síkgráf minden területe monoton sokszöggé válik.

3. lépés A grafikon minden területét háromszögekre kell osztani. Ehhez használhatja a két háromszögelés nem konvex összevonásának algoritmusát (4. ábra, d).

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

A láncalgoritmus megvalósításához a legjobb olyan adatstruktúrákat használni, amelyekben az élek kifejezetten vannak ábrázolva, mint például a „Kettős élek” vagy „Csomók, é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 egy optimális háromszögelés, nem egy mohó, és nem egy kötött Delaunay-háromszögelés. A láncalgoritmus nagyon hosszú megnyúlt háromszögeket tud előállítani.

Az így létrejövő háromszögelés minőségének javítása érdekében minden szomszédos, szerkezeti éllel nem elválasztott háromszögpár ellenőrizhető a Delaunay-feltétel teljesülése szempontjából, és szükség esetén átépíthető. Ennek eredményeként egy Delaunay-háromszögelést kapnak korlátozásokkal.