Telpiskā Delaunay triangulācija

Nepārklājošu trīsstūru tīkla konstruēšanas problēma ir viena no skaitļošanas ģeometrijas pamatproblēmām un tiek plaši izmantota datorgrafikā un ģeogrāfiskās informācijas sistēmās virsmu modelēšanai un telpisko problēmu risināšanai.

Nepārklājošu trīsstūru tīkla izveides problēma pirmo reizi tika izvirzīta 1934. gadā padomju matemātiķa B. N. Delones darbā, kurš formulēja atbilstošos nosacījumus.

Matemātikā uzdevums konstruēt triangulāciju no dotajiem punktiem ir uzdevums tos savienot pa pāriem ar nekrustojas posmiem tā, lai veidojas trīsstūru tīkls. Tās galvenie elementi ir (5.3. att.): mezgli (trijstūru virsotnes), malas (malas) un skaldnes (paši trīsstūri). Konstruētā triangulācija var būt izliekta (ja tas ir minimāls daudzstūris, kas aptver modelēšanas laukumu), neizliekts (ja triangulācija nav izliekta) un optimāla (ja visu malu garumu summa ir minimāla).

Šādu trīsstūru tīklu sauc par Delaunay triangulāciju, ja tas atbilst noteiktiem nosacījumiem:

Neviens no sākotnējiem punktiem neietilpst apli, kas ir norobežots ap jebkuru trīsstūri (5.3. att.);

Triangulācija ir izliekta un atbilst iepriekš formulētajam Delaunay nosacījumam;

Visu trīsstūru minimālo leņķu summa ir visu iespējamo triangulāciju maksimālā;

Ap trijstūriem aprakstīto apļu rādiusu summa ir minimāla starp visām iespējamām triangulācijām.

Pirmais no iepriekš minētajiem Delaunay triangulācijas konstruēšanas kritērijiem, ko sauc par apļveida, ir viens no galvenajiem, un tiek pārbaudīts, vai nav trijstūra pāra ar kopīgām skaldnēm. Kritērija matemātiskā interpretācija izriet no att. 5.3:

(5.2)

Ir daudzi veidi, kā izveidot Delaunay triangulāciju, kas ir viens no populārākajiem Nesen metodes triangulācijas sieta konstruēšanai. To izmanto daudzās ĢIS sistēmās, lai izveidotu reljefa modeļus.

Lietojot uz divdimensiju telpu, to formulē šādi: savstarpēji savienotu nepārklājošu trīsstūru sistēmai ir mazākais perimetrs, ja neviena no virsotnēm neietilpst nevienā no ap veidotajiem trijstūriem aprakstītajiem apļiem (5.4. att.).

Rīsi. 5.4. Delaunay triangulācija

Tas nozīmē, ka iegūtie trīsstūri ar šādu trīsstūri ir pēc iespējas tuvāki vienādmalu trijstūriem, un katra no iegūto trīsstūru malām no pretējās virsotnes ir redzama maksimālā leņķī no visiem iespējamiem atbilstošās pusplaknes punktiem. Tieši šī ir optimālā triangulācija, kuras malās parasti tiek veikta lineārā interpolācija, lai izveidotu izolīnas.

Daudzi Delaunay triangulācijas konstruēšanas algoritmi izmanto šādu teorēmu.

Teorēma 1. Delaunay triangulāciju var iegūt no jebkuras citas triangulācijas, izmantojot to pašu punktu sistēmu, secīgi pārkārtojot blakus esošo trīsstūru ABC un BCD pārus, kas neatbilst Delaunay nosacījumam, trīsstūru ABD un ACD pāros (5.5. att.).

Rīsi. 5.5.. Delaunay nosacījumam neatbilstošu trīsstūru rekonstrukcija

Šo atjaunošanas darbību bieži sauc par flip. Šī teorēma ļauj secīgi konstruēt Delonē triangulāciju, vispirms izveidojot kādu triangulāciju un pēc tam secīgi uzlabojot to Delaunay nosacījuma izpratnē. Pārbaudot Delaunay nosacījumu blakus esošo trīsstūru pāriem, definīciju var izmantot tieši, taču dažreiz tiek izmantotas citas metodes, pamatojoties uz iepriekš uzskaitītajiem nosacījumiem.

Šādos apstākļos parādās visas triangulācijas kopējais raksturlielums (minimālo leņķu summa vai rādiusu summa), kuru optimizējot var iegūt Delaunay triangulāciju.

Kā minēts iepriekš, viens no kritiskās operācijas ko veic, veidojot triangulāciju, ir jāpārbauda Delaunay nosacījums dotajiem trīsstūru pāriem. Pamatojoties uz Delaunay triangulācijas definīciju un attiecīgajiem nosacījumiem, praksē parasti tiek izmantotas vairākas pārbaudes metodes:

– pārbaude caur apļveida apļa vienādojumu;

– pārbaudīt ar iepriekš aprēķinātu ierobežotu apli;

– pretējo leņķu summas pārbaude;

– modificēta pretējo leņķu summas pārbaude.

Daudzas sistēmas veic pārbaudi, izmantojot iepriekš aprēķinātu apli. Pārbaudes algoritma, izmantojot iepriekš aprēķinātus apļus, galvenā ideja ir iepriekš aprēķināt katram izveidotajam trīsstūrim ap to aprakstītā apļa centru un rādiusu, pēc kura Delaunay stāvokļa pārbaude tiks samazināta līdz attāluma līdz centram aprēķināšanai. no šī apļa un salīdzinot rezultātu ar rādiusu. Apkārt aprakstītā apļa centru un rādiusu r var atrast kā , , , r 2 = (b 2 + c 2 - 4аd)/4а 2, kur vērtības a, b, c, d nosaka ar formulām (5.3.)

(5.3)

Vēl viens šī apļa vienādojuma ieraksts ir:

(5.5.)

(5.6)

Tad Delaunay nosacījums tiks izpildīts tikai tad, ja jebkuram citam triangulācijas punktam tas ir:

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

Pašlaik ir daudz algoritmu Delaunay triangulācijas konstruēšanai. Daudzi labi zināmie algoritmi izmanto Delaunay triangulācijas definīciju kā sekundāro triangulācijas līdzekli. Tāpēc šādos algoritmos tiek konstatēti šādi trūkumi:

– algoritmi izmanto pastāvīgi aprēķinātas trigonometriskās funkcijas, kas krasi palēnina procesu;

– pētot attiecības starp punktiem un bāzes segmentu, rodas ļoti mazi leņķi, un izmantojot trigonometriskās funkcijas Pastāv pastāvīgas kārtības izzušanas un dalījuma ar 0 draudi ierobežotās datu attēlojuma precizitātes dēļ datorā, šī situācija prasa pastāvīgu papildu apstrādi.

Vispazīstamākie programmatūras produkti veido Delaunay triangulāciju, izmantojot tukšās bumbas teorēmu kā galveno, primāro trijstūra konstruēšanas principu. Algoritms izskatās šādi:

– visa punktu kopa ir sadalīta trīsstūros, t.i. tiek veidotas trīs punktu kombinācijas;

– katrai kombinācijai tiek atrasts ierobežotais aplis un tā centra koordinātas;

– ja pašreizējās kombinācijas apļa iekšpusē nav neviena punkta, tad šī kombinācija ir trīsstūris - daļa no Delaunay triangulācijas.

Šī algoritma priekšrocības ietver:

– trigonometrisko funkciju neizmantošana, kas nebremzē būvniecības procesu;

– tieša Delaunay triangulācijas izbūve, bez jebkādām priekškonstrukcijām;

– visu aprēķinu un pārveidojumu vienkāršība;

– rezultātā triangulācijas režģi attēlo daudzi trīsstūri, nevis atsevišķas līnijas.

Tādā veidā konstruētā triangulācija ir ģeometriskais pamats izolīnu konstruēšanai.

Delaunay triangulācijas konstruēšanas algoritmus var iedalīt vairākās grupās, kas atšķiras pēc izmantoto ievaddatu struktūras, skaitļošanas operāciju apjoma, sākotnējām premisām utt. Apskatīsim dažus no tiem.

Algoritmu apvienošana ietver avota punktu kopas sadalīšanu apakškopās, triangulācijas izveidošanu katrai no tām un pēc tam apvienošanu vienā tīklā. Viena no šiem algoritmiem būtība ir šāda.

