TEPLOV A.A., diplomirani, Moskovska državna tehnična univerza po imenu N.E. Bauman, Oddelek za računalniško programsko opremo in informacijske tehnologije, Moskva, [e-pošta zaščitena]

MAIKOV K.A., doktor tehničnih znanosti, profesor Moskovske državne tehnične univerze po imenu N.E. Bauman, Oddelek za računalniško programsko opremo in informacijske tehnologije, Moskva, [e-pošta zaščitena]

Spremenjen algoritem
Delaunayeva triangulacija

Predstavljeni so rezultati primerjalne analize Delaunayjevih triangulacijskih metod, ki imajo visoko zmogljivost in nizko intenzivnost virov. Izbira prototipa za kasnejšo posodobitev je utemeljena glede na konstrukcijo dinamičnih tridimenzionalnih objektov v realnem času s praktično potrebno stopnjo podrobnosti. Predlagan je algoritem za intervalno razdelitev niza triangulacijskih točk v skladu z gostoto porazdelitve, ki omogoča izogibanje napakam pri strojni izvedbi. Analiziran je bil predlagani modificirani algoritem Delaunayeve triangulacije

Uvod

Ena od stopenj, ki določajo intenzivnost virov pri gradnji dinamičnih 3D objektov z dano stopnjo podrobnosti, je triangulacija. V praksi postane potrebno določiti prototip triangulacijske metode, ki izpolnjuje zahtevo po visoki zmogljivosti in nizki intenzivnosti virov z naknadno modifikacijo za določen razred problemov.

Navedba nalog, ki jih je treba rešiti

Za številne praktične probleme je značilna potreba po modeliranju 3D objektov, opisanih z ustreznim nizom točk z neznanim zakonom porazdelitve. Primer takih nalog je modeliranje gorske verige ali kompleksnih in nepravilnih površinskih struktur, katerih višine so predhodno pridobljene z daljinskim zaznavanjem. V tem primeru je treba izvesti triangulacijo na začetnem nizu točk, ki zagotavlja najvišjo "stopnjo pravilnosti" trikotnikov, za katero je značilna izključitev konstrukcije "tankih" trikotnikov z najmanjšo vrednostjo vsote polmeri opisanih krogov.

Problem "stopnje pravilnosti" trikotnikov je rešen s triangulacijo, ki zadošča Delaunayevemu pogoju.

Znane algoritme Delaunayeve triangulacije lahko razdelimo v naslednje štiri kategorije: iterativni algoritmi, fuzijski algoritmi, algoritmi z dvema prehodoma in algoritmi po korakih; glavne značilnosti teh algoritmov so obravnavane spodaj.

Iterativni algoritmi za konstruiranje Delaunayeve triangulacije

V iterativnih algoritmih je implementirano zaporedno dodajanje točk k delno zgrajeni Delaunayevi triangulaciji. Kompleksnost iterativnih Delaunayjevih algoritmov je definirana kot O(N2) , za primer enakomerne porazdelitve točk pa - O(N) . Slabosti iterativnih Delaunayjevih algoritmov so veliko število iterativnih ciklov, odvisnost sortirnega algoritma od strukture izvornih podatkov in potreba po preverjanju Delaunayevega pogoja v vsakem ciklu. Prednosti iterativnih Delaunayjevih algoritmov so enostavnost implementacije in visoka hitrost izbire učinkovitega algoritma za razvrščanje na podlagi določenega niza vhodnih podatkov.

Algoritmi za konstruiranje Delaunayeve triangulacije z združevanjem

Algoritmi združevanja izvajajo razdelitev začetnega nabora točk na več podmnožic, v katerih so skonstruirane triangulacije, čemur sledi združitev številnih rešitev. Kompleksnost algoritmov spajanja je v povprečju O(N) . Algoritmi združevanja so sami po sebi redundantni, kar določa potreba po konstruiranju konveksnih območij za "ozke" pasove in s tem oblikovanje dolgih, "ozkih" trikotnikov, ki se po združevanju ponovno zgradijo. Algoritmi spajanja imajo visoko hitrost, kar določa njihovo praktično prednost.

Dvohodni algoritmi za konstruiranje Delaunayeve triangulacije

Prednostna lastnost dvoprehodnih algoritmov je, da se v prvem ciklu zgradi nekaj triangulacije brez upoštevanja Delaunayevega pogoja, ki se na drugi stopnji spremeni v skladu z Delaunayevim pogojem. Kompleksnost dvoprehodnih algoritmov je v povprečju O(N) , v najmanj ugodnem primeru pa O(N 2) . Pomanjkljivost dvoprehodnih Delaunayjevih algoritmov je potreba po velikem številu vrst za vsak pas. Hkrati je za ta algoritem značilna visoka zmogljivost, ker naslednji trikotnik, ki pade v triangulacijo, ni podvržen preizkusu izpolnjevanja Delaunayevega pogoja, kar zahteva precejšnja strojna sredstva.

Algoritmi po korakih za izdelavo Delaunayeve triangulacije

Algoritmi za gradnjo po korakih izvajajo le trikotnike, ki izpolnjujejo Delaunayev pogoj v končni triangulaciji in zato ne zahtevajo ponovne gradnje. Pri visoki koncentraciji točk je uporaba celičnega algoritma po korakih neprimerna. Kompleksnost tega algoritma je v povprečju O(N), v najslabšem primeru pa O(N 2).

Izbira prototipa za modifikacijo Delaunayeve triangulacije

Praktične značilnosti naloge konstruiranja dinamičnih 3D objektov v realnem času določajo zahteve za algoritme Delaunayeve triangulacije, kot sta visoka zmogljivost in nizka poraba virov. Kot izhaja iz zgornjih rezultatov analize, obravnavani algoritmi ne izpolnjujejo v celoti teh zahtev. Zato postane potrebno zgraditi algoritem, ki ni odvisen od razdelitve triangulacijskega območja na primitive, ki vsebujejo točke same triangulacije, in ne zahteva preverjanja Delaunayevega pogoja pri vsaki ponovitvi dodajanja trenutnega trikotnika prvotni triangulaciji .

Iz rezultatov zgoraj podane primerjalne analize sledi, da algoritmi dvoprehodne Delaunayeve triangulacije, še posebej pahljačasti algoritem dveh prehodov, le delno zadostijo kriterijem visoke hitrosti in nizke porabe virov.

Vendar je treba algoritme te vrste spremeniti, da bi povečali zmogljivost, ki se uporablja za težave v realnem času. Dvoprehodni pahljačasti algoritem je odvečen pri določanju težišča točk. Pri določanju koordinate središča mase točke z OX ali OY je pri velikem številu točk neprimerno izračunati aritmetično srednjo vrednost, pri velikih vrednostih koordinat točk pa lahko pride do prelivanja podatkov, kar bo povzročilo napako ali okvaro programa. Zato je priporočljivo vse vrednosti triangulacijskih točk razdeliti na intervale vzdolž osi X z Δх 1, Δх 2, Δх 3 ... Δх n in vzdolž osi Y z Δy 1, Δy 2, Δy 3 . .. Δy n. Prav tako je treba določiti število točk, ki pripadajo ustreznim intervalom vzdolž osi X in Y. Dobljene formule za pridobitev središča koordinat mas točk so naslednje:

• x c - x-koordinata točke masnega središča;
• Δх i – i-ti interval na X-osi;
• X max - največja vrednost vzdolž osi X med vsemi triangulacijskimi točkami;
• X min - najmanjša vrednost vzdolž osi X med vsemi triangulacijskimi točkami;

• y c - y-koordinata točke središča mase;
• n i je število točk v i-tem intervalu;
• Δy i – i-ti interval na Y-osi;
• Y max - največja vrednost vzdolž osi Y med vsemi triangulacijskimi točkami;
• Y min - najmanjša vrednost vzdolž osi Y med vsemi triangulacijskimi točkami.

Naslednje stopnje triangulacije se izvajajo po klasičnem pahljačastem algoritmu. Shema razvitega Delaunayjevega triangulacijskega algoritma v obliki pahljače je prikazana na sl. eno.

Najbolj zamudne faze v predstavljeni shemi so faze razvrščanja in konstruiranja triangulacije v konveksno. Za algoritem razvrščanja je bil izbran merge algoritem, za algoritem za konstruiranje konveksne triangulacije pa Grahamov algoritem. Oba algoritma delujeta v sprejemljivem času in sta med svojimi predstavniki v praksi najbolj priljubljena.

Analiza modificiranega triangulacijskega algoritma Fan Delaunay

