Uy Og'iz bo'shlig'i Delaunay bo'sh to'p usuli. Umumiy holatda qurilish

Og'iz bo'shlig'i

Delaunay bo'sh to'p usuli. Umumiy holatda qurilish

2012-yil 20-avgust, soat 22:41

Aylana tenglamasi orqali Delaunay holatini tekshirish algoritmini optimallashtirish va uni qo'llash

Men sizga ikkita uchburchak uchun Delaunay holatini tezda qanday tekshirish haqida sirni aytib beraman.
Aslida, optimallashtirishning o'zi biroz pastroq tavsiflangan ("Delaunay holatini aylana tenglamasi orqali tekshirish algoritmini optimallashtirish" bo'limiga qarang), lekin men sizga hamma narsani tartibda aytib beraman.

Mening holimda triangulyatsiya tasvirni kuzatishda tekislikni ibtidoiy sektorlarga (uchburchaklar) bo'lish uchun ishlatiladi. Ma'lumki, u ham bir necha bosqichlarga bo'linadi: sozlash, chegaralarni aniqlash, chegaralar bo'ylab yurish, konturlarni supurish. U judayam ichida umumiy ko'rinish. Men to'xtashni juda xohlardim, menimcha qiyin bosqich: samolyotni supurish.

Kirish joyida

Chegaralarni aniqlab, kesib o'tgandan so'ng, men chiqishda juda ko'p tashqi ko'chadan oldim. Har bir teginish konturi bor turli ranglar. Har bir bunday sxema ma'lum miqdordagi ichki sxemalarni ham o'z ichiga oladi.
Shunday qilib, "samolyotni supurish" nuqtai nazaridan, agar biz tashqi konturlarni alohida ko'rib chiqsak, bizda bir qator nuqtalar mavjud bo'lib, ularning har biri o'ngga va chapga bitta qo'shniga ega. Bular. barcha nuqtalar zanjirda yopilgan, bitta "osilgan" nuqta yo'q va har bir zanjirda kamida 3 nuqta mavjud (1-rasm).

1-rasm

Nima qilish kerak

Shaklni uchburchaklar bilan qoplashingiz kerak.

Qidirmoq

Kitobni o'qib chiqqandan so'ng, men hech bo'lmaganda mening ishim uchun mos keladigan Delaunay triangulyatsiyasini qurishning bitta (kamida bitta) usulini topa olmadim. Boshqa kitoblarni qidirmadim. Va bu etarli edi, bu mening boshimdagi fikrlarni tartibga soldi. Natijada, u o'zining "velosipedini" ixtiro qildi.

Algoritm

1) Keling, boshlanuvchilar uchun, ko'rib chiqilayotgan rasmda faqat bitta ketma-ketlik bor deb faraz qilaylik. Keyin hammasi ketma-ket uchburchaklarni olishga tushadi. Biz har qanday nuqtani olamiz va qo'shni nuqtalar bilan uchburchak qurishga harakat qilamiz. Agar uchburchak qurishning iloji bo'lmasa (bu ikki nuqtani bog'laydigan chiziq allaqachon qurilganlar bilan kesishadi yoki chiziq istisno zonasida o'tadi (2-rasm), biz keyingi nuqtaga o'tamiz, o'ngga aytamiz. Keyingi uchburchak qachon topilgan bo'lsa, biz uni ro'yxatga qo'shamiz (3-rasm) va u qurilgan nuqtani olib tashlaymiz (4-rasm).

2-rasm

3-rasm

4-rasm

Yana bir narsa: keyingi uchburchakni saqlashda cho'qqilarni soat yo'nalishi bo'yicha (to'g'ri koordinatalar tizimida) yozish kerak. Bu kelajakda hisoblash resurslarini kamaytirish uchun foydali bo'ladi.

2) Butun tekislikni supurib bo'lgunimizcha 1-bosqichni takrorlang.

3) Agar bir nechta ketma-ketliklar mavjud bo'lsa, ya'ni. biri va uning ichida boshqa yoki bir nechta ichki konturlar mavjud (1-rasm). Bu erda har bir ketma-ketlikni alohida ko'rib chiqish kerak. Keling, yana bir ichki konturni olaylik. Bitta tashqi va bitta ichki qismdan ikkita bitta sxema yasaymiz. Buni amalga oshirish uchun siz bir sxemadan ikkinchisiga ikkita "port" ni topishingiz kerak. "Portlar" uchun shart: ular bir-biri bilan kesishmasligi kerak (hatto ularning uchlari tegmasligi kerak) va ular kontur chiziqlari bilan kesishmasligi kerak (5-rasm).

5-rasm

6-rasm
4) Keyinchalik, siz barcha ichki ketma-ketliklarni bir-biridan ajratilgan shakllangan ketma-ketliklarga birma-bir kiritishingiz kerak (3-band). Siz uni yangisini o'z ichiga olgan bilan birlashtirishingiz kerak. Ta'rifga ko'ra, hech qanday ichki ketma-ketlik boshqalarga (har ikkala tashqi va barcha mumkin bo'lgan ichki) tegmaydi yoki kesishmaydi, shuning uchun hamma narsa muammosiz ketadi.
Portlarni topgandan so'ng (6-rasm), joriy algoritmning 1 va 2-bandlari yordamida yangi ketma-ketliklarni qurish va ularni chetlab o'tish oson (7-rasm).

7-rasm

5) 4-bosqichdan so'ng bizda uchburchaklar ro'yxati mavjud (8-rasm). Go'yo vazifa allaqachon bajarilgandek, lekin faqat rasmni chiroyli qilish qoladi: Delaunay sharti bajarilganligini tekshiring (9-rasm).

8-rasm

9-rasm

6) Oldinga qarab, men sizga oltinchi nuqta haqida gapirib beraman. U 5-bosqichdan foydalangan holda olingan uchburchaklar ro'yxatini ketma-ket bajarishdan iborat. Birinchidan, biz barcha uchburchaklarni "iflos" deb belgilaymiz. Har bir tsiklda biz har bir uchburchak uchun Delaunay holatini tekshiramiz. Agar shart bajarilmasa, biz qo'shnilarni va joriy uchburchakni qayta quramiz va "iflos" deb belgilaymiz. Agar shart bajarilsa, biz uni toza deb belgilaymiz. Algoritmni amalga oshirishda har bir uchburchak o'z qo'shnilari bilan bog'langan. Bunday holda, 6-band eng tez ishlaydi.

Beshinchi bosqich haqida ko'proq

Endi, bilishimcha, ikkitasi bor mumkin bo'lgan usullar uchburchaklar Delonay shartini qanoatlantiradimi yoki yo'qligini aniqlang: 1) Qarama-qarshi burchaklar yig'indisini tekshiring. 180 dan kichik bo'lishi kerak. 2) Cheklangan aylana markazini hisoblang va 4-nuqtagacha bo'lgan masofani hisoblang. Agar nuqta chegaralangan doiradan tashqarida bo'lsa, Delaune sharti qondirilishini hamma biladi.

Hisoblash quvvati №1: 10 ko'paytirish / bo'lish va 13 qo'shish / ayirish.
Hisoblash quvvati №2: 29 ko'paytirish / bo'lish va 24 qo'shish / ayirish.