Sākotnējo punktu kopa tiek sadalīta ar vertikālām līnijām divās vai vairākās daļās, pēc kurām katra no tām tiek sadalīta ar horizontālām un vertikālām līnijām aptuveni vienādās daļās. Rezultātā viss sākuma punktu laukums tiek sadalīts trīs vai četru punktu primitīvos (2.4. att.), pa kuriem tiek izveidots viens vai divi trīsstūri.

Šo trīsstūru apvienošana vienā tīklā tiek veikta, izveidojot divas bāzes līnijas (P 0 P 1 un P 2 P 3, rīsi. 5.7.a), zīmējot mainīga rādiusa apļus, kuru centrs ir perpendikulāra bisektrise bāzes līnijai (5.7. att., b), meklējot mezglu, kas krīt uz apļa (punkta). A, rīsi. 5.7. c) un jauna trīsstūra uzbūve (P 0 P 1 A).Šādā gadījumā var būt nepieciešams dzēst esošu trīsstūri (piemēram, P 0 AB).

Iteratīvie algoritmi ir balstīti uz ideju secīgi pievienot punktus daļēji konstruētai triangulācijai ar tās vienlaicīgu uzlabošanu un rekonstrukciju saskaņā ar Delaunay kritērijiem. IN vispārējs skats tie ietver vairākus soļus un beidzas līdz trīsstūra izveidošanai uz pirmajiem trim sākuma punkti un izpētot vairākas iespējas, kā ievietot nākamo punktu. Jo īpaši tiek apsvērtas iespējas, lai tā izkristu ārpus modelēšanas apgabala robežas, uz esoša mezgla vai malas, konstruēta trīsstūra iekšpusē utt. Katra no šīm iespējām ietver noteiktas darbības veikšanu: malas sadalīšanu divās daļās, skaldnes trīs utt.; pēc tam tiek pārbaudīta iegūto trijstūri atbilstība Delaunay nosacījumam un nepieciešamajām rekonstrukcijām.

Divkāršu algoritmi vispirms ietver dažas triangulācijas konstruēšanu, ignorējot Delaunay nosacījumus, un pēc tam tās rekonstrukciju saskaņā ar šiem nosacījumiem. Algoritma pielietojuma piemērs ir parādīts attēlā. 5.8.

Lai radīto reljefa modeli tuvinātu reālajam, tajā tiek ieviesti papildu elementi, lai nodrošinātu tā lineāro un apgabalu strukturālo elementu ņemšanu vērā un attēlošanu. Šādi papildu elementi ir topogrāfijā plaši izmantotas strukturālās līnijas, kas definē “reljefa skeletu”: ūdensšķirtnes, kalves, grēdas, klintis, dzegas, ezeri, gravas, krasta līnijas, mākslīgo konstrukciju robežas utt., kuru kopums rada sava veida reljefu. rāmis Delaunay triangulācijai. Šīs strukturālās līnijas tiek ievadītas triangulācijā kā trijstūra malas, kas panāk reālu reljefa elementu modelēšanu uz vispārējo zemes virsmas nelīdzenumu fona. Šādas malas sauc par strukturālām (fiksētām, nepārkonfigurējamām), tās nekrustojas ar citu trīsstūru malām un pēc tam nemainās.

Virsmas modeļa konstruēšanas problēmu, ņemot vērā lūzuma līnijas, sauc par ierobežotu Delonē triangulāciju, ja Delonē nosacījumi ir izpildīti jebkuram blakus esošu trīsstūru pārim, kas nav atdalīts ar lūzuma līnijām. Pētnieki uzskata, ka visefektīvākais veids ir izveidot šādu triangulāciju, izmantojot iteratīvus algoritmus.

Delaunay triangulācijas fragments ar tajā iekļautajiem papildu elementiem parādīts attēlā. 5.9, kur labajā pusē ir parādīti mezgli, malas, šķautnes un konstrukcijas līnijas, bet kreisajā pusē ir reljefa strukturālās līnijas (krasta līnijas, gravu malas utt.) un punkti ar zināmām atzīmēm.

Delaunay triangulācijas konstruēšanas algoritmi tiek realizēti ar reālu vai veselu mezglu koordinātu attēlojumu, kas var ievērojami palielināt apstrādes ātrumu un precizitāti, bet rada problēmas meklējot un izslēdzot atbilstošos mezglus.

TIN modeli ir viegli rediģēt, pārvietojot mezglus, ievietojot jaunus, dzēšot esošos, mainot vienas vai vairāku malu stāvokli, ieviešot jaunas struktūras līnijas utt. Šādas izmaiņas vienmēr skar nelielu blakus esošo trīsstūru grupu, nav nepieciešams pārbūvēt visā tīklā un tiek veiktas tiešsaistē, virzot kursoru uz atbilstošo elementu.

Par precizitāti:

Izvietojot piketus uz raksturīgiem reljefa elementiem (piemēram, ūdensšķirtnēm un zariem), mēs ignorējam mazākus elementus spraugās. Konstruējot kontūrlīnijas1 pa šādām trijstūra malām, rodas kļūda, kas atkarīga no reljefa nelīdzenumu daudzuma un reljefa slīpuma leņķa. Piemēram, vidējā kļūda reljefa uzmērīšanā nedrīkst pārsniegt 1/3 no reljefa šķērsgriezuma virsmas slīpuma leņķos no 2 līdz 10 grādiem. Var aprēķināt, ka ar reljefa posmu 0,5 m maksimālā izlaistā nelīdzenuma vērtība (tas ir, zemes virsmas novirze no taisnes, kas iet caur blakus piketiem) nedrīkst pārsniegt (0,5/3)*cos10°. =0,16 m.

Transportētās grunts apjoma noteikšanas precizitātei svarīga ir arī platība, ko aizņem neuzskaitītā reljefa detaļa. Pieņemsim, ka 20x20 m kvadrātā starp diviem piketu pāriem ir cilindrisks izliekums, kura maksimālais augstums ir 0,15 m. Ir viegli aprēķināt, ka, to neņemot vērā, attēlojot šo virsmu tikai ar diviem trijstūriem, radīsies kļūda aptuveni 40 m3. Ne tik daudz, bet uz 1 hektāra zemes gabala, kas atrodas kalnā vai nogāzes augšējā (parasti izliektā) daļā, jūs iegūstat 40 * 25 = 1000 m3 liekās augsnes. Ja piketēs divas reizes biežāk (tas ir, ik pēc 10 m), kļūda samazināsies četras reizes un sasniegs 250 m3 uz hektāru. Šo faktoru var ņemt vērā iepriekš, jo pozitīvajām plakanā reljefa formām parasti ir izliekta forma, bet negatīvajām formām ir ieliekta forma. Ja uzmērāmajā teritorijā ir aptuveni dati par reljefu, tad virsmas izliekuma rādiusu un nepieciešamo piketu blīvumu var viegli aprēķināt pēc kontūrlīniju vai atsevišķu pacēlumu vērtībām.

Pamatdefinīcijas un īpašības

Triangulācija ir plakans grafiks, kura iekšējie apgabali ir trīsstūri.

Īpašības:

· Delaunay triangulācija atbilst vienai un tai pašai punktu kopai Voronoi diagrammai.

· Rezultātā: ja uz viena apļa neatrodas četri punkti, Delonē triangulācija ir unikāla.

· Delaunay triangulācija palielina minimālo leņķi starp visiem visu izveidoto trīsstūru leņķiem, tādējādi izvairoties no "plāniem" trijstūriem.

· Delonē triangulācija palielina ierakstīto sfēru rādiusu summu.

· Delaunay triangulācija samazina diskrēto Dirihlē funkciju.

· Delaunay triangulācija samazina minimālās apkārtējās sfēras maksimālo rādiusu.

· Delaunay triangulācijai plaknē ir ap trijstūriem aprakstīto apļu rādiusu minimālā summa starp visām iespējamām triangulācijām.

Attēls 1. Triangulācija.

Izliekts trīsstūris ir trīsstūris, kuram minimālais daudzstūris, kas aptver visus trīsstūrus, ir izliekts. Triangulāciju, kas nav izliekta, sauc par neizliektu.

Triangulācijas konstruēšanas problēmu no noteiktas divdimensiju punktu kopas sauc par savienojuma problēmu dotos punktus nekrustojas segmentus, lai izveidotu triangulāciju.

Tiek uzskatīts, ka triangulācija atbilst Delaunay nosacījumam, ja neviens no dotajiem triangulācijas punktiem neietilpst aplī, kas apzīmēts ap jebkuru izveidoto trīsstūri.