Od prikazanega na sl. 1 diagrama kaže, da je vrednost časa konstrukcije triangulacije s spremenjenim algoritmom ventilatorja določena z izrazom:

• T 1,T 2 so časovne vrednosti za izračun optimalnega števila intervalov vzdolž osi X oziroma Y;
• T 3, T 4 so vrednosti časa izračuna X min oziroma X max;
• T 5 ,T 6 – vrednosti časa izračuna Y min oziroma Y max;
• T 7, T 8 so časovne vrednosti za izračun intervalnih vrednosti vzdolž osi X oziroma Y;
• T 9 je časovna vrednost za izračun vrednosti polarnega kota vsake točke niza glede na točko A(X c ,Y c);
• T 10 je časovna vrednost razvrščanja z združitvijo vseh točk po polarnem kotu glede na točko A(X c ,Y c);
• T 11 je vrednost časa konstruiranja roba od vsake točke niza do točke A(X c ,Y c);
• T 12 - vrednost časa za dokončanje triangulacije do konveksa;
• T 13 je vrednost časa ponovne izgradnje triangulacije, ki izpolnjuje Delaunayev pogoj;
• n je niz vrednosti koordinat točke.

Upoštevajmo vsako časovno odvisnost posebej.

Pri določanju optimalnega števila intervalov vzdolž osi X in Y uporabljamo Sturgesovo pravilo, po katerem je število intervalov n definirano kot:

• N je skupno število opazovanj količine;
• [x] je celi del števila x.

Očitno imata časovni odvisnosti T 1 in T 2 konstantni predstavitvi c 1 in c 2 .

Na stopnjah določanja vrednosti X min , X max , Y min , Y max bo psevdo koda izgledala takole:

Xmin ← M

za i ← 1 na dolžino (M) – 1

Če Xmin › M[i]

Xmin ← M[i]

Xmax ← M

za i ← 1 na dolžino (M) – 1

IfXmax< M[i]

Xmax ← M[i]

Ymin ← M

za i ← 1 na dolžino (M) – 1

Če Ymin › M[i]

Ymin ← M[i]

Ymax ← M

za i ← 1 na dolžino (M) – 1

Če je Ymax< M[i]

Ymax ← M[i]

Iz zgornjega psevdokoda je jasno razvidno, da ima čas za iskanje največje ali najmanjše vrednosti x ali y linearno odvisnost O(N), torej T 3 (n), T 4 (n), T 5 (n ), T 6 (n) imajo časovno karakteristiko O(N).

Shema za določanje intervalnih vrednosti vzdolž osi X je prikazana na sl. 2.

Iz zgornjega diagrama je vidna tudi linearna časovna odvisnost O(N), saj celoten niz koordinat vrednosti niza točk je vključen v določanje vrednosti. Shema za določanje vrednosti intervalov vzdolž osi Y ima podobno strukturo in časovne značilnosti, zato je časovna odvisnost za T 7 (n) in T 8 (n) O (N).

Shema za določanje vrednosti polarnega kota za začetni niz točk je prikazana na sl. 3.

V psevdo kodi bi ta shema izgledala takole:

za točke do točk

# Če točka leži na koordinatni osi med kvadrantoma I in IV

Če je točka.x ≥ Xc in točka.y = Yc

Točka.kot ← 0

# Če točka leži strogo v prvem kvadrantu

Drugače, če point.x > Xc in point.y > Yc

Temelj ← |točka.x - Xc|

Point.angle ← arctg(pravokotno/temelj)

# Če točka leži na koordinatni osi med I in II kvadrantom

Drugače, če točka.x = Xc in točka.y > Yc

Točka.kot ← p/2

# Če točka leži strogo v drugem kvadrantu

Sicer, če točka.x< Xc and point.y >Yc

Temelj ← |točka.y - Yc|

Point.angle ← p/2 + arctg(pravokotno/temelj)

# Če točka leži na koordinatni osi med II in III kvadrantom

Če točka x< Xc and point.y = Yc

Točka.kot ← str

# Če točka leži strogo v tretjem kvadrantu

Če točka x< Xc and point.y >Yc

Temelj ← |točka.x - Xc|

Pravokotna ← |točka.y - Yc|

Point.angle ← p + arctg(pravokotno/temelj)

# Če točka leži na koordinatni osi med III in IV kvadrantom

Če je točka.x = Xc in točka.y< Yc

Toč.kot ← 3p/2

# Če točka leži strogo v četrtem kvadrantu

Če točka.x > Xc in točka.y< Yc

Temelj ← |točka.y - Yc|

Pravokotna ← |točka.x – Xc|

Point.angle ← 3p/2 + arctg (pravokotno/temelj)

Očitno je, da ima časovna značilnost določanja vrednosti polarnega kota za začetni niz koordinat točk obliko O(N), torej T 9 (n) = O(N).

Kot je prikazano v , ima razvrščanje z združevanjem časovno odvisno obliko O(N), zato je T 10 (n) = O(NlnN).

Shema za izdelavo roba, ki povezuje točke prvotnega niza, je prikazana na sl. štiri.

Psevdokoda za zgornjo shemo bi bila videti takole:

za i ← 0 do dolžine (točke) – 1

Risanje(Xc,Yc,Točke[i].x, Točke[i].y)

Tudi časovni odziv je linearen, zato je T 11 (n) = O(N).

Dopolnitev nastale triangulacije v konveksno se izvede po Grahamovem algoritmu. Vhodni podatek postopka je množica točk Q, kjer je |Q|≥3. Pokliče funkcijo Top(S), ki vrne točko na vrhu sklada S, ne da bi spremenila njegovo vsebino. Poleg tega se uporablja tudi funkcija NextToTop(S), ki vrne točko, ki se nahaja na skladu S, eno pozicijo pod zgornjo točko; sklad S se ne spremeni.

Graham (Q)

Naj bo p 0 točka iz množice Q z minimalno koordinato.

Naj bodo ‹p 1 , p 2 ,...,p N › razvrščene točke množice Q

V naraščajočem vrstnem redu polarnega kota.

Potisni(p 0,S)

Potisni (p 1, S)

za i=2 do N do

Medtem ko je kot, ki ga tvorijo točke NextToTop(S), Top(S) in pi,

Oblikujte nelevi zavoj

# pri gibanju vzdolž lomljene črte, ki jo tvorijo

# točk, gibanje se izvaja neposredno ali v desno

Naredi Pop(S)

Push(pi,S)

vrnitev S

Čas delovanja Grahamove procedure je O(NlnN), kjer je N=dolžina(Q). Kako preprosto je pokazati, da bo zanka while trajala O(N) časa, razvrščanje polarnih kotov pa O(NlnN) časa, kar implicira splošno asimptotiko Grahamovega postopka, torej T 12 (n) = O( NlnN).

Obnovitvena časovna značilnost triangulacije, ki izpolnjuje Delaunayjev pogoj, kot je prikazano v , ima linearno odvisnost O(N), torej T 13 (n) = O(N).

Če v izraz (3) nadomestimo vse najdene časovne značilnosti, bo nastala časovna odvisnost videti takole:

T(n) = c 1 +c 2 +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)

Teoretična analiza časovnih značilnosti modificiranega algoritma Delaunayeve triangulacije potrjuje operabilnost in visoko hitrost predlaganega algoritma.

zaključki

Kot rezultat primerjalne analize praktično zahtevanih algoritmov Delaunayeve triangulacije je prikazano, da obravnavane metode ne izpolnjujejo zahtev za konstrukcijo dinamičnih tridimenzionalnih objektov v realnem času z vnaprej določeno stopnjo podrobnosti, zato obstaja praktična potreba po njihovi spremembi. Predlagana je modifikacija pahljačastega dvoprehodnega Delaunayjevega triangulacijskega algoritma, katerega funkcionalna značilnost je izračun vrednosti masnega središča niza koordinat triangulacijskih točk z razdelitvijo niza točk na podmnožice vzdolž Osi X in Y. Narejena je analiza časovnih karakteristik modificiranega algoritma Delaunayeve triangulacije. Ti izračuni omogočajo bistveno izboljšanje zmogljivosti na velikem nizu točk pri določanju koordinat masne točke in se izognejo prelivanju podatkov in s tem napakam pri implementaciji programske opreme.

