Për kuantifikimi Për cilësinë e trekëndëshit të ndërtuar do të përcaktojmë dy lloje kriteresh: topologjik dhe gjeometrik.

Kriteri topologjik bazohet në fqinjët më të afërt pikë nga grupi. NË në mënyrë ideale një pikë ka 6 fqinjë për një rajon dydimensional dhe 12 fqinjë për një rajon tredimensional. Ne marrim një vlerësim topologjik duke përdorur formulën (1), ku - sasinë totale pikat në një zonë, - shkalla ose numri i pikave fqinje të thurura me një pikë të brendshme.

Kriteri gjeometrik bazohet në ndryshimin midis rrathëve të brendashkruar dhe të rrethuar rreth elementit trekëndor të projektimit. Ne marrim një vlerësim gjeometrik duke përdorur formulën (2), ku është numri i trekëndëshave, është rrezja e rrethit të brendashkruar, është rrezja e rrethit të rrethuar.

Algoritme për ndërtimin e trekëndëshit

Ekziston një numër i madh algoritmesh për ndërtimin e trekëndëshit. Ato ndryshojnë në intensitetin e punës, kompleksitetin e zbatimit në një kompjuter dhe qasjet ndaj ndërtimit. Më shumë informacion rreth algoritmeve mund të gjeni në librin e A.V. Skvortsova. Le të shohim disa algoritme.

Një nga të parët që u propozua algoritmi i pangopur ndërtimi i trekëndëshit. Një trekëndëshim i Delaunay quhet lakmitar nëse ndërtohet duke përdorur një algoritëm të babëzitur. Kompleksiteti i algoritmit të babëzitur me disa nga përmirësimet e tij është . Për shkak të një intensiteti kaq të lartë të punës, pothuajse kurrë nuk përdoret në praktikë. Le të shohim algoritmin hap pas hapi:

Hapi 1. Një listë e të gjitha segmenteve të mundshme që lidhin çifte pikash burimore krijohet dhe renditet sipas gjatësisë së segmentit.

Hapi 2. Duke filluar me më të shkurtërin, segmentet futen në mënyrë sekuenciale në trekëndësh. Nëse një segment nuk kryqëzohet me segmente të tjera të futura më parë, atëherë ai futet, përndryshe hidhet.

Vini re se nëse të gjitha segmentet e mundshme kanë gjatësi të ndryshme, atëherë rezultati i këtij algoritmi është i paqartë, përndryshe varet nga rendi i futjes së segmenteve me të njëjtën gjatësi.

Algoritmi iterativ bazohen në shumë ide e thjeshtë shtimi sekuencial i pikave në trekëndëshin Delaunay të ndërtuar pjesërisht. Kompleksiteti të këtij algoritmi përbëhet nga kompleksiteti i kërkimit të një trekëndëshi, të cilit i shtohet një pikë në hapin tjetër, kompleksiteti i ndërtimit të trekëndëshave të rinj, si dhe kompleksiteti i rindërtimit përkatës të strukturës së trekëndëshit si rezultat i kontrolleve të pakënaqshme të çifteve të fqinjëve. trekëndëshat e trekëndëshit që rezulton për përmbushjen e kushtit Delaunay. Le të shohim algoritmin hap pas hapi:

Hapi 1. Ne ndërtojmë një trekëndësh në tre pikat e para të fillimit.

Hapi 2. Në ciklin për të gjitha pikat e tjera, kryeni hapat 3-5.

Hapi 3. Pika tjetër e i shtohet strukturës së trekëndëshit tashmë të ndërtuar si më poshtë. Së pari, pika lokalizohet, d.m.th. ekziston një trekëndësh (i ndërtuar më herët) në të cilin bie pika tjetër. Ose, nëse pika nuk bie brenda trekëndëshit, një trekëndësh ndodhet në kufirin e trekëndëshit, më afër pikës tjetër.

Hapi 4. Nëse një pikë bie në një nyje trekëndëshi të futur më parë, atëherë një pikë e tillë zakonisht hidhet, përndryshe pika futet në trekëndësh si një nyje e re. Për më tepër, nëse pika bie në ndonjë skaj, atëherë ajo ndahet në dy të reja, dhe të dy trekëndëshat ngjitur me skajin ndahen gjithashtu në dy më të vegjël. Nëse pika bie rreptësisht brenda një trekëndëshi, ajo ndahet në tre të reja. Nëse pika bie jashtë trekëndëshit, atëherë ndërtohen një ose më shumë trekëndësha.

Hapi 5. Bëhen kontrolle lokale të trekëndëshave të sapopërfituar për respektimin e kushtit Delaunay dhe kryhen rikonstruksionet e nevojshme.

Kur ndërtoni trekëndësha të rinj, dy situata janë të mundshme: pika e shtuar bie ose brenda trekëndëshit ose jashtë tij. Në rastin e parë ndërtohen trekëndësha të rinj dhe fiksohet numri i veprimeve të kryera nga algoritmi. Në të dytën, është e nevojshme të ndërtohen trekëndësha shtesë jashtë trekëndëshit aktual, dhe numri i tyre, në rastin më të keq, mund të jetë i barabartë me? 3. Megjithatë, gjatë të gjithë hapave të algoritmit nuk do të shtohen më trekëndësha, ku - numri total pikat e fillimit. Prandaj, në të dyja rastet, koha totale e shpenzuar për ndërtimin e trekëndëshave është.

Algoritmi i zinxhirit një nga algoritmet e para efektive për ndërtimin e trekëndëshit bazohet në procedurën e rregullimit të grafikut planar dhe trekëndimit të shumëkëndëshave monoton. Kompleksiteti i këtij algoritmi është se ku është numri i segmenteve fillestare. Le të shohim algoritmin hap pas hapi:

Hapi 1. Nga grupi i segmenteve strukturore fillestare formojmë një grafik planar të lidhur (Figura 4, a).

Hapi 2. Grafiku është i rregulluar, d.m.th. shtohen skaje të reja që nuk kryqëzojnë të tjerat, në mënyrë që çdo kulm i grafikut të bëhet ngjitur me të paktën një kulm mbi të dhe një nën të. Rregullimi bëhet në dy kalime duke përdorur fshirje vertikale të sheshtë. Në kalimin e parë nga poshtë lart, të gjitha kulmet gjenden në mënyrë sekuenciale nga të cilat nuk dalin skajet që çojnë lart. Për shembull, në (Figura 4, b) kjo është kulmi B. Duke përçuar vijë horizontale, gjejmë skajet më të afërta të grafikut AD dhe EF që ai pret majtas dhe djathtas. Pastaj në katërkëndëshin DEHG gjejmë kulmin më të ulët dhe vizatojmë një skaj nga B në të Kalimi i dytë nga lart poshtë kryhet në mënyrë të ngjashme (Figura 4,c). Si rezultat i këtij hapi, çdo rajon i grafikut planar bëhet një shumëkëndësh monotonik.

Hapi 3.Çdo rajon i grafikut duhet të ndahet në trekëndësha. Për ta bërë këtë, mund të përdorni algoritmin për bashkimin jo konveks të dy trekëndëshave (Figura 4, d).

Figura 4. Skema e funksionimit të algoritmit të trekëndimit zinxhir: a) - segmentet fillestare; b - kalimi nga poshtë-lart i rregullimit të grafikut; c) - kalimi nga lart poshtë; d) - trekëndëshi i shumëkëndëshave monotonikë

Për të zbatuar një algoritëm të lidhur me zinxhirë, është më mirë të përdoren strukturat e të dhënave në të cilat skajet përfaqësohen në mënyrë eksplicite, të tilla si "Edges dyfishtë" ose "Nyjet, skajet dhe trekëndëshat".

Disavantazhi i algoritmit të zinxhirit është se asgjë nuk mund të thuhet paraprakisht për formën e trekëndëshit që rezulton. Ky nuk është trekëndëshim optimal, jo i babëzitur dhe trekëndësh Delaunay jo i kufizuar. Algoritmi i zinxhirit mund të prodhojë trekëndësha shumë të gjatë të zgjatur.

Për të përmirësuar cilësinë e trekëndëshit që rezulton, mund të kontrolloni të gjitha palët e trekëndëshave ngjitur që nuk janë të ndarë nga një skaj strukturor për gjendjen Delaunay dhe, nëse është e nevojshme, të bëni rindërtime. Rezultati do të jetë një trekëndëshim Delaunay me kufizime.

Teplov A.A., Bachelor, MSTU me emrin N.E. Bauman, departamenti " Software kompjuter dhe Teknologjia e informacionit", Moskë, [email i mbrojtur]

