Məkan Delaunay üçbucaqlılığı
Üst-üstə düşməyən üçbucaqlar şəbəkəsinin qurulması problemi hesablama həndəsəsinin əsas problemlərindən biridir və səthin modelləşdirilməsi və fəza məsələlərinin həlli üçün kompüter qrafikası və coğrafi informasiya sistemlərində geniş istifadə olunur.
Üst-üstə düşməyən üçbucaqlar şəbəkəsinin qurulması problemi ilk dəfə 1934-cü ildə müvafiq şərtləri tərtib edən sovet riyaziyyatçısı B. N. Delonenin işində qoyulmuşdur.
Riyaziyyatda verilmiş nöqtələrdən trianqulyasiya qurmaq vəzifəsi onları kəsişməyən seqmentlərlə cüt-cüt birləşdirmək vəzifəsidir ki, üçbucaqlar şəbəkəsi yaransın. Onun əsas elementləri (Şəkil 5.3): düyünlər (üçbucaqların təpələri), kənarlar (yanlar) və üzlər (üçbucaqların özləri). Quraşdırılmış üçbucaqlı qabarıq (əgər bu, modelləşdirmə sahəsini əhatə edən minimal çoxbucaqlıdırsa), qeyri-qabarıq (üçbucaq qabarıq deyilsə) və optimal (bütün kənarların uzunluqlarının cəmi minimal olarsa) ola bilər.
Belə üçbucaqlar şəbəkəsi müəyyən şərtlərə cavab verirsə, Delaunay üçbucaqlılığı adlanır:
İlkin nöqtələrin heç biri hər hansı bir üçbucağın ətrafına çəkilmiş dairənin içərisinə düşmür (şək. 5.3);
Trianqulyasiya qabarıqdır və yuxarıda ifadə olunmuş Delaunay şərtini ödəyir;
Bütün üçbucaqların minimum bucaqlarının cəmi bütün mümkün üçbucaqların maksimumudur;
Üçbucaqlar ətrafında təsvir edilən dairələrin radiuslarının cəmi bütün mümkün üçbucaqlar arasında minimaldır.
Dairəvi adlanan Delaunay üçbucağının qurulması üçün yuxarıda göstərilən kriteriyalardan birincisi əsas meyarlardan biridir və ümumi üzləri olan hər hansı bir cüt üçbucaq üçün yoxlanılır. Kriteriyanın riyazi şərhi Şek. 5.3:
(5.2)
Ən məşhurlardan biri olan Delaunay üçbucağını qurmağın bir çox yolu var son vaxtlar triangulyasiya şəbəkəsinin qurulması üsulları. Bir çox GIS sistemlərində relyef modelləri yaratmaq üçün istifadə olunur.
İki ölçülü fəzaya tətbiq edildikdə, o, aşağıdakı kimi tərtib edilir: bir-biri ilə əlaqəli üst-üstə düşməyən üçbucaqlar sistemi ən kiçik perimetrə malikdir, əgər təpələrdən heç biri əmələ gələn üçbucaqların ətrafında təsvir olunan dairələrin heç birinin içərisinə düşmürsə (şək. 5.4).
düyü. 5.4. Delaunay üçbucaqlılığı
Bu o deməkdir ki, belə üçbucaqlı yaranan üçbucaqlar bərabərtərəfli olanlara mümkün qədər yaxındır və əks təpədən yaranan üçbucaqların hər biri müvafiq yarım müstəvinin bütün mümkün nöqtələrindən maksimum bucaq altında görünür. Bu, kənarları boyunca adətən izoqrafik xətlərin qurulması üçün xətti interpolyasiya edilən optimal üçbucaqlamadır.
Delaunay trianqulyasiyasının qurulması üçün bir çox alqoritmlər aşağıdakı teoremdən istifadə edir.
Teorem 1. Delaunay üçbucaqlılığını, Delaunay şərtini ödəməyən bitişik ABC və BCD üçbucaqlarının cütlərini ardıcıl olaraq ABD və ACD cütü üçbucaqlarına çevirməklə eyni nöqtələr sistemindən istifadə etməklə istənilən başqa üçbucaqdan əldə etmək olar (şək. 5.5).
düyü. 5.5.. Delauna şərtini ödəməyən üçbucaqların yenidən qurulması
Bu yenidənqurma əməliyyatı tez-tez flip adlanır. Bu teorem Delaunay üçbucağını ardıcıl olaraq qurmağa imkan verir, əvvəlcə bəzi trianqulyasiyalar qurur, sonra onu ardıcıl olaraq Delaunay şərti mənasında təkmilləşdirir. Qonşu üçbucaq cütləri üçün Delaunay şərtini yoxlayarkən, tərifdən birbaşa istifadə edə bilərsiniz, lakin bəzən yuxarıda sadalanan şərtlərə əsasən başqa üsullardan istifadə olunur.
Bu şərtlərdə, hansının Delaunay üçbucağını əldə edə biləcəyini optimallaşdıraraq, bütün trianqulyasiyanın ümumi xarakteristikası (minimum bucaqların cəmi və ya radiusların cəmi) görünür.
Yuxarıda qeyd edildiyi kimi, biri kritik əməliyyatlar trianqulyasiya qurarkən yerinə yetirilən iş, verilmiş üçbucaq cütləri üçün Delaunay şərtini yoxlamaqdır. Delaunay trianqulyasiyasının tərifinə və müvafiq şərtlərə əsasən praktikada adətən bir neçə yoxlama metodundan istifadə olunur:
– dairəvi tənlik vasitəsilə yoxlama;
– əvvəlcədən hesablanmış dairəvi dairə ilə yoxlayın;
– əks bucaqların cəminin yoxlanılması;
– əks bucaqların cəminin dəyişdirilmiş yoxlanışı.
Bir çox sistem testi əvvəlcədən hesablanmış çevrə ilə həyata keçirir. Əvvəlcədən hesablanmış dairələr vasitəsilə yoxlama alqoritminin əsas ideyası hər bir qurulmuş üçbucaq üçün onun ətrafında təsvir olunan dairənin mərkəzini və radiusunu əvvəlcədən hesablamaqdır, bundan sonra Delaunay şərtinin yoxlanılması mərkəzə olan məsafənin hesablanmasına qədər azalacaqdır. bu dairənin və nəticənin radiusla müqayisə edilməsi. Ətrafında təsvir edilən dairənin mərkəzi və r radiusu , , , r 2 = (b 2 + c 2 - 4аd)/4а 2 kimi tapıla bilər, burada qiymətlər a, b, c, d düsturlarla müəyyən edilir (5.3)
(5.3)
Bu dairənin tənliyi üçün başqa bir giriş:
(5.5.)
(5.6)
Delaunay şərti yalnız hər hansı digər trianqulyasiya nöqtəsi üçün olduqda yerinə yetiriləcək:
(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)
Hal-hazırda Delaunay trianqulyasiyasının qurulması üçün bir çox alqoritmlər mövcuddur. Tanınmış alqoritmlərin bir çoxu ikinci dərəcəli trianqulyasiya xüsusiyyəti kimi Delaunay trianqulyasiya tərifindən istifadə edir. Beləliklə, belə alqoritmlərdə aşağıdakı zəif cəhətlər qeyd olunur:
– alqoritmlər daim hesablanan triqonometrik funksiyalardan istifadə edir ki, bu da prosesi kəskin şəkildə ləngidir;
– nöqtələrlə əsas seqment arasındakı əlaqəni öyrənərkən çox kiçik bucaqlar yaranır və istifadə edərkən triqonometrik funksiyalar Kompüterdə məlumatların təsvirinin məhdud dəqiqliyi səbəbindən sifarişin yoxa çıxması və 0-a bölünməsi təhlükəsi var; bu vəziyyət daimi əlavə emal tələb edir.
Ən məşhur proqram məhsulları, üçbucaqların qurulması üçün əsas, əsas prinsip kimi boş top teoremindən istifadə edərək Delaunay trianqulyasiyasını qurur. Alqoritm belə görünür:
– bütün nöqtələr dəsti üçbucaqlara bölünür, yəni. üç nöqtənin birləşmələri yaradılır;
– hər kombinasiya üçün dairəvi dairə və onun mərkəzinin koordinatları tapılır;
– cari kombinasiyanın dairəsi daxilində bir dənə də olsun nöqtə yoxdursa, bu birləşmə üçbucaqdır – Delaunay üçbucağının bir hissəsidir.
Bu alqoritmin üstünlüklərinə aşağıdakılar daxildir:
– tikinti prosesini ləngitməyən triqonometrik funksiyalardan istifadə edilməməsi;
– heç bir ilkin tikililər olmadan Delaunay üçbucağının birbaşa tikintisi;
– bütün hesablamaların və çevrilmələrin sadəliyi;
– nəticədə üçbucaqlı şəbəkə fərdi xətlərlə deyil, çoxlu üçbucaqlarla təmsil olunur.
Bu şəkildə qurulan trianqulyasiya izoqrafik xətlərin qurulması üçün həndəsi əsasdır.
Delaunay trianqulyasiyasının qurulması alqoritmlərini istifadə olunan giriş məlumatlarının strukturuna, hesablama əməliyyatlarının həcminə, ilkin binalara və s. görə fərqlənən bir sıra qruplara bölmək olar. Onlardan bəzilərini nəzərdən keçirək.
Birləşmə alqoritmləri bir sıra mənbə nöqtələrinin alt çoxluqlara bölünməsini, onların hər biri üzərində trianqulyasiyanın qurulmasını və sonra onları vahid şəbəkədə birləşdirməyi nəzərdə tutur. Bu alqoritmlərdən birinin mahiyyəti aşağıdakılara gəlir.
Başlanğıc nöqtələr dəsti şaquli xətlərlə iki və ya daha çox hissəyə bölünür, bundan sonra onların hər biri üfüqi və şaquli xətlərlə təxminən bərabər hissələrə bölünür. Nəticədə, başlanğıc nöqtələrinin bütün sahəsi üç və ya dörd nöqtədən ibarət primitivlərə bölünür (Şəkil 2.4), onlar boyunca bir və ya iki üçbucaq qurulur.
Bu üçbucaqların vahid şəbəkədə birləşdirilməsi iki əsas xəttin qurulması ilə həyata keçirilir (P 0 P 1 və P 2 P 3, düyü. 5.7.a), əsas xəttinə perpendikulyar bissektrisa üzərində mərkəzləşdirilmiş dəyişən radiuslu dairələrin çəkilməsi (Şəkil 5.7, b), dairəyə düşən düyünün axtarışı (nöqtə). A, düyü. 5.7. c) və yeni üçbucağın qurulması (P 0 P 1 A). Bu halda, mövcud üçbucağı silmək lazım ola bilər (məsələn, P 0 AB).
İterativ alqoritmlər, Delaunay meyarlarına uyğun olaraq eyni vaxtda təkmilləşdirilməsi və yenidən qurulması ilə qismən qurulmuş trianqulyasiyaya ardıcıl olaraq nöqtələr əlavə etmək fikrinə əsaslanır. IN ümumi görünüş onlar bir neçə addımı əhatə edir və ilk üçdə üçbucağın qurulmasına qədər qaynayırlar başlanğıc nöqtələri və növbəti nöqtəni yerləşdirmək üçün bir neçə variantı araşdırmaq. Xüsusilə, onun modelləşdirmə sahəsinin hüdudlarından kənara, mövcud node və ya kənara, qurulmuş üçbucağın içərisinə və s. düşməsi variantları nəzərdən keçirilir. Bu variantlardan hər biri müəyyən əməliyyatın yerinə yetirilməsini nəzərdə tutur: kənarın ikiyə, üzlərin bölünməsi. üç və s.; bundan sonra yaranan üçbucaqların Delaunay şərtinə uyğunluğu yoxlanılır və lazımi rekonstruksiyalar aparılır.
İki keçidli alqoritmlər əvvəlcə Delaunay şərtlərinə məhəl qoymadan bəzi trianqulyasiyanın qurulmasını, sonra isə bu şərtlərə uyğun olaraq yenidən qurulmasını nəzərdə tutur. Alqoritmin tətbiqi nümunəsi Şəkildə göstərilmişdir. 5.8.
Yaradılmış relyef modelini real olana yaxınlaşdırmaq üçün onun xətti və ərazi struktur elementlərinin nəzərə alınmasını və nümayiş etdirilməsini təmin etmək üçün ona əlavə elementlər daxil edilir. Bu cür əlavə elementlər topoqrafiyada geniş istifadə olunan və “relyef skeleti”ni müəyyən edən struktur xətlərdir: suayrıcları, talveqlər, silsilələr, qayalar, kənarlar, göllər, yarğanlar, sahil xətləri, süni tikililərin sərhədləri və s. Delaunay trianqulyasiyası üçün çərçivə. Bu struktur xətlər üçbucaqların kənarları kimi trianqulyasiyaya daxil edilir ki, bu da yer səthinin ümumi qeyri-bərabərliyi fonunda real relyef elementlərinin modelləşdirilməsinə nail olur. Belə kənarlar struktur adlanır (sabit, yenidən qurulmayan), digər üçbucaqların kənarları ilə kəsişmir və sonradan dəyişmir.
Qırılma xətləri nəzərə alınmaqla səth modelinin qurulması problemi, kəsilmə xətləri ilə ayrılmayan hər hansı bir bitişik üçbucaq cütü üçün Delaunay şərtləri təmin edilirsə, məhdud Delaunay üçbucaqlılığı adlanır. Tədqiqatçıların fikrincə, ən təsirli üsul iterativ alqoritmlərdən istifadə edərək belə bir trianqulyasiya qurmaqdır.
Əlavə elementləri olan Delaunay üçbucağının bir parçası Şəkildə göstərilmişdir. 5.9, burada sağda qovşaqlar, kənarlar, kənarlar və struktur xətlər, solda isə ərazinin struktur xətləri (sahil xətləri, yarğan kənarları və s.) və nöqtələr məlum işarələri ilə göstərilir.
Delaunay trianqulyasiyasının qurulması üçün alqoritmlər qovşaqların koordinatlarının həqiqi və ya tam ədədi təsviri ilə həyata keçirilir ki, bu da emal sürətini və dəqiqliyini əhəmiyyətli dərəcədə artıra bilər, lakin uyğun qovşaqların axtarışı və istisna edilməsi problemlərinə səbəb olur.
VÖEN modeli qovşaqların köçürülməsi, yenilərinin daxil edilməsi, mövcud olanların silinməsi, bir və ya bir neçə kənarın mövqeyinin dəyişdirilməsi, yeni struktur xətlərin tətbiqi və s. yolu ilə asanlıqla redaktə olunur. bütün şəbəkə və kursoru müvafiq elementə yönəltməklə onlayn həyata keçirilir.
Dəqiqlik haqqında:
Piketləri xarakterik relyef elementlərinə (məsələn, su hövzələri və talveqlər) yerləşdirməklə, biz boşluqlardakı kiçik elementlərə məhəl qoymuruq. Üçbucaqların belə kənarları boyunca kontur xətlərini1 qurarkən, relyefin qeyri-bərabərliyinin miqdarından və relyefin meyl bucağından asılı olan xəta baş verir. Məsələn, relyefin çəkilişində orta xəta 2-dən 10 dərəcəyə qədər səthin meyl bucaqlarında relyef en kəsiyinin 1/3-dən çox olmamalıdır. Hesablamaq olar ki, 0,5 m relyef bölməsi ilə buraxılmış qeyri-bərabərliyin maksimum dəyəri (yəni, yer səthinin bitişik piketlərdən keçən düz xəttdən sapması) (0,5/3) * cos10 ° -dən çox olmamalıdır. = 0,16 m.
Daşınan qruntun həcminin müəyyən edilməsinin dəqiqliyi üçün uçota alınmamış relyef detalının tutduğu ərazi də mühüm əhəmiyyət kəsb edir. Deyək ki, iki cüt piket arasında 20x20 m kvadratda maksimum hündürlüyü 0,15 m olan silindrik qabarıqlıq var ki, bu səthi yalnız iki üçbucaqla təmsil edərkən nəzərə alınmaması bir nəticə verəcəkdir səhv təxminən 40 m3. Çox deyil, bir təpədə və ya yamacın yuxarı (adətən konveks) hissəsində yerləşən 1 hektarlıq bir sahə üçün 40 * 25 = 1000 m3 artıq torpaq alırsınız. Piketləri iki dəfə tez-tez (yəni hər 10 m-dən bir) götürsəniz, səhv dörd dəfə azalacaq və hektara 250 m3 təşkil edəcəkdir. Bu amili əvvəlcədən nəzərə almaq olar, çünki düz relyefin müsbət formaları adətən qabarıq, mənfi formalar isə konkav formaya malikdir. Tədqiq ediləcək ərazinin relyef üzrə təxmini məlumatları varsa, o zaman səthin əyrilik radiusu və piketlərin tələb olunan sıxlığı kontur xətlərinin və ya fərdi yüksəkliklərin dəyərlərindən asanlıqla hesablana bilər.
Əsas təriflər və xüsusiyyətlər
Trianqulyasiya daxili bölgələri hamısı üçbucaq olan müstəvi qrafikdir.
Xüsusiyyətlər:
· Delaunay trianqulyasiyası eyni nöqtələr dəsti üçün Voronoi diaqramına bir-bir uyğun gəlir.
· Nəticə olaraq: eyni çevrədə dörd nöqtə yoxdursa, Delaunay trianqulyasiyası unikaldır.
· Delaunay triangulyasiyası bütün qurulmuş üçbucaqların bütün bucaqları arasında minimum bucağı maksimum dərəcədə artırır və bununla da “nazik” üçbucaqlardan qaçır.
· Delaunay trianqulyasiyası, yazılan kürələrin radiuslarının cəmini maksimuma çatdırır.
· Delaunay trianqulyasiyası diskret Dirichlet funksionalını minimuma endirir.
· Delaunay trianqulyasiyası minimum mühit sferasının maksimum radiusunu minimuma endirir.
· Təyyarədə Delaunay trianqulyasiyası bütün mümkün üçbucaqlar arasında üçbucaqlar ətrafında təsvir edilmiş dairələrin radiuslarının minimum cəminə malikdir.
Şəkil 1. Triangulyasiya.
Qabarıq üçbucaqlı, bütün üçbucaqları əhatə edən minimum çoxbucaqlının qabarıq olduğu üçbucaqlılıqdır. Qabarıq olmayan üçbucaqlılığa qeyri-qabarıq deyilir.
Verilmiş ikiölçülü nöqtələr toplusundan trianqulyasiyanın qurulması məsələsi əlaqə problemi adlanır xallar verilir kəsişməyən seqmentlər beləliklə trianqulyasiya əmələ gəlir.
Verilmiş üçbucaqlı nöqtələrdən heç biri qurulmuş hər hansı üçbucağın ətrafına çəkilmiş dairənin içərisinə düşmürsə, üçbucaqlaşmanın Delaunay şərtini ödədiyi deyilir.
Üçbucaqlı qabarıqdırsa və Delaunay şərtini ödəyirsə, Delaunay üçbucaqlılığı adlanır.
Şəkil 2. Delaunay trianqulyasiyası.
Delaunay boş top üsulu. Ümumi halda tikinti
Hərəkət edəcəyimiz boş bir topdan istifadə edək, ölçüsünü dəyişdirərək sistemin (A) nöqtələrinə toxuna bilsin, lakin həmişə boş qalsın.
Beləliklə, (A) nöqtələr sisteminə yerləşdirək. boş top Delaunay. Kifayət qədər kiçik bir top seçsəniz, bu həmişə mümkündür. Topun mərkəzini yerində qoyaraq onun radiusunu artırmağa başlayaq. Bir nöqtədə topun səthi (A) sisteminin bəzi i nöqtəsi ilə qarşılaşacaq. Bu, mütləq baş verəcək, çünki sistemimizdə sonsuz böyük boşluqlar yoxdur. Boş topun radiusunu artırmağa davam edəcəyik ki, i nöqtəsi onun səthində qalsın. Bunun üçün topun mərkəzini i nöqtəsindən hərəkət etdirməli olacaqsınız. Gec-tez top öz səthi ilə sistemin başqa bir nöqtəsinə çatacaq (A).
şək.3
Delaunay simplexləri boşluqlar və üst-üstə düşmələr olmadan boşluğu doldurur.
Hər hansı bir simpleksin təsvir olunan sferası öz daxilində sistemin digər nöqtələrini ehtiva etmir.
Bu j nöqtəsi olsun. Hər iki nöqtəni səthində saxlayaraq topumuzun radiusunu artırmağa davam edək. Top artdıqca sistemin üçüncü nöqtəsi olan k nöqtəsinə çatacaq. İki ölçülü vəziyyətdə, "boş dairəmiz" bu anda sabitlənəcəkdir, yəni. Dairəni boş saxlayaraq onun radiusunu daha da artırmaq qeyri-mümkün olacaq. Eyni zamanda, müəyyən bir üçbucağı təyin edən üç nöqtənin (i, j, k) elementar ikiölçülü konfiqurasiyasını müəyyənləşdiririk, onun xüsusiyyəti onun dairəsi daxilində sistemin (A) başqa nöqtələrinin olmamasıdır. Üç ölçülü məkanda top üç nöqtə ilə müəyyən edilmir. Səthində tapılan hər üç nöqtəni saxlayaraq onun radiusunu artırmağa davam edək. Bu, topun səthi sistemin dördüncü l nöqtəsinə çatana qədər mümkün olacaq. Bundan sonra boş topun hərəkəti və böyüməsi qeyri-mümkün olacaq. Tapılan dörd nöqtə (i,j,k,l) tetraedrin təpələrini müəyyənləşdirir, bu da onun əhatə olunmuş sferasında sistemin (A) başqa nöqtələrinin olmaması ilə xarakterizə olunur. Belə tetraedr Delaunay simpleksi adlanır.
Riyaziyyatda simpleks verilmiş ölçülü fəzada ən sadə fiqurdur: tetraedr - üçölçülü fəzada; üçbucaq - iki ölçüdə. Sistemin eyni müstəvidə olmayan ixtiyari üç (dörd) nöqtəsi həmişə müəyyən bir sadəliyi müəyyən edir. Bununla belə, o, yalnız təsvir olunan sferası boş olduqda Delaunay simpleksi olacaq. Başqa sözlə, Delaunay sadəlikləri (A) sistemindəki nöqtələrin üçlüklərinin (dördlüklərinin) xüsusi seçimi ilə müəyyən edilir.
Biz bir Delaunay simplex qurduq, lakin boş topu müxtəlif yerlərə yerləşdirməklə və eyni proseduru təkrarlamaqla digərlərini müəyyən edə bilərik. Bildirilir ki, (A) sisteminin bütün Delaunay sadəliklərinin çoxluğu məkanı üst-üstə düşmə və boşluqlar olmadan doldurur, yəni. kosmosun bölünməsini həyata keçirir, lakin bu dəfə tetraedrlərə. Bu bölmə adlanır Delaunay kafel(şək. 3).
Delaunay trianqulyasiyasının tətbiqi
Evklid fəzasında tez-tez Delaunay üçbucaqlarından istifadə olunur. Evklid minimumu əhatə edən ağacın Delaunay üçbucaqlılığında yerləşdiyinə zəmanət verilir, buna görə də bəzi alqoritmlər trianqulyasiyadan istifadə edir. Həmçinin, Delaunay trianqulyasiyası vasitəsilə Evklid səyyar satıcı problemi təxminən həll edilir.
2D interpolyasiyada Delaunay trianqulyasiyası təyyarəni çox kəskin və çox küt bucaqlardan qaçaraq mümkün olan ən qalın üçbucaqlara bölür. Bu üçbucaqlardan istifadə edərək, məsələn, ikixətli interpolyasiya qura bilərsiniz.
Geoinformatikada tez-tez rast gəlinən digər problem yamacların ekspozisiyalarının qurulmasıdır. Burada kardinal istiqamət üzrə yamacların dominant istiqamətlərini müəyyən etmək və səthi müəyyən istiqamətin üstünlük təşkil etdiyi rayonlara bölmək lazımdır. Ekspozisiyanı təyin etmək səthin üfüqi sahələri üçün mənasız olduğundan, üfüqi və ya bir qədər yamacı olan sahələr, məsələn, ayrı bir bölgəyə ayrılır.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.
Şəkil 4.
Yamacların ekspozisiyalarının hesablanması problemi adətən Yerin işıqlandırılmasını təhlil etmək üçün istifadə olunur. Bununla əlaqədar olaraq, tez-tez Günəşin mövcud vəziyyətini əlavə olaraq nəzərə almağa ehtiyac var, yəni. məruz qalma üçbucağın normalı ilə Günəşə istiqamət arasındakı istiqamət kimi hesablanır.
Beləliklə, hər bir üçbucaqlı üçbucaq müəyyən bir bölgəyə aidiyyət prinsipinə görə təsnif edilə bilər. Bundan sonra yalnız bölgə seçim alqoritmini çağırmalısınız.
Üçbucaqlı modelləşdirilmiş obyektin səthinin ondan müəyyən müəyyən edilmiş qiymətdən çox olmayan məsafədə yerləşən üçbucaqlı lövhələrlə yaxınlaşmasıdır 6. Bütün üçbucaqlı lövhələr bir-birinə birləşdirilməlidir. Onların üstləri səthdə yatır. Üçbucaqlı lövhələr dəsti ilə işləmək ümumi səthdən daha asandır. Üçbucaqlı plitələri üçbucaq adlandıracağıq. Üçbucaq üçün verilən nöqtəyə qədər olan məsafə və ya fəzada verilmiş xətt ilə kəsişmə nöqtəsi tez hesablanır. Üzlərin üçbucaqlanması həndəsi modelin vizual qavranılması üçün həyata keçirilir, buna görə də üçbucaqların tərəfləri gözlərin əyilmələri görməməsi üçün seçilir.
Səthlərin parametrik müstəvilərində həndəsi cisimləri üçbucaqlarla göstərərkən, kosmosda bir sıra nöqtələr massivi və bu nöqtələrdə cismin üzlərinə normallar massivi hesablanaraq, cismin üzlərinin fəza üçbucağı qurulmalıdır. iki ölçülü nöqtələr cəsədləri tez göstərmək üçün onların üzləri üzərində qurulmuş üçbucaqlı lövhələrlə yaxınlaşdırılır. Əvvəlki fəsillərdə və bu fəsildə ton təsvirləri trianqulyasiyadan istifadə etməklə hazırlanmışdır.
Səthi üçbucaqlama nəticəsində biz parametrik müstəvidə iki ölçülü nöqtələr massivi və birinci qeyd olunan massivdəki nöqtələrin nömrələri olan üçlü tam ədədlər massivinə sahib olmaq istəyirik. Beləliklə, hər üçbucaq parametr massivində öz təpələrinin üç ədədi ilə təmsil olunacaq. Parametrik sahənin hər iki ölçülü nöqtəsi üçün səthdəki fəza nöqtəsi və onun içindəki normal səth hesablana bilər. Məkan nöqtələri və normallar 2D nöqtə massivinə bənzər massivlərdə saxlanıla bilər.
Trianqulyasiyanın bəzi üsullarına nəzər salaq. Düz səthlər üçün, səthin sərhəd nöqtələrində üçbucaqların qurulduğu və parametrik bölgə daxilində nöqtələri axtarmağa ehtiyac olmadığı qənaətli üçbucaqlı üsullar mövcuddur.
Delaunay üçbucaqlılığı.
Təyyarədə bəzi sahələrə nəzər salaq. Sərhədi boyunca hərəkət edərkən yalnız bir istiqamətə (yalnız sola və ya yalnız sağa) dönmək lazımdırsa, sahəni qabarıq adlandıracağıq. Delaunay alqoritmi qabarıq planar bölgələri üçbucaqlaşdırmaq üçün istifadə edilə bilər. Biz bu alqoritmi sərbəst formalı səthləri üçbucaqlaşdırmaq üçün birbaşa tətbiq edə bilməyəcəyik, lakin üçbucaqların qurulması üçün onun metodundan istifadə edəcəyik.
düyü. 9.7.1. İçəridə verilmiş nöqtələri olan qabarıq bölgə
Qapalı qırıq xəttlə hüdudlanan bəzi qabarıq ikiölçülü rayon və bu regionun daxilindəki nöqtələr toplusu verilsin (şək. 9.7.1).
Göstərilən sahəni üçbucaqlara bölmək tələb olunur ki, onların təpələri sahənin daxilində verilmiş nöqtələr və onu hüdudlayan qırıq xəttin təpələridir. Üçbucaqlar bir-biri ilə üst-üstə düşməməlidir və onların tərəfləri yalnız təpələrdə kəsişə bilər.
Müəyyən edilmiş sahəni doldurmaq üçün bir neçə müxtəlif üçbucaq dəsti tikilə bilər. Bütün hallarda üçbucaqların sayı bərabərdir, burada K - sərhədyanı polixəttin təpələrinin sayı, I - region daxilində verilmiş nöqtələrin sayıdır.
düyü. 9.7.2. Delaunay alqoritminin üçüncü nöqtəsinin seçilməsi
Hər üçbucağın ətrafında təsvir edilən dairənin içərisində başqa üçbucaqların təpələri yoxdursa, bölgənin üçbucaqlılığı Delaunay üçbucaqlılığı olacaqdır. Delaunay üçbucaqlı üçbucaqları mümkün qədər bərabərbucaqlıya yaxın qurur (əsassız şəkildə uzanan üçbucaqların qurulmasına imkan vermir).
Bunu balanslı adlandırmaq olar. Dörd təpə eyni çevrədə yerləşmirsə, Delaunay üçbucaqlılığı unikal olacaqdır.
Delaunay üçbucağını nəzərdən keçirək. Bölgəni əhatə edən çoxxəttin təpələrini və bölgə daxilində verilmiş nöqtələri üçbucaqlılığın təpələri adlandıracağıq. Üçbucaqların tərəflərini kənarlar adlandıracağıq. Kenarlar arasında biz sərhəd kənarları adlandıracağımız məhdudlaşdırıcı çoxlu xəttin seqmentlərini seçirik. Bütün sərhəd kənarlarını elə istiqamətləndirək ki, qabarıq bölgə hər kənarın solunda olsun. Şəkildə göstərilən tərəfi AB sərhəd kənarı olan üçbucaq qurmaq lazım gəlsin. 9.7.2.
A, B təpələri və onlarla eyni xəttdə olmayan istənilən təpə vasitəsilə dairə çəkilə bilər. Üçbucağın üçüncü təpəsi olaraq V təpəsini seçirik, müvafiq dairədə V nöqtəsinin yerləşdiyi AB seqmentinə nisbətən eyni tərəfdə olan digər təpələr yoxdur tapılsın. Biz onu ən yaxını adlandıracağıq. A, B və V nöqtələrindən keçən dairənin mərkəzi AB, BV və VA seqmentlərinin orta nöqtələrinə perpendikulyarların kəsişməsində yerləşir. Dairənin mərkəzinin mövqeyi AB kənarına perpendikulyar, uzunluğuna bərabər və AB kənarının ortasından keçən MN seqmentinin t parametri ilə xarakterizə olunacaq.
düyü. 9.7.3. Delaunay trianqulyasiya prosesi
AB seqmentinin solunda yerləşən bütün təpələr üçün ən yaxın təpə ən kiçik t parametrinə malikdir. Ən yaxın təpəyə uyğun olan dairədə AB seqmentinin solunda olan digər təpələr yoxdur. A, B və V təpələri müvafiq olaraq ikiölçülü radius vektorları ilə təsvir edilsin. AB və BV seqmentlərinin orta nöqtələrinin radius vektorları bərabər olacaqdır
A, B və V nöqtələrindən keçən dairənin mərkəzinin üzərindəki vəziyyətə uyğun olan xəttin t parametrinin qiyməti bərabərdir.
AB seqmentinin soluna ən yaxın təpə üçün t parametri minimum qiymətə malikdir.
Bütün sərhəd kənarlarını elə istiqamətləndirək ki, üçbucaqlaşdırılacaq sahə onların hər birinin solunda olsun. Hər hansı bir sərhəd kənarından üçbucaqlar qurmağa başlayırıq. Onun üçün ən yaxın təpəni tapaq, onun uyğun çevrəsində başqa təpələr yoxdur. AB sərhəd kənarı üçün ən yaxın V təpəsi tapılsın. Sonra ABV üçbucağını qururuq və AB kənarını qeyri-aktivlər kateqoriyasına köçürük. Trianqulyasiya alqoritmində iştirak etməyən qeyri-aktiv kənarları və təpələri çağıracağıq. Əgər sərhəd kənarları arasında BV kənarı yoxdursa, onda VB seqmentində yeni sərhəd kənarı qururuq. Əgər sərhəd kənarları arasında BV kənarı varsa, onda onu və B təpəsini qeyri-aktivlər kateqoriyasına keçirik. Əgər sərhəd kənarları arasında VA kənarı yoxdursa, onda biz AV seqmentində yeni sərhəd kənarı quracağıq. Əgər sərhəd kənarları arasında VA kənarı varsa, onda biz onu və A təpəsini qeyri-aktivlər kateqoriyasına keçiririk. Trianqulyasiya prosesi Şəkildə göstərilmişdir. 9.7.3.
düyü. 9.7.4. Delaunay üçbucaqlılığı
Bütün təpələr və kənarlar qeyri-aktiv olduqda triangulyasiyanı bitiririk. Müəyyən bir sahənin üçbucaqlanmasının nəticəsi Şəkildə göstərilmişdir. 9.7.4.
Korreksiya üsulu ilə üçbucaqlaşdırma.
Parametrləri təyin etmək üçün düzbucaqlı sahə ilə müəyyən bir səthin üçbucağını nəzərdən keçirək. (9.4.7) düsturuna uyğun olaraq bitişik xətlər arasındakı parametrik məsafələri bərabər qəbul edək.
(9.4.8) düsturuna uyğun olaraq bitişik xətlər arasındakı parametrik məsafələri bərabər qəbul edək.
Bütün düzbucaqlı hüceyrələrdə diaqonallar quraraq, səthin üçbucağını əldə edirik (tələblərə cavab verən üçbucaqlar dəsti əldə edirik). Şəkildə. 9.7.5 təsvir edilən üsuldan istifadə edərək, inqilab səthinin üçbucaqlaşdırılmasını göstərir.
İxtiyari sərhədi olan səthin üçbucağını nəzərdən keçirək. Parametrləri təyin etmək üçün yuxarıda təsvir edilən səth üçbucaqlılığının sərhəd konturları ilə düzəldilməsi üzərində üçbucaqlı üsulunu quracağıq.
düyü. 9.7.5. Parametrləri təyin etmək üçün düzbucaqlı bir sahə ilə səthin üçbucaqlanması
Parametrlərin təyini sahəsində səth sərhədi bir neçə kəsişməyən ikiölçülü konturla təsvir edilsin (2.12.7). Konturlardan biri xaricidir və qalan konturları ehtiva edir. Hər bir kontur üçün müsbət istiqamət üçün biz hərəkət edərkən səthi təyin edən sahənin həmişə konturun solunda, normal səthə baxarkən olduğu istiqaməti götürəcəyik. Səthin təyini sahəsinin sərhəd konturlarının müsbət istiqamətində çoxbucaqlılar quraq. Sərhəd poliqonlarını qurmaq üçün bəzi dəyişən addımlarla səthin sərhəd konturları boyunca gəzmək və koordinatları səth parametrləri olan iki ölçülü nöqtələr massivini doldurmaq lazımdır. Parametrik müstəvidəki nöqtələrdən çoxbucaqlı quracağıq, lakin bir nöqtədən digərinə keçərkən addım fəza həndəsəsindən, yəni bitişik nöqtələr arasında əyri qövsün əyilməsinin veriləndən çox olmaması şərti ilə müəyyən ediləcəkdir. dəyər. Səthin sərhəd kontur əyrisi üçün çoxbucaqlının qurulması üçün parametrik addımları (9.4.4) düsturu ilə hesablayırıq.
Hər bir çoxbucaqlı ikiölçülü nöqtələrin sıralı çoxluğundan ibarətdir. Çoxbucaqlının hər bir bölməsi iki bitişik nöqtə üzərində qurulmuş ikiölçülü düz xətt seqmenti kimi qəbul edilə bilər. Belə sahələrdən sərhəd kənarları kimi istifadə edəcəyik və kənarların əsaslandığı çoxbucaqlıların nöqtələri üçbucaqlı təpələri kimi istifadə ediləcək. Səth parametrlərinin təyini sahəsi sərhəd çoxbucaqlılarının solunda yerləşdiyinə görə, hər bir sərhəd üçbucaqlı kənarı üçün üçbucaqlar qurarkən, üçbucağın üçüncü təpəsini kənarın solunda axtarmaq lazımdır.
Hansı qovşaqların sərhəd çoxbucaqlılarının daxilində, hansının isə sərhəddə və ya səthin təyini sahəsindən kənarda olduğunu müəyyən edək. Bu məlumatdan istifadə edərək, düzbucaqlı şəbəkə hüceyrələrini iki qrupa ayırırıq. Birinci qrupa bütövlükdə səth parametrlərinin təyin olunduğu ərazidə yerləşən hüceyrələr daxildir (hüceyrələr sərhəd poliqonlarına toxunmamalıdır). İkinci qrupa qalan hüceyrələr daxildir (səthin müəyyən edilmiş sahəsindən kənarda yerləşən və ya sərhəd poliqonları ilə kəsişən).
düyü. 9.7.6. Yarımçıq səthi üçbucaqlama
Birinci qrupun hər bir hüceyrəsinin içərisində diaqonaldan istifadə edərək iki üçbucaq quracağıq. Beləliklə, yarımçıq üçbucaq alırıq. Konturlarla məhdudlaşan bir inqilab səthi üçün birinci qrupun hüceyrələrində üçbucaqların qurulması nümunəsi Şəkil 1-də göstərilmişdir. 9.7.6.
İkinci qrupun xanalarının kəsişməyən tərəflərində sərhəd kənarları quracağıq və onları elə istiqamətləndirəcəyik ki, müvafiq hüceyrə kənarın solunda olsun. Birinci qrupun hüceyrələrinin ətrafında qapalı bir qırıq xətt (bəlkə də bir neçə qapalı xətt) quracağıq ki, onun boyunca hərəkət edərkən üçbucaqlara bölünməyən sahənin hissəsi normal səthə baxarkən solda olsun. . Bu qırıq xəttin düz hissələrini də sərhəd kənarları kimi istifadə edəcəyik. Bütün kənarları bərabər hesab edəcəyik. Triangulyasiyanı başa çatdırmaq üçün sərhəd kənarları arasında üçbucaqlar qurmalıyıq. Hər kənar üçün onun solunda yerləşən və üçbucaq yaratmaq üçün istifadə edilə bilən təpə axtaracağıq. Biz təpəni yalnız kənarı ilə eyni xanada yerləşən təpələr arasında axtaracağıq. Bir təpə seçmək üçün yuxarıda təsvir edilmiş və Şəkil 1-də təsvir edilmiş Delaunay metodundan istifadə edirik. 9.7.2. Əgər belə bir təpə tapılarsa, onda siz üçbucağın iki yeni kənarının hər hansı bir sərhəd kənarı ilə kəsişib-kəsişmədiyini yoxlamaq lazımdır. AB sərhəd kənarı üçün ən yaxın V təpəsi tapılsın və BV və VA seqmentlərinin digər sərhəd kənarları ilə kəsişmədiyini yoxlayın. Sonra ABV üçbucağını quracağıq və AB kənarını qeyri-aktiv kateqoriyaya köçürəcəyik. Əgər sərhəd kənarları arasında BV kənarı yoxdursa, onda VB seqmentində yeni sərhəd kənarı quracağıq, lakin sərhəd kənarları arasında BV kənarı varsa, onda onu və B təpəsini qeyri-aktiv kateqoriyasına keçirəcəyik. Əgər sərhəd kənarları arasında VA kənarı yoxdursa, onda biz AV seqmentində yeni sərhəd kənarı quracağıq, lakin sərhəd kənarları arasında VA kənarı varsa, onda biz onu və A təpəsini qeyri-aktiv kateqoriyasına keçirəcəyik.
Əgər seqment və ya VA digər sərhəd kənarları ilə kəsişirsə, onda biz başqa sərhəd kənarı üçün ən yaxın təpənin axtarışına keçirik. Bütün kənarlar və təpələr qeyri-aktiv kimi təsnif edildikdən sonra üçbucaqlama tamamlanacaq.
düyü. 9.7.7. Korreksiya üsulu ilə üçbucaqlaşdırma
Şəkildə. 9.7.7 sərhəd konturları ilə kəsişən hüceyrələrdə üçbucaqların düzəldilməsi üsulu ilə səthi üçbucaqlılığı göstərir. Şəkildə. 9.7.8, nəticədə yaranan üçbucaqdan istifadə edərək, səthin özü göstərilir.
Əgər sərhəd poliqonları və səthi müəyyən simmetriyaya malikdirsə, onda korreksiya üsulu ilə üçbucaqlaşma oxşar simmetriyaya malik olacaqdır.
Absorbsiya üsulu ilə trianqulyasiya.
Başqa bir trianqulyasiya üsulunu nəzərdən keçirək. Sürət baxımından o, Delaunay trianqulyasiyasından və onun modifikasiyalarından daha aşağıdır. Trianqulyasiya proseduruna başlamaq üçün səth sərhədini qapalı çoxbucaqlılar şəklində təqdim etmək lazımdır. Trianqulyasiya prosesi zamanı səth parametrlərinə əsaslanaraq addımlar təyin etməmiz lazım olacaq. Məlum hərəkət istiqaməti ilə bu addımlar düsturlarla müəyyən edilir (9.4.6). Səth parametrləri üçün təxmini addımlar aşağıdakı kimi tapıla bilər. Müəyyən bir nöqtə ətrafında parametr müstəvisində elə bir bölgə təyin edək ki, bu bölgədəki nöqtədən nöqtəyə hər hansı fəza seqmenti səthdən verilən S qiymətindən uzaq olmasın.
Bunun üçün koordinat xətləri boyunca parametrlərin icazə verilən artımlarını hesablayırıq
nöqtədə səthin birinci və ikinci kvadrat formalarının əmsalları haradadır. İstədiyiniz bölgənin sərhədi olaraq, bir nöqtədə mərkəzi və yarım oxları olan bir ellips alırıq. Bu ellipsin tənliyi var
Əgər müstəvidə və oxu ilə bucağın verdiyi istiqamətdə nöqtənin yanında bir nöqtə tapmaq istəyirsinizsə, onda onun parametrləri belə olacaq.
Birincisi, səth parametrlərinin sahəsi bir xarici konturla məhdudlaşdıqda daha sadə bir vəziyyəti nəzərdən keçirək. Səth sərhədini parametrik sahədə qapalı çoxbucaqlı ilə təxmin edirik. Trianqulyasiyanı qurarkən işçi çoxbucaqlıdan istifadə edəcəyik, bu halda xarici konturun çoxbucaqlı kimi götürəcəyik. Çoxbucaqlı nöqtələrini iki ölçülü nöqtələrin nəticə massivinə əlavə edəcəyik. İş sahəsinin kənarından üçbucaqlar quracağıq, iş yerində yalnız üç nöqtə qalana qədər onu daraldacağıq.
İşçi çoxbucaqlının bölgəyə çevrildiyi təpə nöqtəsini tapaq. Belə bir nöqtə həmişə mövcuddur və oradakı fırlanma bucağı daha kiçikdir. Bu nöqtəni O ilə, parametrlərini isə fırlanma bucağından asılı olaraq bu nöqtənin yaxınlığında bir və ya iki üçbucaq quracağıq. Əgər bucaq daha kiçikdirsə, onda bu üç nöqtə üzərində bir üçbucaq quracağıq (şək. 9.7.9). Əks təqdirdə, bunun üzərində iki qonşu və bir yeni nöqtə olan iki üçbucaq quracağıq (Şəkil 9.7.11). Yeni nöqtə P ilə təyin olunur. B OS P paraleloqramının diaqonalında P nöqtəsini axtaracağıq. Əgər paraleloqramın təpəsi ellipsin daxilində yerləşirsə (şək. 9.7.10), onda biz onu P nöqtəsi kimi qəbul edəcəyik. Əks halda, biz ellipsin kəsişməsini və paraleloqramın diaqonalını P nöqtəsi kimi qəbul edəcəyik. Sonuncu halda, ellipsin və seqmentin kəsişməsini axtarmaq heç də lazım deyil.
P nöqtəsinin koordinatları BC O nöqtələrinin koordinatları vasitəsilə müəyyən edilir
OP seqmentinin üfüqi ilə bucağı bərabərliklə müəyyən edilir
(9.7.8)
Bu məlumatlar P nöqtəsinin ellipsə nisbətən mövqeyini müəyyən etməyə imkan verir (9.7.5).
Şəkildə göstərilən vəziyyətdə. 9.7.9, bir üçbucaq quraq (onun təpələrinin nömrələrini xatırlayaq) və Şəkildə göstərilən vəziyyətdə O nöqtəsini silək. 9.7.11, biz iki üçbucaq quracağıq və iş sahəsində O nöqtəsini P nöqtəsi ilə əvəz edəcəyik və sonuncunu əldə edilən nöqtələr massivinə yerləşdirəcəyik. Şəkildə. Şəkil 9.7.12-də iki üçbucaq qurulduqdan və O nöqtəsi aradan qaldırıldıqdan sonra alınan çoxbucaqlı göstərilir. Hər iki halda O nöqtəsi işçi çoxbucaqlıdan çıxarılacaq və işçi çoxbucaqlı daralacaq. Qeyd edək ki, üçbucaqlar yalnız iş sahəsi daraldıqdan sonra özünü kəsmədikdə tikilə bilər.
düyü. 9.7.9. Üçbucağın qurulması
düyü. 9.7.10. Nəticə çoxbucaqlı
düyü. 9.7.11. İki üçbucağın qurulması
düyü. 9.7.12. Nəticə çoxbucaqlı
Belə vəziyyətlər Şek. 9.7.13. Onlar qurulmuş üçbucaqların tərəfləri onlara bitişik olmayan iş sahəsinin tərəfləri ilə kəsişdikdə baş verə bilər. Şəkildə göstərilən vəziyyətdə olduğu kimi yeni bir üçbucaq qurmadan əvvəl. 9.7.9 və Şəkildə göstərilən halda. 9.7.11, nəticədə yaranan çoxbucaqlının öz-özünə kəsişmədiyinə əmin olmaq üçün yoxlama aparılmalıdır.
Üstəlik, P nöqtəsinin mövqeyini təyin edərkən, onun iş sahəsinin digər nöqtələrindən kifayət qədər məsafədə olması və ərazinin nöqtələrini birləşdirən seqmentlərə yaxınlaşmaması vacibdir. Əks təqdirdə, üçbucaqlar qurarkən gələcəkdə çətinliklər yarana bilər. Buna görə də, işçi çoxbucaqlını daraltmadan əvvəl, nəticədə yaranan çoxbucaqlının özünü kəsişməsi üçün yoxlamaq lazımdır. O nöqtəsinin yaxınlığında üçbucaq (üçbucaqlar) qurmaq mümkün deyilsə, bunun əvəzinə çoxbucaqlının kontur daxilində digərlərinə nisbətən daha çox büküldüyü başqa bir nöqtə tapmalı və orada təsvir olunan hərəkətləri yerinə yetirməlisiniz.
Sonra, dəyişdirilmiş iş sahəsi ilə, biz təsvir etdiyimiz eyni hərəkətləri edəcəyik. İşçi çoxbucaqlının digər nöqtələrə nisbətən ərazinin daxilində daha çox döndüyü nöqtəni tapaq, bir və ya iki üçbucaq qurmaqla oradakı çoxbucaqlının daralmasının mümkünlüyünü yoxlayaq və çoxbucaqlını daralt.
düyü. 9.7.13. Bu küncdə üçbucaqlar qura bilməzsiniz.
Bu prosesi davam etdirərək ikiölçülü nöqtələr massivini və üçbucaq massivini genişləndirəcəyik və eyni zamanda işçi çoxbucaqlını daraldıb onun əhatə etdiyi ərazini və nöqtələrinin sayını azaldacağıq. Bu hərəkətlərin bəzi mərhələsində biz üç nöqtədən ibarət işləyən bir çoxbucaqlı alacağıq. Bu nöqtələrdə son üçbucağı quraq, iş sahəsini aradan qaldıraq və üçbucağı bitirək. Təsvir edilən üçbucaqlı üsulda, iş sahəsi ilə məhdudlaşan sahə, ondan üçbucaqları kəsməklə aradan qaldırılır.
Səth parametrlərinin sahəsi bir xarici kontur və tamamilə xarici konturun içərisində olan bir neçə daxili kontur ilə məhdudlaşdıqda ümumi vəziyyəti nəzərdən keçirək. Səth sərhədini parametrik sahədə qapalı çoxbucaqlılarla təxmin edirik. Hər kontur üçün öz poliqonumuzu quracağıq. Konturlar üçün olduğu kimi, onların üzərində qurulmuş çoxbucaqlılar üçün də onların qarşılıqlı orientasiya qaydası yerinə yetirilməlidir. Daxili çoxbucaqlıların istiqaməti xarici çoxbucaqlının oriyentasiyasına əks olmalıdır. Xarici kontur çoxbucaqlı ilə triangulyasiya qurmağa başlayaq. Gəlin onun nöqtələrini yaranan iki ölçülü nöqtələr massivinə qoyaq və çoxbucaqlının özünü işlək hala gətirək.
Biz üçbucaqları sadə birləşmiş bölgə vəziyyətində olduğu kimi quracağıq. İş sahəsində O nöqtəsini tapaq, orada iş sahəsinin daralma ehtimalını yoxlayaq və sahəni daralt. Daxili konturlar varsa, seçilmiş nöqtədə iş sahəsini daraltma ehtimalını yoxlamaq çətinləşir. Üçbucaqların tərəflərinin iş sahəsinin tərəfləri ilə kəsişməsi üçün təsvir edilən yoxlamalara əlavə olaraq, üçbucaqların tərəflərinin bütün daxili çoxbucaqlıların tərəfləri ilə kəsişməsini yoxlamaq lazımdır.
O nöqtəsində iki üçbucağın qurulmasının mümkünlüyünü yoxlayaq (şək. 9.7.11) və müəyyən edək ki, yeni P nöqtəsi qurulduqdan sonra daxili çoxbucaqlılardan birinin içərisinə düşəcək və ya onun seqmentlərinə qəbuledilməz yaxınlıqda olacaq. Bu halda, biz P nöqtəsini qurmayacağıq, əksinə şəkildə göstərilən iki üçbucağı qurmaqla bu daxili çoxbucaqlını işçi çoxbucaqlıya daxil edəcəyik. 9.7.14.
Daxili çoxbucaqlılardan birinin nöqtələrini işçi çoxbucaqlıya daxil etmək üçün daxili çoxbucaqlının nöqtələri arasında işçi çoxbucaqlının C nöqtəsinə (O nöqtəsinə bitişik) ən yaxın nöqtəni tapırıq.
OCF və CEF nöqtələrində və iş sahəsinin O və C nöqtələrində üçbucaqlar quraq, daxili çoxbucaqlının F nöqtəsindən başlayaraq E nöqtəsi ilə bitən nöqtələrini daxil edin. Beləliklə, OS seqmentində iş sahəsini qıracağıq, EF seqmentində daxili çoxbucaqlı və onları OF və AB seqmentləri ilə birləşdirin.
düyü. 9.7.14. İki üçbucağın qurulması
düyü. 9.7.15. Xarici və daxili çoxbucaqlıların birləşdirilməsi
Birləşmənin nəticəsi Şəkildə göstərilmişdir. 9.7.15. Əlbəttə ki, xarici və daxili çoxbucaqlıları birləşdirməzdən əvvəl bu əməliyyatın düzgünlüyünü təmin etmək üçün yoxlamalar aparılmalıdır.
Sonra, başqa bir daxili sahəyə yaxın olana və onu iş sahəsinə daxil edənə qədər iş sahəsini təsvir olunan şəkildə daraltmağa davam edəcəyik. Nəticədə, bütün daxili çoxbucaqlılar işçi çoxbucaqlıya daxil ediləcək, bu da son üç nöqtəyə qədər daralmalıdır. Nəticədə, səth parametrlərini təyin etmək üçün bütün çarpan bağlı sahə üçbucaqlarla örtüləcəkdir.
düyü. 9.7.16. Bu küncdə üçbucaqlar qura bilməzsiniz.
Verilmiş çoxbucaqlılar üzərində tək üçbucaq qurmaq mümkün olmayan vəziyyətlər ola bilər. Şəkildə. Şəkil 9.7.16-da hər biri dörd seqmentdən ibarət olan iki çoxbucaqlı ilə məhdudlaşan sahə göstərilir. Xarici çoxbucaqlı üçün triangulyasiyaya davam edə bilmərik, çünki daxili çoxbucaqlı yoldadır. Bu halda, çoxbucaqlının iki qonşu B və C nöqtəsini tapacağıq, bunun üçün HRV üçbucağını qura bilərik. P nöqtəsi BC tərəfinin ortasına proyeksiya edilir və ondan elə məsafədə yerləşir ki, yeni üçbucaq çoxbucaqlıları kəsməsin.
Trianqulyasiyanın digər üsulları.
Trianqulyasiyanın başqa yolları da var. Məsələn, səthin təyini sahəsinin xarici və daxili konturlarının çoxbucaqlılarını qurduqdan sonra üçbucaqların qurulması üçün fərqli strategiya seçilə bilər. Başqa bir seçim, üçbucaqlılığa başlamazdan əvvəl xarici və daxili çoxbucaqlıları bir çoxbucaqlıda birləşdirməkdir. Müəyyən bir alqoritmdən istifadə edərək, parametrlərin təyini sahəsinin daxilində nöqtələri “çizmək” və onlardan və sərhəd kontur poliqonlarının nöqtələrindən istifadə edərək Delaunay üçbucağını həyata keçirə bilərsiniz. Əvvəlcə böyük üçbucaqlar quran və sonra onları idarə edilə bilən ölçülərə bölən alqoritmlər var.
Bədən üçbucaqlılığı.
Cismin üçbucaqlılığı onun üzlərinin səthlərini üçbucaqlaşdırmaqla əldə edilən üçbucaqlar toplusudur. Ayrı-ayrı səthlərin trianqulyasiyası bədən üzlərinin trianqulyasiyasından onunla fərqlənir ki, sonuncu halda bitişik üzlər üçün sərhəd poliqonları ardıcıl olmalıdır (şək. 9.7.17).
düyü. 9.7.17. Bədən Üz Sərhəd Çoxbucaqlı Ardıcıllığı
Ümumi kənarlar boyunca keçən bitişik üzlərin çoxbucaqlı hissələri kosmosda nöqtələri üst-üstə düşərsə, ardıcıl olacaqdır.
Trianqulyasiyanın tətbiqi.
Triangulyasiya nəticəsində qurulan üçbucaqlar ton təsvirləri əldə etmək üçün istifadə olunur. Şəkildə. 9.7.18 və 9.7.19-da vərəq gövdəsinin üzünün üçbucaqlılığı göstərilir, ton təsviri Şəkil 1-də göstərilmişdir. 6.5.1.
düyü. 9.7.18. Korreksiya metodundan istifadə edərək bədən üzünün üçbucaqlanması
Səth parametrlərinin təyini sahəsinin üçbucaqlara bölünməsi cisimlərin həndəsi xarakteristikalarının hesablanması zamanı (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) inteqrallarında istifadə edilə bilər. . Ədədi inteqrasiya zamanı əyrilər üçün parametrik addım (8.11.5) düsturu ilə, səthlər üçün isə (8.11.1) və (8.11.2) düsturlarından istifadə etməklə parametrik addımlar hesablanmalıdır.
Sonlu S nöqtələri çoxluğu üçün üçbucaqlılıq S çoxluğunun bütün nöqtələrini əhatə edən qabarıq gövdə CH(S) üçbucağının üçbucaqlaşdırılması problemidir. Trianqulyasiyada düz xətt seqmentləri kəsişə bilməz - onlar yalnız S çoxluğuna aid ümumi nöqtələrdə görüşə bilərlər. Çünki düz xətt seqmentləri üçbucaqları bağlayır, biz onları qabırğa hesab edəcəyik. Şəkildə. Şəkil 1 eyni nöqtələr dəsti üçün üçbucaqlılığın iki fərqli versiyasını göstərir (biz bu rəqəmlərdə çəkilmiş dairələri müvəqqəti olaraq nəzərdən qaçıracağıq).
düyü. 1
Verilmiş S nöqtələri toplusu üçün biz görə bilərik ki, S çoxluğundakı bütün nöqtələr sərhəd nöqtələrinə - qabarıq gövdə CH(S) sərhədində yerləşən nöqtələr və daxili nöqtələr - qabarıq içərisində yerləşən nöqtələrə bölünə bilər. gövdə CH(S). S trianqulyasiyası nəticəsində əldə edilən kənarları da təsnif edə bilərsiniz qabıq qabırğaları Və daxili qabırğalar. Korpusun kənarlarına qabarıq gövdə CH(S) sərhədi boyunca yerləşən kənarlar, daxili kənarlara isə qabarıq gövdə daxilində üçbucaqlar şəbəkəsini təşkil edən bütün digər kənarlar daxildir. Qeyd edək ki, qabığın hər bir kənarı iki bitişik sərhəd nöqtəsini birləşdirir, daxili kənarlar isə istənilən növ iki nöqtəni birləşdirə bilər. Xüsusilə, daxili kənar iki sərhəd nöqtəsini birləşdirirsə, bu, qabarıq gövdənin CH(S) akkordudur. Onu da qeyd edək ki, trianqulyasiyanın hər kənarı iki bölgənin sərhədidir: hər bir daxili kənar iki üçbucaq arasındadır və qabığın hər kənarı üçbucaq və sonsuz müstəvi arasındadır.
Bəzi əhəmiyyətsiz hallar istisna olmaqla, istənilən nöqtələr dəsti birdən çox trianqulyasiya metoduna imkan verir. Ancaq diqqətəlayiq bir xüsusiyyət var: verilmiş çoxluq üçün hər hansı bir üçbucaqlama üsulu teoremdən irəli gələn eyni sayda üçbucaqları təyin edir:
Nöqtələr çoxluğunun üçbucaqlanmasına dair teorem. Tutaq ki, S nöqtələri çoxluğunda n>3 nöqtə var və onların heç də hamısı kollinear deyil. Bundan əlavə, onlardan i nöqtələri daxilidir (yəni qabarıq gövdə CH(S) daxilində uzanır. Onda S çoxluğunun hər hansı bir trianqulyasiya üsulu tam olaraq n + i - 2 üçbucaqla nəticələnəcəkdir.
Teoremi sübut etmək üçün ilk növbədə n-i sərhəd nöqtələrinin trianqulyasiyasını nəzərdən keçirək. Onların hamısı qabarıq çoxbucaqlının təpələri olduğu üçün belə üçbucaqlama (n - i) - 2 üçbucaqla nəticələnəcək. (Bunu yoxlamaq çətin deyil və üstəlik, hər hansı bir trianqulyasiya olduğunu göstərmək olar ixtiyari M-tərəfli çoxbucaqlı - qabarıq və ya qabarıq olmayan - m - 2 üçbucaqdan ibarətdir). İndi isə hər dəfə bir ədəd olmaqla qalan i daxili nöqtələri əlavə etdikdə trianqulyasiyanın nə olacağını yoxlayaq. Biz iddia edirik ki, hər bir belə nöqtənin əlavə edilməsi üçbucaqların sayını iki artırır. Daxili bir nöqtə əlavə edərkən, Şəkildə göstərilən iki vəziyyət yarana bilər. 2. Birincisi, nöqtə hansısa üçbucağın daxilində ola bilər və sonra belə üçbucaq üç yeni üçbucaqla əvəz olunur. İkincisi, əgər nöqtə trianqulyasiya kənarlarından biri ilə üst-üstə düşürsə, bu kənara bitişik olan iki üçbucağın hər biri iki yeni üçbucaqla əvəz olunur. Buradan belə nəticə çıxır ki, bütün i nöqtələrini əlavə etdikdən sonra üçbucaqların ümumi sayı (n - i - 2) + (2i) və ya sadəcə n + i - 2 olacaqdır.
düyü. 2
Bu bölmədə biz Delaunay trianqulyasiyası kimi tanınan xüsusi bir trianqulyasiya növünün yaradılması üçün alqoritmi təqdim edəcəyik. Bu üçbucaqlaşma yaxşı balanslaşdırılmışdır ki, əmələ gələn üçbucaqlar bərabərbucaqlı olurlar. Məsələn, Şəkildə göstərilən üçbucaqlılıq. 1a Delaunay trianqulyasiya növünə aid edilə bilər və Şek. 1b üçbucaqlı bir neçə yüksək uzunsov üçbucaqları ehtiva edir və onları Delaunay tipinə aid etmək olmaz. Şəkildə. Şəkil 3-də çoxlu sayda nöqtələr dəsti üçün Delaunay trianqulyasiyasının nümunəsi göstərilir.
düyü. 3
Delaunay üçbucağını yaratmaq üçün bizə bir neçə yeni tərif lazımdır. Çoxluğun bütün nöqtələrinin yerləşdiyi bir dairə varsa, nöqtələr çoxluğu dairəvi hesab olunur. Belə bir dairə verilmiş nöqtələr dəsti üçün məhdudlaşdırılacaqdır. Üçbucağın dairəsi onun hər üç təpəsindən keçir (kollinear olmayan). Əgər dairənin daxilində S çoxluğundan heç bir nöqtə yoxdursa, dairənin verilmiş S nöqtələrinə münasibətdə nöqtəsiz olacağı deyilir ən xalsız.
Əgər hər üçbucaq üçün çevrə nöqtələrdən azaddırsa, S nöqtələri dəstinin trianqulyasiyası Delaunay trianqulyasiyası olacaqdır. Üçbucaqlı diaqramda Şek. Şəkil 1a, içərisində başqa nöqtələri açıq şəkildə ehtiva etməyən iki dairəni göstərir (digər üçbucaqlar üçün dairələr çəkə bilərsiniz ki, onlar da çoxluğun nöqtələrindən azad olsunlar). Şəkildəki diaqramda bu qayda müşahidə edilmir. 16 - digər üçbucağın bir nöqtəsi çəkilmiş dairənin içərisinə düşür, buna görə də bu qrianqulyasiya Delaunay tipinə aid deyil.
Trianqulyasiya alqoritmini sadələşdirmək üçün S çoxluğundakı nöqtələr haqqında iki fərziyyə irəli sürmək olar. Birincisi, trianqulyasiyanın ümumiyyətlə mövcud olması üçün S çoxluğunda ən azı üç nöqtənin olduğunu və onların kollinear olmadığını düşünməliyik. İkincisi, Delaunay üçbucağının unikal olması üçün S çoxluğundan heç bir dörd nöqtənin eyni dairədə olmaması lazımdır. Belə bir fərziyyə olmadan Delaunay üçbucağının unikal olmayacağını görmək asandır, çünki bir dairədə 4 nöqtə iki fərqli Delaunay üçbucağını həyata keçirməyə imkan verir.
Alqoritmimiz cari trianqulyasiyanı hər dəfə bir üçbucaq artıraraq işləyir. Başlanğıcda cari triangulyasiya alqoritmin sonunda qabığın tək kənarından ibarətdir, cari trianqulyasiya Delaunay üçbucağına çevrilir. Hər iterasiyada alqoritm ona qoşulan yeni üçbucaq axtarır sərhəd cari trianqulyasiya.
Sərhədin tərifi ondan asılıdır aşağıdakı diaqram cari trianqulyasiyaya nisbətən Delaunay trianqulyasiyasının kənarlarının təsnifatı. Hər kənar ola bilər yatmaq, diri və ya ölü:
- yuxu qabırğaları: Delaunay trianqulyasiyasının kənarı alqoritm tərəfindən hələ aşkar edilməmişdirsə, hərəkətsizdir;
- canlı qabırğalar: qabırğa tapılarsa canlıdır, ancaq bir bitişik sahə məlumdur;
- ölü qabırğalar: Kenar tapılıbsa və hər iki qonşu sahə məlumdursa, ölü sayılır.
Əvvəlcə qabarıq i lobuna aid olan yeganə kənar canlıdır - sərhədsiz bir müstəvi ona bitişikdir və bütün digər kənarlar hərəkətsizdir. Alqoritm işlədikcə kənarlar yuxudan diriliyə, ölüyə keçir. Hər mərhələdə sərhəd canlı kənarlar dəstindən ibarətdir.
Hər bir təkrarlamada sərhədin hər hansı bir kənarı seçilir və o, e kənarının aid olduğu naməlum bölgənin axtarışından ibarət olan emala məruz qalır kənarının son nöqtələri e və bəzi üçüncü təpə v, sonra e kənarı ölü olur, çünki ona bitişik hər iki sahə artıq məlumdur. Üçbucağın digər iki kənarının hər biri t aşağıdakı vəziyyətə keçir: yuxudan diriyə və ya diridən ölüyə. Burada v təpəsi çağırılacaq qoşma kənarı ilə e. Əks halda, naməlum bölgə sonsuz müstəviyə çevrilirsə, e kənarı sadəcə ölür. Bu halda e kənarında konjugat təpəsi yoxdur.
Şəkildə. Şəkil 4 alqoritmin işini göstərir, burada hərəkət yuxarıdan aşağıya və şöhrət sağa doğru baş verir. Hər mərhələdə sərhəd qalın bir xətt ilə vurğulanır.
Alqoritm delaunayTriangulate proqramında həyata keçirilir. Proqrama n nöqtədən ibarət s massivi verilir və Delaunay üçbucağını təmsil edən üçbucaqların siyahısını qaytarır. Tətbiq həndəsi məlumat strukturu bölməsindən dairəvi siyahı sinifindən və siniflərdən istifadə edir. Lüğət sinfi tələb olunan əməliyyatları dəstəkləyən istənilən lüğət ola bilər. Məsələn, siz #define Dictionary RandomizedSearchTree-ni ləğv edə bilərsiniz.
Siyahı
sərhəd (edgeCmp);
Kənar *e = gövdə kənarı(lar, n);
Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) 1-i qaytarın;< b->əgər (a->org > b->org) 1-i qaytarır;
əgər (a->dest
dest) qayıtmaq -1;
əgər (a->dest > b->dest) 1-i qaytarır;
0 qaytarmaq; )
updateFrontier funksiyası sərhəd lüğətini redaktə edir, burada a nöqtəsindən b nöqtəsinə qədər kənarın vəziyyəti dəyişir:
düyü. 5< 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]); }
Cəbhə yeniləməsini ləğv edin (Lüğət
&sərhəd, Nöqtə &a, Nöqtə &b) ( Kənar *e = yeni Kənar (a, b); əgər (sərhəd.tapmaq (e)) sərhədi.silmək(e); başqa ( e->flip(); sərhəd.insert( e);
HullEdge funksiyası s massivindəki n nöqtə arasında gövdə kənarını tapır. Bu funksiya əslində başlanğıc addımından və hədiyyə paketləmə metodunun ilk iterasiyasından istifadə edir:
Edge *hullEdge (Point s, int n) ( int m = 0; for (int i = 1; i) 
Üçbucaq funksiyası sadəcə olaraq parametr kimi ona ötürülən üç nöqtə üçün çoxbucaqlı yaradır və qaytarır: 
Üçbucaq funksiyası sadəcə olaraq parametr kimi ona ötürülən üç nöqtə üçün çoxbucaqlı yaradır və qaytarır: 
Çoxbucaqlı *üçbucaq (Nöqtə &a, Nöqtə &b, Nöqtə &c) ( Poliqon *t = yeni Çoxbucaqlı; t->daxil et (a); t->daxil et (b); t->daxil et (c); qaytar t; ) 
GRID modelləri müntəzəm hüceyrələrin modelləridir. 
.
,
Koordinat sistemi təqdim edilsin
Və 
Üçbucaq funksiyası sadəcə olaraq parametr kimi ona ötürülən üç nöqtə üçün çoxbucaqlı yaradır və qaytarır: 
,
- bit şəbəkəsi.
- kvantlaşdırılmış dəyərlər. Real:
- alqoritm parametri - nöqtələrin sayı, 
- çəki. Nöqtə nə qədər yaxın olsa, çəki bir o qədər çox olar.
- məsafə dərəcəsi (1 və ya 2).
Normallaşma əmsalı: 
Necə 
1-ə yaxın olduqda, çəkisi daha yüksək olan xallar nəzərə alınır.
Bu IDW üsuludur - uzundur, hər t üçün qonşu tapmaq lazımdır. Qonşuların dəsti səmərəli şəkildə tapıla bilər - ən yaxın. Hər bir nöqtə müəyyən hündürlükdə bir “mix” yaradır. Bunun üçün götürdükləri nöqtənin nizamsızlığından çox şey asılıdır; 
və ya 
olanlar. sektorlara bölünür və yaxınlıqda nöqtələr tikir.
Üstünlük- sadəlik
Qüsur:
------Bilet 14. Kalay modeli. Delaunay üçbucaqlaşdırma alqoritmləri------
1) Üçbucaqlı (qalay).
Üçbucaqlılıq– hissə-hissə xətti funksiyalar toplusu şəklində funksiyanın qurulması
Üçbucaqlılıq– qabarıq bölgə daxilində interpolyasiya.
Üçbucaqlılıq– bütün daxili kənarları üçbucaq olan planar qrafik; məkanı üst-üstə düşmədən bir-birinə bitişik üçbucaqlar şəklində təqdim etmə üsulu. Üçbucaqlılıq bir neçə yolla bir sıra nöqtələr üzərində qurulur.
Optimal trianqulyasiyanı qurmaq üçün alqoritm lazımdır.
3 nöqtədən keçən təyyarə.
1) Üçbucağı tapın 
;
2)
- müstəvi tənliyini qurun.
Nöqtələrin üçbucağın içərisində olub-olmadığını yoxlamaq üçün dəyəri xətlərin tənliyinə - üçbucağın kənarlarına əvəz etməlisiniz. Əgər bütün 3 tənlik > 0 olarsa, onda içəridə.
Təqdimat quruluşu:
Hər üçbucaq eyni sayda üçbucaqları ehtiva edir.
, Harada 
- daxili nöqtələrin sayı, 
- xalların sayı.
Acgöz üçbucaqlaşma.
Bütün nöqtələri kənarlarla bağlayırıq, minimumu seçirik və onları üçbucaqlıya əlavə edirik. Sonra, əvvəlkilərlə kəsişməyən növbəti minimumu götürürük və s. Nəticə acgöz triangulyasiyadır.
Delaunay üçbucaqlılığı.
Hər hansı bir üçbucağın ətrafına çəkilmiş dairənin içərisinə digər üçbucaqların nöqtələri daxil deyil. Yeganə şəkildə tikilir.
Flip kənarların köçürülməsidir. Bu, adi trianqulyasiyadan Delaunay trianqulyasiyasına keçməyə imkan verir. Nöqtənin dairəyə aid olub-olmadığını yoxlamaq üçün: if əvəz edin< R, то внутри.
Delaunay vəziyyəti.
Üç nöqtədən keçən dairənin tənliyi:
Sıfırdan azdırsa, xarici, əks halda - daxili.
- Delaunay vəziyyəti.
Delaunay trianqulyasiyasının qurulması alqoritmi:
1) Tədqiq olunan nöqtələrin əlavə edilməsi- sadə iterativ alqoritm:
Komplekt var 
üçbucağa əlavə edin, tikinti aparılır 
üçbucağın parçalanması 
yenidən qurulması. Sıfır mərhələdə, zərfimizi, içərisindəki bütün nöqtələri açıq şəkildə əhatə edən 3-4 uydurma nöqtə əlavə edirik. Sonra nöqtəni atırıq, hansı üçbucağa dəydiyinə baxırıq, 3-ə bölürük, hər üçbucaq üçün Delaunay şərtini yoxlayırıq və kənarların flip transferini həyata keçiririk. Zolaq dəyişmələrinin orta sayı üçdür.
Nəzəri mürəkkəblik 
2) Sürətləndirmə üsulları. Statistik cəhətdən asılı olan nöqtələrə əsaslanır. Toxum üçbucağı əvvəlki nöqtənin düşdüyü üçbucaqdır. Sonra iki nöqtəni birləşdiririk - əvvəlki və yeni.
Birinci nöqtədən digərinə keçirik.