1. Knut D.E. Umetnost programiranja. Zvezek 1. Osnovni algoritmi. – M.: Williams, 2008. – 680 str.
2. Knut D.E. Umetnost programiranja. Zvezek 3. Razvrščanje in iskanje. – M.: Williams, 2008. – 800 str.
3. Mandelbrot B. Fraktalna geometrija narave. - M .: Inštitut za računalniške raziskave, 2002. - 656 str.
4. Skvortsov A. V. Delaunayeva triangulacija in njena uporaba. - Tomsk: Založba Univerze v Tomsku, 2002. - 128 str.
5. Skvorcov A.V. Konstrukcija Delaunayeve triangulacije v linearnem času. - Tomsk: Založba Univerze v Tomsku, 1999. - Str. 120-126.
6. Skvortsov A.V., Mirza N.S. Algoritmi za konstruiranje in analizo triangulacije. - Tomsk: Založba Univerze v Tomsku, 2006. - 168 str.
7. Thomas H. Cormen, Charles I. Leiseron, Ronald L. Rivest, Clifford Stein. Algoritmi: konstrukcija in analiza, 3. izd.: Per. iz angleščine. – M.: Williams, 2013. – 1328 str.
8. Shaydurov V.V. Večmrežne metode končnih elementov. – M.: Nauka, 1989. – 288 str.
9. Sturges H. (1926). Izbira razrednega intervala. J.Amer. statist. izr., 21, 65-66.

Ključne besede: virtualna resničnost, triangulacija na danem nizu točk, Delaunayeva triangulacija, konstrukcija dinamičnih tridimenzionalnih objektov.

Modificirani Delaunayev triangulacijski algoritem

Teplov A.A., Bachelor, MSTU Bauman, Oddelek za "Programsko opremo in informacijske tehnologije", Moskva, [e-pošta zaščitena]

Maikov K.A., doktor tehničnih znanosti, profesor, MSTU Bauman, Oddelek za "Programsko opremo in informacijske tehnologije", Moskva, [e-pošta zaščitena]

povzetek: V tem članku so opisani rezultati primerjalne analize praktično priljubljenih metod Delaunayeve triangulacije z visoko zmogljivostjo in nizko porabo virov. Utemeljena je izbira metode za nadaljnjo posodobitev s ciljem gradnje dinamičnih 3-D objektov v realnem času z določeno stopnjo podrobnosti. Modificirana je ena od glavnih stopenj fibered dvoprehodnega algoritma Delaunayeve triangulacije. Obstaja predlog algoritma za intervalno razdelitev niza celic triangulacije v skladu z gostoto porazdelitve, ki omogoča izogibanje napakam pri strojni izvedbi.

ključne besede: navidezna resničnost, triangulacija na danem nizu celic, Delaunayeva triangulacija, gradnja dinamičnih 3-D objektov.

V stiku z

Na splošno vsi algoritmi temeljijo na zelo preprosti ideji zaporednega dodajanja točk v delno zgrajeno Delaunayjevo triangulacijo. Formalno je to videti takole.

Podan niz N točk.

1. Na prvih treh izhodiščih zgradimo en trikotnik.

2. V ciklu za n za vse druge točke izvedite korake 3-5.

3. Naslednjo n-to točko dodamo že zgrajeni triangulacijski strukturi na naslednji način. Najprej je točka lokalizirana, tj. obstaja trikotnik (zgrajen prej), v katerega pade naslednja točka. Če pa točka ne sodi znotraj triangulacije, je na meji triangulacije trikotnik, ki je najbližje naslednji točki.

4. Če točka zadene predhodno vstavljeno triangulacijsko vozlišče, se taka točka običajno zavrže, sicer pa se točka vstavi v triangulacijo kot novo vozlišče. Poleg tega, če točka zadene rob, se razdeli na dva nova, oba trikotnika, ki mejita na rob, pa se prav tako razdeli na dva manjša. Če je točka strogo znotraj katerega koli trikotnika, je razdeljena na tri nove. Če je točka zunaj triangulacije, je zgrajen en ali več trikotnikov.

5. Izvedejo se lokalni pregledi novo pridobljenih trikotnikov glede skladnosti z Delaunayevim pogojem in izvedejo se potrebne preureditve.

Konec algoritma.

Spodaj je podroben opis več algoritmov.

Pohlepni algoritem

Eden prvih je predlagal naslednji algoritem za konstrukcijo triangulacije.

Pohlepna metoda To je metoda, ki nikoli ne razveljavi že narejenega. Naslednji koraki se v algoritmu izvajajo zaporedno.

1. Konci vseh strukturnih segmentov so postavljeni v niz začetnih točk.

2. Generirajo se segmenti, ki povezujejo vse pare točk, segmenti so razvrščeni po dolžini.

3. Vsi segmenti lomne črte so vstavljeni v triangulacijo.

4. Segmenti so zaporedno izbrani za triangulacijo iz množice segmentov, razvrščenih po dolžini (od krajših k daljšim). Če se segment seka s katerim od že vstavljenih, se ga zavrže, sicer pa se vstavi v triangulacijo.

4. korak se ponavlja, dokler ne zmanjka segmentov.

Upoštevajte, da če imajo vsi možni segmenti različne dolžine, je rezultat tega algoritma nedvoumen, sicer pa je odvisen od vrstnega reda vstavljanja segmentov enake dolžine.

Triangulacija se imenuje požrešna, če je zgrajena s pohlepnim algoritmom.

Algoritem "Izbriši in zgradi"

Delete and Build ne izvaja nobenih ponovnih gradenj. Namesto tega se z vsako vstavitvijo novega vozlišča (a) takoj izbrišejo vsi trikotniki, v katerih novo vozlišče (b) pade znotraj opisanih krogov. V tem primeru vsi oddaljeni trikotniki implicitno tvorijo določen poligon. Nato se namesto izbrisanih trikotnikov zgradi triangulacija polnila s povezavo novega vozlišča na ta poligon (slika c).

riž. 4. Algoritem "Izbriši in zgradi"

Ta algoritem zgradi vse potrebne trikotnike naenkrat, v nasprotju z običajnim iterativnim algoritmom, kjer je pri vstavljanju enega vozlišča možno večkratno obnavljanje istega trikotnika. Vendar pa tukaj pride v ospredje postopek za ekstrakcijo konture oddaljenega poligona, od njegove učinkovitosti je odvisna skupna hitrost algoritma. Na splošno lahko ta algoritem, odvisno od uporabljene strukture podatkov, traja manj časa kot algoritem z vnovičnimi izgradnjami in obratno.

Algoritem "Build by breaking"

Algoritem za vstavljanje strukturnih segmentov "Build by breaking" je najenostavnejši pri izvedbi in stabilen pri delovanju.

V njem je potrebno zaporedno skozi trikotnike vzdolž vstavljenega segmenta najti točke njegovega presečišča z robovi triangulacije. Na teh presečiščih morate postaviti nova triangulacijska vozlišča, tako da obstoječe robove in trikotnike razdelite na dele. Po tem je treba vse na novo zgrajene trikotnike preveriti glede Delaunayjevega pogoja in jih po potrebi ponovno zgraditi, ne da bi to vplivalo na fiksne robove.

riž. 5. Algoritem "Build by breaking"

V nekaterih primerih je lahko pomanjkljivost tega algoritma vstavljanja ustvarjanje velikega števila dodatnih triangulacijskih vozlišč in robov. Hkrati pa v drugih primerih ta pomanjkljivost postane prednost, saj preprečuje nastanek dolgih ozkih trikotnikov, kar je še posebej cenjeno pri modeliranju terena.

Druga prednost tega algoritma vstavljanja v primerjavi z nadaljnjimi se pojavi pri poskusu vstavljanja strukturnega segmenta v triangulacijo, v kateri so med robovi, ki jih seka, fiksni robovi. Takšne robove, tako kot vse druge, preprosto razdelimo na dva dela.

Algoritem z indeksiranjem središč trikotnikov k-D - drevo

V triangulacijskem algoritmu s k-D-drevesnim indeksiranjem središč trikotnikov so v k-D-drevo postavljena samo središča trikotnikov (za k = 2). Pri brisanju starih trikotnikov je potrebno odstraniti njihova središča iz k-D-drevesa, pri gradnji novih pa jih je potrebno vpisati.

Za iskanje trikotnika, ki vsebuje trenutno točko, vstavljeno v triangulacijo, je treba izvesti nestandardno točkovno poizvedbo k k-D-drevu. Iskanje na drevesu se mora začeti pri korenini in se spustiti do listov. Če potomci trenutnega vozlišča k-D-drevesa (pravokotnik, ki obdaja potomce) ne pokrivajo trenutne točke, je treba za nadaljnje spuščanje po drevesu izbrati potomca, ki je najbližji iskalni točki.

Kot rezultat bo najden nek trikotnik, katerega središče bo blizu dane točke. Če podana točka ne sodi v najdeni trikotnik, potem je treba nadalje uporabiti običajni algoritem iskanja trikotnika iz preprostega iterativnega algoritma za konstrukcijo Delaunayeve triangulacije.