MAYKOV K.A., Doktor i Shkencave Teknike, Profesor, Universiteti Teknik Shtetëror i Moskës me emrin N.E. Bauman, Departamenti i Softuerit Kompjuterik dhe Teknologjive të Informacionit, Moskë, [email i mbrojtur]

Algoritmi i modifikuar
Trekëndëshimi i Delaunay

Rezultatet janë dhënë analiza krahasuese Metodat e trekëndëshimit Delaunay me performancë të lartë dhe konsum të ulët të burimeve. Zgjedhja e një prototipi për modernizimin e mëvonshëm është vërtetuar në lidhje me ndërtimin e objekteve dinamike tre-dimensionale në kohë reale me një shkallë praktikisht të nevojshme detajesh. Propozohet një algoritëm për ndarjen intervale të një grupi pikash trekëndëshi në përputhje me densitetin e shpërndarjes, i cili lejon shmangien e gabimeve në zbatimin e harduerit. Një analizë e propozuar algoritmi i modifikuar Trekëndëshimi i Delaunay

Hyrje

Një nga fazat që përcakton intensitetin e burimit të ndërtimit të objekteve dinamike 3D me një nivel të caktuar detajesh është trekëndëshimi. Në praktikë, ekziston nevoja për të përcaktuar një prototip të një metode trekëndëshi që plotëson kërkesat e performancës së lartë dhe intensitetit të ulët të burimeve, me modifikim të mëvonshëm për një klasë specifike problemesh.

Vendosja e detyrave për t'u zgjidhur

Një numër problemesh praktike karakterizohen nga nevoja për të modeluar objekte 3D të përshkruara nga një grup përkatës pikash me një ligj të panjohur shpërndarjeje. Shembull detyra të ngjashmeështë modelimi i një vargu malor ose i strukturave sipërfaqësore komplekse dhe të çrregullta, lartësitë e të cilave më parë janë marrë me sensorë në distancë. Në këtë rast, është e nevojshme të kryhet trekëndëshi në grupin origjinal të pikave, duke siguruar "shkallën e korrektësisë" më të lartë të trekëndëshave, e cila karakterizohet nga përjashtimi i ndërtimit të trekëndëshave "të hollë" me një vlerë minimale të shumës. të rrezeve të rrathëve të rrethuar.

Problemi i "shkallës së rregullsisë" së trekëndëshave zgjidhet me anë të trekëndëshit që plotëson kushtin Delaunay.

Algoritmet e njohura të trekëndëshimit të Delaunay mund të ndahen në katër kategoritë e mëposhtme: algoritme përsëritëse, algoritme bashkimi, algoritme me dy kalime dhe hap pas hapi; karakteristikat kryesore algoritme të specifikuara diskutohen më poshtë.

Algoritme përsëritëse për ndërtimin e trekëndëshit të Delaunay

Algoritmet përsëritëse zbatojnë shtimin sekuencial të pikave në një trekëndëshim Delaunay të ndërtuar pjesërisht. Kompleksiteti i algoritmeve iterative Delaunay përkufizohet si O(N2), dhe për rastin shpërndarje uniforme pikë – O(N) . Disavantazhet e algoritmeve iterative Delaunay janë numër i madh sythe përsëritëse, varësia e algoritmit të renditjes nga struktura e të dhënave burimore, si dhe nevoja për të kontrolluar kushtin Delaunay në çdo lak. Përparësitë e algoritmeve iterative Delaunay janë lehtësia e zbatimit dhe përzgjedhja me shpejtësi të lartë algoritmi efikas renditja bazuar në një grup specifik të dhënash hyrëse.

Algoritme për ndërtimin e trekëndëshit të Delaunay me bashkim

Algoritmet e bashkimit zbatojnë ndarjen e grupit origjinal të pikave në një numër nënbashkësish, në të cilat ndërtohen trekëndëshat me bashkimin e mëvonshëm të një numri zgjidhjesh. Kompleksiteti i algoritmeve të bashkimit është mesatarisht O(N) . Algoritmet e bashkimit karakterizohen nga teprica, e përcaktuar nga nevoja për të ndërtuar zona konvekse për vija "të ngushta" dhe, rrjedhimisht, formimi i trekëndëshave të gjatë, "të ngushtë", të rindërtuar gjatë bashkimit. Algoritmet e bashkimit kanë performancë të lartë, gjë që përcakton avantazhin e tyre praktik.

Algoritme me dy kalime për ndërtimin e trekëndëshit të Delaunay

Karakteristika e favorshme e algoritmeve me dy kalime është se në ciklin e parë ndërtohet një trekëndësh i caktuar pa marrë parasysh kushtin Delaunay, i cili modifikohet në fazën e dytë sipas kushtit Delaunay. Kompleksiteti i algoritmeve me dy kalime është mesatarisht O(N), dhe në rastin më pak të favorshëm – O(N 2). Disavantazhi i algoritmeve Delaunay me dy kalime është nevoja për sasi të mëdha renditje për çdo korsi. Në të njëjtën kohë, ky algoritëm karakterizohet me performancë të lartë, sepse trekëndëshi tjetër që bie në trekëndësh nuk kontrollohet për përmbushjen e kushtit Delaunay, i cili kërkon burime të konsiderueshme harduerike.

Algoritme hap pas hapi për ndërtimin e trekëndëshit të Delaunay

Algoritmet e ndërtimit hap pas hapi zbatojnë vetëm trekëndëshat që plotësojnë kushtin Delaunay në trekëndëshimin përfundimtar dhe për këtë arsye nuk kërkojnë rindërtim. Me një përqendrim të madh pikash, përdorimi i një algoritmi qelizor hap pas hapi është jopraktik. Kompleksiteti i këtij algoritmi është mesatarisht O(N), dhe në rastin më të keq – O(N 2).

Zgjedhja e një prototipi për modifikimin e trekëndëshit Delaunay

Karakteristikat praktike të problemit të ndërtimit të objekteve dinamike 3D në kohë reale përcaktojnë kërkesa të tilla për algoritmet e trekëndëshimit Delaunay si performanca e lartë dhe intensiteti i ulët i burimeve. Siç vijon nga rezultatet e analizës së mësipërme, algoritmet e konsideruara nuk i plotësojnë plotësisht këto kërkesa. Prandaj, ekziston nevoja për të ndërtuar një algoritëm që nuk varet nga ndarja e zonës së trekëndëshit në primitivë që përmbajnë pika të vetë trekëndëshit dhe nuk kërkon kontrollimin e kushtit Delaunay në çdo përsëritje të shtimit të trekëndëshit aktual në trekëndëshin origjinal. .

Nga rezultatet e mësipërme të analizës krahasuese rezulton se algoritmet e trekëndimit Delaunay me dy kalime, në veçanti algoritmi i ventilatorit me dy kalime, plotësojnë vetëm pjesërisht kriteret e performancës së lartë dhe intensitetit të ulët të burimit.

Megjithatë, algoritmet të këtij lloji kanë nevojë për modifikim për të përmirësuar performancën kur zbatohet për detyrat në kohë reale. Algoritmi i ventilatorit me dy kalime është i tepërt në përcaktimin e qendrës së masës së pikave. Gjatë përcaktimit të koordinatës së një qendre të masës së pikës duke përdorur OX ose OY, me një numër të madh pikash është e papërshtatshme të llogaritet vlera e mesatares aritmetike dhe kur vlera të mëdha koordinatat e pikave, mund të ndodhë tejmbushja e të dhënave, e cila do të çojë në një gabim ose dështim të programit. Prandaj, këshillohet që të gjitha vlerat e pikave të trekëndëshit të ndahen në intervale përgjatë boshtit X në Δx 1, Δx 2, Δx 3 ... Δx n dhe përgjatë boshtit Y në Δy 1, Δy 2, Δy 3 ... Δy n. Është gjithashtu e nevojshme të përcaktohet numri i pikave që i përkasin intervaleve përkatëse përgjatë boshteve X dhe Y. Formulat që rezultojnë për marrjen e qendrës së masës së pikave kanë formën e mëposhtme:

• x c – x-koordinata e qendrës së pikës së masës;
• Dh i - intervali i i-të në boshtin X;
• X max - vlera maksimale përgjatë boshtit X midis të gjitha pikave të trekëndëshit;
• X min – vlera minimale përgjatë boshtit X midis të gjitha pikave të trekëndëshit;