Masalan, kitobda hisoblangan hisoblash quvvati nuqtai nazaridan 1-variant foydaliroq. Men buni amalga oshirgan bo'lardim, agar bo'lmasa ... (10-rasm). Ishlab chiqarishdan keyin ma'lum bo'lishicha bu usul"konveyer lentasi" ga, natijada noaniqlik paydo bo'ldi. Bu A burchagining o'zi 180 darajadan ortiq bo'lgan variant. Bu kitobda individual xususiy usullardan biri sifatida ko'rib chiqiladi. Va bu bilan uning barcha nafisligi, shaffofligi va ishlashi yo'qoladi. Va keyinroq ma'lum bo'ldiki, №2 usul juda sezilarli darajada optimallashtirilishi mumkin.

10-rasm

Aylana tenglamasi orqali Delaunay holatini tekshirish algoritmini optimallashtirish

Keyingi - sof matematika.

Shunday qilib, bizda:
M(X, Y) nuqtaning shartini A(x1, y1), B(x2, y2), C(x3, y3) nuqtalardan o‘tuvchi aylana tenglamasi orqali tekshirish quyidagicha yozilishi mumkin:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ a ≥ 0 belgisi

Tafsilotlarni ajoyib kitobda topish mumkin. (Yo'q, men muallif emasman)
Shunday qilib, a belgisi - bu o'tish yo'nalishi belgisi, men boshidanoq uchburchaklarni soat yo'nalishi bo'yicha qurdim, shuning uchun uni tashlab yuborish mumkin (u birga teng).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

11-rasm

Oddiy, shunday emasmi?

Kitobga ko'ra, yana

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Bizda: 15 ta koʻpaytirish/boʻlish amallari va 14 ta qoʻshish/ayirish amallari mavjud.

E'tiboringiz uchun rahmat. Men tanqidni kutaman.

Bibliografiya

1. Skvortsov A.V. Delaunay triangulyatsiyasi va uning qo'llanilishi. - Tomsk: Tom nashriyoti. Universitet, 2002. – 128 b. ISBN 5-7511-1501-5

GRID modellari oddiy hujayralar modellaridir.

Koordinatalar tizimi kiritilsin
Va Va
. Foydalanuvchilar to'plami
va namuna olish bosqichlari
.

- nuqtaning fizik koordinatalari.

Biz hisoblaymiz
Va
,
- bit panjara.

- kvantlangan qiymatlar. Haqiqiy:

- algoritm parametri - nuqtalar soni, - vazn. Nuqta qanchalik yaqin bo'lsa, og'irlik shunchalik katta bo'ladi.

- masofa darajasi (1 yoki 2).

Normalizatsiya omili:

Qanaqasiga 1 ga yaqinroq bo'lsa, og'irligi yuqori bo'lgan ko'proq ball hisobga olinadi.

Bu IDW usuli - uzoq, har bir t uchun qo'shnilarni topish kerak. Qo'shnilar to'plamini samarali ravishda topish mumkin - eng yaqin. Har bir nuqta ma'lum balandlikdagi "qoziq" hosil qiladi. Ko'p narsa nuqtani belgilashning tartibsizligiga bog'liq, buning uchun ular qabul qilishadi
yoki
bular. sektorlarga bo'lingan va yaqin joylarda punktlarni qurish.

Afzallik- oddiylik

Kamchilik:

------Bilet 14. Qalay modeli. Delaunay triangulyatsiya algoritmlari------

1) Triangulyatsiya (qalay).

Triangulyatsiya– qismli chiziqli funksiyalar to‘plami ko‘rinishidagi funksiyani qurish

Triangulyatsiya– qavariq mintaqa ichidagi interpolyatsiya.

Triangulyatsiya– barcha ichki qirralari uchburchak bo‘lgan planar grafik; bo'shliqni bir-biriga qo'shni bo'lgan uchburchaklar shaklida bir-birining ustiga chiqmasdan tasvirlash usuli. Triangulyatsiya nuqtalar to'plamiga bir necha usul bilan qurilgan.

Optimal triangulyatsiyani qurish uchun algoritm kerak.

3 nuqtadan o'tuvchi samolyot.

1) Bunday uchburchakni toping
;

2)
- tekislikning tenglamasini tuzing.

Nuqtalar uchburchak ichida yoki yo'qligini tekshirish uchun siz qiymatni chiziqlar tenglamasiga - uchburchakning qirralariga almashtirishingiz kerak. Agar barcha 3 tenglama > 0 bo'lsa, u holda ichkarida.

Taqdimot tuzilishi:

Har bir triangulyatsiyada bir xil sonli uchburchaklar mavjud.

, Qayerda - ichki nuqtalar soni,
- ball miqdori.

Ochko'z uchburchak.

Biz barcha nuqtalarni qirralar bilan bog'laymiz, minimalni tanlaymiz va ularni triangulyatsiyaga qo'shamiz. Keyinchalik, biz oldingilar bilan kesishmaydigan keyingi minimalni olamiz va hokazo. Natijada ochko'z triangulyatsiya.

Delaunay triangulyatsiyasi.

Har qanday uchburchak atrofida aylananing ichki qismi boshqa uchburchaklarning nuqtalarini o'z ichiga olmaydi. U yagona usulda qurilgan.

Flip - bu qirralarning uzatilishi. Bu an'anaviy triangulyatsiyadan Delaunay triangulyatsiyasiga o'tish imkonini beradi. Nuqta aylanaga tegishli ekanligini tekshirish uchun: if ni almashtiring< R, то внутри.

Delaunay holati.

Uch nuqtadan o'tuvchi aylana tenglamasi:

Agar noldan kam bo'lsa, u holda tashqi, aks holda - ichki.

- Delaunay holati.

Delaunay triangulyatsiyasini qurish algoritmi:

1) Tekshirilayotgan nuqtalarni qo'shish- oddiy iterativ algoritm:

To'plam bor
uchburchakka qo'shing, qurilish amalga oshiriladi
uchburchakning bo'linishi
qayta qurish. Nolinchi bosqichda biz konvertimizni, ichidagi barcha nuqtalarni qoplaydigan 3-4 xayoliy nuqta qo'shamiz. Keyin nuqtani tashlaymiz, qaysi uchburchakka tegishini ko'rib chiqamiz, uni 3 ga bo'lamiz, har bir uchburchak uchun biz Delaunay shartini tekshiramiz va qirralarning burilishni amalga oshiramiz. Chiziqni o'zgartirishning o'rtacha soni uchta.

Nazariy murakkablik

2) Tezlashtirish usullari. Statistik jihatdan bog'liq bo'lgan nuqtalar asosida. Urug' uchburchagi - oldingi nuqta tushgan uchburchak. Keyin ikkita nuqtani bog'laymiz - oldingi va yangi.

Biz birinchi nuqtadan ikkinchisiga o'tamiz.

2012-yil 20-avgust, soat 22:41

Aylana tenglamasi orqali Delaunay holatini tekshirish algoritmini optimallashtirish va uni qo'llash

Tasvirga ishlov berish,
Dasturlash

Mening holimda triangulyatsiya tasvirni kuzatishda tekislikni ibtidoiy sektorlarga (uchburchaklar) bo'lish uchun ishlatiladi. Ma'lumki, u ham bir necha bosqichlarga bo'linadi: sozlash, chegaralarni aniqlash, chegaralar bo'ylab yurish, konturlarni supurish. Bu eng umumiy ma'noda. Men, menimcha, eng qiyin bosqichda to'xtashni xohlayman: samolyotni supurish.