Triangulacija je aproksimacija površine simuliranega predmeta s trikotnimi ploščami, odmaknjenimi od nje na razdalji, ki ne presega določene določene vrednosti 6. Vse trikotne plošče morajo biti med seboj spojene. Njihovi vrhovi ležijo na površini. S kompletom trikotnih plošč je lažje delati kot s splošno površino. Trikotne plošče bomo imenovali trikotniki. Za trikotnik se hitro izračuna razdalja do dane točke ali presečišča z dano premico v prostoru. Triangulacija obrazov se izvaja za vizualno zaznavo geometrijskega modela, zato so stranice trikotnikov izbrane tako, da oko ne opazi prelomov.

Pri prikazu geometrijskih objektov s trikotniki na parametričnih ravninah površin je treba zgraditi prostorsko triangulacijo ploskev telesa z izračunom niza točk v prostoru in niza normal na ploskve telesa v teh točkah z uporabo niza dveh dimenzionalne točke Za hiter prikaz teles so njihovi obrazi aproksimirani s trikotnimi ploščami, zgrajenimi na točkah. Za določitev obnašanja svetlobnih žarkov, ki medsebojno delujejo s telesnimi obrazi, so potrebne normale. Tonski vzorci v prejšnjih poglavjih in v tem poglavju so izdelani s triangulacijo.

Kot rezultat površinske triangulacije želimo imeti niz dvodimenzionalnih točk na parametrični ravnini in niz trojk celih števil, ki so števila točk v prvem omenjenem nizu. Tako bo vsak trikotnik predstavljen s svojimi tremi številkami oglišč v nizu parametrov. Za vsako dvodimenzionalno točko parametrične domene je mogoče izračunati prostorsko točko na površini in normalo površine v njej. Prostorske točke in normale je mogoče shraniti v polja, podobna nizu 2D točk.

Oglejmo si nekaj metod triangulacije. Za ravne površine obstajajo ekonomične metode triangulacije, pri katerih so trikotniki zgrajeni na mejnih točkah površine in ni potrebno iskati točk znotraj parametričnega območja.

Delaunayeva triangulacija.

Razmislite o območju na letalu. Območje se imenuje konveksno, če se mora pri premikanju vzdolž njegove meje obrniti samo v eno smer (samo v levo ali samo v desno). Delaunayev algoritem lahko uporabite za triangulacijo konveksnih ravninskih regij. Tega algoritma ne bomo mogli neposredno uporabiti za triangulacijo površin proste oblike, ampak bomo uporabili njegovo metodo konstruiranja trikotnikov.

riž. 9.7.1. Konveksno območje z danimi točkami znotraj

Naj bo podano neko konveksno dvodimenzionalno območje, ki ga omejuje sklenjena lomljena črta in niz točk znotraj tega območja (slika 9.7.1).

Določeno območje je treba razdeliti na trikotnike, katerih oglišča so dane točke znotraj območja in oglišča poličrte, ki ga omejuje. Trikotnika se ne smeta prekrivati, stranice pa se lahko sekata le v ogliščih.

Sestavite lahko več različnih nizov trikotnikov, ki zapolnijo določeno območje. V vseh primerih je število trikotnikov , kjer je K število oglišč omejujoče poličrte, I je število danih točk znotraj območja.

riž. 9.7.2. Izbira tretje točke Delaunayevega algoritma

Domenska triangulacija bo Delaunayeva triangulacija, če znotraj opisanega kroga okoli vsakega trikotnika ni oglišč drugih trikotnikov. Delaunayeva triangulacija gradi trikotnike čim bližje enakokotnim (ne dovoljuje konstrukcije nerazumno podaljšanih trikotnikov).

Lahko ga imenujete uravnoteženo. Delaunayeva triangulacija bo edinstvena, če nobena štiri oglišča ne ležijo na istem krogu.

Razmislite o Delaunayevi triangulaciji. Oglišča poličrte, ki omejuje območje, in dane točke znotraj območja se imenujejo triangulacijska oglišča. Stranice trikotnikov bomo imenovali robovi. Med robovi izberemo segmente omejevalne človeške črte, ki jih bomo imenovali mejni robovi. Usmerimo vse mejne robove tako, da bo konveksno območje ležalo levo od vsakega roba. Naj bo treba sestaviti trikotnik, katerega stranica je mejni rob AB, prikazan na sl. 9.7.2.

Skozi oglišča A, B in vsako oglišče, ki z njima ne leži na isti premici, lahko narišemo krog. Za tretje oglišče trikotnika izberemo oglišče V, ki mu ustreza krožnica ne vsebuje drugih oglišč na isti strani glede na odsek AB, na katerem leži točka V. V splošnem primeru je eno tako oglišče lahko najdete za mejni rob. Recimo mu najbližji. Središče krožnice, ki poteka skozi točke A, B in V, leži v presečišču navpičnic na razpolovišča odsekov AB, BV in VA. Položaj središča kroga bo označen s parametrom t odseka MN, ki je pravokoten na rob AB, enak po dolžini z njim in poteka skozi sredino roba AB.

riž. 9.7.3. Delaunayev triangulacijski proces

Za vsa oglišča levo od segmenta AB ima najbližje oglišče najmanjši parameter t. Krog, ki ustreza najbližji točki, ne vsebuje drugih tock levo od odseka AB. Naj bodo vozlišča A, B in V opisana z dvodimenzionalnimi radijskimi vektorji. Radijska vektorja razpolovišč odsekov AB in BV bosta enaka

Vrednost parametra t premice, ki ustreza položaju na njej središča kroga, ki poteka skozi točke A, B in V, je enaka

Za oglišče, ki je najbližje levi odseku AB, ima parameter t minimalno vrednost.

Usmerite vse mejne robove tako, da območje, ki ga želite triangulirati, leži levo od vsakega od njih. Trikotnike začnemo sestavljati s poljubnega mejnega roba. Poiščite mu najbližje vozlišče, katerega ustrezni krog ne vsebuje drugih vozlišč. Za mejni rob AB najdemo najbližje oglišče V. Nato sestavimo trikotnik ABV in rob AB pretvorimo v kategorijo neaktivnih. Poklicali bomo neaktivne robove in oglišča, ki ne sodelujejo v triangulacijskem algoritmu. Če med mejnimi robovi ni roba BV, zgradimo nov robni rob na segmentu VB. Če je med mejnimi robovi rob BV, ga skupaj z ogliščem B prenesemo v kategorijo neaktivnih. Če med mejnimi robovi ni roba VA, zgradimo nov robni rob na odseku AV. Če je med mejnimi robovi rob VA, ga skupaj z ogliščem A prenesemo v kategorijo neaktivnih. Postopek triangulacije je prikazan na sl. 9.7.3.

riž. 9.7.4. Delaunayeva triangulacija

Triangulacija je končana, ko postanejo vsa oglišča in robovi neaktivni. Rezultat triangulacije danega območja je prikazan na sl. 9.7.4.

Triangulacija s korekcijsko metodo.

Oglejmo si triangulacijo neke ploskve s pravokotno domeno definiranja parametrov.Razdelimo področje definiranosti površinskih parametrov na pravokotne celice z dvodimenzionalnimi črtami.Te črte tvorijo pravokotno mrežo. Parametrične razdalje med sosednjimi črtami v skladu s formulo (9.4.7) vzamemo enake

Vzamemo parametrske razdalje med sosednjimi črtami v skladu s formulo (9.4.8), ki je enaka

S konstruiranjem diagonal v vseh pravokotnih celicah dobimo triangulacijo površja (dobimo množico trikotnikov, ki zadošča zahtevam). Na sl. 9.7.5 prikazuje triangulacijo vrtilne površine na opisan način.

Razmislite o triangulaciji ploskve s poljubno mejo. Triangulacijsko metodo gradimo na popravku z mejnimi konturami zgoraj opisane triangulacije površja s pravokotno domeno definicije parametrov.

riž. 9.7.5. Triangulacija ploskve s pravokotno domeno parametrov