Triangulāciju sauc par Delaunay triangulāciju, ja tā ir izliekta un atbilst Delaunay nosacījumam.

2. attēls. Delaunay triangulācija.

Delaunay tukšas bumbas metode. Būvniecība vispārīgā gadījumā

Izmantosim tukšu bumbiņu, kuru pārvietosim, mainot tās izmēru tā, lai tā varētu pieskarties sistēmas punktiem (A), bet vienmēr paliktu tukša.

Tātad, ievietosim punktu sistēmā (A) tukša bumba Delonē. Tas vienmēr ir iespējams, ja izvēlaties pietiekami mazu bumbu. Sāksim palielināt tā rādiusu, atstājot bumbiņas centru vietā. Kādā brīdī bumbiņas virsma saskarsies ar kādu sistēmas punktu i (A). Tas noteikti notiks, jo mūsu sistēmā nav bezgala lielu tukšumu. Mēs turpināsim palielināt tukšās lodītes rādiusu, lai punkts i paliktu uz tās virsmas. Lai to izdarītu, jums būs jāpārvieto bumbiņas centrs no punkta i. Agrāk vai vēlāk bumbiņa ar savu virsmu sasniegs citu sistēmas punktu (A).

3. att

Delaunay simplexes aizpilda vietu bez atstarpēm vai pārklāšanās.

Nevienas simpleksa aprakstītā sfēra nesatur citus sistēmas punktus sevī.

Lai tas būtu j punkts. Turpināsim palielināt savas bumbiņas rādiusu, paturot abus punktus uz tās virsmas. Bumbai pieaugot, tā sasniegs kādu trešo sistēmas punktu, punktu k. Divdimensiju gadījumā mūsu “tukšais aplis” tiks fiksēts šajā brīdī, t.i. Būs neiespējami vēl vairāk palielināt tā rādiusu, vienlaikus saglabājot apli tukšu. Tajā pašā laikā mēs identificējam elementāru trīs punktu (i, j, k) divdimensiju konfigurāciju, kas definē noteiktu trīsstūri, kura īpatnība ir tāda, ka tā apļa iekšpusē nav citu sistēmas (A) punktu. Trīsdimensiju telpā bumbiņu nenosaka trīs punkti. Turpināsim palielināt tā rādiusu, saglabājot visus trīs atrastos punktus uz tā virsmas. Tas būs iespējams, līdz bumbiņas virsma saskarsies ar sistēmas ceturto punktu l. Pēc tam tukšās bumbas kustība un augšana kļūs neiespējama. Atrastie četri punkti (i,j,k,l) ​​nosaka tetraedra virsotnes, kuras raksturo tas, ka tās ierobežotās sfēras iekšpusē nav citu sistēmas (A) punktu. Šādu tetraedru sauc par Delaunay simplex.

Matemātikā simplekss ir visvienkāršākā figūra noteiktas dimensijas telpā: tetraedrs - trīsdimensiju telpā; trīsstūris - divās dimensijās. Patvaļīgi trīs (četri) sistēmas punkti, kas neatrodas vienā plaknē, vienmēr nosaka noteiktu simpleksu. Tomēr tas būs Delaunay simplex tikai tad, ja tā aprakstītā sfēra ir tukša. Citiem vārdiem sakot, Delaunay vienkāršojumus nosaka īpaša punktu trīskāršu (četrkāršu) izvēle sistēmā (A).

Mēs esam uzbūvējuši vienu Delaunay simplex, bet, novietojot tukšo bumbu dažādās vietās un atkārtojot to pašu procedūru, mēs varam definēt citas. Tiek norādīts, ka sistēmas (A) visu Delaunay vienkāršojumu kopums aizpilda telpu bez pārlaidumiem un atstarpēm, t.i. realizē telpas dalīšanu, bet šoreiz tetraedros. Šo nodalījumu sauc Delaunay flīzēšana(3. att.).

Delaunay triangulācijas pielietojums

Eiklīda telpā bieži izmanto Delaunay triangulācijas. Eiklīda minimālais aptverošais koks ir garantēts, ka atrodas uz Delaunay triangulācijas, tāpēc daži algoritmi izmanto triangulāciju. Turklāt, izmantojot Delaunay triangulāciju, Eiklīda ceļojošā pārdevēja problēma ir aptuveni atrisināta.

2D interpolācijā Delaunay triangulācija sadala plakni iespējami biezākajos trīsstūros, izvairoties no pārāk asiem un pārāk neasiem leņķiem. Izmantojot šos trīsstūrus, varat izveidot, piemēram, bilineāru interpolāciju.

Vēl viena bieži sastopama problēma ģeoinformātikā ir nogāžu atsegumu veidošana. Šeit nepieciešams noteikt nogāžu dominējošos virzienus pēc kardinālā virziena un sadalīt virsmu reģionos, kuros dominē noteikts virziens. Tā kā ekspozīcijas noteikšana nav jēga horizontālajiem virsmas laukumiem, horizontāli vai ar nelielu slīpumu apgabali tiek iedalīti atsevišķā reģionā, piemēram,<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

4. att.

Slīpuma ekspozīcijas aprēķināšanas problēma parasti tiek izmantota, lai analizētu Zemes apgaismojumu. Šajā sakarā bieži vien ir nepieciešams papildus ņemt vērā Saules pašreizējo stāvokli, t.i. ekspozīciju aprēķina kā virzienu starp normālu pret trīsstūri un virzienu uz Sauli.

Tādējādi katru triangulācijas trīsstūri var klasificēt pēc piederības principam konkrētam reģionam. Pēc tam jums vienkārši jāizsauc reģiona atlases algoritms.

Triangulācija ir modelēta objekta virsmas aproksimācija ar trīsstūrveida plāksnēm, kas novietotas no tās attālumā, kas nepārsniedz noteiktu norādīto vērtību 6. Visām trīsstūrveida plāksnēm jābūt savienotām kopā. Viņu galotnes atrodas uz virsmas. Ar trīsstūrveida plākšņu komplektu ir vieglāk strādāt nekā ar vispārīgu virsmu. Trīsstūrveida plāksnes sauksim par trijstūriem. Trijstūrim ātri tiek aprēķināts attālums līdz noteiktam punktam vai krustošanās punktam ar noteiktu līniju telpā. Seju triangulācija tiek veikta ģeometriskā modeļa vizuālai uztverei, tāpēc trīsstūru malas tiek atlasītas tā, lai acs nepamanītu locījumus.

Attēlojot ģeometriskus objektus ar trijstūriem uz virsmu parametriskām plaknēm, ķermeņa virsmu telpiskā triangulācija ir jākonstruē, aprēķinot punktu masīvu telpā un normālu masīvu ķermeņa virsmām šajos punktos, izmantojot masīvu Divdimensiju punkti Lai ātri parādītu ķermeņus, to sejas tiek tuvinātas ar trīsstūrveida plāksnēm, kas veidotas uz parastajiem punktiem, lai noteiktu gaismas staru uzvedību, kas mijiedarbojas ar ķermeņa virsmām. Toņu zīmējumi iepriekšējās nodaļās un šajā nodaļā ir veidoti, izmantojot triangulāciju.

Virsmas triangulācijas rezultātā mēs vēlamies, lai parametru plaknē būtu divdimensiju punktu masīvs un veselu skaitļu tripletu masīvs, kas ir punktu skaitļi pirmajā minētajā masīvā. Tādējādi katrs trīsstūris tiks attēlots ar trīs tā virsotņu skaitļiem parametru masīvā. Katram parametriskā domēna divdimensiju punktam var aprēķināt telpisko punktu uz virsmas un virsmas normālu tajā. Telpiskos punktus un normas var saglabāt masīvos, kas līdzīgi 2D punktu masīvam.

Apskatīsim dažas triangulācijas metodes. Plakanām virsmām ir ekonomiski izdevīgas triangulācijas metodes, kurās trīsstūri tiek konstruēti virsmas robežpunktos un nav nepieciešams meklēt punktus parametru apgabalā.

Delaunay triangulācija.

Apskatīsim kādu apgabalu plaknē. Apgabalu sauksim par izliektu, ja, pārvietojoties pa tā robežu, jāgriežas tikai vienā virzienā (tikai pa kreisi vai tikai pa labi). Delaunay algoritmu var izmantot, lai triangulētu izliektos plakanos apgabalus. Mēs nevarēsim tieši izmantot šo algoritmu, lai triangulētu brīvas formas virsmas, bet mēs izmantosim tā metodi trīsstūru konstruēšanai.