• y c – y-koordinata e qendrës së pikës së masës;
• n i – numri i pikave në intervalin e i-të;
• Δy i – intervali i i-të në boshtin Y;
• Y max – vlera maksimale përgjatë boshtit Y midis të gjitha pikave të trekëndëshit;
• Y min – vlera minimale përgjatë boshtit Y midis të gjitha pikave të trekëndëshit.

Fazat pasuese të trekëndëshimit zbatohen sipas algoritmit klasik të ventilatorit. Diagrami i algoritmit të trekëndëshimit Delaunay të modifikuar të modifikuar në formë ventilatori është paraqitur në Fig. 1.

Fazat më intensive të punës në skemën e paraqitur janë fazat e renditjes dhe ndërtimit të trekëndëshit në konveks. Algoritmi i bashkimit u zgjodh si algoritmi i renditjes dhe algoritmi Graham u zgjodh si algoritmi për ndërtimin e trekëndëshit konveks. Të dy algoritmet funksionojnë në kohë e pranueshme dhe janë më të preferuarit në aspektin praktik midis përfaqësuesve të tyre.

Analiza e algoritmit të modifikuar të trekëndëshit Delaunay në formë ventilatori

Nga ai i paraqitur në Fig. 1 i diagramit tregon se vlera kohore për ndërtimin e trekëndëshit duke përdorur algoritmin e modifikuar të ventilatorit përcaktohet nga shprehja:

• T 1, T 2 - vlerat kohore për llogaritjen e numrit optimal të intervaleve përgjatë boshteve X dhe Y, përkatësisht;
• T 3, T 4 - vlerat e kohës së llogaritjes X min dhe X max, përkatësisht;
• T 5 , T 6 - respektivisht vlerat e kohës së llogaritjes Y min dhe Y max;
• T 7, T 8 - vlerat kohore për llogaritjen e vlerave të intervalit përgjatë boshteve X dhe Y, përkatësisht;
• T 9 – vlera kohore për llogaritjen e këndit polar të secilës pikë të vargut në lidhje me pikën A(X c ,Y c);
• T 10 – vlera e kohës së renditjes duke bashkuar të gjitha pikat sipas këndit polar në raport me pikën A(X c ,Y c);
• T 11 – vlera kohore për ndërtimin e një skaji nga çdo pikë e vargut në pikën A(X c ,Y c);
• T 12 - vlera kohore për plotësimin e trekëndëshit në një konveks;
• T 13 – vlera e kohës së rindërtimit të trekëndëshit që plotëson kushtin Delaunay;
• n – vargu i vlerave të koordinatave të pikës.

Le të shqyrtojmë varësinë çdo herë veç e veç.

Kur përcaktojmë numrin optimal të intervaleve përgjatë boshtit X dhe Y, ne përdorim rregullin e Sturges, sipas të cilit numri i intervaleve n përcaktohet si:

• N është numri i përgjithshëm i vëzhgimeve të sasisë;
• [x] - pjesë e tërë numrat x.

Është e qartë se varësitë kohore T 1 dhe T 2 kanë paraqitje konstante c 1 dhe c 2.

Në fazat e përcaktimit të vlerave X min, X max, Y min, Y max pseudokodi do të duket si ky:

Xmin ← M

për i ← 1 deri në gjatësi (M) – 1

Nëse Xmin › M[i]

Xmin ← M[i]

Xmax ← M

për i ← 1 deri në gjatësi (M) – 1

Nëse Xmax< M[i]

Xmax ← M[i]

Ymin ← M

për i ← 1 deri në gjatësi (M) – 1

Nëse Ymin › M[i]

Ymin ← M[i]

Ymax ← M

për i ← 1 deri në gjatësi (M) – 1

Nëse Ymax< M[i]

Ymax ← M[i]

Nga pseudokodi i mësipërm shihet qartë se koha për të gjetur maksimumin ose vlerë minimale vlerat x ose y ka varësia lineare O(N), pra, T 3 (n), T 4 (n), T 5 (n), T 6 (n), kanë një karakteristikë kohore O(N), përkatësisht.

Diagrami për përcaktimin e vlerave të intervaleve përgjatë boshtit X është paraqitur në Fig. 2.

Nga diagrami i paraqitur më sipër është e dukshme edhe varësia kohore lineare e O(N), sepse I gjithë grupi i koordinatave të vlerave të grupit të pikave është i përfshirë në përcaktimin e vlerave. Skema për përcaktimin e vlerave të intervaleve përgjatë boshtit Y ka një strukturë të ngjashme dhe karakteristika kohore, prandaj, varësia kohore për T 7 (n) dhe T 8 (n) ka formën O(N).

Skema për përcaktimin e vlerave të këndit polar për grupin fillestar të pikave është paraqitur në Fig. 3.

Si pseudokod këtë skemë do të duket kështu:

për pikë në pikë

# Nëse pika shtrihet në boshtin koordinativ midis tremujorit të 1-të dhe të 4-të

Nëse pika.x ≥ Xc dhe pika.y = Yc

Pika.këndi ← 0

# Nëse pika qëndron rreptësisht në tremujorin e parë

Përndryshe nëse pika.x > Xc dhe pika.y > Yc

Themeli ← |pika.x – Xc|

Pika.këndi ← arctg (pingule/themeli)

# Nëse pika shtrihet në boshtin koordinativ midis tremujorit të 1-të dhe të dytë

Përndryshe nëse pika.x = Xc dhe pika.y > Yc

Pika.këndi ← p/2

# Nëse pika qëndron rreptësisht në tremujorin e dytë

Përndryshe nëse pika.x< Xc and point.y >Yc

Themeli ← |pika.y – Yc|

Pika.këndi ← p/2 + arctg (pingule/themeli)

# Nëse pika shtrihet në boshtin koordinativ midis tremujorit II dhe III

Nëse pika.x< Xc and point.y = Yc

Pika.këndi ← f

# Nëse pika qëndron rreptësisht në tremujorin e tretë

Nëse pika.x< Xc and point.y >Yc

Themeli ← |pika.x – Xc|

Perpendikulare ← |pika.y – Yc|

Pika.këndi ← p + arctan (pingule/themeli)

# Nëse pika shtrihet në boshtin koordinativ midis tremujorit III dhe IV

Nëse pika.x = Xc dhe pika.y< Yc

Pika.kënd ← 3p/2

# Nëse pika qëndron rreptësisht në tremujorin e IV

Nëse pika.x > Xc dhe pika.y< Yc

Themeli ← |pika.y – Yc|

Perpendikulare ← |pika.x – Xc|

Pika.këndi ← 3p/2 + arctg(pingule/themeli)

Natyrisht, karakteristika kohore për përcaktimin e vlerave të këndit polar për grupin origjinal të koordinatave të pikave ka formën O(N), pra, T 9 (n) = O(N).

Siç tregohet në , renditja e bashkimit ka një varësi kohore të formës O(N), prandaj T 10 (n) = O(NlnN).

Diagrami për ndërtimin e një skaji që lidh pikat e grupit origjinal është paraqitur në Fig. 4.

Pseudokodi i qarkut të mësipërm do të duket si ky:

për i ← 0 në gjatësi (Pikë) – 1

Barazim (Xc, Yc, Pikat[i].x, Pikat[i].y)

Përgjigja kohore është gjithashtu lineare, prandaj T 11 (n) = O (N).

Përfundimi i trekëndëshit që rezulton në një konveks kryhet sipas algoritmit të Graham. Të dhënat hyrëse të procedurës janë bashkësia e pikave Q, ku |Q|≥3. Ai e quan funksionin Top(S), i cili kthen pikën në krye të pirgut S pa ndryshuar përmbajtjen e tij. Përveç kësaj, përdoret edhe funksioni NextToTop(S), i cili kthen një pikë të vendosur në stivën S, një pozicion poshtë pikës së sipërme; Stafi S mbetet i pandryshuar.

Graham (Q)

Le të jetë p 0 një pikë nga bashkësia Q me një koordinatë minimale.

Le të ‹p 1 , p 2 ,...,p N › – pikat e bashkësisë Q, të renditura

Në mënyrë të rritjes së këndit polar.

Push (p 0 ,S)

Push (p 1 ,S)

për i=2 deri në N bëj

Ndërsa këndi i formuar nga pikat NextToTop(S), Top(S) dhe pi,

Formoni një kthesë jo majtas

# kur lëvizni përgjatë një linje të thyer të formuar nga këto

# pika, lëvizja kryhet drejt ose djathtas

Bëj Pop(S)

Push(pi,S)

ktheje S