Naj bo meja površine v domeni definiranja parametrov opisana z več nesekajočimi se dvodimenzionalnimi konturami (2.12.7). Ena od kontur je zunanja in vsebuje ostale konture. Za pozitivno smer za vsako konturo vzamemo smer, pri premikanju po kateri je območje definiranosti površine vedno levo od konture, če gledamo proti normali površine. Zgradimo poligone v pozitivni smeri mejnih obrisov območja definiranja površine. Za gradnjo mejnih poligonov je potrebno z določenim spremenljivim korakom iti vzdolž mejnih kontur površine in zapolniti niz dvodimenzionalnih točk, katerih koordinate so parametri površine. Poligon bomo zgradili iz točk na parametrični ravnini, vendar bo korak pri premikanju iz ene točke v drugo določen iz prostorske geometrije, in sicer iz pogoja, da odklon krivuljnega loka med sosednjima točkama ne bo večji od dano vrednost. Parametrični koraki za konstrukcijo poligona za krivuljo mejne konture površine se izračunajo po formuli (9.4.4).

Vsak poligon je sestavljen iz urejenega nabora 2D točk. Vsak odsek poligona si lahko predstavljamo kot 2D odsek ravne črte, zgrajen na dveh sosednjih točkah. Takšne odseke bomo uporabili kot mejne robove, točke poligonov, na katerih robovi temeljijo, pa kot triangulacijska oglišča. Ker leži področje definiranja površinskih parametrov levo od mejnih poligonov, je treba pri konstruiranju trikotnikov za vsak mejni rob triangulacije iskati tretje oglišče trikotnika levo od roba.

Določimo, katera vozlišča ležijo znotraj mejnih poligonov in katera na meji ali izven območja definicije površine. Z uporabo teh informacij razvrstimo celice pravokotne mreže v dve skupini. V prvo skupino sodijo celice, ki so v celoti v domeni definiranja površinskih parametrov (celice se ne smejo dotikati mejnih poligonov). Druga skupina vključuje preostale celice (ležijo izven območja definiranosti površine ali jih presekajo mejni poligoni).

riž. 9.7.6. Nedokončana površinska triangulacija

Znotraj vsake celice prve skupine bomo s pomočjo diagonale zgradili dva trikotnika. Tako dobimo nedokončano triangulacijo. Primer konstruiranja trikotnikov v celicah prve skupine za vrtilno površino, omejeno s konturami, je prikazan na sl. 9.7.6.

Na nesekanih straneh celic druge skupine zgradimo mejne robove in jih usmerimo tako, da je ustrezna celica levo od roba. Okoli celic prve skupine zgradimo sklenjeno poličrto (možnih je več sklenjenih črt), tako da pri premikanju po njej del območja, ki ni razdeljen na trikotnike, leži na levi, če gledamo proti normali površine. Ravni odseki te poličnije bodo uporabljeni tudi kot mejni robovi. Upoštevali bomo, da so vsi robovi enakopravni. Za dokončanje triangulacije moramo zgraditi trikotnike med mejnimi robovi. Za vsak rob bomo poiskali oglišče, ki leži levo od njega in iz njega lahko zgradimo trikotnik. Oglišče bomo iskali samo med tistimi oglišči, ki ležijo v isti celici z robom. Za izbiro vozlišča uporabimo Delaunayjevo metodo, opisano zgoraj in prikazano na sl. 9.7.2. Če takšno oglišče najdemo, je treba preveriti, ali se dva nova robova trikotnika sekata s katerimkoli mejnim robom. Za mejni rob AB najdemo najbližje oglišče V in preverimo, da odseka BV in VA ne sekata drugih mejnih robov. Nato sestavimo trikotnik ABV in rob AB prenesemo v kategorijo neaktivnih. Če med mejnimi robovi ni roba BV, bomo zgradili nov robni rob na segmentu VВ, če pa je med robnimi robovi rob BV, ga bomo skupaj z ogliščem B prenesli v kategorijo neaktivnih . Če med mejnimi robovi ni roba VA, potem na odseku AV zgradimo nov robni rob, če pa je med robnimi robovi rob VA, ga skupaj z ogliščem A prenesemo v kategorijo neaktivnih.

Če segment ali VA seka druge mejne robove, potem nadaljujemo z iskanjem najbližjega oglišča za drug mejni rob. Triangulacija bo končana po prenosu vseh robov in oglišč v neaktivno kategorijo.

riž. 9.7.7. Triangulacija s korekcijsko metodo

Na sl. 9.7.7 prikazuje triangulacijo površine z metodo korekcije trikotnikov v celicah, ki jih prečkajo mejne konture. Na sl. 9.7.8 s pomočjo dobljene triangulacije se prikaže samo površje.

Če imajo mejni poligoni in površje nekaj simetrije, bo imela tudi korekcijska triangulacija podobno simetrijo.

Triangulacija z absorpcijsko metodo.

Razmislite o drugi metodi triangulacije. Po hitrosti je slabša od Delaunayeve triangulacije in njenih modifikacij. Za začetek postopka triangulacije je potrebno mejo površja predstaviti v obliki zaprtih poligonov. V procesu triangulacije bomo morali določiti korake na parametrih površine. Pri znani smeri gibanja so ti koraki določeni s formulami (9.4.6). Približne korake površinskih parametrov najdete na naslednji način. Določimo območje na ravnini parametrov okoli določene točke tako, da noben prostorski segment od točke do točke v tem območju ne bo oddaljen od površine največ dane vrednosti S.

Da bi to naredili, izračunamo dovoljene prirastke parametrov vzdolž koordinatnih črt

kjer sta koeficienta prve in druge kvadratne oblike ploskve v točki . Za mejo želenega območja vzamemo elipso s središčem v točki in polose. Ta elipsa ima enačbo

Če je potrebno najti točko na ravnini poleg točke v smeri, ki jo daje kot z osjo in , potem bodo njeni parametri

Najprej razmislimo o enostavnejšem primeru, ko je območje površinskih parametrov omejeno z eno zunanjo konturo. Mejo površja aproksimiramo z zaprtim poligonom na parametrični domeni. Pri izdelavi triangulacije bomo uporabili delovni poligon, za katerega bomo v tem primeru vzeli poligon zunanje konture. Točke poligona bodo vnesene v nastali niz dvodimenzionalnih točk. Z roba delovnega poligona bomo zgradili trikotnike in ga ožili, dokler v delovnem poligonu ne bodo ostale samo tri točke.

Poiščite oglišče v delovnem poligonu, na katerem se obrne znotraj območja. Takšna točka vedno obstaja in vrtilni kot v njej je manjši od . Označimo to točko skozi O in njene parametre - skozi Okoli te točke bomo zgradili enega ali dva trikotnika, odvisno od kota vrtenja. Če je kot manjši, bomo na teh treh točkah zgradili en trikotnik (slika 9.7.9). V nasprotnem primeru sestavimo dva trikotnika na dani, dve sosednji in eno novo točko (slika 9.7.11). Novo točko označimo s P. Točko P bomo iskali na diagonali paralelograma B OS P. Če leži oglišče paralelograma znotraj elipse (slika 9.7.10), jo bomo vzeli za točko P. V nasprotnem primeru bomo za točko P vzeli presečišče elipse in diagonale paralelograma. V slednjem primeru sploh ni treba iskati presečišča elipse in segmenta.

Koordinate točke P so določene preko koordinat točk O VS

Kot odseka OR z vodoravno je določen z enakostjo

(9.7.8)

Ti podatki omogočajo določitev položaja točke P glede na elipso (9.7.5).

V primeru, prikazanem na sl. 9.7.9, zgradite trikotnik (zapomnite si številke njegovih vrhov) in v delovnem mnogokotniku izbrišite točko O. V primeru, prikazanem na sl. 9.7.11, zgradite dva trikotnika in zamenjajte točko O v delovnem poligonu s točko P in slednjo postavite v nastali niz točk. Na sl. 9.7.12 prikazuje poligon, dobljen po konstruiranju dveh trikotnikov in izločitvi točke O. V obeh primerih bo točka O odstranjena iz delovnega poligona in delovni poligon se bo zožil. Upoštevajte, da je trikotnike mogoče zgraditi le, če delovni poligon po zožitvi ne bo sekal samega sebe.

riž. 9.7.9. Konstrukcija trikotnika

riž. 9.7.10. Poligon rezultatov

riž. 9.7.11. Konstrukcija dveh trikotnikov

riž. 9.7.12. Poligon rezultatov

Takšne situacije so prikazane na sl. 9.7.13. Pojavijo se lahko, ko stranice zgrajenih trikotnikov sekajo stranice delovnega mnogokotnika, ki jim niso sosednje. Preden zgradite nov trikotnik, kot je prikazano na sl. 9.7.9, in v primeru, prikazanem na sl. 9.7.11 je treba preveriti odsotnost samopreseka dobljenega poligona.