Rīsi. 9.7.1. Izliekts apgabals ar dotiem punktiem iekšpusē

Dots kāds izliekts divdimensiju apgabals, ko ierobežo slēgta lauzta līnija un punktu kopa šajā apgabalā (9.7.1. att.).

Norādītais laukums ir jāsadala trīsstūros, kuru virsotnes ir dotie punkti laukuma iekšpusē un to norobežojošās lauztās līnijas virsotnes. Trijstūri nedrīkst pārklāties viens ar otru, un to malas var krustoties tikai virsotnēs.

Lai aizpildītu noteiktu apgabalu, var izveidot vairākas dažādas trīsstūru kopas. Visos gadījumos trīsstūru skaits ir vienāds ar , kur K ir ierobežojošās polilīnijas virsotņu skaits, I ir doto punktu skaits apgabalā.

Rīsi. 9.7.2. Izvēloties Delaunay algoritma trešo punktu

Apgabala triangulācija būs Delaunay triangulācija, ja ap katru trīsstūri aprakstītajā aplī nav citu trīsstūru virsotņu. Delaunay triangulācija veido trīsstūrus pēc iespējas tuvāk vienādstūriem (neļauj veidot nepamatoti izstieptus trīsstūrus).

To var saukt par līdzsvarotu. Delaunay triangulācija būs unikāla, ja uz viena apļa neatrodas četras virsotnes.

Apskatīsim Delaunay triangulāciju. Apgabalu ierobežojošās polilīnijas virsotnes un dotos punktus apgabala iekšpusē sauksim par triangulācijas virsotnēm. Trijstūru malas sauksim par malām. Starp malām mēs izvēlamies ierobežojošās polilīnijas segmentus, kurus sauksim par robežšķautnēm. Orientēsim visas robežmalas tā, lai izliektais apgabals atrastos pa kreisi no katras malas. Jākonstruē trijstūris, kura mala ir robežmala AB, kā parādīts attēlā. 9.7.2.

Caur virsotnēm A, B un jebkuru virsotni, kas neatrodas vienā taisnē ar tām, var novilkt apli. Kā trešo trijstūra virsotni izvēlamies virsotni V, atbilstošais aplis nesatur citas virsotnes tajā pašā pusē attiecībā pret nogriezni AB, uz kuras atrodas punkts V. Robežmalai vispārīgā gadījumā var atrasties viena šāda virsotne. tikt atrastam. Mēs to sauksim par tuvāko. Riņķa punkts, kas iet caur punktiem A, B un V, atrodas perpendikulu krustpunktā ar nogriežņu AB, BV un VA viduspunktiem. Apļa centra stāvokli raksturos ar nogriežņa MN parametru t, kas ir perpendikulāra malai AB, vienāda garumā un iet caur malas AB vidu.

Rīsi. 9.7.3. Delaunay triangulācijas process

Visām virsotnēm, kas atrodas pa kreisi no segmenta AB, tuvākajai virsotnei ir mazākais parametrs t. Aplis, kas atbilst tuvākajai virsotnei, nesatur citas virsotnes pa kreisi no segmenta AB. Apzīmēsim virsotnes A, B un V attiecīgi ar divdimensiju rādiusa vektoriem. Nogriežņu AB un BV viduspunktu rādiusa vektori būs vienādi

Taisnes parametra t vērtība, kas atbilst apļa centra pozīcijai uz tās, kas iet caur punktiem A, B un V, ir vienāda ar

Virsotnei, kas atrodas vistuvāk pa kreisi no segmenta AB, parametram t ir minimālā vērtība.

Orientēsim visas robežmalas tā, lai triangulējamais laukums atrastos pa kreisi no katras no tām. Mēs sākam konstruēt trīsstūrus no jebkuras robežmalas. Atradīsim tai tuvāko virsotni, kuras atbilstošais aplis nesatur citas virsotnes. Robežmalai AB atrod tuvāko virsotni V. Pēc tam izveidojam trijstūri ABV un pārnesam malu AB uz neaktīvo kategoriju. Mēs izsauksim neaktīvās malas un virsotnes, kas nepiedalās triangulācijas algoritmā. Ja starp robežmalām nav malas BV, tad nogriežam VB konstruējam jaunu robežmalu. Ja starp robežmalām ir mala BV, tad to un virsotni B pārnesam uz neaktīvo kategoriju. Ja starp robežmalām nav malas VA, tad segmentā AV konstruēsim jaunu robežmalu. Ja starp robežmalām ir mala VA, tad to un virsotni A pārnesam uz neaktīvo kategoriju. Triangulācijas process ir parādīts attēlā. 9.7.3.

Rīsi. 9.7.4. Delaunay triangulācija

Mēs pabeidzam triangulāciju, kad visas virsotnes un malas kļūst neaktīvas. Dotā laukuma triangulācijas rezultāts ir parādīts attēlā. 9.7.4.

Triangulācija ar korekcijas metodi.

Aplūkosim noteiktas virsmas triangulāciju ar taisnstūra domēnu parametru noteikšanai.Virsmas parametru definēšanas domēnu sadalām taisnstūra šūnās ar divdimensiju līnijām.Šīs līnijas veido taisnstūra režģi. Pieņemsim, ka parametru attālumi starp blakus esošajām līnijām saskaņā ar formulu (9.4.7) ir vienādi

Pieņemsim, ka parametru attālumi starp blakus esošajām līnijām saskaņā ar formulu (9.4.8.) ir vienādi

Konstruējot diagonāles visās taisnstūra šūnās, iegūstam virsmas triangulāciju (iegūstam prasībām atbilstošu trijstūri komplektu). Attēlā 9.7.5 parāda apgriezienu virsmas triangulāciju, izmantojot aprakstīto metodi.

Apskatīsim virsmas triangulāciju ar patvaļīgu robežu. Triangulācijas metodi veidosim uz iepriekš aprakstītās virsmas triangulācijas korekcijas pēc robežkontūrām ar taisnstūra laukumu parametru noteikšanai.

Rīsi. 9.7.5. Virsmas triangulācija ar taisnstūra domēnu parametru noteikšanai

Ļaujiet virsmas robežu parametru definīcijas jomā aprakstīt ar vairākām nekrustojas divdimensiju kontūrām (2.12.7). Viena no kontūrām ir ārējā un satur atlikušās kontūras. Katrai kontūrai pozitīvajam virzienam ņemsim virzienu, pa kuru, pārvietojoties, virsmas definīcijas laukums vienmēr atrodas pa kreisi no kontūras, skatoties pret virsmas normālu. Konstruēsim daudzstūrus virsmas definīcijas apgabala robežkontūru pozitīvajā virzienā. Lai izveidotu robežpoligonus, ar kādu mainīgu soli jāiet pa virsmas robežkontūrām un jāaizpilda divdimensiju punktu masīvs, kuru koordinātas ir virsmas parametri. Daudzstūri veidosim no punktiem parametriskā plaknē, bet solis, pārejot no viena punkta uz otru, tiks noteikts no telpiskās ģeometrijas, proti, no nosacījuma, ka līknes loka novirze starp blakus punktiem nav lielāka par doto. vērtību. Mēs aprēķinām parametru soļus daudzstūra konstruēšanai virsmas robežas kontūras līknei, izmantojot formulu (9.4.4).

Katrs daudzstūris sastāv no sakārtotas divdimensiju punktu kopas.Katru daudzstūra posmu var uzskatīt par divdimensiju taisnas līnijas nogriezni, kas veidota uz diviem blakus punktiem. Tādus apgabalus izmantosim kā robežmalas, un to daudzstūru punkti, uz kuriem balstās malas, tiks izmantoti kā triangulācijas virsotnes. Tā kā virsmas parametru noteikšanas laukums atrodas pa kreisi no robeždaudzstūriem, tad, veidojot trijstūrus katrai robežtriangulācijas malai, jāmeklē trešā trijstūra virsotne pa kreisi no malas.

Noteiksim, kuri mezgli atrodas robežpoligonu iekšpusē un kuri atrodas uz robežas vai ārpus virsmas definīcijas apgabala. Izmantojot šo informāciju, mēs sakārtojam taisnstūrveida režģa šūnas divās grupās. Pirmajā grupā ietilpst šūnas, kas pilnībā atrodas apgabalā, kurā tiek noteikti virsmas parametri (šūnas nedrīkst pieskarties robeždaudzstūriem). Otrajā grupā ietilpst pārējās šūnas (kas atrodas ārpus virsmas definīcijas apgabala vai ir krustotas ar robežpoligoniem).