Koha e ekzekutimit të procedurës Graham është O(NlnN), ku N=gjatësia (Q). Është e lehtë të tregohet se cikli while do të marrë kohë O(N) dhe renditja e këndeve polare do të marrë kohë O(NlnN), që nënkupton sjelljen e përgjithshme asimptotike të procedurës Graham, prandaj, T 12 (n) = O (NlnN).

Karakteristika kohore e rindërtimit të një trekëndëshi që plotëson kushtin Delaunay, siç tregohet në , ka një varësi lineare O(N), pra T 13 (n) = O(N).

Nëse i zëvendësojmë të gjitha karakteristikat e gjetura kohore në shprehjen (3), atëherë varësia kohore që rezulton do të duket si:

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)

Drejtuar analiza teorike Karakteristikat kohore të algoritmit të modifikuar të trekëndëshit Delaunay konfirmojnë efikasitetin dhe performancën e lartë të algoritmit të propozuar.

konkluzione

Si rezultat i analizës krahasuese të algoritmeve praktikisht të njohura të trekëndimit Delaunay, tregohet se metodat e konsideruara nuk plotësojnë kërkesat për ndërtimin e objekteve dinamike tredimensionale në kohë reale me avancim. në një masë të caktuar detaje, dhe për këtë arsye, ekziston nevoja praktike për modifikimin e tyre. Propozohet një modifikim i algoritmit të trekëndëshimit Delaunay me dy kalime të ventilatorit, veçori funksionale e cila është për të llogaritur vlerat e qendrës së masës së grupit koordinativ të pikave të trekëndëshit duke e ndarë grupin e pikave në nënbashkësi përgjatë boshteve X dhe Y. Është kryer analiza e karakteristikave kohore të algoritmit të modifikuar të trekëndëshit Delaunay jashtë. Llogaritjet e specifikuara ju lejon të përmirësoni ndjeshëm performancën në një grup të madh pikash kur përcaktoni koordinatat e qendrës së pikës së masës dhe shmangni tejmbushjen e të dhënave, dhe për rrjedhojë gabimet në zbatimin e softuerit.

1. Knut D.E. Arti i programimit. Vëllimi 1. Algoritmet bazë. – M.: Williams, 2008. – 680 f.
2. Knut D.E. Arti i programimit. Vëllimi 3. Renditja dhe kërkimi. – M.: Williams, 2008. – 800 f.
3. Mandelbrot B. Gjeometria fraktale e natyrës. – M.: Instituti i Kërkimeve Kompjuterike, 2002. – 656 f.
4. Skvortsov A.V. Trekëndëshimi i Delaunay dhe aplikimi i tij. – Tomsk: Shtëpia botuese Universiteti Tomsk, 2002. – 128 f.
5. Skvortsov A.V. Ndërtimi i trekëndëshit Delaunay në kohë lineare. – Tomsk: Shtëpia Botuese e Universitetit Tomsk, 1999. – F.120-126.
6. Skvortsov A.V., Mirza N.S. Algoritme për ndërtimin dhe analizimin e trekëndëshit. – Tomsk: Shtëpia Botuese e Universitetit Tomsk, 2006. – 168 f.
7. Thomas H. Corman, Charles I. Leiseron, Ronald L. Rivest, Clifford Stein. Algoritmet: ndërtim dhe analizë, botimi i tretë: Përkth. nga anglishtja – M.: Williams, 2013. – 1328 f.
8. Shaidurov V.V. Metodat e elementeve të fundme me shumë rrjete. – M.: Nauka, 1989. – 288 f.
9. Sturges H. (1926). Zgjedhja e një intervali klase. J. Amer. Statist. Asoc., 21, 65-66.

Fjalët kyçe: realiteti virtual, trekëndëshimi në një grup të caktuar pikash, trekëndëshimi i Delaunay, ndërtimi i objekteve dinamike tredimensionale.

Algoritmi i modifikuar i trekëndëshit të Delaunay

Teplov A.A., Bachelor, MSTU Bauman, Departamenti i "Software dhe Teknologjive të Informacionit", Moskë, [email i mbrojtur]

Maikov K.A., Doktor i Shkencave Teknike, Profesor, MSTU Bauman, Departamenti i "Softuerëve dhe Teknologjive të Informacionit", Moskë, [email i mbrojtur]

Abstrakt: Rezultatet e analizës krahasuese të metodave praktikisht të njohura të trekëndëshit të Delaunay me performancë të lartë dhe konsum të ulët të burimeve janë përshkruar në këtë artikull. Zgjedhja e metodës për modernizim të mëtejshëm me qëllim të ndërtimit të objekteve dinamike 3-D në kohë reale me një shkallë të caktuar detajesh është e justifikuar. Një nga fazat kryesore të një fibrash, algoritmi me dy kalime të trekëndëshit të Delaunay është modifikuar. Ekziston propozimi i algoritmit për Ndarja intervale e grupit të qelizave të trekëndëshit në përputhje me densitetin e shpërndarjes, duke lejuar që të shmangen gabimet në zbatimin e harduerit.

Fjalë kyçe: realiteti virtual, trekëndëshimi në një grup të caktuar qelizash, trekëndëshimi i Delaunay, ndërtimi i objekteve dinamike 3-D.

Trekëndëshimi hapësinor i Delaunay

Detyra e ndërtimit të një rrjeti trekëndëshash jo të mbivendosur është një nga ato themelore në gjeometria llogaritëse dhe përdoret gjerësisht në grafika e makinës Dhe sistemet e informacionit gjeografik për modelimin e sipërfaqeve dhe zgjidhjen e problemeve hapësinore.

Problemi i ndërtimit të një rrjeti të trekëndëshave jo të mbivendosur u shtrua për herë të parë në vitin 1934 në vepër Matematikan sovjetik B. N. Delaunay, i cili formuloi kushtet përkatëse.

Në matematikë, detyra e ndërtimit të trekëndëshit nga pikat e dhëna është detyra e lidhjes së tyre në çift me segmente që nuk kryqëzohen në mënyrë që të formohet një rrjet trekëndëshash. Elementet kryesore të tij janë (Fig. 5.3): nyjet (kulmet e trekëndëshave), skajet (anët) dhe faqet (vetë trekëndëshat). Trekëndëshi i ndërtuar mund të jetë konveks (nëse është një shumëkëndësh minimal që mbulon zonën e modelimit), jo konveks (nëse trekëndëshi nuk është konveks) dhe optimal (nëse shuma e gjatësive të të gjitha skajeve është minimale).

Një rrjet trekëndëshash të tillë quhet trekëndësh Delaunay nëse plotëson disa kushte:

Asnjë nga pikat origjinale nuk bie brenda rrethit të rrethuar rreth ndonjë trekëndëshi (Fig. 5.3);

Trekëndëshi është konveks dhe plotëson kushtin Delaunay të formuluar më sipër;

Shuma e këndeve minimale të të gjithë trekëndëshave është maksimumi i të gjithë trekëndëshave të mundshëm;

Shuma e rrezeve të rrathëve të përshkruar rreth trekëndëshave është minimale midis të gjithë trekëndëshave të mundshëm.

I pari nga kriteret e mësipërme për ndërtimin e një trekëndëshi Delaunay, i quajtur rrethor, është një nga më kryesorët dhe kontrollohet për çdo çift trekëndëshash me faqe të përbashkëta. Interpretimi matematik i kriterit rrjedh nga Fig. 5.3:

(5.2)

Ka shumë mënyra për të ndërtuar trekëndëshimin Delaunay, i cili është një nga më të njohurit në kohët e fundit metodat për ndërtimin e një rrjete trekëndore. Përdoret në shumë sisteme GIS për të ndërtuar modele reliev.

Kur aplikohet në hapësirën dydimensionale, ai formulohet si vijon: një sistem trekëndëshash të ndërlidhur jo të mbivendosur ka perimetrin më të vogël nëse asnjë nga kulmet nuk bie brenda asnjë prej rrathëve të përshkruar rreth trekëndëshave të formuar (Fig. 5.4).

Oriz. 5.4. Trekëndëshimi i Delaunay

Kjo do të thotë që trekëndëshat që rezultojnë me një trekëndësh të tillë janë sa më afër që të jetë e mundur me ato barabrinjës, dhe secila nga anët e trekëndëshave rezultues nga kulmi i kundërt është i dukshëm në këndin maksimal nga të gjitha pikat e mundshme të gjysmëplanit përkatës. Ky është pikërisht trekëndëshimi optimal përgjatë skajeve të të cilit zakonisht bëhet interpolimi linear për të ndërtuar izolina.