Poleg tega je pri določanju položaja točke P pomembno, da je dovolj oddaljena od drugih točk delovnega poligona in se ne približuje segmentom, ki povezujejo točke poligona. V nasprotnem primeru se lahko v prihodnosti pojavijo težave pri konstruiranju trikotnikov. Zato morate pred zoženjem delovnega poligona preveriti nastali poligon za samopresek. Če trikotnika (trikotnikov) ni mogoče zgraditi v bližini točke O, potem namesto nje poiščite drugo točko, v kateri se mnogokotnik ovije več kot drugi znotraj konture, in v njej izvedite opisana dejanja.

Nato bomo s spremenjenim delovnim poligonom izvedli ista dejanja, ki smo jih pravkar opisali. V delovnem poligonu poiščemo točko, v kateri se obrača znotraj območja bolj kot v drugih točkah, preverimo možnost zožitve poligona v njej s konstrukcijo enega ali dveh trikotnikov in poligon zožimo.

riž. 9.7.13. Trikotniki v tem kotu niso dovoljeni.

Z nadaljevanjem tega procesa bomo razširili niz dvodimenzionalnih točk in niz trikotnikov, hkrati pa bomo zožili delovni poligon, zmanjšali površino, ki jo pokriva, in število njegovih točk. Na neki stopnji teh dejanj bomo dobili delovni poligon, sestavljen iz treh točk. Na teh točkah zgradimo zadnji trikotnik, odstranimo delovni poligon in zaključimo triangulacijo. Pri opisani metodi triangulacije območje, omejeno z delovnim poligonom, tako rekoč izločimo tako, da iz njega odrežemo trikotnike.

Razmislimo o splošnem primeru, ko je območje površinskih parametrov omejeno z eno zunanjo konturo in več notranjimi konturami, ki v celoti ležijo znotraj zunanje konture. Mejo površja aproksimiramo z zaprtimi poligoni na parametrični domeni. Za vsako konturo bomo zgradili svoj poligon. Tako kot za obrise mora biti tudi za na njih zgrajene poligone izpolnjeno pravilo njihove medsebojne usmerjenosti. Usmerjenost notranjih mnogokotnikov mora biti nasprotna usmerjenosti zunanjega poligona. Začnimo graditi triangulacijo s poligonom zunanje konture. Postavimo njegove točke v nastali niz dvodimenzionalnih točk in poskrbimo, da poligon sam deluje.

Trikotnike sestavljamo na enak način kot v primeru preprosto povezane regije. V delovnem poligonu poiščemo točko O, v njej preverimo možnost zožitve delovnega poligona in poligon zožimo. Če obstajajo notranji konturji, je težje preveriti možnost zožitve delovnega poligona na izbrani točki. Poleg opisanih preverjanj presečišča stranic trikotnikov s stranicami delovnega mnogokotnika morate preveriti presečišče stranic trikotnikov s stranicami vseh notranjih mnogokotnikov.

Preverimo možnost konstruiranja dveh trikotnikov v točki O (slika 9.7.11) in ugotovimo, da bo nova točka P, ki jo konstruiramo, padla znotraj enega od notranjih mnogokotnikov ali pa bo v nesprejemljivo blizu njegovih segmentov . V tem primeru ne bomo zgradili točke P, temveč bomo ta notranji poligon vključili v delovni poligon s konstrukcijo dveh trikotnikov, prikazanih na sl. 9.7.14.

Za vključitev točk enega od notranjih poligonov v delovni poligon poiščemo med točkami notranjega poligona točko, ki je najbližja točki C (meji na točko O) delovnega poligona.

Zgradimo trikotnike na točkah OCF in CEF in med točki O in C delovnega poligona vstavimo točke notranjega poligona, začenši s točko F in konča s točko E. Tako bomo delovni poligon razbili na segmentu OS, prelomi notranji poligon na odseku EF in ju združi z odsekoma OF in EU.

riž. 9.7.14. Konstrukcija dveh trikotnikov

riž. 9.7.15. Združevanje zunanjih in notranjih poligonov

Rezultat združitve je prikazan na sl. 9.7.15. Seveda je treba pred spajanjem zunanjega in notranjega mnogokotnika preveriti pravilnost te operacije.

Nadalje bomo delovni poligon ožili na opisan način, dokler se ne znajdemo v neposredni bližini drugega notranjega poligona in ga vključimo v delovni poligon. Posledično bodo vsi notranji poligoni vključeni v delovni poligon, ki naj bo zožen na zadnje tri točke. Posledično bo celotna večpovezana domena površinskih parametrov prekrita s trikotniki.

riž. 9.7.16. Trikotniki v tem kotu niso dovoljeni.

Obstajajo situacije, ko je na danih poligonih nemogoče zgraditi en sam trikotnik. Na sl. 9.7.16 prikazuje območje, omejeno z dvema poligonoma, od katerih je vsak sestavljen iz štirih segmentov. Za zunanji poligon ne moremo nadaljevati triangulacije, ker notranji poligon moti. V tem primeru najdemo dve sosednji točki B in C mnogokotnika, za kateri lahko sestavimo trikotnik VSR. Točka P je projicirana na sredino stranice BC in je od nje tako oddaljena, da novi trikotnik ne seka mnogokotnikov.

Druge metode triangulacije.

Obstajajo tudi drugi načini triangulacije. Na primer, po konstruiranju poligonov zunanjih in notranjih obrisov območja definicije površine je mogoče izbrati drugačno strategijo za konstruiranje trikotnikov. Druga možnost je, da združite zunanji in notranji poligon v en poligon, preden začnete s triangulacijo. Znotraj območja definiranja parametrov je možno »risati« točke po določenem algoritmu in z njihovo uporabo ter točkami poligonov mejnih kontur izvajati Delaunayevo triangulacijo. Obstajajo algoritmi, ki najprej zgradijo velike trikotnike in jih nato razdelijo na sprejemljive velikosti.

Triangulacija telesa.

Triangulacija telesa je množica trikotnikov, ki jih dobimo s triangulacijo površin njegovih ploskev. Triangulacija posameznih ploskev se od triangulacije telesnih ploskev razlikuje po tem, da je treba v slednjem primeru uskladiti mejne poligone za sosednje ploskve (slika 9.7.17).

riž. 9.7.17. Skladnost mejnih poligonov telesnih ploskev

Odseki mnogokotnikov sosednjih ploskev, ki potekajo vzdolž skupnih robov, bodo skladni, če njihove točke sovpadajo v prostoru.

Uporaba triangulacije.

Trikotniki, zgrajeni kot rezultat triangulacije, se uporabljajo za pridobivanje tonskih slik. Na sl. Sliki 9.7.18 in 9.7.19 prikazujeta triangulacije ploskve pločevine, katere tonska slika je prikazana na sl. 6.5.1.

riž. 9.7.18. Triangulacija obraza telesa s korekcijsko metodo

Razdelitev domene definicije površinskih parametrov na trikotnike se lahko uporabi v integralih (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) pri izračunu geometrijskih značilnosti telesa. Za numerično integracijo je treba parametrični korak za krivulje izračunati po formuli (8.11.5), za površine pa je treba izračunati parametrični korak po formulah (8.11.1) in (8.11.2).

Triangulacija za končno množico točk S je problem triangulacije konveksne lupine CH(S), ki zajema vse točke množice S. Odseki premice se med triangulacijo ne morejo sekati - srečajo se lahko le v skupnih točkah, ki pripadajo množici S. Ker je premica segmenti zaprejo trikotnike, jih bomo obravnavali kot robove. Na sl. 1 prikazuje dve različni varianti triangulacije za isto množico točk (na teh slikah narisane kroge bomo začasno zanemarili).

riž. eno

Glede na množico točk S vidimo, da lahko vse točke iz množice S razdelimo na mejne točke - tiste točke, ki ležijo na meji konveksne lupine CH(S), in notranje točke - tiste, ki ležijo znotraj konveksne lupine trup CH(S). Robove, ki jih dobimo kot rezultat triangulacije S, je mogoče razvrstiti tudi kot robovi lupine in notranja rebra. Robovi lupine vključujejo robove, ki se nahajajo vzdolž meje konveksne lupine CH(S), notranji robovi pa vključujejo vse druge robove, ki tvorijo mrežo trikotnikov znotraj konveksne lupine. Upoštevajte, da vsak rob lupine povezuje dve sosednji mejni točki, notranji robovi pa lahko povezujejo dve točki katere koli vrste. Še posebej, če notranji rob povezuje dve mejni točki, potem je to tetiva konveksne lupine CH(S). Upoštevajte tudi, da je vsak triangulacijski rob meja dveh regij: vsak notranji rob je med dvema trikotnikoma, vsak rob lupine pa je med trikotnikom in neskončno ravnino.