Kirish joyida

Chegaralarni aniqlab, kesib o'tgandan so'ng, men chiqishda juda ko'p tashqi ko'chadan oldim. Har bir teginish konturi boshqa rangga ega. Har bir bunday sxema ma'lum miqdordagi ichki sxemalarni ham o'z ichiga oladi.
Shunday qilib, "samolyotni supurish" nuqtai nazaridan, agar biz tashqi konturlarni alohida ko'rib chiqsak, bizda bir qator nuqtalar mavjud bo'lib, ularning har biri o'ngga va chapga bitta qo'shniga ega. Bular. barcha nuqtalar zanjirda yopilgan, bitta "osilgan" nuqta yo'q va har bir zanjirda kamida 3 nuqta mavjud (1-rasm).

1-rasm

Nima qilish kerak

Shaklni uchburchaklar bilan qoplashingiz kerak.

Qidirmoq

Algoritm

2-rasm

3-rasm

4-rasm

2) Butun tekislikni supurib bo'lgunimizcha 1-bosqichni takrorlang.

Beshinchi bosqich haqida ko'proq

Endi, men bilishimcha, uchburchaklar Delaunay shartini qanoatlantiradimi yoki yo'qligini aniqlashning ikkita mumkin bo'lgan usuli bor: 1) Qarama-qarshi burchaklar yig'indisini tekshiring. 180 dan kichik bo'lishi kerak. 2) Cheklangan aylana markazini hisoblang va 4-nuqtagacha bo'lgan masofani hisoblang. Agar nuqta chegaralangan doiradan tashqarida bo'lsa, Delaune sharti qondirilishini hamma biladi.

Hisoblash quvvati №1: 10 ko'paytirish / bo'lish va 13 qo'shish / ayirish.
Hisoblash quvvati №2: 29 ko'paytirish / bo'lish va 24 qo'shish / ayirish.

Masalan, kitobda hisoblangan hisoblash quvvati nuqtai nazaridan 1-variant foydaliroq. Men buni amalga oshirgan bo'lardim, agar bo'lmasa ... (10-rasm). Ma'lum bo'lishicha, ushbu usulni "konveyer" ga qo'ygandan so'ng, noaniqlik paydo bo'ldi. Bu A burchagining o'zi 180 darajadan ortiq bo'lgan variant. Bu kitobda individual xususiy usullardan biri sifatida ko'rib chiqiladi. Va bu bilan uning barcha nafisligi, shaffofligi va ishlashi yo'qoladi. Va keyinroq ma'lum bo'ldiki, №2 usul juda sezilarli darajada optimallashtirilishi mumkin.

10-rasm

Aylana tenglamasi orqali Delaunay holatini tekshirish algoritmini optimallashtirish

Keyingi - sof matematika.

Shunday qilib, bizda:
M(X, Y) nuqtaning shartini A(x1, y1), B(x2, y2), C(x3, y3) nuqtalardan o‘tuvchi aylana tenglamasi orqali tekshirish quyidagicha yozilishi mumkin:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ a ≥ 0 belgisi

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

11-rasm

Oddiy, shunday emasmi?

Kitobga ko'ra, yana

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Bizda: 15 ta koʻpaytirish/boʻlish amallari va 14 ta qoʻshish/ayirish amallari mavjud.

E'tiboringiz uchun rahmat. Men tanqidni kutaman.

Bibliografiya

1. Skvortsov A.V. Delaunay triangulyatsiyasi va uning qo'llanilishi. - Tomsk: Tom nashriyoti. Universitet, 2002. – 128 b. ISBN 5-7511-1501-5

Asosiy ta'riflar va xususiyatlar

Triangulyatsiya - bu ichki hududlari barcha uchburchaklar bo'lgan planar grafik.

Xususiyatlari:

· Delaunay triangulyatsiyasi bir xil nuqtalar to'plami uchun Voronoi diagrammasiga birma-bir mos keladi.

· Natijada: agar bitta aylanada to'rtta nuqta bo'lmasa, Delaunay triangulyatsiyasi noyobdir.

· Delaunay triangulyatsiyasi barcha qurilgan uchburchaklarning barcha burchaklari orasidagi minimal burchakni maksimal darajada oshiradi va shu bilan "ingichka" uchburchaklardan qochadi.

· Delaunay triangulyatsiyasi chizilgan sharlar radiusi yig‘indisini maksimal darajada oshiradi.

· Delaunay triangulyatsiyasi diskret Dirixlet funksiyasini minimallashtiradi.

· Delaunay triangulyatsiyasi minimal muhit sferasining maksimal radiusini minimallashtiradi.

· Tekislikdagi Delaunay triangulyatsiyasi barcha mumkin bo'lgan uchburchaklar orasida uchburchaklar atrofida tasvirlangan doiralar radiuslarining minimal yig'indisiga ega.

1-rasm. Triangulyatsiya.

Qavariq triangulyatsiya - bu barcha uchburchaklarni o'rab turgan minimal ko'pburchak qavariq bo'lgan triangulyatsiya. Qavariq bo'lmagan triangulyatsiya qavariq bo'lmagan deb ataladi.

Berilgan ikki oʻlchovli nuqtalar toʻplamidan triangulyatsiya yasash masalasi berilgan nuqtalarni ajratilgan segmentlar orqali bir-biriga bogʻlab, triangulyatsiya hosil boʻlishi masalasidir.

Agar berilgan uchburchak nuqtalarining hech biri qurilgan uchburchak atrofida aylana ichiga tushmasa, triangulyatsiya Delaunay shartini qanoatlantiradi, deyiladi.

Triangulyatsiya Delonay uchburchagi deb ataladi, agar u qavariq bo'lsa va Delon shartini qanoatlantirsa.

Shakl 2. Delaunay triangulyatsiyasi.

Delaunay bo'sh to'p usuli. Umumiy holatda qurilish

Keling, bo'sh to'pdan foydalanamiz, biz uni harakatlantiramiz, uning hajmini tizimning (A) nuqtalariga tegishi uchun o'zgartiramiz, lekin har doim bo'sh qoladi.

Shunday qilib, (A) nuqtalar tizimiga bo'sh Delaunay to'pini joylashtiramiz. Agar siz etarlicha kichik to'pni tanlasangiz, bu har doim ham mumkin. Keling, to'pning markazini joyida qoldirib, uning radiusini oshirishni boshlaylik. Bir nuqtada to'pning yuzasi tizimning (A) biron bir i nuqtasi bilan uchrashadi. Bu, albatta, sodir bo'ladi, chunki bizning tizimimizda cheksiz katta bo'shliqlar yo'q. Biz bo'sh to'pning radiusini oshirishda davom etamiz, shunda i nuqta uning yuzasida qoladi. Buning uchun to'pning markazini i nuqtadan siljitish kerak bo'ladi. Ertami-kechmi to'p o'z yuzasi bilan tizimdagi boshqa nuqtaga etib boradi (A).

3-rasm

Delaunay simplekslari bo'shliqlar va bir-birining ustiga chiqmasdan bo'sh joyni to'ldiradi.

Har qanday simpleksning tavsiflangan sferasi o'z ichida tizimning boshqa nuqtalarini o'z ichiga olmaydi.