Shumë algoritme për ndërtimin e trekëndëshit të Delaunay përdorin teoremën e mëposhtme.

Teorema 1. Trekëndëshi Delaunay mund të merret nga çdo trekëndësh tjetër duke përdorur të njëjtin sistem pikash, duke rirregulluar në mënyrë sekuenciale çifte fqinjësh trekëndëshat ABC dhe BCD, të cilat nuk plotësojnë kushtin Delaunay, në çifte trekëndëshash ABD dhe ACD (Fig. 5.5).

Oriz. 5.5.. Rindërtimi i trekëndëshave që nuk plotësojnë kushtin Delaunay

Ky operacion rindërtimi shpesh quhet rrokullisje. Kjo teoremë ju lejon të ndërtoni një trekëndëshim Delaunay në mënyrë sekuenciale, fillimisht duke ndërtuar një trekëndëshim, dhe më pas duke e përmirësuar atë në mënyrë të njëpasnjëshme në kuptimin e kushtit Delaunay. Kur kontrolloni kushtin Delaunay për çiftet e trekëndëshave ngjitur, mund ta përdorni drejtpërdrejt përkufizimin, por ndonjëherë përdoren metoda të tjera bazuar në kushtet e listuara më sipër.

Në këto kushte, shfaqet karakteristika totale e të gjithë trekëndëshit (shuma e këndeve minimale ose shuma e rrezeve), duke optimizuar se cilat mund të merret një trekëndësh Delaunay.

Siç u përmend më lart, një nga operacionet më të rëndësishme të kryera gjatë ndërtimit të trekëndëshit është kontrollimi i kushtit Delaunay për dyshe të dhëna trekëndëshat. Bazuar në përkufizimin e trekëndëshit të Delaunay dhe kushtet përkatëse, zakonisht përdoren disa metoda verifikimi në praktikë:

– kontrollimi përmes ekuacionit rrethor;

– kontrolloni me një rreth të përcaktuar paraprakisht;

– kontrollimi i shumës së këndeve të kundërta;

– kontroll i modifikuar i shumës së këndeve të kundërta.

Shumë sisteme e kryejnë testin me një rreth të llogaritur paraprakisht. Ideja kryesore e algoritmit të verifikimit përmes rrathëve të llogaritur paraprakisht është të parallogarisë për çdo trekëndësh të ndërtuar qendrën dhe rrezen e rrethit të përshkruar rreth tij, pas së cilës kontrollimi i gjendjes Delaunay do të reduktohet në llogaritjen e distancës deri në qendër. të këtij rrethi dhe duke krahasuar rezultatin me rrezen. Qendra dhe rrezja r e rrethit të përshkruar rreth mund të gjenden si , , , r 2 = (b 2 + c 2 - 4аd)/4а 2, ku vlerat a, b, c, d përcaktuar nga formula (5.3)

(5.3)

Një tjetër hyrje për ekuacionin e këtij rrethi është:

(5.5.)

(5.6)

Atëherë kushti Delaunay për do të plotësohet vetëm kur për çdo pikë tjetër trekëndëshimi është:

(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)

Aktualisht, ka shumë algoritme për ndërtimin e trekëndëshit të Delaunay. Shumë prej algoritme të njohura përdorni përkufizimin e trekëndëshit të Delaunay si simptomë dytësore trekëndëshim. Prandaj, dobësitë e mëposhtme vërehen në algoritme të tilla:

– algoritmet përdorin funksione trigonometrike të llogaritura vazhdimisht, gjë që ngadalëson në mënyrë dramatike procesin;

– gjatë studimit të marrëdhënieve ndërmjet pikave dhe segmentit bazë, lindin kënde shumë të vogla dhe gjatë përdorimit funksionet trigonometrike Ekziston një rrezik i vazhdueshëm i zhdukjes dhe ndarjes së rendit me 0 për shkak të saktësisë së kufizuar të paraqitjes së të dhënave në një kompjuter, kjo situatë kërkon përpunim të vazhdueshëm shtesë.

Më i famshmi produkte softuerike ndërtoni trekëndëshin e Delaunay duke përdorur teoremën e topit të zbrazët si parimin kryesor, primar për ndërtimin e trekëndëshave. Algoritmi duket si ky:

– i gjithë grupi i pikave ndahet në trekëndësha, d.m.th. krijohen kombinime të tre pikave;

– për çdo kombinim gjendet rrethi i rrethuar dhe koordinatat e qendrës së tij;

– nëse nuk ka mbetur asnjë pikë e vetme brenda rrethit të kombinimit aktual, atëherë ky kombinim është një trekëndësh - pjesë e trekëndëshit Delaunay.

Përparësitë e këtij algoritmi përfshijnë:

– mungesa e përdorimit të funksioneve trigonometrike, e cila nuk e ngadalëson procesin e ndërtimit;

– ndërtimi i drejtpërdrejtë i trekëndëshit Delaunay, pa asnjë ndërtim paraprak;

– thjeshtësia e të gjitha llogaritjeve dhe transformimeve;

– si rezultat, rrjeti i trekëndëshit përfaqësohet nga shumë trekëndësha, në vend të vijave individuale.

Trekëndëshi i ndërtuar në këtë mënyrë është baza gjeometrike për të ndërtuar izolina.

Algoritmet për ndërtimin e trekëndëshit Delaunay mund të ndahen në një sërë grupesh, që ndryshojnë në strukturën e të dhënave hyrëse të përdorura, vëllimin e operacioneve llogaritëse, premisat fillestare, etj. Le të shqyrtojmë disa prej tyre.

Algoritmet e bashkimit përfshijnë ndarjen e një grupi pikash burimore në nënbashkësi, ndërtimin e një trekëndëshi në secilën prej tyre dhe më pas kombinimin e tyre në një rrjet të vetëm. Thelbi i njërit prej këtyre algoritmeve zbret në sa vijon.

Grupi i pikave të origjinës është i ndarë vija vertikale në dy ose më shumë pjesë, pas së cilës secila prej tyre ndahet me vija horizontale dhe vertikale në pjesë afërsisht të barabarta. Si rezultat, e gjithë zona e pikave të fillimit ndahet në primitivë me tre ose katër pika (Fig. 2.4), përgjatë të cilave ndërtohen një ose dy trekëndësha.

Bashkimi i këtyre trekëndëshave në një rrjet të vetëm bëhet duke ndërtuar dy vija bazë (P 0 P 1 dhe P 2 P 3, oriz. 5.7.a), duke vizatuar rrathë me rreze të ndryshueshme me qendër përgjysmues pingul në vijën bazë (Fig. 5.7, b), kërkoni për një nyje që bie mbi rreth (pika A, oriz. 5.7. c) dhe ndërtimi i një trekëndëshi të ri (P 0 P 1 A). Në këtë rast, mund të jetë e nevojshme të fshihet një trekëndësh ekzistues (për shembull, P 0 AB).

Algoritmet përsëritëse bazohen në idenë e shtimit të pikave në mënyrë sekuenciale në një trekëndëshim të ndërtuar pjesërisht me përmirësimin dhe rindërtimin e tij të njëkohshëm në përputhje me kriteret e Delaunay. NË pamje e përgjithshme ato përfshijnë disa hapa dhe përfundojnë në ndërtimin e një trekëndëshi në tre pikat e para të fillimit dhe eksplorimin e disa opsioneve për vendosjen e pikës tjetër. Në veçanti, konsiderohen opsionet që ai të bjerë jashtë kufirit të zonës së modelimit, në një nyje ose skaj ekzistues, brenda një trekëndëshi të ndërtuar, etj. Secili prej këtyre opsioneve përfshin kryerjen e një operacioni të caktuar: ndarjen e një skaji në dysh, fytyrat në tre etj.; pas së cilës trekëndëshat që rezultojnë kontrollohen për pajtueshmërinë me kushtin Delaunay dhe rindërtimet e nevojshme.

Algoritmet me dy kalime fillimisht përfshijnë ndërtimin e disa trekëndëshave, duke injoruar kushtet e Delaunay, dhe më pas rindërtimin e tij në përputhje me këto kushte. Një shembull i aplikimit të algoritmit është paraqitur në Fig. 5.8.