Vsak nabor točk, razen v nekaterih trivialnih primerih, omogoča več kot en način triangulacije. Toda hkrati obstaja izjemna lastnost: vsak način triangulacije za dano množico določa enako število trikotnikov, kar izhaja iz izreka:

Izrek o triangulaciji množice točk. Predpostavimo, da množica točk S vsebuje n>3 točk in niso vse kolinearne. Poleg tega je i točk iz njih notranjih (to pomeni, da ležijo znotraj konveksne lupine CH(S). Potem bomo za katero koli metodo triangulacije množice S dobili točno n + i - 2 trikotnika.

Za dokaz izreka najprej razmislimo o triangulaciji n-i mejnih točk. Ker so vsa oglišča konveksnega mnogokotnika, bo taka triangulacija povzročila (n - i) - 2 trikotnika. (Tega ni težko preveriti in poleg tega je mogoče dokazati, da vsaka triangulacija arbitrarna m-strani mnogokotnik - konveksen ali nekonveksen - vsebuje m - 2 trikotnika). Zdaj pa preverimo, kaj se bo zgodilo s triangulacijo, ko dodamo preostalih i notranjih točk, vsakokrat eno. Trdimo, da dodatek vsake take točke vodi do povečanja števila trikotnikov za dva. Pri dodajanju notranje točke lahko pride do dveh situacij, kot je prikazano na sl. 2. Najprej je lahko točka znotraj nekega trikotnika, nato pa se tak trikotnik nadomesti s tremi novimi trikotniki. Drugič, če točka sovpada z enim od robov triangulacije, se vsak od dveh trikotnikov, ki mejita na ta rob, nadomesti z dvema novima trikotnikoma. Iz tega sledi, da bo po seštevanju vseh r točk skupno število trikotnikov (n - i - 2) + (2i) ali samo n + i - 2.

riž. 2

V tem razdelku predstavljamo algoritem za generiranje posebne vrste triangulacije, znane kot Delaunayeva triangulacija. Ta triangulacija je dobro uravnotežena v smislu, da so oblikovani trikotniki ponavadi enakokotni. Na primer, triangulacija, prikazana na sl. 1a je mogoče pripisati vrsti Delaunayeve triangulacije, na sl. Triangulacija na sliki 1b vsebuje več močno podolgovatih trikotnikov in je ni mogoče pripisati Delaunayevemu tipu. Na sl. 3 prikazuje primer Delaunayeve triangulacije za množico velikega števila točk.

riž. 3

Za oblikovanje Delaunayeve triangulacije potrebujemo več novih definicij. Množica točk se šteje za krožno, če obstaja krog, na katerem ležijo vse točke množice. Takšen krog bo opisan za dano množico točk. Opisani krog trikotnika poteka skozi vsa tri njegova (nekolinearna) oglišča. Za krog pravimo, da je brez točk glede na dano množico točk S, če znotraj kroga ni točk iz množice S. Toda točke iz množice S se lahko nahajajo na krogu, ki je najbolj prost od točk.

Triangulacija množice točk S bo Delaunayeva triangulacija, če je opisani krog vsakega trikotnika brez točk. V triangulacijskem diagramu na sl. 1a prikazuje dva kroga, ki očitno ne vsebujeta drugih točk v sebi (lahko narišete kroge za druge trikotnike, da se prepričate, da so tudi brez točk v nizu). To pravilo ni upoštevano v diagramu na sl. 16 - ena točka drugega trikotnika je zašla znotraj narisanega kroga, zato ta graangulacija ne pripada Delaunayevemu tipu.

Za poenostavitev triangulacijskega algoritma lahko podamo dve predpostavki o točkah v množici S. Prvič, da triangulacija sploh obstaja, moramo predpostaviti, da množica S vsebuje vsaj tri točke in te niso kolinearne. Drugič, za edinstvenost Delaunayeve triangulacije je potrebno, da nobene štiri točke iz množice S ne ležijo na istem opisanem krogu. Zlahka je videti, da brez takšne predpostavke Delaunayeva triangulacija ne bo edinstvena, saj nam 4 točke na eni opisani krožnici omogočajo realizacijo dveh različnih Delaunayjevih triangulacij.

Naš algoritem deluje tako, da nenehno gradi trenutno triangulacijo en trikotnik naenkrat. Na začetku je trenutna triangulacija sestavljena iz enega samega roba lupine, po zaključku algoritma pa trenutna triangulacija postane Delaunayeva triangulacija. Pri vsaki ponovitvi algoritem išče nov trikotnik, ki se povezuje z meja trenutna triangulacija.

Opredelitev meje je odvisna od naslednje sheme klasifikacije robov Delaunayeve triangulacije glede na trenutno triangulacijo. Vsak rob je lahko spanje, živ oz mrtev:

• mirujoča rebra: rob Delaunayeve triangulacije miruje, če ga algoritem še ni odkril;
• živa rebra: rob je živ, če je najden, vendar je znano samo eno območje, ki meji nanj;
• mrtva rebra: rob se šteje za mrtvega, če je najden in sta znani obe sosednji regiji.

Sprva je edini rob, ki pripada konveksni točki i, živ - nanj meji neomejena ravnina, vsi ostali robovi pa so v mirovanju. Ko algoritem deluje, mirujoči robovi oživijo, nato pa odmrejo. Meja na vsaki stopnji je sestavljena iz niza živih robov.

Pri vsaki iteraciji je izbran kateri koli rob meje in je podvržen obdelavi, ki je sestavljena iz iskanja neznanega območja, ki mu pripada rob e. Če se izkaže, da je to območje trikotnik f, definiran s končnimi točkami rob e in neko tretje oglišče v, potem postane rob e mrtev, saj sta zdaj znani obe sosednji regiji. Vsak od ostalih dveh robov trikotnika t se prestavi v naslednje stanje: iz spečega v živo ali iz živega v mrtvo. Tukaj bo klicano oglišče v konjugat z robom e. V nasprotnem primeru, če se izkaže, da je neznano območje neskončna ravnina, potem rob e preprosto umre. V tem primeru rob e nima konjugiranega oglišča.

Na sl. 4 prikazuje delovanje algoritma, kjer se dejanje odvija od zgoraj navzdol in od zgoraj proti desni. Meja na vsaki stopnji je označena z debelo črto.

Algoritem je implementiran v programu delaunayTriangulate. Program dobi niz s n točk in vrne seznam trikotnikov, ki predstavljajo Delaunayevo triangulacijo. Izvedba uporablja razred obročnega seznama in razrede iz razdelka Strukture geometrijskih podatkov. Vsak slovar, ki podpira zahtevane operacije, je mogoče uporabiti kot razred Slovar. Na primer, lahko preglasite #define Dictionary RandomizedSearchTree.

Seznam * (Točka s, int n) ( Točka p; Seznam *trikotniki = nov seznam ; Slovar meja (edgeCmp); Rob *e = hullEdge(s, n); mejni vložek(e); medtem ko (!frontier.isEmpty()) ( e = frontier.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(frontier, p, e->org); updateFrontier(frontier, e ->dest, p); trikotniki->insert(triangle(e->org, e->dest, p)); ) izbriši e; ) vrni trikotnike; )

riž. štiri

Trikotniki, ki tvorijo triangulacijo, so zapisani na seznamu trikotnikov. Frontier je predstavljen s slovarjem mejnih živih robov. Vsak rob je usmerjen tako, da njegovo neznano območje (ki ga je treba določiti) leži desno od roba. Primerjalna funkcija edgeCmp se uporablja za iskanje slovarja. Primerja začetne točke dveh robov, če sta enaka, se primerjata njuni končni točki:

Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) vrni 1; če (a->org > b->org) vrne 1; če (a->dest< b->dest) return -1; if (a->dest > b->dest) vrni 1; vrni 0; )

Kako se torej meja spreminja od enega koraka do drugega in kako funkcija updateFrontier spremeni slovar robov obrobe, da odraža te spremembe? Ko na mejo pritrdimo nov trikotnik t, se spremenijo stanja treh robov trikotnika. Rob trikotnika t, ki meji na mejo, iz živega postane mrtev. Funkcija updateFrontier lahko prezre ta rob, saj mora biti ob klicu funkcije removeMin že odstranjen iz slovarja. Vsak od dveh preostalih robov trikotnika ne spremeni svoje stanje iz spečega v živo, če še nista zapisana v slovar, ali iz živega v mrtvo, če je rob že v slovarju. Na sl. 5 prikazuje oba primera. V skladu s sliko obdelamo živi rob af in ko ugotovimo, da je točka b z njim konjugirana, trenutni triangulaciji dodamo trikotnik afb. Nato poiščemo edge fb v slovarju in ker ga še ni in je prvič odkrit, se njegovo stanje spremeni iz spečega v živo. Za urejanje slovarja bomo zasukali rob fb tako, da bo neznana regija, ki meji nanj, ležala desno od njega, in ta rob zapisali v slovar. Potem bomo v slovarju našli rob ba - ker je v njem, je že živ (znano območje, ki meji nanj, je trikotnik abc). Ker je bilo pravkar odkrito njemu neznano območje, trikotnik afb, je ta rob odstranjen iz slovarja.

