Fazoviy Delaunay triangulyatsiyasi
Bir-birining ustiga chiqmaydigan uchburchaklar tarmog‘ini qurish muammosi hisoblash geometriyasining asosiy masalalaridan biri bo‘lib, kompyuter grafikasi va geografik axborot tizimlarida sirtni modellashtirish va fazoviy masalalarni yechishda keng qo‘llaniladi.
Bir-birining ustiga chiqmaydigan uchburchaklar tarmog'ini qurish muammosi birinchi marta 1934 yilda sovet matematigi B. N. Delonening tegishli shartlarni tuzgan ishida qo'yilgan.
Matematikada berilgan nuqtalardan triangulyatsiya yasash vazifasi, ularni juft bo‘lib kesishmaydigan segmentlar orqali bir-biriga bog‘lab, uchburchaklar tarmog‘i hosil qilish vazifasi hisoblanadi. Uning asosiy elementlari (5.3-rasm): tugunlar (uchburchaklarning uchlari), qirralari (yonlari) va yuzlari (uchburchaklarning o'zlari). Tuzilgan triangulyatsiya konveks (agar u modellashtirish maydonini qoplaydigan minimal ko'pburchak bo'lsa), qavariq bo'lmagan (agar triangulyatsiya qavariq bo'lmasa) va optimal (barcha qirralarning uzunliklarining yig'indisi minimal bo'lsa) bo'lishi mumkin.
Bunday uchburchaklar tarmog'i, agar u ma'lum shartlarni qondirsa, Delaunay triangulyatsiyasi deyiladi:
Asl nuqtalarning hech biri har qanday uchburchak atrofida aylana ichiga tushmaydi (5.3-rasm);
Triangulyatsiya qavariq va yuqorida ifodalangan Delaunay shartini qanoatlantiradi;
Barcha uchburchaklarning minimal burchaklarining yig'indisi barcha mumkin bo'lgan uchburchaklarning maksimali;
Uchburchaklar atrofida tasvirlangan doiralar radiuslarining yig'indisi barcha mumkin bo'lgan uchburchaklar orasida minimaldir.
Delaunay triangulyatsiyasini qurish uchun yuqoridagi mezonlardan birinchisi dumaloq deb ataladi, asosiylaridan biri bo'lib, umumiy yuzli har qanday uchburchak juftligi uchun tekshiriladi. Mezonning matematik talqini shakldan kelib chiqadi. 5.3:
(5.2)
Eng mashhurlaridan biri bo'lgan Delaunay triangulyatsiyasini qurishning ko'plab usullari mavjud Yaqinda triangulyatsiya tarmog'ini qurish usullari. U ko'plab GIS tizimlarida relyef modellarini yaratish uchun ishlatiladi.
Ikki o'lchovli fazoga qo'llanilganda, u quyidagicha ifodalanadi: bir-biriga bog'langan bir-birining ustiga tushmaydigan uchburchaklar tizimi, agar cho'qqilarning hech biri hosil bo'lgan uchburchaklar atrofida tasvirlangan doiralarning hech biri ichiga tushmasa, eng kichik perimetrga ega bo'ladi (5.4-rasm).
Guruch. 5.4. Delaunay triangulyatsiyasi
Bu shuni anglatadiki, bunday uchburchakka ega bo'lgan uchburchaklar teng qirrali uchburchaklarga iloji boricha yaqinroqdir va qarama-qarshi cho'qqidan olingan uchburchaklarning har bir tomoni mos keladigan yarim tekislikning barcha mumkin bo'lgan nuqtalaridan maksimal burchak ostida ko'rinadi. Bu aynan eng maqbul triangulyatsiya bo'lib, uning qirralari bo'ylab chiziqli interpolyatsiya odatda izoliyalarni qurish uchun amalga oshiriladi.
Delaunay triangulyatsiyasini qurish uchun ko'plab algoritmlar quyidagi teoremadan foydalanadi.
Teorema 1. Delonay uchburchaklarini bir xil nuqtalar sistemasidan foydalangan holda boshqa har qanday triangulyatsiyadan Deloney shartini qanoatlantirmaydigan qo‘shni uchburchaklar ABC va BCD juftlarini ABD va ACD uchburchaklar juftlariga ketma-ket joylashtirish orqali olish mumkin (5.5-rasm).
Guruch. 5.5.. Delona shartini qanoatlantirmaydigan uchburchaklarni rekonstruksiya qilish
Ushbu qayta qurish operatsiyasi ko'pincha flip deb ataladi. Bu teorema Delaun triangulyatsiyasini ketma-ket qurishga imkon beradi, avval ba'zi bir triangulyatsiyani qurish va keyin uni Delona sharti ma'nosida ketma-ket takomillashtirish. Qo'shni uchburchaklar juftlari uchun Delaunay shartini tekshirishda siz to'g'ridan-to'g'ri ta'rifdan foydalanishingiz mumkin, lekin ba'zida yuqorida sanab o'tilgan shartlar asosida boshqa usullar qo'llaniladi.
Bunday sharoitda butun triangulyatsiyaning umumiy xarakteristikasi (minimal burchaklar yig'indisi yoki radiuslar yig'indisi) paydo bo'ladi, qaysi birini optimallashtirish orqali Delaunay triangulyatsiyasini olish mumkin.
Yuqorida aytib o'tilganidek, biri muhim operatsiyalar triangulyatsiyani qurishda bajarilgan uchburchaklar juftlari uchun Delaunay shartini tekshirish. Delaunay triangulyatsiyasining ta'rifi va tegishli shartlarga asoslanib, amalda odatda bir nechta tekshirish usullari qo'llaniladi:
– aylana tenglamasi orqali tekshirish;
– oldindan hisoblangan chegaralangan doira bilan tekshiring;
– qarama-qarshi burchaklar yig‘indisini tekshirish;
- qarama-qarshi burchaklar yig'indisining o'zgartirilgan tekshiruvi.
Ko'pgina tizimlar sinovni oldindan hisoblangan aylana bilan amalga oshiradi. Oldindan hisoblangan doiralar orqali tekshirish algoritmining asosiy g'oyasi har bir qurilgan uchburchak uchun uning atrofida tasvirlangan doiraning markazi va radiusini oldindan hisoblashdan iborat, shundan so'ng Delaunay holatini tekshirish markazgacha bo'lgan masofani hisoblash uchun qisqartiriladi. bu doiraning va natijani radius bilan solishtirish. Atrofda tasvirlangan aylananing markazi va r radiusini , , , r 2 = (b 2 + c 2 - 4ad)/4a 2 shaklida topish mumkin, bunda qiymatlar a B C D(5.3) formulalar bilan aniqlanadi.
(5.3)
Ushbu doira tenglamasining yana bir yozuvi:
(5.5.)
(5.6)
Delaunay sharti boshqa triangulyatsiya nuqtasi uchun bo'lgandagina bajariladi:
(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)
Hozirgi vaqtda Delaunay triangulyatsiyasini qurish uchun ko'plab algoritmlar mavjud. Ko'pgina taniqli algoritmlar Delaunay triangulyatsiyasi ta'rifini ikkilamchi triangulyatsiya xususiyati sifatida ishlatadi. Shunday qilib, bunday algoritmlarda quyidagi kamchiliklar qayd etilgan:
– algoritmlarda doimiy hisoblangan trigonometrik funksiyalardan foydalaniladi, bu jarayonni keskin sekinlashtiradi;
- nuqtalar va tayanch segment o'rtasidagi munosabatni o'rganishda juda kichik burchaklar paydo bo'ladi va foydalanilganda trigonometrik funktsiyalar Kompyuterda ma'lumotlarni ko'rsatishning aniqligi cheklanganligi sababli tartib va 0 ga bo'linishning yo'qolishi doimiy xavfi mavjud; bu holat doimiy ravishda qo'shimcha ishlov berishni talab qiladi.
Eng mashhur dasturiy mahsulotlar Delaunay triangulyatsiyasini uchburchaklar qurishning asosiy, asosiy printsipi sifatida bo'sh to'p teoremasidan foydalanadi. Algoritm quyidagicha ko'rinadi:
- nuqtalarning butun to'plami uchburchaklarga bo'linadi, ya'ni. uch nuqtadan iborat kombinatsiyalar yaratiladi;
– har bir birikma uchun aylana va uning markazining koordinatalari topiladi;
– agar joriy kombinatsiya doirasi ichida bitta qolgan nuqta bo‘lmasa, bu kombinatsiya uchburchak bo‘lib, Delaunay triangulyatsiyasining bir qismidir.
Ushbu algoritmning afzalliklari quyidagilardan iborat:
– qurilish jarayonini sekinlashtirmaydigan trigonometrik funksiyalardan foydalanmaslik;
– hech qanday dastlabki konstruksiyasiz Delaunay triangulyatsiyasining bevosita qurilishi;
- barcha hisob-kitoblar va o'zgarishlarning soddaligi;
- natijada, triangulyatsiya panjarasi alohida chiziqlar emas, balki ko'plab uchburchaklar bilan ifodalanadi.
Shu tarzda qurilgan triangulyatsiya izoliyalarni qurish uchun geometrik asosdir.
Delaunay triangulyatsiyasini qurish algoritmlarini bir qancha guruhlarga bo'lish mumkin, ular qo'llaniladigan kirish ma'lumotlarining tuzilishi, hisoblash operatsiyalari hajmi, boshlang'ich binolari va hokazo. Ulardan ba'zilarini ko'rib chiqamiz.
Birlashtirish algoritmlari manba nuqtalari to'plamini kichik to'plamlarga bo'lish, ularning har biri bo'yicha triangulyatsiya qurish va keyin ularni yagona tarmoqqa birlashtirishni o'z ichiga oladi. Ushbu algoritmlardan birining mohiyati quyidagilarga to'g'ri keladi.
Dastlabki nuqtalar to'plami vertikal chiziqlar bilan ikki yoki undan ortiq qismlarga bo'linadi, shundan so'ng ularning har biri gorizontal va vertikal chiziqlar bilan taxminan teng qismlarga bo'linadi. Natijada, boshlang'ich nuqtalarning butun maydoni uch yoki to'rt nuqtadan iborat primitivlarga bo'linadi (2.4-rasm), ular bo'ylab bir yoki ikkita uchburchaklar qurilgan.
Ushbu uchburchaklarni bitta tarmoqqa birlashtirish ikkita asosiy chiziqni qurish orqali amalga oshiriladi (P 0 P 1 va P 2 P 3, guruch. 5.7.a), asosiy chiziqqa perpendikulyar bissektrisada markazlashtirilgan o'zgaruvchan radiusli doiralarni chizish (5.7-rasm, b), aylana (nuqta) ustiga tushadigan tugunni qidirish A, guruch. 5.7. v) va yangi uchburchakni qurish (P 0 P 1 A). Bunday holda, mavjud uchburchakni o'chirish kerak bo'lishi mumkin (masalan, P 0 AB).
Iterativ algoritmlar Delaunay mezonlariga muvofiq bir vaqtning o'zida takomillashtirish va qayta qurish bilan qisman tuzilgan triangulyatsiyaga nuqtalarni ketma-ket qo'shish g'oyasiga asoslanadi. IN umumiy ko'rinish ular bir necha bosqichlarni o'z ichiga oladi va dastlabki uchtasida uchburchakni qurish uchun qaynatiladi boshlang'ich nuqtalari va keyingi nuqtani joylashtirish uchun bir nechta variantlarni o'rganish. Xususan, uning modellash maydoni chegarasidan tashqarida, mavjud tugun yoki chetga, qurilgan uchburchak ichida va hokazo tushishi variantlari ko'rib chiqiladi. Bu variantlarning har biri ma'lum bir operatsiyani bajarishni o'z ichiga oladi: chetni ikkiga, yuzlarni bo'lish. uchta va boshqalar; shundan so'ng hosil bo'lgan uchburchaklar Delaunay shartiga muvofiqligi va kerakli rekonstruktsiyalar tekshiriladi.
Ikki o'tishli algoritmlar avval Delaunay shartlarini e'tiborsiz qoldirib, ba'zi bir triangulyatsiyani qurishni va keyin uni ushbu shartlarga muvofiq qayta qurishni o'z ichiga oladi. Algoritmni qo'llash misoli rasmda ko'rsatilgan. 5.8.
Yaratilgan relyef modelini realga yaqinlashtirish uchun uning chiziqli va hududiy strukturaviy elementlarini hisobga olish va aks ettirishni ta'minlash uchun unga qo'shimcha elementlar kiritiladi. Bunday qo'shimcha elementlar topografiyada keng qo'llaniladigan "relef skeleti" ni belgilaydigan strukturaviy chiziqlar: suv havzalari, talveglar, tizmalar, qoyalar, qirlar, ko'llar, jarliklar, qirg'oqlar, sun'iy inshootlarning chegaralari va boshqalar, ularning yig'indisi o'ziga xos shaklni yaratadi. Delaunay triangulyatsiyasi uchun ramka. Ushbu konstruktiv chiziqlar uchburchaklar qirralari sifatida triangulyatsiyaga kiritiladi, bu esa er yuzasining umumiy notekisligi fonida haqiqiy relyef elementlarini modellashtirishga erishadi. Bunday qirralarning konstruktiv (sobit, qayta sozlanmaydigan) deb ataladi, boshqa uchburchaklarning qirralarini kesib o'tmaydi va keyinchalik o'zgarmaydi.
Kesish chiziqlarini hisobga olgan holda sirt modelini qurish masalasi chegaralangan Delonay uchburchagi deb ataladi, agar Delaunay shartlari uzilish chiziqlari bilan ajratilmagan qo'shni uchburchaklar juftligi uchun qanoatlansa. Tadqiqotchilarning fikriga ko'ra, eng samarali yo'l, takrorlanuvchi algoritmlar yordamida bunday triangulyatsiyani qurishdir.
Delaunay triangulyatsiyasining bir qismi unga kiritilgan qo'shimcha elementlar bilan rasmda ko'rsatilgan. 5.9, bu erda o'ng tomonda tugunlar, qirralar, qirralar va strukturaviy chiziqlar, chapda esa erning strukturaviy chiziqlari (sohil chiziqlari, jarliklar va boshqalar) va ma'lum belgilarga ega nuqtalar ko'rsatilgan.
Delaunay triangulyatsiyasini qurish algoritmlari tugunlar koordinatalarining haqiqiy yoki butun sonli tasviri bilan amalga oshiriladi, bu ishlov berish tezligi va aniqligini sezilarli darajada oshirishi mumkin, ammo mos keladigan tugunlarni qidirish va istisno qilish muammolarini keltirib chiqaradi.
TIN modeli tugunlarni ko'chirish, yangilarini kiritish, mavjudlarini o'chirish, bir yoki bir nechta qirralarning o'rnini o'zgartirish, yangi strukturaviy chiziqlarni kiritish va boshqalar orqali osongina tahrirlanadi. Bunday o'zgarishlar har doim qo'shni uchburchaklarning kichik guruhiga ta'sir qiladi, qayta qurishni talab qilmaydi. butun tarmoq va kursorni mos keladigan elementga yo'naltirish orqali onlayn rejimda amalga oshiriladi.
Aniqlik haqida:
Piketlarni xarakterli relyef elementlariga (masalan, suv havzalari va talveglar) joylashtirish orqali biz bo'shliqlardagi kichikroq elementlarga e'tibor bermaymiz. Uchburchaklarning bunday qirralari bo'ylab kontur chiziqlarini1 qurishda xatolik yuzaga keladi, bu erning notekisligi miqdori va erning moyillik burchagiga bog'liq. Masalan, relyefni o'lchashda o'rtacha xato 2 dan 10 gradusgacha bo'lgan sirt moyillik burchaklarida relyef kesimining 1/3 qismidan oshmasligi kerak. Hisoblash mumkinki, relef kesimi 0,5 m bo'lgan holda, o'tkazib yuborilgan notekislikning maksimal qiymati (ya'ni, er yuzasining qo'shni piketlardan o'tadigan to'g'ri chiziqdan og'ishi) (0,5/3) *cos10 ° dan oshmasligi kerak. =0,16 m.
Tashilayotgan tuproq hajmini aniqlashning aniqligi uchun hisobga olinmagan relyef detali egallagan maydon ham muhim ahamiyatga ega. Aytaylik, ikki juft piket o'rtasida 20x20 m kvadratda maksimal balandligi 0,15 m bo'lgan silindrsimon qavariq bor.Hisoblash oson, bu sirtni faqat ikkita uchburchak bilan ifodalashda uni hisobga olmaslik, buning natijasida yuzaga keladi. taxminan 40 m3 xato. Juda ko'p emas, lekin tepalikda yoki nishabning yuqori (odatda konveks) qismida joylashgan 1 gektar maydon uchun siz 40 * 25 = 1000 m3 ortiqcha tuproqni olasiz. Agar siz ikki marta tez-tez (ya'ni har 10 m) piketlarni olsangiz, xatolik to'rt barobar kamayadi va gektariga 250 m3 ni tashkil qiladi. Bu omilni oldindan hisobga olish mumkin, chunki tekis relyefning ijobiy shakllari odatda konveks shaklga ega, salbiy shakllar esa konkav shaklga ega. Agar o'rganiladigan maydon relyef bo'yicha taxminiy ma'lumotlarga ega bo'lsa, u holda sirtning egrilik radiusi va piketlarning kerakli zichligini kontur chiziqlari yoki individual balandliklar qiymatlaridan osongina hisoblash mumkin.
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 triangulyatsiyani qurish masalasi ulanish masalasi deb ataladi berilgan ballar kesishmaydigan segmentlar, shuning uchun triangulyatsiya hosil bo'ladi.
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, keling, nuqtalar tizimiga joylashtiramiz (A) bo'sh to'p Delaunay. 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 sohasi o'zida 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 kattalashganda, u tizimning uchinchi nuqtasiga, 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, juda 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 tez ko'rsatish uchun ularning yuzlari uchburchak plitalarga yaqinlashtiriladi. 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 qidirishning hojati 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, bu erda K - chegaralovchi ko'p chiziqning uchlari soni, I - mintaqa 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'qqini tanlaymiz, mos aylana V nuqtada joylashgan AB segmentiga nisbatan bir tomonda boshqa cho'qqilarni o'z ichiga olmaydi.Chegara chekkasi uchun umumiy holatda shunday cho'qqilardan biri bo'lishi mumkin. 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 mos keladigan aylanada AB segmentining chap tomonidagi boshqa cho'qqilar mavjud emas. 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. Triangulyatsiya algoritmida qatnashmaydigan faol bo'lmagan qirralar va uchlarini chaqiramiz. Agar chegara qirralari orasida BV chekkasi bo'lmasa, u holda VB segmentida yangi chegara quramiz. Agar chegara qirralari orasida BV qirrasi 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, uni va A cho'qqisini 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 ma'lum bir sirtni to'rtburchaklar sohasi bilan uchburchakni ko'rib chiqamiz.Yuza parametrlarini aniqlash sohasini ikki o'lchovli chiziqlar bilan to'rtburchaklar kataklarga ajratamiz.Bu chiziqlar to'rtburchaklar panjara hosil qiladi. (9.4.7) formulaga muvofiq qo'shni chiziqlar orasidagi parametrik masofalar teng bo'lsin.
(9.4.8) formulaga muvofiq qo'shni chiziqlar orasidagi parametrik masofalar teng bo'lsin.
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 qurish uchun parametrik bosqichlarni hisoblaymiz.
Har bir ko'pburchak ikki o'lchovli nuqtalarning tartiblangan to'plamidan iborat.Ko'pburchakning har bir kesimini ikkita qo'shni nuqtaga qurilgan ikki o'lchovli to'g'ri chiziq segmenti deb hisoblash mumkin. Biz bunday maydonlarni chegara qirralari sifatida ishlatamiz va uchburchak cho'qqilari sifatida qirralarning asosi bo'lgan ko'pburchaklar nuqtalaridan foydalanamiz. Sirt parametrlarini aniqlash maydoni chegara ko'pburchaklarining chap tomonida joylashganligi sababli, har bir chegara uchburchagi uchun uchburchaklar qurishda siz uchburchakning uchinchi uchini chetning chap tomonida qidirishingiz 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 ko'pburchaklariga 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 to'g'ri 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 uchi 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. Istalgan 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, 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, buning ustiga ikkita qo'shni va bitta yangi nuqta bo'lgan ikkita uchburchak quramiz (9.7.11-rasm). Yangi nuqta P bilan belgilanadi. B OS P parallelogramma diagonalida P nuqtani qidiramiz. Agar parallelogrammning cho'qqisi ellips ichida bo'lsa (9.7.10-rasm), u holda uni P nuqta deb olamiz. Aks holda ellips va parallelogramm diagonalining kesishuvini P nuqta deb 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 ish maydonidagi O nuqtasini o'chiramiz.1-rasmda ko'rsatilgan holatda. 9.7.11, biz ikkita uchburchak quramiz va ish sohasida 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. Uchburchakning qurilishi
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 uchburchakni 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‘pburchakda u boshqa nuqtalarga qaraganda maydon ichida ko‘proq aylanadigan nuqtani 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 cheklangan 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 poligonga 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 segmentida 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 butun ko'paytiriladigan bog'langan hudud 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'pburchakka 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.
Cheklangan S nuqtalar to‘plami uchun triangulyatsiya - S to‘plamning barcha nuqtalarini o‘rab turgan CH(S) qavariq korpusini uchburchak qilish muammosi. Triangulyatsiyadagi to‘g‘ri chiziq segmentlari kesisha olmaydi – ular faqat S to‘plamga tegishli umumiy nuqtalarda uchrasha oladi. to'g'ri chiziq segmentlari uchburchaklarni yopadi, biz ularni qovurg'a deb hisoblaymiz. Shaklda. 1-rasmda bir xil nuqtalar to'plami uchun triangulyatsiyaning ikki xil versiyasi ko'rsatilgan (biz bu raqamlarda chizilgan doiralarni vaqtincha e'tiborsiz qoldiramiz).
Guruch. 1
Berilgan S nuqtalar to‘plami uchun biz S to‘plamdagi barcha nuqtalarni chegara nuqtalariga - qavariq korpus CH(S) chegarasida yotuvchi nuqtalarga va qavariq ichida yotgan ichki nuqtalarga bo‘lish mumkinligini ko‘rishimiz mumkin. korpus CH(S). S triangulyatsiyasi natijasida olingan qirralarni ham tasniflashingiz mumkin qobiq qovurg'alari Va ichki qovurg'alar. Korpus qirralariga qavariq korpus CH(S) chegarasi bo‘ylab joylashgan qirralar kiradi, ichki qirralarga esa qavariq korpus ichida uchburchaklar tarmog‘ini tashkil etuvchi barcha boshqa qirralar kiradi. E'tibor bering, har bir qobiq qirrasi ikkita qo'shni chegara nuqtasini bog'laydi, ichki qirralar esa har qanday turdagi ikkita nuqtani bog'lashi mumkin. Xususan, agar ichki chekka ikkita chegara nuqtasini bog'laydigan bo'lsa, u holda bu CH(S) konveks korpusining akkordidir. Shuni ham yodda tutingki, triangulyatsiyaning har bir qirrasi ikkita mintaqaning chegarasi: har bir ichki chekka ikkita uchburchak orasida va qobiqning har bir chekkasi uchburchak va cheksiz tekislik orasida.
Har qanday nuqtalar to'plami, ba'zi bir ahamiyatsiz holatlar bundan mustasno, bir nechta triangulyatsiya usullariga imkon beradi. Ammo diqqatga sazovor xususiyat bor: berilgan to'plam uchun triangulyatsiyaning har qanday usuli teoremadan kelib chiqadigan bir xil sonli uchburchaklarni aniqlaydi:
Nuqtalar to'plamining triangulyatsiyasi haqidagi teorema. Faraz qilaylik, S nuqtalar to'plamida n>3 nuqta bor va ularning hammasi ham kollinear emas. Bundan tashqari, ulardan i nuqtalari ichki (ya'ni, qavariq korpus CH(S) ichida yotgan. Keyin, S to'plamni triangulyatsiya qilishning har qanday usuli aniq n + i - 2 uchburchakka olib keladi.
Teoremani isbotlash uchun birinchi navbatda n-i chegara nuqtalarining triangulyatsiyasini ko‘rib chiqamiz. Ularning barchasi qavariq ko'pburchakning cho'qqilari bo'lganligi sababli, bunday triangulyatsiya natijasida (n - i) - 2 ta uchburchak paydo bo'ladi. (Buni tekshirish qiyin emas va bundan tashqari, har qanday triangulyatsiya mavjudligini ko'rsatish mumkin o'zboshimchalik bilan M qirrali ko'pburchak - qavariq yoki qavariq bo'lmagan - m - 2 uchburchakni o'z ichiga oladi). Keling, qolgan i ichki nuqtalarni har safar bittadan qo'shganda triangulyatsiya nima bo'lishini tekshirib ko'ramiz. Biz har bir bunday nuqtani qo'shish uchburchaklar sonini ikkiga oshiradi, deb da'vo qilamiz. Ichki nuqta qo'shganda, rasmda ko'rsatilgan ikkita holat yuzaga kelishi mumkin. 2. Birinchidan, nuqta qandaydir uchburchak ichida bo'lishi mumkin va keyin bunday uchburchak uchta yangi uchburchak bilan almashtiriladi. Ikkinchidan, agar nuqta triangulyatsiya qirralarining biriga to'g'ri kelsa, u holda bu chetga ulashgan ikkita uchburchakning har biri ikkita yangi uchburchak bilan almashtiriladi. Bundan kelib chiqadiki, barcha i nuqtalarni qo'shgandan so'ng, uchburchaklarning umumiy soni (n - i - 2) + (2i) yoki oddiygina n + i - 2 bo'ladi.
Guruch. 2
Ushbu bo'limda biz Delaunay triangulyatsiyasi deb nomlanuvchi triangulyatsiyaning maxsus turini yaratish algoritmini taqdim etamiz. Ushbu triangulyatsiya yaxshi muvozanatlangan, chunki hosil bo'lgan uchburchaklar teng burchakli bo'ladi. Misol uchun, rasmda ko'rsatilgan triangulyatsiya. 1a Delaunay triangulyatsiyasi turiga tegishli bo'lishi mumkin va rasmda. 1b triangulyatsiya bir nechta juda cho'zilgan uchburchaklarni o'z ichiga oladi va ularni Delaunay turiga kiritish mumkin emas. Shaklda. 3-rasmda ko'p sonli nuqtalar to'plami uchun Delaunay triangulyatsiyasi misoli ko'rsatilgan.
Guruch. 3
Delaunay triangulyatsiyasini shakllantirish uchun bizga bir nechta yangi ta'riflar kerak. Agar to'plamdagi barcha nuqtalar yotadigan doira mavjud bo'lsa, nuqtalar to'plami aylana hisoblanadi. Bunday doira berilgan nuqtalar to'plami uchun chegaralangan bo'ladi. Uchburchakning chegaralangan doirasi uning uchta (kollinear bo'lmagan) uchidan ham o'tadi. Aylana ichida S to‘plamdan nuqtalar bo‘lmasa, aylana berilgan S nuqtalar to‘plamiga nisbatan nuqtasiz bo‘ladi, deyishadi, lekin S to‘plamdan nuqtalar aylanada joylashgan bo‘lishi mumkin. eng nuqtasiz.
Agar har bir uchburchakning aylanasi nuqtalardan xoli bo'lsa, S nuqtalar to'plamining triangulyatsiyasi Delaunay triangulyatsiyasi bo'ladi. Triangulyatsiya diagrammasida rasm. 1a-rasmda ularning ichida boshqa nuqtalar aniq bo'lmagan ikkita doira ko'rsatilgan (boshqa uchburchaklar to'plam nuqtalaridan ozod ekanligiga ishonch hosil qilish uchun siz doiralar chizishingiz mumkin). Ushbu qoida rasmdagi diagrammada kuzatilmagan. 16 - boshqa uchburchakning bir nuqtasi chizilgan doira ichiga tushadi, shuning uchun bu griangulyatsiya Delaunay tipiga tegishli emas.
Triangulyatsiya algoritmini soddalashtirish uchun S to'plamidagi nuqtalar haqida ikkita taxmin qilish mumkin. Birinchidan, triangulyatsiya umuman mavjud bo'lishi uchun S to'plami kamida uchta nuqtani o'z ichiga oladi va ular kollinear emas deb taxmin qilishimiz kerak. Ikkinchidan, Delonay triangulyatsiyasi yagona bo'lishi uchun S to'plamining to'rtta nuqtasi bir xil aylanada yotmasligi kerak. Ko'rinib turibdiki, bunday taxminsiz Delaun triangulyatsiyasi yagona bo'lmaydi, chunki bitta chegaralangan doiradagi 4 nuqta bizga ikki xil Delaunay triangulyatsiyasini amalga oshirishga imkon beradi.
Bizning algoritmimiz joriy triangulyatsiyani bir vaqtning o'zida bir uchburchakni doimiy ravishda oshirish orqali ishlaydi. Dastlab, joriy triangulyatsiya qobiqning bir chetidan iborat bo'lsa, algoritm oxirida joriy triangulyatsiya Delaunay triangulyatsiyasiga aylanadi. Har bir iteratsiyada algoritm ulanadigan yangi uchburchakni qidiradi chegara joriy triangulyatsiya.
Chegaraning ta'rifi quyidagilarga bog'liq quyidagi diagramma joriy triangulyatsiyaga nisbatan Delaunay triangulyatsiyasi qirralarining tasnifi. Har bir chekka bo'lishi mumkin uxlash, tirik yoki o'lik:
- uxlab yotgan qovurg'alar: Delaunay triangulyatsiyasining chekkasi, agar u hali algoritm tomonidan aniqlanmagan bo'lsa, harakatsiz hisoblanadi;
- jonli qovurg'alar: qovurg'a topilsa tirik, lekin faqat bitta qo'shni hudud ma'lum;
- o'lik qovurg'alar: Agar chekka topilsa va ikkala qo'shni hudud ham ma'lum bo'lsa, o'lik hisoblanadi.
Dastlab, qavariq i bo'lakchasiga tegishli bo'lgan yagona chekka tirik - chegaralanmagan tekislik unga qo'shni, qolgan barcha qirralar esa harakatsizdir. Algoritm ishlayotganda, chekkalar uyqudan tirikga o'likgacha o'tadi. Har bir bosqichdagi chegara tirik qirralarning to'plamidan iborat.
Har bir iteratsiyada chegaraning istalgan chetidan biri tanlanadi va u e chekkasi tegishli bo'lgan noma'lum mintaqani qidirishdan iborat bo'lgan qayta ishlanadi.Agar bu mintaqa f uchburchak bo'lib chiqsa, u bilan aniqlanadi. chekka e ning so'nggi nuqtalari va ba'zi uchinchi uchlari v, keyin chekka e o'lik bo'ladi , chunki unga qo'shni ikkala soha ham ma'lum. Uchburchakning qolgan ikki chetining har biri t quyidagi holatga o'tadi: uyqudan tirikga yoki tirikdan o'lik. Bu erda v tepasi chaqiriladi konjugat qirra bilan e. Aks holda, agar noma'lum mintaqa cheksiz tekislik bo'lib chiqsa, u holda e chekkasi shunchaki o'ladi. Bunday holda, e chekkasi konjugat cho'qqiga ega emas.
Shaklda. 4-rasmda algoritmning ishlashi ko'rsatilgan, bu erda harakat yuqoridan pastga va o'ngga shon-shuhrat sodir bo'ladi. Har bir bosqichdagi chegara qalin chiziq bilan ta'kidlangan.
Algoritm delaunayTriangulate dasturida amalga oshiriladi. Dasturga n nuqtadan iborat s massiv beriladi va Delaunay triangulyatsiyasini ifodalovchi uchburchaklar ro'yxatini qaytaradi. Amalga oshirish geometrik ma'lumotlar strukturasi bo'limidagi dumaloq ro'yxat sinfi va sinflaridan foydalanadi. Lug'at sinfi kerakli operatsiyalarni qo'llab-quvvatlaydigan har qanday lug'at bo'lishi mumkin. Masalan, siz #define Dictionary RandomizedSearchTree ni bekor qilishingiz mumkin.
Roʻyxat
Guruch. 4
Triangulyatsiyani tashkil etuvchi uchburchaklar uchburchaklar ro'yxatiga yoziladi. Chegara chegara yashovchi qirralarning lug'ati bilan ifodalanadi. Har bir chekka yo'naltirilgan bo'lib, u uchun noma'lum hudud (aniqlanishi kerak) chetning o'ng tomonida yotadi. EdgeCmp taqqoslash funktsiyasi lug'atni qidirish uchun ishlatiladi. Ikki qirraning boshlang'ich nuqtalarini taqqoslaydi; agar ular teng bo'lsa, ularning oxirgi nuqtalari taqqoslanadi:
Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) qaytish 1; agar (a->org > b->org) 1ni qaytarsa; agar (a->dest< b->dest) qaytish -1; agar (a->dest > b->dest) 1ni qaytarsa; qaytish 0; )
Chegara bir bosqichdan ikkinchisiga qanday o'zgaradi va updateFrontier funksiyasi bu o'zgarishlarni aks ettirish uchun chegaraning chekka lug'atini qanday o'zgartiradi? Chegaraga yangi uchburchak t ulanganda uchburchakning uch chetining holatlari o'zgaradi. Chegaraga tutashgan uchburchak t qirrasi tirikdan o'likgacha o'zgaradi. updateFrontier funksiyasi bu chekkaga e'tibor bermasligi mumkin, chunki removeMin funksiyasi chaqirilganda u allaqachon lug'atdan olib tashlanishi kerak. Uchburchakning qolgan ikkita chetining har biri t, agar ular ilgari lug'atda qayd etilmagan bo'lsa, uxlash holatidan tirikga yoki qirrasi allaqachon lug'atda bo'lsa, tirikdan o'lik holatiga o'zgartiradi. Shaklda. 5 ikkala holatni ham ko'rsatadi. Rasmga ko'ra, biz jonli af chetini qayta ishlaymiz va b nuqtasi uning konjugati ekanligini aniqlagandan so'ng, joriy triangulyatsiyaga afb uchburchagini qo'shamiz. Keyin fb chekkasini lug'atdan qidiramiz va u hali yo'qligi va birinchi marta kashf etilganligi sababli, uning holati uyqu holatidan tirikga o'zgaradi. Lug'atni tahrirlash uchun fb chetini shunday aylantiramizki, unga qo'shni noma'lum mintaqa uning o'ng tomonida yotadi va bu chetni lug'atga yozamiz. Keyin biz lug'atda ba chekkasini topamiz - u ichida bo'lgani uchun u allaqachon tirik (unga qo'shni ma'lum bo'lgan uchburchak abc). Unga noma'lum bo'lgan uchburchak afb hududi endigina kashf etilganligi sababli, bu chekka lug'atdan olib tashlandi.
UpdateFrontier funktsiyasi chegara lug'atini tahrirlaydi, bunda a nuqtadan b nuqtagacha bo'lgan chekka holati o'zgaradi:
Guruch. 5
Yangilanishni bekor qilingFrontier (Lug'at
HullEdge funksiyasi s massivdagi n nuqta orasidan korpus chetini topadi. Bu funktsiya aslida ishga tushirish bosqichidan va sovg'ani o'rash usulining birinchi iteratsiyasidan foydalanadi:
Edge *hullEdge (Point 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]); }
Uchburchak funktsiyasi oddiygina parametr sifatida berilgan uchta nuqta uchun ko'pburchak hosil qiladi va qaytaradi:
Ko'pburchak *uchburchak (Nuqta &a, Nuqta &b, Nuqta &c) ( Ko'pburchak *t = yangi Ko'pburchak; t->qo'shish (a); t->qo'shish (b); t->qo'shish (c); t-ni qaytarish; )
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 koeffitsienti: 
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 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 teskari uzatilishini bajaramiz. 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 boshqasiga o'tamiz.