Rīsi. 9.7.6. Nepabeigta virsmas triangulācija

Katras pirmās grupas šūnas iekšpusē, izmantojot diagonāli, mēs izveidosim divus trīsstūrus. Tādējādi mēs iegūstam nepabeigtu triangulāciju. Piemērs trīsstūru konstruēšanai pirmās grupas šūnās apgriezienu virsmai, ko ierobežo kontūras, ir parādīts attēlā. 9.7.6.

Otrās grupas šūnu nekrustotās malās konstruēsim robežmalas un virzīsim tās tā, lai atbilstošā šūna būtu pa kreisi no malas. Ap pirmās grupas šūnām konstruēsim slēgtu lauztu līniju (iespējams vairākas slēgtas līnijas), lai, pārvietojoties pa to, tā laukuma daļa, kas nav sadalīta trīsstūros, atrodas pa kreisi, skatoties uz virsmas normālu. . Kā robežmalas izmantosim arī šīs lauztās līnijas taisnās daļas. Visas malas uzskatīsim par vienādām. Lai pabeigtu triangulāciju, mums ir jākonstruē trīsstūri starp robežas malām. Katrai malai mēs meklēsim virsotni, kas atrodas pa kreisi no tās un kuru var izmantot, lai izveidotu trīsstūri. Mēs meklēsim virsotni tikai starp tām virsotnēm, kas atrodas vienā šūnā ar malu. Lai atlasītu virsotni, mēs izmantojam Delaunay metodi, kas aprakstīta iepriekš un ilustrēta attēlā. 9.7.2. Ja šāda virsotne ir atrasta, tad jāpārbauda, ​​vai divas jaunas trīsstūra malas krustojas ar kādu robežmalu. Ļaujiet atrast tuvāko virsotni V robežmalai AB un pārbaudīt, vai nogriežņi BV un VA nekrustojas ar citām robežšķautnēm. Pēc tam konstruēsim trijstūri ABV un pārcelsim malu AB uz neaktīvo kategoriju. Ja starp robežmalām nav malas BV, tad uz nogriežņa VB konstruēsim jaunu robežmalu, bet, ja starp robežmalām ir mala BV, tad to un virsotni B pārnesim uz neaktīvo kategoriju. Ja starp robežmalām nav malas VA, tad uz nogriežņa AV konstruēsim jaunu robežmalu, bet, ja starp robežmalām ir mala VA, tad to un virsotni A pārnesim uz neaktīvo kategoriju.

Ja segments vai VA krustojas ar citām robežšķautnēm, mēs pārejam uz tuvākās virsotnes meklēšanu citai robežmalai. Triangulācija tiks pabeigta pēc tam, kad visas malas un virsotnes ir klasificētas kā neaktīvas.

Rīsi. 9.7.7. Triangulācija ar korekcijas metodi

Attēlā 9.7.7. parādīta virsmas triangulācija ar trīsstūru korekcijas metodi šūnās, kuras krusto robežkontūras. Attēlā 9.7.8., izmantojot iegūto triangulāciju, tiek parādīta pati virsma.

Ja robeždaudzstūriem un virsmai ir kāda simetrija, tad triangulācijai ar korekcijas metodi būs līdzīga simetrija.

Triangulācija ar absorbcijas metodi.

Apskatīsim vēl vienu triangulācijas metodi. Ātruma ziņā tas ir zemāks par Delaunay triangulāciju un tās modifikācijām. Lai sāktu triangulācijas procedūru, virsmas robeža ir jāattēlo slēgtu daudzstūru veidā. Triangulācijas procesa laikā mums būs jānosaka soļi, pamatojoties uz virsmas parametriem. Ar zināmu kustības virzienu šos soļus nosaka ar formulām (9.4.6.). Aptuvenās virsmas parametru darbības var atrast šādi. Definēsim apgabalu parametru plaknē ap noteiktu punktu tā, lai jebkurš telpiskais segments no punkta līdz punktam šajā reģionā neatrastos tālāk par doto vērtību S no virsmas.

Lai to izdarītu, mēs aprēķinām pieļaujamos parametru soli pa koordinātu līnijām

kur ir virsmas pirmās un otrās kvadrātiskās formas koeficienti punktā . Kā vēlamā apgabala robežu mēs ņemam elipsi ar centru un pusasīm . Šai elipsei ir vienādojums

Ja vēlaties atrast punktu plaknē blakus punktam virzienā, ko nosaka leņķis ar un asi, tad tā parametri būs

Pirmkārt, aplūkosim vienkāršāku gadījumu, kad virsmas parametru laukums ir ierobežots ar vienu ārējo kontūru. Mēs tuvinām virsmas robežu ar slēgtu daudzstūri parametru domēnā. Veidojot triangulāciju, izmantosim darba daudzstūri, kuru šajā gadījumā ņemsim par ārējās kontūras daudzstūri. Mēs pievienosim daudzstūra punktus iegūtajam divdimensiju punktu masīvam. Mēs veidosim trīsstūrus no darba zonas malas, sašaurinot to, līdz darba zonā paliek tikai trīs punkti.

Atradīsim darba daudzstūrī virsotni, kurā tā pārvēršas apgabalā. Šāds punkts pastāv vienmēr un griešanās leņķis pie tā ir mazāks. Apzīmēsim šo punktu ar O, bet tā parametrus ar Pie šī punkta mēs izveidosim vienu vai divus trīsstūrus atkarībā no griešanās leņķa. Ja leņķis ir mazāks, tad uz šiem trim punktiem veidosim vienu trīsstūri (9.7.9. att.). Pretējā gadījumā mēs uz tā izveidosim divus trīsstūrus, divus blakus esošos un vienu jaunu punktu (9.7.11. att.). Jauno punktu apzīmē ar P. Punktu P meklēsim uz paralelograma diagonāles B OS P. Ja paralelograma virsotne atrodas elipses iekšpusē (9.7.10. att.), tad ņemsim to par punktu P. Pretējā gadījumā par punktu P pieņemsim elipses un paralelograma diagonāles krustpunktu. Pēdējā gadījumā vispār nav jāmeklē elipses un segmenta krustpunkts.

Punkta P koordinātas nosaka caur punktu O BC koordinātām

Segmenta OP leņķi ar horizontāli nosaka vienādība

(9.7.8)

Šie dati ļauj noteikt punkta P pozīciju attiecībā pret elipsi (9.7.5.).

Attēlā parādītajā gadījumā. 9.7.9., konstruēsim trīsstūri (atcerēsimies tā virsotņu skaitļus) un izdzēsīsim punktu O darba zonā. Attēlā parādītajā gadījumā. 9.7.11., mēs izveidosim divus trīsstūrus un darba zonā aizstāsim punktu O ar punktu P un ievietosim pēdējo iegūtajā punktu masīvā. Attēlā 9.7.12. attēlā parādīts daudzstūris, kas iegūts pēc divu trīsstūru izveidošanas un punkta O likvidēšanas. Abos gadījumos punkts O tiks noņemts no darba daudzstūra un darba daudzstūris sašaurināsies. Ņemiet vērā, ka trijstūri var izveidot tikai tad, ja darba zona pēc sašaurināšanas pati nekrustojas.

Rīsi. 9.7.9. Trīsstūra uzbūve

Rīsi. 9.7.10. Rezultāta daudzstūris

Rīsi. 9.7.11. Divu trīsstūru konstrukcija

Rīsi. 9.7.12. Rezultāta daudzstūris

Šādas situācijas ir parādītas attēlā. 9.7.13. Tās var rasties, ja izveidoto trīsstūru malas krustojas ar darba zonas malām, kas tām nav blakus. Pirms jauna trīsstūra izveidošanas, kā parādīts attēlā. 9.7.9., un gadījumā, kas parādīts attēlā. 9.7.11., ir jāpārbauda, ​​vai iegūtais daudzstūris pats nekrustojas.