Për ta afruar modelin e krijuar të relievit me atë real, futen elementë shtesë në të për të marrë parasysh dhe shfaqur linearin dhe sipërfaqen e tij. elementet strukturore. Elementë të tillë shtesë janë linjat strukturore të përdorura gjerësisht në topografi që përcaktojnë "skeletin e relievit": pellgjet ujëmbledhëse, thalvegë, kreshta, shkëmbinj, parvaz, liqene, lugina, vijat bregdetare, kufijtë struktura artificiale dhe të tjera, tërësia e të cilave krijon, si të thuash, kuadrin e trekëndëshit të Delaunay. Këto vija shkëputëse futen në trekëndësh si skajet e trekëndëshave, kështu që arrihet modelimi. elementet reale lehtësim në sfondin e pabarazisë së përgjithshme sipërfaqen e tokës. Skajet e tilla quhen strukturore (të fiksuara, jo të rikonfigurueshme), nuk kryqëzojnë skajet e trekëndëshave të tjerë dhe nuk ndryshojnë më pas.

Problemi i ndërtimit të një modeli sipërfaqësor duke marrë parasysh vijat e shkëputjes quhet trekëndëshim i kufizuar i Delaunay nëse kushtet e Delaunay janë të kënaqura për çdo çift trekëndëshash ngjitur që nuk ndahen me vija shkëputëse. Mënyra më efektive, besojnë studiuesit, është ndërtimi i një trekëndëshi të tillë duke përdorur algoritme përsëritëse.

Algoritmet për ndërtimin e trekëndëshit të Delaunay zbatohen me një paraqitje reale ose të plotë të koordinatave të nyjeve, gjë që mund të rrisë ndjeshëm shpejtësinë dhe saktësinë e përpunimit, por krijon probleme të kërkimit dhe përjashtimit të nyjeve përputhëse.

Modeli TIN modifikohet lehtësisht duke lëvizur nyjet, duke futur të reja, duke fshirë ato ekzistuese, duke ndryshuar pozicionin e një ose disa skajeve, duke futur linja të reja strukturore, etj. Ndryshime të tilla prekin gjithmonë një grup të vogël trekëndëshash ngjitur, nuk kërkojnë rindërtimin e të gjithë rrjetin dhe kryhen on-line, duke e drejtuar kursorin në elementin përkatës.

Rreth saktësisë:

Duke vendosur kunja në elementë karakteristikë të relievit (për shembull, pellgje ujëmbledhëse dhe thalvegë), ne injorojmë elementë më të vegjël në boshllëqe. Kur ndërtohen vija konturore1 përgjatë skajeve të tilla të trekëndëshave, ndodh një gabim, i cili varet nga sasia e pabarazisë së terrenit dhe këndi i pjerrësisë së terrenit. Për shembull, gabim mesatar Rilevimi i relievit nuk duhet të kalojë 1/3 e seksionit të relievit në kënde të pjerrësisë së sipërfaqes nga 2 deri në 10 gradë. Mund të llogaritet që me një seksion reliev prej 0,5 m, vlera maksimale e pabarazisë së humbur (d.m.th., devijimi i sipërfaqes së tokës nga një vijë e drejtë që kalon nëpër gjilpëra ngjitur) nuk duhet të kalojë (0,5/3) * cos10° = 0,16 m.

Për saktësinë e përcaktimit të vëllimit të tokës së transportuar, zona e zënë nga detaji i relievit të pa llogaritur është gjithashtu i rëndësishëm. Le të themi se në një katror 20 x 20 m midis dy palëve ka një fryrje cilindrike me lartësia maksimale 0,15 m Është e lehtë të llogaritet se mosmarrja parasysh kur përfaqësohet një sipërfaqe e caktuar me vetëm dy trekëndësha do të çojë në një gabim prej afërsisht 40 m3. Jo aq shumë, por për një ngastër prej 1 hektari, të vendosur në një kodër ose në pjesën e sipërme (zakonisht konveks) të shpatit, ju merrni 40 * 25 = 1000 m3 tokë të tepërt. Nëse merrni piketa dy herë më shpesh (d.m.th., çdo 10 m), gabimi do të ulet katërfish dhe do të arrijë në 250 m3 për hektar. Ky faktor mund të merret parasysh paraprakisht, pasi forma pozitive terrenet e sheshta zakonisht kanë formë konvekse, ndërsa ato negative kanë formë konkave. Nëse zona që do të vrojtohet ka të dhëna të përafërta për relievin, atëherë rrezja e lakimit të sipërfaqes dhe dendësia e kërkuar e kutive mund të llogariten lehtësisht nga vlerat e vijave konturore ose lartësive individuale.

Përkufizimet dhe vetitë themelore

Një trekëndësh është një grafik planar, rajonet e brendshme të të cilit janë të gjitha trekëndësha.

Vetitë:

· Trekëndëshi i Delaunay korrespondon një me një me diagramin Voronoi për të njëjtin grup pikash.

· Si pasojë: nëse nuk ka katër pika në të njëjtin rreth, trekëndëshi i Delaunay është unik.

· Trekëndëshi Delaunay maksimizon këndin minimal midis të gjitha këndeve të të gjithë trekëndëshave të ndërtuar, duke shmangur kështu trekëndëshat "të hollë".

· Trekëndëshimi Delaunay maksimizon shumën e rrezeve të sferave të brendashkruara.

· Trekëndëshimi Delaunay minimizon funksionalitetin diskrete të Dirichlet.

· Trekëndëshimi Delaunay minimizon rrezen maksimale të sferës minimale të ambientit.

· Trekëndëshi Delaunay në rrafsh ka shumën minimale të rrezeve të rrathëve të përshkruar rreth trekëndëshave midis të gjithë trekëndëshave të mundshëm.

Figura 1. Triangulimi.

Një trekëndësh konveks është një trekëndësh për të cilin shumëkëndëshi minimal që përfshin të gjithë trekëndëshat është konveks. Një trekëndësh që nuk është konveks quhet jokonveks.

Problemi i ndërtimit të trekëndëshit nga një grup i caktuar pikash dydimensionale quhet problemi i lidhjes pikët e dhëna segmente jo të kryqëzuara në mënyrë që të formohet një trekëndësh.

Një trekëndësh thuhet se plotëson kushtin Delaunay nëse asnjë nga pikat e dhëna të trekëndëshit nuk bie brenda rrethit të rrethuar rreth ndonjë trekëndëshi të ndërtuar.

Një trekëndësh quhet trekëndësh Delaunay nëse është konveks dhe plotëson kushtin Delaunay.

Figura 2. Trekëndëshimi i Delaunay.

Metoda e topit të zbrazët Delaunay. Ndërtimi në rastin e përgjithshëm

Le të përdorim një top bosh, të cilin do ta lëvizim, duke ndryshuar madhësinë e tij në mënyrë që të mund të prekë pikat e sistemit (A), por të mbetet gjithmonë bosh.

Pra, le të vendosim një top të zbrazët Delaunay në sistemin e pikëve (A). Kjo është gjithmonë e mundur nëse zgjidhni një top mjaft të vogël. Le të fillojmë të rrisim rrezen e tij, duke e lënë qendrën e topit në vend. Në një moment sipërfaqja e topit do të takohet me një pikë i të sistemit (A). Kjo do të ndodhë patjetër, sepse nuk ka zbrazëti pafundësisht të mëdha në sistemin tonë. Ne do të vazhdojmë të rrisim rrezen e topit bosh në mënyrë që pika i të mbetet në sipërfaqen e tij. Për ta bërë këtë, do t'ju duhet të lëvizni qendrën e topit nga pika i. Herët a vonë topi do të arrijë me sipërfaqen e tij një pikë tjetër në sistemin (A).

Fig.3

Simplekset Delaunay mbushin hapësirën pa boshllëqe ose mbivendosje.

Sfera e përshkruar e çdo Simplex nuk përmban pika të tjera të sistemit brenda vetes.

Le të jetë kjo pika j. Le të vazhdojmë të rrisim rrezen e topit tonë, duke i mbajtur të dyja pikat në sipërfaqen e tij. Ndërsa topi rritet, ai do të arrijë një pikë të tretë të sistemit, pikën k. NË rasti dydimensional“rrethi ynë bosh” do të rregullohet në këtë moment, d.m.th. Do të bëhet e pamundur të rritet më tej rrezja e tij duke e mbajtur rrethin bosh. Në të njëjtën kohë, ne identifikojmë një konfigurim elementar dy-dimensional të tre pikave (i, j, k), duke përcaktuar një trekëndësh të caktuar, e veçanta e të cilit është se nuk ka pika të tjera të sistemit (A) brenda rrethit të tij. NË hapësirë ​​tredimensionale topi nuk përcaktohet me tre pikë. Le të vazhdojmë të rrisim rrezen e tij, duke mbajtur të tre pikat që gjenden në sipërfaqen e tij. Kjo do të jetë e mundur derisa sipërfaqja e topit të përmbushë pikën e katërt l të sistemit. Pas kësaj, lëvizja dhe rritja e topit bosh do të bëhet e pamundur. Katër pikat e gjetura (i,j,k,l) ​​përcaktojnë kulmet e tetraedrit, i cili karakterizohet nga fakti se brenda sferës së tij të rrethuar nuk ka pika të tjera të sistemit (A). Një tetraedron i tillë quhet Delaunay simplex.