Funkcija updateFrontier ureja mejni slovar, v katerem se stanje roba spreminja od točke a do točke b:

riž. 5

Void updateFrontier(slovar &frontier, Point &a, Point &b) ( Edge *e = new Edge (a, b); if (frontier.find (e)) frontier.remove(e); else ( e->flip(); frontier.insert( e);))

Funkcija hullEdge najde rob lupine med n točkami matrike s. Ta funkcija dejansko uporablja korak inicializacije in prvo ponovitev metode zavijanja daril:

Rob *hullEdge (Točka s, int n) ( 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]); }

Funkcija trikotnika preprosto oblikuje in vrne poligon za tri točke, ki so ji bile posredovane kot parametri:

Mnogokotnik *trikotnik (Točka &a, Točka &b, Točka &c) ( Mnogokotnik *t = nov mnogokotnik; t->vstavi (a); t->vstavi (b); t->vstavi (c); vrni t; )

Za kvantifikacijo kakovosti izdelane triangulacije definiramo dve vrsti kriterijev, topološke in geometrijske.

Topološki kriterij temelji na najbližjih sosedih točke iz množice. V idealnem primeru ima točka 6 sosedov za 2D regijo in 12 sosedov za 3D regijo. Topološko oceno dobimo z uporabo formule (1), kjer je skupno število točk v regiji, je stopnja ali število sosednjih točk, povezanih z notranjo točko.

Geometrijsko merilo temelji na razliki med včrtanimi in opisanimi krogi okrog izračunanega trikotnega elementa. Geometrično oceno dobimo s formulo (2), kjer je število trikotnikov, je polmer včrtanega kroga, je polmer opisanega kroga.

Algoritmi za izdelavo triangulacije

Obstaja veliko število algoritmov za izdelavo triangulacije. Med seboj se razlikujejo po zahtevnosti, zahtevnosti izvedbe na računalniku in pristopih k gradnji. Več o algoritmih lahko izveste v knjigi A.V. Skvorcova. Razmislimo o nekaterih algoritmih.

Eden prvih predlaganih požrešen algoritem gradnjo triangulacije. Delaunayeva triangulacija se imenuje požrešna, če je zgrajena z uporabo pohlepnega algoritma. Kompleksnost pohlepnega algoritma z nekaterimi njegovimi izboljšavami je . Zaradi tako velike kompleksnosti se v praksi skoraj ne uporablja. Razmislite o algoritmu korak za korakom:

Korak 1. Ustvari se seznam vseh možnih odsekov črte, ki povezujejo pare izvornih točk in je razvrščen po dolžini odsekov.

2. korak Začenši z najkrajšim, se segmenti zaporedno vstavijo v triangulacijo. Če se segment ne seka z drugimi predhodno vstavljenimi segmenti, se vstavi, sicer se zavrže.

Upoštevajte, da če imajo vsi možni segmenti različne dolžine, je rezultat tega algoritma nedvoumen, sicer pa je odvisen od vrstnega reda vstavljanja segmentov enake dolžine.

Iterativni algoritem temeljijo na zelo preprosti ideji zaporednega dodajanja točk v delno zgrajeno Delaunayjevo triangulacijo. Kompleksnost tega algoritma je sestavljena iz kompleksnosti iskanja trikotnika, ki mu v naslednjem koraku dodamo točko, kompleksnosti konstruiranja novih trikotnikov, pa tudi kompleksnosti ustrezne ponovne izgradnje triangulacijske strukture kot posledice nezadovoljive preverjanja parov sosednjih trikotnikov nastale triangulacije za Delaunayev pogoj. Razmislite o algoritmu korak za korakom:

Korak 1. Na prvih treh izhodiščih zgradimo en trikotnik.

2. korak V zanki za vse druge točke izvedite korake 3-5.

3. korak Naslednjo -to točko dodamo že zgrajeni triangulacijski strukturi na naslednji način. Najprej je točka lokalizirana, tj. obstaja trikotnik (zgrajen prej), v katerega pade naslednja točka. Če pa točka ne sodi znotraj triangulacije, je na meji triangulacije trikotnik, ki je najbližje naslednji točki.

4. korakČe točka zadene predhodno vstavljeno triangulacijsko vozlišče, se taka točka običajno zavrže, sicer pa se točka vstavi v triangulacijo kot novo vozlišče. Poleg tega, če točka zadene rob, se razdeli na dva nova, oba trikotnika, ki mejita na rob, pa se prav tako razdeli na dva manjša. Če je točka strogo znotraj katerega koli trikotnika, je razdeljena na tri nove. Če je točka zunaj triangulacije, je zgrajen en ali več trikotnikov.

5. korak Izvedejo se lokalni pregledi na novo pridobljenih trikotnikov glede skladnosti z Delaunayevim pogojem in izvedejo se potrebne preureditve.

Pri konstruiranju novih trikotnikov sta možni dve situaciji, ko dodana točka pade znotraj ali zunaj triangulacije. V prvem primeru se konstruirajo novi trikotniki in število dejanj, ki jih izvede algoritem, je določeno. V drugem je treba zgraditi dodatne trikotnike zunaj trenutne triangulacije, njihovo število pa je lahko v najslabšem primeru enako? 3. Vendar pa za vse korake algoritma ne bodo dodani več kot trikotniki, kjer je skupno število začetnih točk. Zato je v obeh primerih skupni čas, porabljen za gradnjo trikotnikov.

Verižni algoritem eden prvih učinkovitih algoritmov za konstrukcijo triangulacije temelji na postopku regulacije ravninskega grafa in monotoni poligonski triangulaciji. Kompleksnost tega algoritma je, kjer je število začetnih segmentov. Razmislite o algoritmu korak za korakom:

Korak 1. Iz množice začetnih strukturnih segmentov oblikujemo povezan ravninski graf (slika 4, a).

2. korak Graf je regulariziran, tj. dodani so novi robovi, ki ne sekajo drugih, tako da vsako vozlišče grafa postane sosednje vsaj enemu vozlišču nad njim in enemu pod njim. Regulacija se izvede v dveh prehodih z navpičnim ravnim pomikom. Pri prvem prehodu od spodaj navzgor zaporedno poiščemo vsa oglišča, iz katerih navzgor ne vodijo robovi. Na primer, na (slika 4, b) je to točka B. Če narišemo vodoravno črto, najdemo najbližje robove grafov AD in EF, ki jih prečkata na levi in ​​desni. Nato poiščemo najnižje oglišče v štirikotniku DEHG in vanj narišemo rob iz B. Podobno se izvede drugi prehod od zgoraj navzdol (slika 4, c). Kot rezultat tega koraka postane vsako območje ravninskega grafa monoton poligon.

3. korak Vsako območje grafa je treba razdeliti na trikotnike. Če želite to narediti, lahko uporabite algoritem nekonveksnega združevanja dveh triangulacij (slika 4, d).

Slika 4. Shema delovanja algoritma triangulacijske verige: a) - začetni segmenti; b - prehod od spodaj navzgor regularizacije grafa; c) - prehod od zgoraj navzdol; d) - triangulacija monotonih mnogokotnikov

Za implementacijo verižnega algoritma je najbolje uporabiti podatkovne strukture, v katerih so robovi eksplicitno predstavljeni, kot so "Dvojni robovi" ali "Vozli, robovi in ​​trikotniki".

Pomanjkljivost verižnega algoritma je, da o obliki nastale triangulacije ni mogoče reči ničesar vnaprej. To ni optimalna triangulacija, ne požrešna in ne omejena Delaunayeva triangulacija. Verižni algoritem lahko ustvari zelo dolge podolgovate trikotnike.

Za izboljšanje kakovosti dobljene triangulacije je mogoče vse pare sosednjih trikotnikov, ki niso ločeni s strukturnim robom, preveriti glede izpolnjevanja Delaunayevega pogoja in jih po potrebi ponovno zgraditi. Kot rezultat bo pridobljena Delaunayeva triangulacija z omejitvami.