Bu j nuqta bo'lsin. Keling, ikkala nuqtani uning yuzasida ushlab turgan holda, to'pimizning radiusini oshirishda davom etaylik. To'p oshgani sayin, u tizimning uchinchi nuqtasi, k nuqtasiga etib boradi. Ikki o'lchovli holatda, bizning "bo'sh doiramiz" hozirgi vaqtda o'rnatiladi, ya'ni. Doira bo'sh turgan holda uning radiusini yanada oshirish imkonsiz bo'ladi. Shu bilan birga, biz ma'lum bir uchburchakni aniqlaydigan uchta nuqtaning (i, j, k) elementar ikki o'lchovli konfiguratsiyasini aniqlaymiz, uning o'ziga xos xususiyati shundaki, uning aylanasi ichida tizimning (A) boshqa nuqtalari yo'q. Uch o'lchovli fazoda to'p uch nuqta bilan belgilanmaydi. Keling, uning yuzasida topilgan uchta nuqtani saqlab, uning radiusini oshirishda davom etaylik. Bu to'pning yuzasi tizimning to'rtinchi l nuqtasiga to'g'ri kelguncha mumkin bo'ladi. Shundan so'ng, bo'sh to'pning harakati va o'sishi imkonsiz bo'ladi. Topilgan to'rtta nuqta (i, j, k, l) tetraedrning uchlarini belgilaydi, bu uning chegaralangan sferasi ichida tizimning boshqa nuqtalari (A) yo'qligi bilan tavsiflanadi. Bunday tetraedr Delaunay simpleks deb ataladi.