Në matematikë, një simpleks quhet figura më e thjeshtë në një hapësirë ​​të një dimensioni të caktuar: tetrahedron - në hapësirën tredimensionale; trekëndësh - në dy dimensione. Një tre (katër) pika arbitrare të sistemit që nuk shtrihen në të njëjtin rrafsh përcakton gjithmonë një simpleks të caktuar. Megjithatë, do të jetë një Simplex Delaunay vetëm nëse sfera e përshkruar e tij është bosh. Me fjalë të tjera, thjeshtësimet e Delaunay përcaktohen nga një zgjedhje e veçantë e trinjakëve (katërfishave) të pikave në sistemin (A).

Ne kemi ndërtuar një Delaunay simplex, por duke vendosur topin bosh në vende të ndryshme dhe duke përsëritur të njëjtën procedurë, ne mund të përcaktojmë të tjerat. Thuhet se grupi i të gjitha thjeshtësimeve të Delaunay të sistemit (A) e mbush hapësirën pa mbivendosje dhe boshllëqe, d.m.th. zbaton ndarjen e hapësirës, ​​por këtë herë në katërkëndëshe. Kjo ndarje quhet tjegulla Delaunay(Fig. 3).

Zbatimi i trekëndëshimit të Delaunay

Trekëndëshat Delaunay përdoren shpesh në hapësirën Euklidiane. Pema e shtrirjes minimale Euklidiane është e garantuar të shtrihet në trekëndëshin Delaunay, kështu që disa algoritme përdorin trekëndëshim. Gjithashtu, përmes trekëndëshimit të Delaunay, problemi i shitësit udhëtues Euklidian zgjidhet përafërsisht.

Në interpolimin 2D, trekëndëshimi Delaunay e ndan rrafshin në trekëndëshat më të trashë të mundshëm, duke shmangur këndet shumë të mprehta dhe shumë të mprehta. Duke përdorur këto trekëndësha, mund të ndërtoni, për shembull, interpolim bilinear.

Një problem tjetër i hasur shpesh në gjeoinformatikë është ndërtimi i ekspozimeve të shpateve. Këtu është e nevojshme të përcaktohen drejtimet mbizotëruese të shpateve sipas drejtimit kardinal dhe të ndahet sipërfaqja në rajone në të cilat dominon një drejtim i caktuar. Meqenëse përcaktimi i ekspozimit nuk ka kuptim për zonat horizontale të sipërfaqes, zonat që janë horizontale ose kanë një pjerrësi të vogël ndahen në një rajon të veçantë, p.sh.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Fig.4.

Problemi i llogaritjes së ekspozimeve të pjerrësisë zakonisht përdoret për të analizuar ndriçimin e Tokës. Në këtë drejtim, shpesh ekziston nevoja për të marrë parasysh gjithashtu pozicionin aktual të Diellit, d.m.th. ekspozimi llogaritet si drejtimi ndërmjet normales në trekëndësh dhe drejtimit drejt diellit.

Kështu, çdo trekëndësh trekëndëshi mund të klasifikohet sipas parimit të përkatësisë në një rajon të caktuar. Pas kësaj, ju vetëm duhet të telefononi algoritmin e përzgjedhjes së rajonit.

Struktura e leksionit Përkufizimet Përkufizimet Fushat e aplikimit Fushat e aplikimit Vetitë e trekëndëshimit të Delaunay Karakteristikat e trekëndëshimit të Delaunay Metodat për ndërtimin e trekëndëshimit të Delaunay Metodat për ndërtimin e trekëndëshimit të Delaunay Metodat e hyrjes hap pas hapi Metodat e hyrjes hap pas hapi Metodat e hyrjes hap pas hapi -metodat e kampionimit me hapa Metodat e zbërthimit Metodat e zbërthimit Metodat e skanimit Metodat e skanimit Metodat me dy kalime Metodat me dy kalime

Trekëndëshi Trekëndëshi është një graf planar, rajonet e brendshme të të cilit janë të gjitha trekëndësha. Trekëndëshi është një graf planar, rajonet e brendshme të të cilit janë të gjitha trekëndësha. Termi "Triangulation" është Termi "Triangulation" është një grafik; grafiku; procesi i ndërtimit të grafikut. procesi i ndërtimit të grafikut. Problemi i trekëndëshit për një grup pikash S është problemi i lidhjes së të gjitha pikave të një bashkësie S me segmente të shkëputura për të marrë një grafik trekëndëshi. Problemi i trekëndëshit për një grup pikash S është problemi i lidhjes së të gjitha pikave të një bashkësie S me segmente të shkëputura për të marrë një grafik trekëndëshi. Përkufizimi i trekëndëshit Bashkësia e pikave S

Trekëndëshimi optimal është një trekëndësh me shumën minimale të gjatësive të të gjitha skajeve të grafikut. Trekëndëshimi optimal është një trekëndësh me shumën minimale të gjatësive të të gjitha skajeve të grafikut. ! Një problem popullor, por që kërkon shumë kohë O(2 n)! Në praktikë përdoren përafrimet (përafrimet me) trekëndëshimin optimal: Trekëndëshi “Greedy” O(N 2 *logN) Trekëndëshi “Greedy” O(N 2 *logN) Trekëndëshi Delaunay O(N*logN) Trekëndëshi Delaunay O(N*logN ) Përkufizimi i trekëndëshit optimal

Trekëndëshimi i Delaunay (DT(S)) është një trekëndësh konveks që plotëson kushtin Delaunay: Trekëndëshi i Delaunay (DT(S)) është një trekëndësh konveks që plotëson kushtin Delaunay: asnjë nga kulmet e grafikut nuk duhet të bjerë brenda rrethit të rrethuar rreth ndonjë nga trekëndëshat e tij. asnjë nga kulmet e grafikut nuk duhet të bjerë brenda rrethit të rrethuar rreth ndonjë prej trekëndëshave të tij. Përkufizimi i trekëndëshit të Delaunay Kushti i Delaunay është i kënaqur Kushti i Delaunay nuk është i kënaqur B.N. Delaunay ()

Zbatimi i trekëndëshit të Delaunay në problemet e tjera VG Në problemet e tjera VG Përfshirja minimale e një grupi pikash Hapësira minimale e një grupi pikash Ndërtimi i zonave tampon Ndërtimi i zonave tampon Ndërtimi i një diagrami Voronoi (zonat e afërsisë) Ndërtimi i një diagrami Voronoi (afërsia Zonat) Gjetja e rrethit maksimal të zbrazët Gjetja e rrethit maksimal bosh, etj etj. Në aplikime në CG, GIS, GM në CAD Në aplikime në CG, GIS, GM në CAD Modele poligonale të sipërfaqeve Modele poligonale të sipërfaqeve Relieve në GIS, skulptura , modele industriale, modele në lojëra, Relieve në GIS, skulptura, .modele industriale, modele në lojëra, Analiza numerike e modeleve Analiza numerike e modeleve Izolines, Isoclines, FEM. Izolinat, Izoklinat, FEM.

Vetitë e çdo trekëndëshi konveks 1. Për një grup prej n pikash nga të cilat m janë të brendshme Numri i trekëndëshave të trekëndëshit = n + m – 2 Numri i trekëndëshave të trekëndëshit = n + m – 2 Numri i skajeve të trekëndëshit 3n – 6 Numri i skajeve të trekëndëshit 3n – 6 Shembull: Pika (n) – 13 Pika (n) – 13 e brendshme (m) – 4 e brendshme (m) – 4 trekëndësha – 15 = trekëndësha – 15 = skaje – 26 3*13-6 = 33 skaje – 26 3 *13-6 = 33

Vetitë e trekëndëshit Delaunay 2. Trekëndëshi Delaunay ka shumën maksimale të këndeve minimale të të gjithë trekëndëshave midis të gjithë trekëndëshave të mundshëm. 3. Trekëndëshi Delaunay ka shumën minimale të rrezeve të rrathëve të përshkruar rreth trekëndëshave midis të gjithë trekëndëshave të mundshëm. Trekëndëshimi i Delaunay JO trekëndëshimi i Delaunay