Turklāt, nosakot punkta P pozīciju, ir svarīgi, lai tas atrastos pietiekamā attālumā no citiem darba zonas punktiem un netuvotos segmentiem, kas savieno zonas punktus. Pretējā gadījumā, veidojot trīsstūrus, nākotnē var rasties grūtības. Tāpēc, pirms sašaurināt darba daudzstūri, jums jāpārbauda iegūtais daudzstūris, vai tas nav krustojies. Ja nav iespējams izveidot trijstūri (trijstūri) pie punkta O, tad tā vietā jāatrod cits punkts, kurā daudzstūris ietītas kontūras iekšpusē vairāk nekā citos, un tajā jāveic aprakstītās darbības.

Tālāk ar modificēto darba zonu mēs veiksim tās pašas darbības, kuras tikko aprakstījām. Atradīsim darba daudzstūrī punktu, kurā tas apgriežas apgabala iekšienē vairāk nekā citos punktos, pārbaudīsim iespēju sašaurināt daudzstūri tajā, izveidojot vienu vai divus trīsstūrus, un sašaurināsim daudzstūri.

Rīsi. 9.7.13. Šajā stūrī nevar izveidot trīsstūrus.

Turpinot šo procesu, mēs paplašināsim divdimensiju punktu masīvu un trīsstūru masīvu un vienlaikus sašaurināsim darba daudzstūri, samazinot tā aptverto laukumu un tā punktu skaitu. Kādā šo darbību posmā mēs saņemsim darba daudzstūri, kas sastāv no trim punktiem. Šajos punktos izveidosim pēdējo trīsstūri, likvidēsim darba zonu un pabeigsim triangulāciju. Aprakstītajā triangulācijas metodē darba zonas ierobežotā platība it kā tiek likvidēta, nogriežot no tās trīsstūrus.

Apskatīsim vispārējo gadījumu, kad virsmas parametru laukumu ierobežo viena ārējā kontūra un vairākas iekšējās kontūras, kas pilnībā atrodas ārējās kontūras iekšpusē. Mēs tuvinām virsmas robežu ar slēgtiem daudzstūriem parametru domēnā. Katrai kontūrai mēs izveidosim savu daudzstūri. Tāpat kā kontūrām, arī uz tām uzbūvētiem daudzstūriem ir jāizpilda to savstarpējās orientācijas noteikums. Iekšējo daudzstūru orientācijai jābūt pretējai ārējā daudzstūra orientācijai. Sāksim konstruēt triangulāciju ar ārējo kontūru daudzstūri. Ieliksim tā punktus iegūtajā divdimensiju punktu masīvā un padarīsim pašu daudzstūri par strādājošu.

Mēs konstruēsim trīsstūrus tāpat kā vienkārši savienota reģiona gadījumā. Atradīsim darba zonā punktu O, pārbaudīsim, vai tur ir iespējams sašaurināt darba zonu, un sašaurināsim zonu. Ja ir iekšējās kontūras, kļūst grūtāk pārbaudīt iespēju sašaurināt darba zonu izvēlētajā punktā. Papildus aprakstītajām pārbaudēm trijstūra malu krustojumam ar darba zonas malām, ir jāpārbauda trijstūra malu krustošanās ar visu iekšējo daudzstūru malām.

Pārbaudīsim iespēju punktā O konstruēt divus trīsstūrus (9.7.11. att.) un konstatēsim, ka jaunais punkts P, kad tas ir izveidots, iekritīs vienā no iekšējiem daudzstūriem vai būs nepieņemamā tuvumā tā segmentiem. Šajā gadījumā mēs nekonstruēsim punktu P, bet tā vietā iekļausim šo iekšējo daudzstūri darba daudzstūrī, izveidojot divus trijstūrus, kas parādīti attēlā. 9.7.14.

Lai darba daudzstūrī iekļautu viena iekšējā daudzstūra punktus, starp iekšējā daudzstūra punktiem atrodam punktu, kas ir vistuvāk darba daudzstūra punktam C (blakus punktam O).

Konstruēsim trijstūrus punktos OCF un CEF un starp darba zonas punktiem O un C ievietojiet iekšējā daudzstūra punktus, sākot no punkta F un beidzot ar punktu E. Tādējādi mēs sadalīsim darba laukumu segmentā OS, sadalīsim iekšējais daudzstūris segmentā EF un apvienot tos ar segmentiem OF un EU.

Rīsi. 9.7.14. Divu trīsstūru konstrukcija

Rīsi. 9.7.15. Ārējo un iekšējo daudzstūru sapludināšana

Apvienošanās rezultāts ir parādīts attēlā. 9.7.15. Protams, pirms ārējā un iekšējā daudzstūra sapludināšanas ir jāveic pārbaudes, lai pārliecinātos par šīs darbības pareizību.

Tālāk mēs turpināsim sašaurināt darba zonu aprakstītajā veidā, līdz nonāksim citas iekšējās zonas tiešā tuvumā un iekļausim to darba zonā. Rezultātā visi iekšējie daudzstūri tiks iekļauti darba daudzstūrī, kas jāsamazina līdz pēdējiem trim punktiem. Rezultātā viss daudzkārt savienotais apgabals virsmas parametru noteikšanai tiks pārklāts ar trīsstūriem.

Rīsi. 9.7.16. Šajā stūrī nevar izveidot trīsstūrus.

Var būt situācijas, kad uz dotajiem daudzstūriem nav iespējams izveidot vienu trīsstūri. Attēlā 9.7.16 parāda apgabalu, ko ierobežo divi daudzstūri, no kuriem katrs sastāv no četriem segmentiem. Ārējam daudzstūrim mēs nevaram turpināt triangulāciju, jo iekšējais daudzstūris ir ceļā. Šajā gadījumā mēs atradīsim divus daudzstūra blakus punktus B un C, kuriem varam izveidot trīsstūri HRV. Punkts P tiek projicēts uz malas BC vidu un atrodas tādā attālumā no tā, lai jaunais trīsstūris nekrustos ar daudzstūriem.

Citas triangulācijas metodes.

Ir arī citi triangulācijas veidi. Piemēram, pēc virsmas definēšanas apgabala ārējo un iekšējo kontūru daudzstūru konstruēšanas var izvēlēties citu trijstūra konstruēšanas stratēģiju. Vēl viena iespēja ir apvienot ārējo un iekšējo daudzstūri vienā daudzstūrī pirms triangulācijas uzsākšanas. Varat “ieskicēt” punktus parametru definēšanas apgabalā, izmantojot noteiktu algoritmu, un veikt Delaunay triangulāciju, izmantojot tos un robežkontūru daudzstūru punktus. Ir algoritmi, kas vispirms izveido lielus trīsstūrus un pēc tam sadala tos pārvaldāmos izmēros.

Ķermeņa triangulācija.

Ķermeņa triangulācija ir trīsstūru kopa, kas iegūta, triangulējot tā virsmu virsmas. Atsevišķu virsmu triangulācija atšķiras no ķermeņa skaldņu triangulācijas ar to, ka pēdējā gadījumā robeždaudzstūriem blakus esošajām virsmām jābūt konsekventiem (9.7.17. att.).

Rīsi. 9.7.17. Ķermeņa sejas robežas daudzstūra konsistence

Blakus esošo skaldņu daudzstūru posmi, kas iet gar kopīgām malām, būs konsekventi, ja to punkti telpā sakrīt.

Triangulācijas pielietojums.

Triangulācijas rezultātā konstruētie trijstūri tiek izmantoti toņu attēlu iegūšanai. Attēlā 9.7.18. un 9.7.19. attēlotas loksnes korpusa virsmas triangulācijas, kuru toņu attēls parādīts att. 6.5.1.

Rīsi. 9.7.18. Ķermeņa sejas triangulācija ar korekcijas metodi

Virsmas parametru noteikšanas domēna sadalīšanu trīsstūros var izmantot integrāļos (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22), aprēķinot ķermeņu ģeometriskos raksturlielumus. . Skaitliskās integrācijas laikā parametru solis līknēm jāaprēķina, izmantojot formulu (8.11.5), bet virsmām parametru pakāpieni jāaprēķina, izmantojot formulas (8.11.1) un (8.11.2).

Triangulācija ierobežotai punktu kopai S ir izliektā korpusa CH(S), kas aptver visus kopas S punktus, triangulācijas problēma. Taisnu līniju segmenti triangulācijā nevar krustoties – tie var satikties tikai kopīgos punktos, kas pieder kopai S. Tā kā taisnu līniju segmenti aizver trīsstūrus, mēs tos uzskatīsim par ribām. Attēlā 1. attēlā parādītas divas dažādas triangulācijas versijas vienai un tai pašai punktu kopai (šajos attēlos uzzīmētos apļus mēs īslaicīgi ignorēsim).