Matematikada simpleks berilgan o'lchamdagi fazodagi eng oddiy figuradir: tetraedr - uch o'lchovli fazoda; uchburchak - ikki o'lchamda. Bir tekislikda yotmaydigan tizimning ixtiyoriy uch (to'rt) nuqtasi har doim ma'lum bir simpleksni belgilaydi. Biroq, agar tasvirlangan sfera bo'sh bo'lsa, u Delaunay simplex bo'ladi. Boshqacha qilib aytganda, Delaunay soddaliklari (A) sistemadagi nuqtalarning uchlik (to'rtlik) maxsus tanlovi bilan aniqlanadi.

Biz bitta Delaunay simplexini qurdik, ammo bo'sh to'pni turli joylarga qo'yib, xuddi shu protsedurani takrorlash orqali biz boshqalarni aniqlashimiz mumkin. Ta'kidlanishicha, (A) tizimning barcha Delaunay soddaliklari to'plami bo'shliqni bir-biriga yopishmasdan va bo'shliqlarsiz to'ldiradi, ya'ni. kosmosning bo'linishini amalga oshiradi, lekin bu safar tetraedrlarga. Ushbu bo'lim deyiladi Delaunay kafel qoplamasi(3-rasm).

Delaunay triangulyatsiyasini qo'llash

Evklid fazosida Delaunay triangulyatsiyasi ko'pincha qo'llaniladi. Evklidning minimal uzunligi daraxti Delaunay triangulyatsiyasida yotishi kafolatlangan, shuning uchun ba'zi algoritmlar triangulyatsiyadan foydalanadi. Bundan tashqari, Delaunay triangulyatsiyasi orqali Evklidning sayohatchi sotuvchisi muammosi taxminan hal qilinadi.

2D interpolyatsiyasida Delaunay triangulyatsiyasi tekislikni iloji boricha qalin uchburchaklarga bo'lib, o'ta o'tkir va o'ta to'g'ri burchaklardan qochadi. Ushbu uchburchaklardan foydalanib, siz, masalan, ikki chiziqli interpolyatsiyani yaratishingiz mumkin.

Geoinformatikada tez-tez uchrab turadigan yana bir muammo qiyalik ekspozitsiyalarini qurishdir. Bu erda qiyaliklarning ustun yo'nalishlarini tub yo'nalish bo'yicha aniqlash va sirtni ma'lum bir yo'nalish hukmronlik qiladigan hududlarga bo'lish kerak. Ekspozitsiyani aniqlash sirtning gorizontal joylari uchun mantiqiy bo'lmaganligi sababli, gorizontal yoki ozgina qiyaligi bo'lgan joylar, masalan, alohida mintaqaga ajratiladi.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

4-rasm.

Nishab ekspozitsiyalarini hisoblash muammosi odatda Yerning yoritilishini tahlil qilish uchun ishlatiladi. Shu munosabat bilan, ko'pincha Quyoshning hozirgi holatini qo'shimcha ravishda hisobga olish kerak, ya'ni. ta'sir qilish uchburchakning normal va Quyoshga yo'nalishi o'rtasidagi yo'nalish sifatida hisoblanadi.

Shunday qilib, har bir triangulyatsiya uchburchagini ma'lum bir mintaqaga tegishli bo'lish printsipiga ko'ra tasniflash mumkin. Shundan so'ng, siz faqat mintaqani tanlash algoritmiga qo'ng'iroq qilishingiz kerak.

Triangulyatsiya - bu modellashtirilgan ob'ektning sirtini ma'lum bir belgilangan qiymatdan oshmaydigan masofada joylashgan uchburchak plitalari bilan yaqinlashtirish 6. Barcha uchburchak plitalari birlashtirilishi kerak. Ularning tepalari sirt ustida yotadi. Uchburchak plitalar to'plami bilan ishlash umumiy sirtga qaraganda osonroq. Biz uchburchak plitalarni uchburchaklar deb ataymiz. Uchburchak uchun ma'lum nuqtagacha bo'lgan masofa yoki fazoda berilgan chiziq bilan kesishish nuqtasi tezda hisoblab chiqiladi. Yuzlarning triangulyatsiyasi geometrik modelni vizual idrok etish uchun amalga oshiriladi, shuning uchun uchburchaklarning tomonlari ko'z burmalarni sezmasligi uchun tanlangan.

Geometrik jismlarni sirtlarning parametrik tekisliklarida uchburchaklar bo‘yicha ko‘rsatishda fazodagi nuqtalar massivi va bu nuqtalarda tananing yuzlari uchun normalar massivini hisoblash yo‘li bilan jism yuzlarining fazoviy triangulyatsiyasi tuzilishi kerak. ikki o'lchovli nuqtalar jismlarni tezda ko'rsatish uchun ularning yuzlari ustiga qurilgan uchburchak plitalar bilan yaqinlashadi. Oldingi boblardagi va ushbu bobdagi ohangli chizmalar triangulyatsiya yordamida tuzilgan.

Sirt triangulyatsiyasi natijasida biz parametrik tekislikdagi ikki o'lchovli nuqtalar massiviga va birinchi eslatib o'tilgan massivdagi nuqtalar sonlari bo'lgan butun sonlarning uchlik massiviga ega bo'lishni xohlaymiz. Shunday qilib, har bir uchburchak parametrlar massivida uning cho'qqilarining uchta raqami bilan ifodalanadi. Parametrik sohaning har bir ikki o'lchovli nuqtasi uchun sirtdagi fazoviy nuqta va undagi normal sirtni hisoblash mumkin. Fazoviy nuqtalar va normalar 2D nuqta massiviga o'xshash massivlarda saqlanishi mumkin.

Keling, triangulyatsiyaning ba'zi usullarini ko'rib chiqaylik. Yassi yuzalar uchun uchburchaklar sirtning chegara nuqtalarida qurilgan iqtisodiy jihatdan samarali triangulyatsiya usullari mavjud va parametrik mintaqa ichidagi nuqtalarni qidirishga hojat yo'q.

Delaunay triangulyatsiyasi.

Keling, samolyotdagi ba'zi maydonni ko'rib chiqaylik. Agar uning chegarasi bo'ylab harakatlanayotganda siz faqat bitta yo'nalishda (faqat chapga yoki faqat o'ngga) burilishingiz kerak bo'lsa, biz uni konveks deb ataymiz. Delaunay algoritmi qavariq planar hududlarni uchburchak qilish uchun ishlatilishi mumkin. Biz bu algoritmni toʻgʻridan-toʻgʻri erkin shaklli yuzalarni uchburchak qilish uchun qoʻllay olmaymiz, lekin uchburchaklar yasashda uning usulidan foydalanamiz.

Guruch. 9.7.1. Ichida berilgan nuqtalari bo'lgan qavariq mintaqa

Yopiq siniq chiziq bilan chegaralangan ba'zi bir qavariq ikki o'lchovli mintaqa va bu mintaqa ichidagi nuqtalar to'plami berilsin (9.7.1-rasm).

Belgilangan maydonni uchburchaklarga bo'lish talab qilinadi, ularning uchlari maydon ichidagi berilgan nuqtalar va uni chegaralovchi siniq chiziqning uchlari. Uchburchaklar bir-birining ustiga tushmasligi kerak va ularning tomonlari faqat cho'qqilarda kesishishi mumkin.

Belgilangan maydonni to'ldirish uchun bir nechta turli xil uchburchaklar to'plamini qurish mumkin. Barcha holatlarda uchburchaklar soni ga teng bo'ladi, bu erda K - chegaralovchi ko'p chiziqning uchlari soni, I - maydon ichidagi berilgan nuqtalar soni.

Guruch. 9.7.2. Delaunay algoritmining uchinchi nuqtasini tanlash

Har bir uchburchak atrofida tasvirlangan doira ichida boshqa uchburchaklarning uchlari bo'lmasa, mintaqaning triangulyatsiyasi Delaunay triangulyatsiyasi bo'ladi. Delaunay triangulyatsiyasi uchburchaklarni iloji boricha teng burchakka yaqinroq quradi (asossiz cho'zilgan uchburchaklar qurishga yo'l qo'ymaydi).

Uni muvozanatli deb atash mumkin. Agar bitta aylanada to'rtta cho'qqi bo'lmasa, Delaunay triangulyatsiyasi noyob bo'ladi.

Keling, Delaunay triangulyatsiyasini ko'rib chiqaylik. Viloyatni chegaralovchi ko‘p chiziqning uchlarini va mintaqa ichidagi berilgan nuqtalarni triangulyatsiya cho‘qqilari deb ataymiz. Biz uchburchaklarning tomonlarini qirralar deb ataymiz. Qirralar orasida biz chegara qirralari deb ataladigan chegaralovchi poliliniyaning segmentlarini tanlaymiz. Keling, barcha chegara qirralarini shunday yo'naltiramizki, qavariq mintaqa har bir chekkaning chap tomonida joylashgan. Shaklda ko'rsatilgan tomoni AB chegarasi bo'lgan uchburchakni qurish kerak bo'lsin. 9.7.2.

A, B cho'qqilari va ular bilan bir chiziqda yotmaydigan har qanday cho'qqi orqali aylana chizish mumkin. Uchburchakning uchinchi cho'qqisi sifatida biz V cho'qqisini tanlaymiz, tegishli doira V nuqta yotadigan AB segmentiga nisbatan bir xil tomonda joylashgan boshqa cho'qqilarni o'z ichiga olmaydi topilsin. Biz uni eng yaqin deb ataymiz. A, B va V nuqtalardan o'tuvchi aylana markazi AB, BV va VA segmentlarining o'rta nuqtalariga perpendikulyarlarning kesishmasida yotadi. Doira markazining holati AB chetiga perpendikulyar, uzunligi teng va AB chetining o'rtasidan o'tuvchi MN segmentining t parametri bilan tavsiflanadi.

Guruch. 9.7.3. Delaunay triangulyatsiya jarayoni

AB segmentining chap tomonida joylashgan barcha cho'qqilar uchun eng yaqin cho'qqi eng kichik parametr t ga ega. Eng yaqin cho'qqiga to'g'ri keladigan aylana AB segmentining chap tomonidagi boshqa cho'qqilarni o'z ichiga olmaydi. A, B va V cho'qqilari mos ravishda ikki o'lchovli radius vektorlari bilan tasvirlansin. AB va BV segmentlarining o'rta nuqtalarining radius vektorlari teng bo'ladi

A, B va V nuqtalardan o'tuvchi aylana markazining undagi holatiga mos keladigan chiziqning t parametrining qiymati ga teng.

AB segmentining chap tomoniga eng yaqin cho'qqi uchun t parametri minimal qiymatga ega.

Keling, barcha chegara qirralarini shunday yo'naltiramizki, uchburchak qilinadigan maydon ularning har birining chap tomonida joylashgan. Biz har qanday chegara chetidan uchburchaklar qurishni boshlaymiz. Keling, unga eng yaqin cho'qqini topamiz, uning tegishli doirasi boshqa uchlarini o'z ichiga olmaydi. AB chegara chekkasi uchun eng yaqin V cho'qqi topilsin, keyin ABV uchburchakni quramiz va AB chetini faol bo'lmaganlar toifasiga o'tkazamiz. Biz triangulyatsiya algoritmida ishtirok etmaydigan faol bo'lmagan qirralar va cho'qqilarni chaqiramiz. Agar chegara qirralari orasida BV chekkasi bo'lmasa, u holda VB segmentida yangi chegara quramiz. Agar chegara qirralari orasida BV chekkasi mavjud bo'lsa, biz uni va B cho'qqini faol bo'lmaganlar toifasiga o'tkazamiz. Agar chegara qirralari orasida VA chekkasi bo'lmasa, u holda AV segmentida yangi chegara quramiz. Agar chegara qirralari orasida VA chekkasi bo'lsa, biz uni va A cho'qqini faol bo'lmaganlar toifasiga o'tkazamiz. Triangulyatsiya jarayoni rasmda ko'rsatilgan. 9.7.3.

Guruch. 9.7.4. Delaunay triangulyatsiyasi

Barcha uchlari va qirralari faol bo'lmaganda biz triangulyatsiyani tugatamiz. Berilgan maydonning triangulyatsiyasi natijasi rasmda ko'rsatilgan. 9.7.4.

Tuzatish usuli bilan triangulyatsiya.

Parametrlarni aniqlash uchun to'rtburchaklar domeni bilan ma'lum bir sirtni uchburchakni ko'rib chiqamiz. (9.4.7) formulaga muvofiq qo'shni chiziqlar orasidagi parametrik masofalarni teng deb olaylik.

(9.4.8) formulaga muvofiq qo'shni chiziqlar orasidagi parametrik masofalarni teng deb olaylik.

Barcha to'rtburchaklar katakchalarda diagonallarni qurish orqali biz sirtning triangulyatsiyasini olamiz (biz talablarga javob beradigan uchburchaklar to'plamini olamiz). Shaklda. 9.7.5 tasvirlangan usul yordamida inqilob sirtining triangulyatsiyasini ko'rsatadi.

Keling, ixtiyoriy chegaraga ega bo'lgan sirtning triangulyatsiyasini ko'rib chiqaylik. Biz parametrlarni aniqlash uchun to'rtburchak maydon bilan yuqorida tavsiflangan sirt triangulyatsiyasining chegara konturlari bo'yicha tuzatish bo'yicha triangulyatsiya usulini quramiz.

Guruch. 9.7.5. Parametrlarni aniqlash uchun to'rtburchaklar domenli sirtni triangulyatsiya qilish

Parametrlarni aniqlash sohasidagi sirt chegarasi bir nechta kesishmaydigan ikki o'lchovli konturlar bilan tasvirlangan bo'lsin (2.12.7). Konturlardan biri tashqi bo'lib, qolgan konturlarni o'z ichiga oladi. Har bir konturning ijobiy yo'nalishi uchun biz yo'nalishni olamiz, u bo'ylab harakatlanayotganda, sirtni aniqlash maydoni har doim konturning chap tomonida, normal sirtga qaraganida. Sirtni aniqlash maydonining chegara konturlarining musbat yo'nalishi bo'yicha ko'pburchaklar quramiz. Chegaraviy ko'pburchaklarni qurish uchun siz qandaydir o'zgaruvchan qadam bilan sirtning chegara konturlari bo'ylab yurishingiz va koordinatalari sirt parametrlari bo'lgan ikki o'lchovli nuqtalar qatorini to'ldirishingiz kerak. Biz parametrik tekislikdagi nuqtalardan ko'pburchak quramiz, lekin bir nuqtadan ikkinchisiga o'tishda qadam fazoviy geometriyadan, ya'ni qo'shni nuqtalar orasidagi egri yoyning egilishi berilgan qiymatdan oshmasligi sharti bilan aniqlanadi. qiymat. Biz (9.4.4) formuladan foydalanib, sirt chegarasi konturi egri chizig'i uchun ko'pburchakni qurishning parametrik bosqichlarini hisoblaymiz.

Har bir ko'pburchak ikki o'lchovli nuqtalarning tartiblangan to'plamidan iborat. Ko'pburchakning har bir bo'limi ikkita qo'shni nuqtaga qurilgan ikki o'lchovli to'g'ri chiziq segmenti sifatida qaralishi mumkin. Biz bunday maydonlarni chegara qirralari sifatida ishlatamiz va uchburchak cho'qqilari sifatida qirralarning asosi bo'lgan ko'pburchaklar nuqtalari qo'llaniladi. Sirt parametrlarini aniqlash maydoni chegara ko'pburchaklarining chap tomonida joylashganligi sababli, har bir chegara uchburchagi uchun uchburchaklar qurishda, uchburchakning uchinchi uchini chetning chap tomonida izlash kerak.

Qaysi tugunlar chegaraviy ko‘pburchaklar ichida, qaysilari chegarada yoki sirtni aniqlash maydonidan tashqarida yotishini aniqlaymiz. Ushbu ma'lumotlardan foydalanib, biz to'rtburchaklar panjara hujayralarini ikki guruhga ajratamiz. Birinchi guruhga sirt parametrlari aniqlangan hududda to'liq yotadigan hujayralar kiradi (hujayralar chegara poligonlariga tegmasligi kerak). Ikkinchi guruh qolgan hujayralarni o'z ichiga oladi (sirtni aniqlash maydonidan tashqarida joylashgan yoki chegara poligonlari bilan kesishgan).

Guruch. 9.7.6. Tugallanmagan sirt triangulyatsiyasi

Birinchi guruhning har bir katakchasi ichida diagonaldan foydalanib, ikkita uchburchak quramiz. Shunday qilib, biz tugallanmagan uchburchakni olamiz. Konturlar bilan chegaralangan inqilob yuzasi uchun birinchi guruh kataklarida uchburchaklar qurish misoli rasmda ko'rsatilgan. 9.7.6.

Biz ikkinchi guruh kataklarining kesilmagan tomonlarida chegara qirralarini quramiz va ularni mos keladigan katak chetning chap tomonida bo'ladigan tarzda yo'naltiramiz. Birinchi guruh kataklari atrofida biz yopiq siniq chiziqni (ehtimol bir nechta yopiq chiziqlar) quramiz, shunda u bo'ylab harakatlanayotganda, uchburchaklarga bo'linmagan maydonning chap tomonida, normal sirtga qaraganida yotadi. . Shuningdek, biz bu singan chiziqning tekis qismlarini chegara qirralari sifatida ishlatamiz. Biz barcha qirralarni teng deb hisoblaymiz. Triangulyatsiyani yakunlash uchun biz chegara qirralari orasidagi uchburchaklarni qurishimiz kerak. Har bir chekka uchun biz uning chap tomonida joylashgan va uchburchak qurish uchun ishlatilishi mumkin bo'lgan cho'qqini qidiramiz. Biz cho'qqini faqat chekkasi bilan bir katakda yotadigan cho'qqilar orasidan qidiramiz. Tepani tanlash uchun biz yuqorida tavsiflangan va rasmda tasvirlangan Delaunay usulidan foydalanamiz. 9.7.2. Agar shunday cho'qqi topilsa, unda siz uchburchakning ikkita yangi qirralari har qanday chegara qirrasi bilan kesishganligini tekshirishingiz kerak. AB chegara chekkasi uchun eng yaqin V cho'qqi topilsin va BV va VA segmentlarining boshqa chegara qirralari bilan kesishmasligini tekshiring. Keyin ABV uchburchagini quramiz va AB chetini faol bo'lmagan toifaga o'tkazamiz. Agar chegara qirralari orasida BV chekkasi bo'lmasa, u holda VB segmentida yangi chegara quramiz, lekin chegara qirralari orasida BV chekkasi bo'lsa, uni va B cho'qqisini faol bo'lmaganlar toifasiga o'tkazamiz. Agar chegara qirralari orasida VA chekkasi bo'lmasa, u holda AV segmentida yangi chegara quramiz, lekin chegara qirralari orasida VA cheti bo'lsa, uni va A cho'qqisini faol bo'lmaganlar toifasiga o'tkazamiz.

Agar segment yoki VA boshqa chegara qirralarini kesib o'tsa, biz boshqa chegara chekkasi uchun eng yaqin cho'qqini qidirishga o'tamiz. Triangulyatsiya barcha qirralar va uchlari nofaol deb tasniflangandan so'ng yakunlanadi.

Guruch. 9.7.7. Tuzatish usuli bilan triangulyatsiya

Shaklda. 9.7.7 chegara konturlari bilan kesishgan hujayralardagi uchburchaklarni tuzatish usuli bilan sirt triangulyatsiyasini ko'rsatadi. Shaklda. 9.7.8, natijada olingan triangulyatsiya yordamida sirtning o'zi ko'rsatiladi.

Agar chegaraviy ko'pburchaklar va sirt qandaydir simmetriyaga ega bo'lsa, u holda tuzatish usuli bilan triangulyatsiya xuddi shunday simmetriyaga ega bo'ladi.

Absorbsiya usuli bilan triangulyatsiya.

Keling, boshqa triangulyatsiya usulini ko'rib chiqaylik. Tezlik jihatidan u Delaunay triangulyatsiyasidan va uning modifikatsiyalaridan past. Triangulyatsiya protsedurasini boshlash uchun sirt chegarasini yopiq ko'pburchaklar shaklida tasvirlash kerak. Triangulyatsiya jarayonida biz sirt parametrlari asosida qadamlarni aniqlashimiz kerak bo'ladi. Harakatning ma'lum yo'nalishi bilan bu qadamlar (9.4.6) formulalar bilan aniqlanadi. Sirt parametrlari uchun taxminiy qadamlarni quyidagicha topish mumkin. Parametr tekisligida ma'lum bir nuqta atrofida shunday mintaqani aniqlaymizki, bu mintaqadagi nuqtadan nuqtaga har qanday fazoviy segment sirtdan berilgan S qiymatidan uzoq bo'lmaydi.

Buning uchun biz koordinata chiziqlari bo'ylab parametrlarning ruxsat etilgan o'sishini hisoblaymiz

nuqtada sirtning birinchi va ikkinchi kvadratik shakllarining koeffitsientlari qaerda. Kerakli hududning chegarasi sifatida biz bir nuqtada markazi va yarim o'qlari bo'lgan ellipsni olamiz. Bu ellips tenglamaga ega

Agar siz tekislikda va o'qi bilan burchak tomonidan berilgan yo'nalishdagi nuqta yonidagi nuqtani topmoqchi bo'lsangiz, u holda uning parametrlari quyidagicha bo'ladi.

Birinchidan, sirt parametrlari maydoni bitta tashqi kontur bilan cheklangan bo'lsa, oddiyroq holatni ko'rib chiqaylik. Biz sirt chegarasini parametrik sohada yopiq ko'pburchak bilan yaqinlashtiramiz. Triangulyatsiyani qurishda biz ishchi ko'pburchakdan foydalanamiz, bu holda biz tashqi konturning ko'pburchagi sifatida olamiz. Olingan ikki o'lchovli nuqtalar qatoriga ko'pburchak nuqtalarini qo'shamiz. Biz ishchi maydonning chetidan uchburchaklar quramiz, ish joyida faqat uchta nuqta qolguncha uni toraytiramiz.

Ishchi ko‘pburchakda u mintaqaga aylanadigan cho‘qqini topamiz. Bunday nuqta har doim mavjud va undagi burilish burchagi kichikroq. Bu nuqtani O bilan belgilaymiz, parametrlarini esa bu nuqtaga yaqin joyda aylanish burchagiga qarab bir yoki ikkita uchburchak quramiz. Agar burchak kichikroq bo'lsa, unda biz ushbu uch nuqtada bitta uchburchak quramiz (9.7.9-rasm). Aks holda, biz buning ustiga ikkita uchburchak, ikkita qo'shni va bitta yangi nuqta quramiz (9.7.11-rasm). Yangi nuqta P bilan belgilanadi. B OS P parallelogramma diagonalida P nuqtani qidiramiz. Agar parallelogrammning tepasi ellips ichida yotsa (9.7.10-rasm), u holda uni P nuqta deb olamiz. Aks holda, ellipsning kesishishini va parallelogramma diagonalini P nuqta sifatida olamiz. Ikkinchi holda, ellips va segmentning kesishishini izlash mutlaqo kerak emas.

P nuqtaning koordinatalari miloddan avvalgi O nuqtalarning koordinatalari orqali aniqlanadi

OP segmentining gorizontal bilan burchagi tenglik bilan aniqlanadi

(9.7.8)

Bu ma'lumotlar P nuqtaning ellipsga nisbatan o'rnini aniqlash imkonini beradi (9.7.5).

Shaklda ko'rsatilgan holatda. 9.7.9, keling, uchburchak quramiz (uning uchlari raqamlarini eslaymiz) va rasmda ko'rsatilgan holatda O nuqtasini o'chiramiz. 9.7.11, biz ikkita uchburchak quramiz va ish sohasida biz O nuqtasini P nuqta bilan almashtiramiz va ikkinchisini hosil bo'lgan nuqtalar qatoriga joylashtiramiz. Shaklda. 9.7.12-rasmda ikkita uchburchakni qurish va O nuqtasini yo'q qilish natijasida olingan ko'pburchak ko'rsatilgan. Ikkala holatda ham O nuqta ishchi ko'pburchakdan chiqariladi va ishchi ko'pburchak torayadi. E'tibor bering, uchburchaklar faqat ish maydoni toraygandan keyin o'zini kesib o'tmaganda tuzilishi mumkin.

Guruch. 9.7.9. Uchburchak qurish

Guruch. 9.7.10. Natija ko'pburchak

Guruch. 9.7.11. Ikkita uchburchakning qurilishi

Guruch. 9.7.12. Natija ko'pburchak

Bunday holatlar rasmda ko'rsatilgan. 9.7.13. Ular qurilgan uchburchaklarning tomonlari ish joyining ularga qo'shni bo'lmagan tomonlarini kesib o'tganda paydo bo'lishi mumkin. Shaklda ko'rsatilgan holatda bo'lgani kabi, yangi uchburchak qurishdan oldin. 9.7.9 va shaklda ko'rsatilgan holatda. 9.7.11, natijada paydo bo'lgan ko'pburchakning o'zini kesib o'tmasligini tekshirish kerak.

Bundan tashqari, P nuqtasining o'rnini aniqlashda, u ish joyining boshqa nuqtalaridan etarlicha masofada joylashganligi va hududning nuqtalarini bog'laydigan segmentlarga yaqinlashmasligi muhimdir. Aks holda, kelajakda uchburchaklarni qurishda qiyinchiliklar paydo bo'lishi mumkin. Shuning uchun, ishchi ko'pburchakni toraytirishdan oldin, natijada olingan ko'pburchakni o'z-o'zidan kesishish uchun tekshirishingiz kerak. Agar O nuqta yaqinida uchburchak (uchburchak) qurishning iloji bo'lmasa, uning o'rniga ko'pburchak kontur ichida boshqalarga qaraganda ko'proq o'raladigan boshqa nuqtani toping va unda tasvirlangan amallarni bajaring.

Keyinchalik, o'zgartirilgan ish maydoni bilan biz yuqorida tavsiflangan harakatlarni bajaramiz. Ishchi ko‘pburchakning boshqa nuqtalarga qaraganda maydon ichida ko‘proq aylanayotgan nuqtasini topamiz, undagi ko‘pburchakni bir yoki ikkita uchburchak yasash orqali toraytirish imkoniyatini tekshiramiz va ko‘pburchakni toraytiramiz.

Guruch. 9.7.13. Bu burchakda uchburchaklar qura olmaysiz

Ushbu jarayonni davom ettirib, biz ikki o'lchovli nuqtalar massivini va uchburchaklar massivini kengaytiramiz va shu bilan birga ishchi ko'pburchakni toraytiramiz, uning qoplagan maydoni va nuqtalari sonini kamaytiramiz. Ushbu harakatlarning bir bosqichida biz uch nuqtadan iborat ishchi ko'pburchakni olamiz. Keling, ushbu nuqtalarda oxirgi uchburchakni quramiz, ish joyini yo'q qilamiz va triangulyatsiyani tugatamiz. Ta'riflangan triangulyatsiya usulida ish maydoni bilan chegaralangan maydon, go'yo undan uchburchaklarni kesib tashlash orqali yo'q qilinadi.

Sirt parametrlarining maydoni bitta tashqi kontur va butunlay tashqi kontur ichida joylashgan bir nechta ichki konturlar bilan chegaralangan bo'lsa, umumiy holatni ko'rib chiqaylik. Biz sirt chegarasini parametrik sohadagi yopiq ko'pburchaklar orqali yaqinlashtiramiz. Har bir kontur uchun biz o'z poligonimizni quramiz. Xuddi konturlarda bo'lgani kabi, ularning ustiga qurilgan ko'pburchaklar uchun ham ularning o'zaro yo'nalishi qoidasi bajarilishi kerak. Ichki ko'pburchaklarning yo'nalishi tashqi ko'pburchakning yo'nalishiga qarama-qarshi bo'lishi kerak. Keling, tashqi konturli ko'pburchak bilan triangulyatsiyani qurishni boshlaylik. Keling, uning nuqtalarini hosil bo'lgan ikki o'lchovli nuqtalar massiviga qo'yamiz va ko'pburchakning o'zini ishlaydigan holga keltiramiz.

Biz uchburchaklarni oddiy bog'langan mintaqada bo'lgani kabi quramiz. Ishchi sohada O nuqtasini topamiz, u erda ish joyini toraytirish imkoniyatini tekshiramiz va maydonni toraytiramiz. Agar ichki konturlar mavjud bo'lsa, tanlangan nuqtada ish joyini toraytirish imkoniyatini tekshirish qiyinroq bo'ladi. Ta'riflangan uchburchaklar tomonlarini ishchi maydonning yon tomonlari bilan kesishishini tekshirishga qo'shimcha ravishda, uchburchaklar tomonlarini barcha ichki ko'pburchaklar tomonlari bilan kesishishini tekshirish kerak.

O nuqtada ikkita uchburchak qurish imkoniyatini tekshirib ko'raylik (9.7.11-rasm) va yangi P nuqta qurilganidan keyin ichki ko'pburchaklardan birining ichiga tushishini yoki uning segmentlariga qabul qilib bo'lmaydigan yaqinlikda bo'lishini aniqlaymiz. Bunday holda, biz P nuqtasini qurmaymiz, aksincha, rasmda ko'rsatilgan ikkita uchburchakni qurish orqali ushbu ichki ko'pburchakni ishchi ko'pburchakka kiritamiz. 9.7.14.

Ichki ko‘pburchaklardan birining nuqtalarini ishchi ko‘pburchakka kiritish uchun ichki ko‘pburchak nuqtalari orasidan ishchi ko‘pburchakning S nuqtasiga (O nuqtaga tutash) eng yaqin nuqtani topamiz.

OCF va CEF nuqtalarida uchburchaklar quramiz va ishchi maydonning O va C nuqtalari orasiga F nuqtadan boshlab E nuqta bilan tugaydigan ichki ko'pburchakning nuqtalarini kiritamiz. Shunday qilib, OS segmentida ish maydonini sindiramiz, EF segmentidagi ichki ko'pburchak va ularni OF va EI segmentlari bilan birlashtiring.

Guruch. 9.7.14. Ikkita uchburchakning qurilishi

Guruch. 9.7.15. Tashqi va ichki ko'pburchaklarni birlashtirish

Birlashma natijasi rasmda ko'rsatilgan. 9.7.15. Albatta, tashqi va ichki ko'pburchaklarni birlashtirishdan oldin, ushbu operatsiyaning to'g'riligini tekshirish uchun tekshirish kerak.

Keyinchalik, biz o'zimizni boshqa ichki hududga yaqin joyda topmagunimizcha va uni ish maydoniga kiritmagunimizcha, tavsiflangan tarzda ish maydonini toraytirishni davom ettiramiz. Natijada, barcha ichki ko'pburchaklar ishchi poligonga kiritiladi, ular oxirgi uch nuqtaga toraytirilishi kerak. Natijada, sirt parametrlarini aniqlash uchun barcha ko'paytiriladigan bog'langan domen uchburchaklar bilan qoplanadi.

Guruch. 9.7.16. Bu burchakda uchburchaklar qura olmaysiz

Berilgan ko'pburchaklar ustida bitta uchburchak qurish mumkin bo'lmagan holatlar bo'lishi mumkin. Shaklda. 9.7.16-rasmda ikkita ko'pburchak bilan chegaralangan maydon ko'rsatilgan, ularning har biri to'rtta segmentdan iborat. Tashqi ko'pburchak uchun biz triangulyatsiyani davom ettira olmaymiz, chunki ichki ko'pburchak yo'lda. Bu holda biz ko'pburchakning ikkita qo'shni B va C nuqtalarini topamiz, ular uchun HRV uchburchakni qurishimiz mumkin. P nuqta BC tomonining o'rtasiga proyeksiyalangan va undan shunday masofada joylashganki, yangi uchburchak ko'pburchaklarni kesib o'tmaydi.

Triangulyatsiyaning boshqa usullari.

Triangulyatsiyaning boshqa usullari mavjud. Masalan, sirtni aniqlash maydonining tashqi va ichki konturlarining ko'pburchaklarini qurishdan so'ng, uchburchaklarni qurish uchun boshqa strategiyani tanlash mumkin. Yana bir variant - triangulyatsiyani boshlashdan oldin tashqi va ichki ko'pburchaklarni bitta ko'pburchakga birlashtirish. Siz ma'lum bir algoritm yordamida parametrlarni aniqlash maydoni ichidagi nuqtalarni "eskiz qilishingiz" va ular va chegara kontur poligonlari nuqtalari yordamida Delaunay triangulyatsiyasini bajarishingiz mumkin. Avval katta uchburchaklarni tuzadigan va keyin ularni boshqariladigan o'lchamlarga bo'ladigan algoritmlar mavjud.

Tana triangulyatsiyasi.

Tananing triangulyatsiyasi - bu uning yuzlari sirtlarini uchburchak qilish natijasida olingan uchburchaklar to'plami. Alohida yuzalarning triangulyatsiyasi tananing yuzlarining triangulyatsiyasidan farq qiladi, chunki ikkinchi holatda qo'shni yuzlar uchun chegara ko'pburchaklari izchil bo'lishi kerak (9.7.17-rasm).

Guruch. 9.7.17. Tana yuzi chegarasi poligon mustahkamligi

Umumiy qirralar bo'ylab o'tadigan qo'shni yuzlarning ko'pburchaklar bo'limlari, agar ularning nuqtalari bo'shliqda mos tushsa, izchil bo'ladi.

Triangulyatsiyani qo'llash.

Triangulyatsiya natijasida tuzilgan uchburchaklar ohangli tasvirlarni olish uchun ishlatiladi. Shaklda. 9.7.18 va 9.7.19 varaq tanasi yuzining uchburchaklarini ko'rsatadi, ularning ohangli tasviri rasmda ko'rsatilgan. 6.5.1.

Guruch. 9.7.18. Tuzatish usuli yordamida tana yuzining triangulyatsiyasi

Sirt parametrlarini aniqlash sohasini uchburchaklarga bo'lish jismlarning geometrik xarakteristikalarini hisoblashda (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) integrallarda qo'llanilishi mumkin. . Raqamli integratsiya jarayonida egri chiziqlar uchun parametrik qadam (8.11.5) formuladan foydalanib, sirtlar uchun parametrik qadamlar (8.11.1) va (8.11.2) formulalar yordamida hisoblanishi kerak.