Metodat për ndërtimin e trekëndëshit të Delaunay Metodat e hyrjes hap pas hapi Metodat e hyrjes hap pas hapi Algoritmet përsëritëse () Algoritmet përsëritëse () Metodat e kampionimit hap pas hapi Metodat e kampionimit hap pas hapi Ndërtimi i drejtpërdrejtë (hap pas hapi) algoritme (3) Algoritme ndërtimi direkt (hap pas hapi) (3) Metodat e zbërthimit Metodat e zbërthimit Algoritmet e bashkimit (2 ) Algoritmet e bashkimit (2) Metodat e skanimit Metodat e skanimit Algoritmet përsëritëse me një rend të ndryshuar të shtimit të pikave (1.4) Algoritmet përsëritëse me një renditje e ndryshuar e shtimit të pikëve (1.4) Algoritme me dy kalime (4) Algoritme me dy kalime (4)

Metodat e hyrjes hap pas hapi Algoritme përsëritëse () Skema e përgjithshme e algoritmeve përsëritëse për ndërtimin e trekëndëshit të Delaunay 1. Ndërtoni një trekëndësh në tre pikat e para 2. Kaloni nëpër të gjitha pikat e mbetura p i të grupit S 3. Gjeni trekëndëshin t j më afër pikës p i i trekëndëshit aktual 4. Nëse pika p i është jashtë trekëndëshit t j, atëherë ndërtoni trekëndësha në skajin më të afërt. 5. Nëse pika p i është brenda trekëndëshit t j, atëherë ndajeni trekëndëshin në tre. 6. Nëse pika p i është në një skaj, atëherë trekëndëshat ngjitur ndajini në çifte. 7. Nëse kushti Delaunay për fqinjët është shkelur, atëherë rindërtoni trekëndëshat fqinjë. Opsionet për përshpejtimin e kërkimit të trekëndëshit: Indeksimi i trekëndëshit (pemë) – O(log n) Indeksimi i trekëndëshit (pemë) – O(log n) Memoria e kujtesës së trekëndëshit (rrjetë) – O(s) Memoria e trekëndëshit (rrjetë) – O(s)

Metodat e kampionimit hap pas hapi Algoritme për ndërtimin e drejtpërdrejtë (hap pas hapi) (3) Ndërtoni menjëherë trekëndëshat e nevojshëm, pa rindërtuar atë që tashmë është ndërtuar. Skema e përgjithshme e algoritmeve për ndërtimin e drejtpërdrejtë të trekëndëshit Delaunay Është i përshtatshëm për të përdorur një pirg skajesh të papërpunuara. 1. Gjeni çdo skaj q të bykut konveks të një grupi pikash S. 2. Shtyjeni skajin q në pirgun e skajeve të papërpunuara. 3. Llokojeni derisa grumbulli i skajeve të papërpunuara të jetë bosh. 4. Nxirrni skajin v nga pirgu. 5. Për skajin v, gjeni një pikë p që plotëson kushtin Delaunay (fqinjë Delaunay) 6. Nëse gjendet fqinji i Delaunay p, atëherë 7. Ndërtoni një trekëndësh nga buza v në pikën p. 8. Shtyni skajet e reja të trekëndëshit të ri në pirgun e skajeve të papërpunuara. Opsionet për përshpejtimin e kërkimit të fqinjëve të Delaunay: Indeksimi i pikave me një pemë k-D – O(log n) Indeksimi i pikave me një pemë k-D – O(log n) Indeksimi celular i pikave – O(c) Indeksimi celular i pikave – O(c )

Procesi i algoritmit të trekëndëshit të babëzitur Delaunay

Metodat e zbërthimit Algoritmet e bashkimit (2) Ndarja në nënbashkësi, përpunimi i pavarur, bashkimi i rezultateve. Skema e përgjithshme e bashkimit të algoritmeve 0. Nëse në bashkësinë S nuk ka më shumë se 3 pika, ndërtoni drejtpërdrejt ndryshe 1. Ndajeni bashkësinë e pikave S në nënbashkësi afërsisht të barabarta. 1. Ndajeni bashkësinë e pikave S në nënbashkësi afërsisht të barabarta. 2. Ndërtimi i trekëndëshit për nënbashkësi. 2. Ndërtimi i trekëndëshit për nënbashkësi. 3. Bashkimi i trekëndëshave që rezultojnë në një. 3. Bashkimi i trekëndëshave që rezultojnë në një. Metodat e ndarjes në nëngrupe Vijat e drejta ortogonale Drejtëza ortogonale Sipas diametrit të bykut konveks Sipas diametrit të bykut konveks Vija vija

Algoritmet e bashkimit (2) Metodat për bashkimin e trekëndëshave "Fshi dhe ndërto" (kontrollo përpara ndërtimit) "Fshi dhe ndërto" (kontrollo përpara ndërtimit) "Ndërto dhe rindërto" (kontrollo pas ndërtimit) "Ndërto dhe rindërto" (kontrollo pas ndërtimit) " Ndërtimi, rindërtimi" (kontrolli gjatë ndërtimit) "Ndërtimi, rindërtimi" (kontrolli gjatë ndërtimit)

Skema e përgjithshme e metodave përsëritëse me një rend të modifikuar të mbledhjes së pikave 1. Rregulloni pikat (ndërtoni një listë pikash ngjarjesh) 2. Skanoni ciklin nëpër të gjitha pikat e ngjarjes 3. Për secilën pikë p i, ndërtoni trekëndësha në trekëndëshin e mëparshëm. 4. Nëse kushti Delaunay për fqinjët është shkelur, atëherë rindërtoni trekëndëshat fqinjë. Metodat e skanimit Algoritme përsëritëse me një rend të modifikuar të shtimit të pikave (1.4)

Metodat e skanimit Metodat për renditjen e pikave të ngjarjeve Drejtvizore Drejtvizore Polare (rrethore, në formë ventilatori) Polare (rrethore, në formë ventilatori) Shirit me shirit katror Sheshi Nga kurba Hilbert Nga kurba e Hilbertit Sipas kodit Z Sipas kodit Z Qëllimet: Ndërtoni menjëherë një maksimum prej trekëndëshat e mirë Ndërtoni menjëherë një maksimum trekëndëshash të mirë Minimizo numrin e ndryshimeve të korsisë Minimizo numrin e ndryshimeve të korsisë

Karakteristikat përmbledhëse të metodave të trekëndëshimit të Delaunay Metoda e trekëndëzimit Koha mesatare Koha në më të keqen Koha sek / t Lehtësia e zbatimit. Metodat e hyrjes hap pas hapi Metodat e hyrjes hap pas hapi Algoritmet përsëritëse () Algoritmet përsëritëse ()O(n)- O(n 3/2) O(n 2) 1.5-9.2 2-5 Hap pas hapi metodat e kampionimit Metodat e kampionimit hap pas hapi Metoda e ndërtimit të drejtpërdrejtë (3) Metoda e ndërtimit të drejtpërdrejtë (3) O(n)- O(n 2) O(n 2) -2 Metodat e dekompozimit Metodat e zbërthimit Metodat e bashkimit (2) Metodat e bashkimit ( 2) O(n)- O(nlogn) O (nlogn)- O(n 2) 2.5-4.52-3 Metodat e skanimit Metodat e skanimit Përsëritës me një rend të ndryshuar të shtimit të pikëve (1.4) Përsëritës me një renditje të ndryshuar të shtimit të pikëve ( 1.4) O(n) O(n 2) 1 ,9-5,34-5 Metoda me dy kalime (4) Metoda me dy kalime (4) O(n)- O(n 2) O(nlogn)- O (n 2) 2.2-15.41-5 Skvortsov rekomandon: algoritëm iterativ me memorie dinamike

Për çfarë bëhet fjalë sot? Rreth trekëndëshit të Delaunay! Përkufizimi Përkufizimi Zonat e aplikimit Vetitë e trekëndëshimit të Delaunay Karakteristikat e trekëndëshimit të Delaunay Metodat për ndërtimin e trekëndëshimit të Delaunay Metodat për ndërtimin e trekëndëshimit të Delaunay Metodat e hyrjes hap pas hapi Metodat e hyrjes hap pas hapi Metodat e kampionimit hap pas hapi -metodat e kampionimit me hapa Metodat e zbërthimit Metodat e zbërthimit Metodat e skanimit Metodat e skanimit Metodat me dy kalime Metodat me dy kalime