Rīsi. 1

Noteiktai punktu kopai S var redzēt, ka visus punktus no kopas S var iedalīt robežpunktos - punktos, kas atrodas uz izliektā korpusa CH(S) robežas, un iekšējos punktos - tajos, kas atrodas izliektā korpusa iekšpusē. korpusa CH(S). Triangulācijas S rezultātā iegūtās malas var klasificēt arī kā čaulas ribas Un iekšējās ribas. Korpusa malas ietver malas, kas atrodas gar izliektā korpusa CH(S) robežu, un iekšējās malas ietver visas pārējās malas, kas veido trīsstūru tīklu izliektā korpusa iekšpusē. Ņemiet vērā, ka katra apvalka mala savieno divus blakus esošos robežpunktus, savukārt iekšējās malas var savienot divus jebkura veida punktus. Jo īpaši, ja iekšējā mala savieno divus robežpunktus, tad tā ir izliektā korpusa CH(S) horda. Ņemiet vērā arī to, ka katra triangulācijas mala ir divu apgabalu robeža: katra iekšējā mala atrodas starp diviem trijstūriem, un katra apvalka mala atrodas starp trīsstūri un bezgalīgu plakni.

Jebkura punktu kopa, izņemot dažus triviālus gadījumus, pieļauj vairāk nekā vienu triangulācijas metodi. Bet ir ievērojama īpašība: jebkura noteiktai kopai triangulācijas metode nosaka tādu pašu trīsstūru skaitu, kas izriet no teorēmas:

Teorēma par punktu kopas triangulāciju. Pieņemsim, ka punktu kopa S satur n>3 punktus un ne visi ir kolineāri. Turklāt i punkti no tiem ir iekšēji (t.i., atrodas izliektā korpusa CH(S) iekšpusē. Tad ar jebkuru kopas S triangulācijas metodi tiks iegūti tieši n + i - 2 trijstūri.

Lai pierādītu teorēmu, vispirms aplūkojam n-i robežpunktu triangulāciju. Tā kā tās visas ir izliekta daudzstūra virsotnes, šādas triangulācijas rezultātā (n - i) - 2 trijstūri. (To nav grūti pārbaudīt, un turklāt var pierādīt, ka jebkura triangulācija patvaļīgi M-malu daudzstūris - izliekts vai neizliekts - satur m - 2 trīsstūrus). Tagad pārbaudīsim, kas notiks ar triangulāciju, pievienojot atlikušos i iekšējos punktus, katru reizi pa vienam. Mēs apgalvojam, ka katra šāda punkta pievienošana palielina trīsstūru skaitu par diviem. Pievienojot iekšējo punktu, var rasties divas situācijas, kas parādītas attēlā. 2. Pirmkārt, punkts var atrasties kāda trijstūra iekšpusē un tad šāds trijstūris tiek aizstāts ar trīs jauniem trijstūriem. Otrkārt, ja punkts sakrīt ar vienu no triangulācijas malām, tad katrs no diviem šai malai blakus esošajiem trijstūriem tiek aizstāts ar diviem jauniem trijstūriem. No tā izriet, ka pēc visu i punktu saskaitīšanas kopējais trīsstūru skaits būs (n - i - 2) + (2i) vai vienkārši n + i - 2.

Rīsi. 2

Šajā sadaļā mēs iepazīstināsim ar algoritmu īpaša veida triangulācijas ģenerēšanai, kas pazīstama kā Delaunay triangulācija. Šis trīsstūris ir labi līdzsvarots tādā nozīmē, ka izveidotie trīsstūri mēdz būt vienādstūri. Piemēram, triangulācija, kas parādīta attēlā. 1a var attiecināt uz Delaunay triangulācijas veidu, un attēlā. 1b triangulācija satur vairākus ļoti iegarenus trīsstūrus, un to nevar attiecināt uz Delaunay tipu. Attēlā 3. attēlā parādīts Delaunay triangulācijas piemērs liela punktu kopai.

Rīsi. 3

Lai izveidotu Delaunay triangulāciju, mums ir vajadzīgas vairākas jaunas definīcijas. Punktu kopa tiek uzskatīta par apļveida, ja ir aplis, uz kura atrodas visi kopas punkti. Šāds aplis tiks norobežots noteiktai punktu kopai. Trijstūra ierobežotais aplis iet cauri visām trim tā (nekolineārām) virsotnēm. Mēdz teikt, ka aplis būs bezpunkts attiecībā pret doto punktu kopu S, ja apļa iekšpusē nav punktu no kopas S. Taču punkti no kopas S var atrasties uz apļa, kas ir lielākā daļa bez punktiem.

Punktu kopas S triangulācija būs Delonē triangulācija, ja katra trijstūra aplis ir bez punktiem. Triangulācijas diagrammā att. 1.a attēlā ir parādīti divi apļi, kuru iekšpusē nepārprotami nav citu punktu (var zīmēt apļus citiem trijstūriem, lai pārliecinātos, ka arī tie ir brīvi no kopas punktiem). Šis noteikums nav ievērots diagrammā attēlā. 16 - viens otra trīsstūra punkts iekrīt zīmētā apļa iekšpusē, tāpēc šī griangulācija nepieder pie Delaunay tipa.

Par kopas S punktiem var izdarīt divus pieņēmumus, lai vienkāršotu triangulācijas algoritmu. Pirmkārt, lai triangulācija vispār pastāvētu, jāpieņem, ka kopa S satur vismaz trīs punktus un ka tie nav kolineāri. Otrkārt, lai Delaunay triangulācija būtu unikāla, ir nepieciešams, lai neviens četri punkti no kopas S neatrastos uz viena un tā paša apļa. Ir viegli saprast, ka bez šāda pieņēmuma Delonē triangulācija nebūs unikāla, jo 4 punkti uz viena ierobežota apļa ļauj realizēt divas dažādas Delonē triangulācijas.

Mūsu algoritms darbojas, nepārtraukti palielinot pašreizējo triangulāciju pa vienam trīsstūrim. Sākotnēji pašreizējā triangulācija sastāv no vienas apvalka malas; algoritma beigās pašreizējā triangulācija kļūst par Delaunay triangulāciju. Katrā iterācijā algoritms meklē jaunu trīsstūri, kas savienojas ar robeža strāvas triangulācija.

Robežas definīcija ir atkarīga no sekojošā diagramma Delaunay triangulācijas malu klasifikācija attiecībā pret pašreizējo triangulāciju. Katra mala var būt guļot, dzīvs vai miris:

• miega ribas: Delaunay triangulācijas mala ir neaktīva, ja algoritms to vēl nav atklājis;
• dzīvas ribas: riba ir dzīva, ja tā ir atrasta, bet ir zināma tikai viena blakus zona;
• mirušās ribas: Mala tiek uzskatīta par mirušu, ja tā ir atrasta un ir zināmas abas blakus esošās zonas.

Sākotnēji vienīgā izliektajai i daivai piederošā mala ir dzīva - tai blakus atrodas neierobežota plakne, un visas pārējās malas ir snaudošas. Algoritmam darbojoties, malas no miega līdz dzīvai kļūst mirušas. Robeža katrā posmā sastāv no dzīvo malu kopas.

Katrā iterācijā tiek atlasīta jebkura no robežas malām un tā tiek pakļauta apstrādei, kas sastāv no nezināma apgabala meklēšanas, kuram pieder mala e. Ja šis apgabals izrādās trīsstūris f, ko nosaka malas e un kādas trešās virsotnes v beigu punkti, tad mala e kļūst nedzīva , jo tagad ir zināmas abas tai piegulošās zonas. Katra no pārējām divām trijstūra t malām tiek pārnesta uz šādu stāvokli: no miega uz dzīvu vai no dzīva uz mirušu. Šeit tiks izsaukta virsotne v konjugāts ar malu e. Pretējā gadījumā, ja nezināmais apgabals izrādās bezgalīga plakne, tad mala e vienkārši nomirst. Šajā gadījumā malai e nav konjugētas virsotnes.

Attēlā 4. attēlā parādīta algoritma darbība, kur darbība notiek no augšas uz leju un godība pa labi. Robeža katrā posmā ir izcelta ar biezu līniju.

Algoritms tiek realizēts programmā delaunayTriangulate. Programmai tiek dots masīvs s ar n punktiem, un tā atgriež sarakstu ar trijstūriem, kas attēlo Delaunay triangulāciju. Īstenošanā tiek izmantota apļveida saraksta klase un klases no sadaļas Ģeometriskā datu struktūra. Vārdnīcas klase var būt jebkura vārdnīca, kas atbalsta nepieciešamās darbības. Piemēram, varat ignorēt #define Vārdnīca RandomizedSearchTree .

Saraksts * (Punkts s, int n) ( Punkts p; saraksts *trijstūri = jauns saraksts ; Vārdnīca robeža(edgeCmp); Mala *e = korpussEdge(s, n); robeža.insert(e); while (!frontier.isEmpty()) ( e = frontier.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(frontier, p, e->org); updateFrontier(robeža, e ->galamērķis, p); trīsstūri->ievietot(trijstūris(e->org, e->galamērķis, p)); ) dzēst e; ) atgriezt trīsstūrus; )

Rīsi. 4

Trijstūri, kas veido trijstūri, tiek ierakstīti trīsstūru sarakstā. Robežu attēlo pierobežas dzīvo malu vārdnīca. Katra mala ir vērsta tā, lai tai nezināmais reģions (jānosaka) atrodas pa labi no malas. Salīdzināšanas funkcija edgeCmp tiek izmantota, lai meklētu vārdnīcu. Tas salīdzina divu šķautņu sākuma punktus; ja tie ir vienādi, tad tiek salīdzināti to beigu punkti:

Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) atgriezties 1; if (a->org > b->org) atgriež 1; if (a->dest< b->dest) atgriešanās -1; if (a->dest > b->dest) return 1; atgriezties 0; )

Kā robeža mainās no viena soļa uz nākamo un kā funkcija updateFrontier modificē apmales vārdnīcu, lai atspoguļotu šīs izmaiņas? Kad robežai tiek pievienots jauns trīsstūris t, mainās trīsstūra trīs malu stāvokļi. Trijstūra mala t, kas atrodas blakus robežai, mainās no dzīvas uz mirušu. Funkcija updateFrontier var ignorēt šo malu, jo tā jau ir jāizņem no vārdnīcas, kad tiek izsaukta funkcija removeMin. Katra no divām atlikušajām trijstūra t malām maina savu stāvokli no miega uz dzīvu, ja tās iepriekš nav ierakstītas vārdnīcā, vai no dzīvas uz mirušu, ja mala jau ir vārdnīcā. Attēlā 5 parādīti abi gadījumi. Saskaņā ar attēlu mēs apstrādājam dzīvo malu af un, atklājot, ka punkts b ir tā konjugāts, mēs pievienojam trijstūri afb pašreizējai triangulācijai. Tad meklējam vārdnīcā malu fb un, tā kā tā vēl nav un tiek atklāta pirmo reizi, tā stāvoklis mainās no miega uz dzīvu. Lai rediģētu vārdnīcu, mēs pagriezīsim malu fb tā, lai nezināmais reģions, kas atrodas blakus tai, atrodas pa labi no tās, un ierakstīsim šo malu vārdnīcā. Tad vārdnīcā atradīsim malu ba - tā kā tā ir tajā, tā jau ir dzīva (zināmā tai blakus esošā zona ir trīsstūris abc). Tā kā tai nezināmais reģions, trīsstūris afb, ir tikko atklāts, šī mala tiek noņemta no vārdnīcas.

Funkcija updateFrontier rediģē robežu vārdnīcu, kurā mainās malas stāvoklis no punkta a līdz punktam b:

Rīsi. 5

Void updateFrontier (vārdnīca &frontier, Point &a, Point &b) ( Edge *e = new Edge (a, b); if (frontier.find (e)) frontier.remove(e); else ( e->flip(); robeža.insert( e) ) )

Funkcija hullEdge atrod korpusa malu starp n punktiem masīvā s. Šī funkcija faktiski izmanto inicializācijas soli un dāvanu iesaiņošanas metodes pirmo iterāciju:

Mala *korpusa mala (punkts 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]); }

Trīsstūra funkcija vienkārši ģenerē un atgriež daudzstūri trim punktiem, kas tai nodoti kā parametri:

Daudzstūris *trijstūris (Punkts &a, Punkts &b, Punkts &c) (Daudzstūris *t = jauns daudzstūris; t->ievietot (a); t->ievietot (b); t->ievietot (c); atgriezties t; )

GRID modeļi ir parasto šūnu modeļi.

Ieviesīsim koordinātu sistēmu
Un Un
. Lietotāju komplekti
un paraugu ņemšanas soļi
.

,

- punkta fiziskās koordinātas.

Mēs aprēķinām
Un
,
- bitu režģis.

- kvantētās vērtības. Īsts:

- algoritma parametrs – punktu skaits, - svars. Jo tuvāk punkts, jo lielāks svars.

- attāluma pakāpe (1 vai 2).

Normalizācijas koeficients:

Kā tuvāk 1, jo vairāk punktu ar lielāku svaru tiek ņemts vērā.

Tāda ir IDW metode - garš, katram t ir jāatrod kaimiņi. Kaimiņu komplektu var efektīvi atrast - tuvākais. Katrs punkts rada noteikta augstuma “knaģi”. Daudz kas ir atkarīgs no punkta noteikšanas nelikumības, tāpēc viņi to pieņem
vai
tie. sadalīts sektoros un tuvumā esošajos būvpunktos.

Priekšrocība- vienkāršība

Trūkums:

------Biļete 14. Skārda modelis. Delaunay triangulācijas algoritmi ------

1) Triangulācija (skārda).

Triangulācija– funkcijas konstruēšana gabalos lineāru funkciju kopas veidā

Triangulācija– interpolācija izliektā apgabalā.

Triangulācija– plakans grafs, kura visas iekšējās malas ir trijstūri; veids, kā attēlot telpu trijstūru veidā, kas atrodas blakus viens otram bez pārklāšanās. Triangulācija tiek veidota uz punktu kopas vairākos veidos.

Lai izveidotu optimālu triangulāciju, ir nepieciešams algoritms.

Plakne, kas iet cauri 3 punktiem.

1) Atrodiet trīsstūri, kas
;

2)
- izveidot plaknes vienādojumu.

Lai pārbaudītu, vai punkti atrodas trijstūrī vai nav, jums ir jāaizstāj vērtība līniju vienādojumā - trijstūra malas. Ja visi 3 vienādojumi > 0, tad iekšā.

Prezentācijas struktūra:

Katrā triangulācijā ir vienāds skaits trijstūri.

, Kur - iekšējo punktu skaits,
- punktu daudzums.

Mantkārīga triangulācija.

Mēs savienojam visus punktus ar malām, atlasām minimumu un pievienojam tos triangulācijai. Tālāk ņemam nākamo minimumu, kas nekrustojas ar iepriekšējiem utt. Rezultāts ir mantkārīga triangulācija.

Delaunay triangulācija.

Ap jebkuru trīsstūri norobežota riņķa iekšpuse neietver citu trīsstūru punktus. Tas ir uzbūvēts vienīgajā veidā.

Flip ir malu pārnešana. Tas ļauj pāriet no parastās triangulācijas uz Delaunay triangulāciju. Lai pārbaudītu, vai punkts pieder aplim: aizstājiet, ja< R, то внутри.

Delaunay stāvoklis.

Apļa vienādojums, kas iet cauri trim punktiem:

Ja mazāks par nulli, tad ārējais, pretējā gadījumā - iekšējais.

– Delaunay stāvoklis.

Delaunay triangulācijas konstruēšanas algoritms:

1) Punktu pievienošana izmeklēšanā- vienkāršs iteratīvs algoritms:

Ir komplekts
pievieno trijstūrim, tiek veikta būvniecība
trīsstūra sadalīšana
pārbūve. Nulles posmā mēs pievienojam 3-4 fiktīvus punktus, kas acīmredzami nosedz mūsu aploksni, visus punktus iekšā. Tad metam punktu, paskatāmies uz kuru trijstūri tas trāpa, sadalām uz 3, katram trijstūrim pārbaudām Delaunay nosacījumu un veicam malu flip transfer. Vidējais joslu maiņas skaits ir trīs.

Teorētiskā sarežģītība

2) Paātrinājuma metodes. Pamatojoties uz statistiski atkarīgiem punktiem. Sēklu trīsstūris ir trīsstūris, kurā iekrita iepriekšējais punkts. Tad savienojam divus punktus - iepriekšējo un jauno.

Mēs pārejam no pirmā punkta uz otru.