İçin nicelik belirleme Oluşturulan üçgenlemenin kalitesi için iki tür kriter tanımlayacağız: topolojik ve geometrik.

Topolojik kriter aşağıdakilere dayanmaktadır: en yakın komşular setten alınan puanlar İÇİNDE ideal olarak Bir noktanın iki boyutlu bölge için 6 komşusu, üç boyutlu bölge için ise 12 komşusu vardır. Formül (1)'i kullanarak topolojik bir tahmin elde ederiz; burada - toplam miktar Bir alandaki noktalar, - bir iç noktayla örülmüş komşu noktaların derecesi veya sayısı.

Geometrik kriter, tasarım üçgen elemanının etrafındaki yazılı ve çevrelenmiş daireler arasındaki farka dayanmaktadır. Formül (2)'yi kullanarak geometrik bir tahmin elde ediyoruz; burada üçgen sayısı, yazılı dairenin yarıçapı, çevreli dairenin yarıçapıdır.

Üçgenleme oluşturmak için algoritmalar

Üçgenleme oluşturmak için çok sayıda algoritma vardır. Emek yoğunluğu, bilgisayardaki uygulamanın karmaşıklığı ve inşaat yaklaşımları bakımından farklılık gösterirler. Algoritmalar hakkında daha fazla bilgiyi A.V.'nin kitabında bulabilirsiniz. Skvortsova. Bazı algoritmalara bakalım.

İlk teklif edilenlerden biri açgözlü algoritmaüçgenleme inşaatı. Bir Delaunay üçgenlemesi, açgözlü bir algoritma kullanılarak oluşturulmuşsa açgözlü olarak adlandırılır. Açgözlü algoritmanın karmaşıklığı ve bazı iyileştirmeleri şu şekildedir: Bu kadar yüksek emek yoğunluğu nedeniyle pratikte neredeyse hiç kullanılmamaktadır. Algoritmaya adım adım bakalım:

Adım 1. Kaynak nokta çiftlerini birbirine bağlayan tüm olası bölümlerin bir listesi oluşturulur ve bölüm uzunluklarına göre sıralanır.

Adım 2. En kısa olandan başlayarak bölümler üçgenlemeye sırayla eklenir. Bir segment önceden eklenen diğer segmentlerle kesişmiyorsa eklenir, aksi halde atılır.

Tüm olası bölümlerin farklı uzunlukları varsa, bu algoritmanın sonucunun kesin olduğunu, aksi takdirde aynı uzunluktaki bölümlerin eklenme sırasına bağlı olduğunu unutmayın.

Yinelemeli algoritmaçok dayanmaktadır basit fikir Kısmen oluşturulmuş Delaunay üçgenlemesine noktaların sıralı eklenmesi. Karmaşıklık bu algoritmanın Bir sonraki adımda bir noktanın eklendiği bir üçgen aramanın karmaşıklığı, yeni üçgenler oluşturmanın karmaşıklığı ve komşu çiftlerin yetersiz kontrolleri sonucunda üçgenleme yapısının karşılık gelen yeniden yapılandırmalarının karmaşıklığından oluşur. Delaunay koşulunun yerine getirilmesi için ortaya çıkan üçgenlemenin üçgenleri. Algoritmaya adım adım bakalım:

Adım 1.İlk üç başlangıç ​​noktasına bir üçgen oluşturuyoruz.

Adım 2. Diğer tüm noktalar için döngüde 3-5. adımları gerçekleştiriyoruz.

Adım 3. Bir sonraki i'inci nokta, önceden oluşturulmuş olan üçgenleme yapısına aşağıdaki gibi eklenir. İlk olarak, nokta yerelleştirilmiştir, yani. bir sonraki noktanın içine düştüğü bir üçgen (daha önce inşa edilmiş) vardır. Veya nokta üçgenlemenin içine girmiyorsa üçgenlemenin sınırında bir sonraki noktaya en yakın bir üçgen yerleştirilir.

Adım 4. Bir nokta daha önce eklenen bir üçgenleme düğümüne düşerse, bu tür bir nokta genellikle atılır, aksi takdirde nokta, yeni bir düğüm olarak üçgenlemeye eklenir. Dahası, nokta bir kenara düşerse, iki yeniye bölünür ve kenara bitişik her iki üçgen de iki küçük parçaya bölünür. Bir nokta tam olarak bir üçgenin içine düşerse, üç yeni noktaya bölünür. Nokta üçgenlemenin dışına çıkarsa bir veya daha fazla üçgen oluşturulur.

Adım 5. Yeni elde edilen üçgenlerin Delaunay koşuluna uygunluğu açısından yerel kontrolleri yapılmakta ve gerekli rekonstrüksiyonlar yapılmaktadır.

Yeni üçgenler oluştururken iki durum mümkündür: eklenen nokta ya üçgenlemenin içindedir ya da dışındadır. İlk durumda yeni üçgenler oluşturulur ve algoritmanın gerçekleştirdiği eylem sayısı sabitlenir. İkincisinde, mevcut üçgenlemenin dışında ek üçgenler oluşturmak gerekir ve bunların sayısı en kötü durumda eşit olabilir mi? 3. Ancak algoritmanın tüm adımları sırasında artık üçgen eklenmez; burada - toplam sayı başlangıç ​​noktaları. Dolayısıyla her iki durumda da üçgen oluşturmak için harcanan toplam süre.

Zincir algoritmasıÜçgenleme oluşturmak için ilk etkili algoritmalardan biri, düzlemsel bir grafiğin düzenlenmesi ve monoton çokgenlerin üçgenlenmesi prosedürüne dayanmaktadır. Bu algoritmanın karmaşıklığı başlangıç ​​bölümlerinin sayısının nerede olduğudur. Algoritmaya adım adım bakalım:

Adım 1. Başlangıçtaki yapısal parçalar kümesinden bağlantılı bir düzlemsel grafik oluşturuyoruz (Şekil 4,a).

Adım 2. Grafik düzenlileştirilmiştir, yani. diğerleriyle kesişmeyen yeni kenarlar eklenir, böylece grafiğin her köşesi, kendisinin üstündeki ve altındaki en az bir köşeye bitişik hale gelir. Düzenlileştirme dikey düz süpürme kullanılarak iki geçişte yapılır. Aşağıdan yukarıya doğru ilk geçişte, yukarıya doğru hiçbir kenarın çıkmadığı tüm köşeler sırayla bulunur. Örneğin (Şekil 4, b)'de bu köşe B'dir. yatay çizgi AD ve EF grafiğinin solda ve sağda kesiştiği en yakın kenarlarını buluruz. Daha sonra DEHG dörtgeninde en alçak köşeyi bulup B'den buraya bir kenar çiziyoruz. Yukarıdan aşağıya ikinci geçiş de aynı şekilde yapılıyor (Şekil 4,c). Bu adımın sonucunda düzlemsel grafiğin her bölgesi monoton bir çokgen haline gelir.

Adım 3. Grafiğin her bölgesi üçgenlere bölünmelidir. Bunu yapmak için, iki üçgenlemenin dışbükey olmayan birleştirilmesine yönelik algoritmayı kullanabilirsiniz (Şekil 4, d).

Şekil 4. Zincir üçgenleme algoritmasının çalışma şeması: a) - başlangıç ​​bölümleri; b - grafik düzenlemesinin aşağıdan yukarıya geçişi; c) - yukarıdan aşağıya geçiş; d) - monotonik çokgenlerin üçgenlenmesi

Zincirleme bir algoritma uygulamak için, "Çift Kenarlar" veya "Düğümler, Kenarlar ve Üçgenler" gibi kenarların açıkça temsil edildiği veri yapılarını kullanmak en iyisidir.

Zincir algoritmasının dezavantajı, ortaya çıkan üçgenlemenin şekli hakkında önceden hiçbir şeyin söylenememesidir. Bu optimal bir üçgenleme değil, açgözlülük değil ve kısıtlı bir Delaunay üçgenlemesi değil. Zincir algoritması çok uzun uzun üçgenler üretebilir.

Ortaya çıkan üçgenlemenin kalitesini artırmak için, yapısal bir kenarla ayrılmamış tüm komşu üçgen çiftlerini Delaunay koşuluna göre kontrol edebilir ve gerekirse yeniden yapılandırmalar yapabilirsiniz. Sonuç, kısıtlamaların olduğu bir Delaunay üçgenlemesi olacaktır.

TEPLOV A.A., Lisans, MSTU, N.E. Bauman, bölüm " Yazılım bilgisayar ve Bilişim teknolojisi"Moskova, [e-posta korumalı]

MAYKOV K.A., Teknik Bilimler Doktoru, Profesör, Moskova Devlet Teknik Üniversitesi N.E. Bauman, Bilgisayar Yazılımı ve Bilgi Teknolojileri Bölümü, Moskova, [e-posta korumalı]

Değiştirilmiş algoritma
Delaunay üçgenlemesi

Sonuçlar verildi karşılaştırmalı analiz Yüksek performanslı ve düşük kaynak tüketimine sahip Delaunay üçgenleme yöntemleri. Daha sonraki modernizasyon için bir prototip seçimi, dinamik üç boyutlu nesnelerin gerçek zamanlı olarak pratik olarak gerekli ayrıntı derecesine sahip inşasıyla bağlantılı olarak doğrulanır. Donanım uygulamasında hataların önlenmesine olanak tanıyan, dağıtım yoğunluğuna uygun olarak bir dizi üçgenleme noktasının aralıklı bölümlenmesi için bir algoritma önerilmiştir. Önerilenin analizi değiştirilmiş algoritma Delaunay üçgenlemesi

giriiş

Belirli bir ayrıntı düzeyine sahip dinamik 3 boyutlu nesneler oluşturmanın kaynak yoğunluğunu belirleyen aşamalardan biri üçgenlemedir. Uygulamada, yüksek performans ve düşük kaynak yoğunluğu şartlarını karşılayan bir üçgenleme yönteminin prototipinin belirlenmesine ve ardından belirli bir problem sınıfı için modifikasyon yapılmasına ihtiyaç vardır.

Çözülecek görevlerin belirlenmesi

Bir dizi pratik problem, bilinmeyen bir dağıtım yasasına sahip karşılık gelen bir dizi nokta tarafından tanımlanan 3 boyutlu nesnelerin modellenmesi ihtiyacıyla karakterize edilir. Örnek benzer görevler yükseklikleri önceden uzaktan algılama ile elde edilen bir dağ sırasının veya karmaşık ve düzensiz yüzey yapılarının modellenmesidir. Bu durumda, minimum toplam değerine sahip "ince" üçgenlerin yapısının hariç tutulmasıyla karakterize edilen, üçgenlerin en yüksek "doğruluk derecesini" sağlayarak orijinal nokta kümesi üzerinde üçgenleme yapmak gerekir. çevrelenmiş dairelerin yarıçapları.

Üçgenlerin "düzenlilik derecesi" sorunu, Delaunay koşulunu sağlayan üçgenleme ile çözülür.

Bilinen Delaunay üçgenleme algoritmaları şu dört kategoriye ayrılabilir: yinelemeli algoritmalar, birleştirme algoritmaları, iki geçişli algoritmalar ve adım adım; ana özellikler belirtilen algoritmalar aşağıda tartışılmaktadır.

Delaunay üçgenlemesini oluşturmak için yinelemeli algoritmalar

Yinelemeli algoritmalar, kısmen oluşturulmuş bir Delaunay üçgenlemesine noktaların sıralı olarak eklenmesini uygular. Yinelemeli Delaunay algoritmalarının karmaşıklığı O(N2) olarak tanımlanır ve bu durum için düzgün dağılım puan – O(N) . Yinelemeli Delaunay algoritmalarının dezavantajları şunlardır: büyük sayı yinelemeli döngüler, sıralama algoritmasının kaynak verinin yapısına bağımlılığı ve ayrıca her döngüde Delaunay koşulunu kontrol etme ihtiyacı. Yinelemeli Delaunay algoritmalarının avantajları, uygulama kolaylığı ve yüksek hızlı seçimdir. verimli algoritma Belirli bir giriş verisi kümesine göre sıralama.

Birleştirme yoluyla Delaunay üçgenlemesini oluşturmaya yönelik algoritmalar

Birleştirme algoritmaları, orijinal nokta kümesinin bir dizi alt kümeye bölünmesini uygular; burada bir dizi çözümün daha sonra birleştirilmesiyle üçgenlemeler oluşturulur. Birleştirme algoritmalarının ortalama karmaşıklığı O(N)'dir. Birleştirme algoritmaları, "dar" şeritler için dışbükey alanlar oluşturma ihtiyacı ve sonuç olarak birleştirme sırasında yeniden oluşturulan uzun, "dar" üçgenlerin oluşumu ile belirlenen artıklık ile karakterize edilir. Birleşme algoritmaları, pratik avantajlarını belirleyen yüksek performansa sahiptir.

Delaunay üçgenlemesini oluşturmak için iki geçişli algoritmalar

İki geçişli algoritmaların avantajlı özelliği, ilk çevrimde, ikinci aşamada Delaunay koşuluna göre değiştirilen Delaunay koşulu dikkate alınmadan belirli bir üçgenlemenin oluşturulmasıdır. İki geçişli algoritmaların karmaşıklığı ortalama olarak O(N) ve en az tercih edilen durumda – O(N 2)'dir. İki geçişli Delaunay algoritmalarının dezavantajı, büyük miktarlar her şerit için sıralama yapar. Aynı zamanda bu algoritma yüksek performansla karakterize edilir, çünkü Üçgenlemeye giren bir sonraki üçgen, önemli donanım kaynakları gerektiren Delaunay koşulunun karşılanması açısından kontrol edilmez.

Delaunay üçgenlemesini oluşturmak için adım adım algoritmalar

Adım adım oluşturma algoritmaları yalnızca son üçgenlemede Delaunay koşulunu karşılayan üçgenleri uygular ve bu nedenle yeniden yapılandırma gerektirmez. Noktaların çok yoğun olduğu durumlarda adım adım hücresel algoritmanın kullanılması pratik değildir. Bu algoritmanın karmaşıklığı ortalama olarak O(N) ve en kötü durumda – O(N 2)'dir.

Delaunay üçgenlemesini değiştirmek için bir prototip seçme

Gerçek zamanlı olarak dinamik 3 boyutlu nesneler oluşturma probleminin pratik özellikleri, Delaunay üçgenleme algoritmaları için yüksek performans ve düşük kaynak yoğunluğu gibi gereksinimleri belirler. Yukarıdaki analiz sonuçlarından da anlaşılacağı üzere, dikkate alınan algoritmalar bu gereksinimleri tam olarak karşılamamaktadır. Bu nedenle, üçgenleme alanının, üçgenlemenin noktalarını içeren temel öğelere bölünmesine bağlı olmayan ve mevcut üçgenin orijinal üçgenlemeye eklenmesinin her yinelemesinde Delaunay koşulunun kontrol edilmesini gerektirmeyen bir algoritma oluşturmaya ihtiyaç vardır. .

Karşılaştırmalı analizin yukarıdaki sonuçlarından, iki geçişli Delaunay üçgenleme algoritmalarının, özellikle de iki geçişli fan algoritmasının, yüksek performans ve düşük kaynak yoğunluğu kriterlerini yalnızca kısmen karşıladığı sonucu çıkmaktadır.

Ancak algoritmalar bu türden Gerçek zamanlı görevlere uygulanabildiğinde performansı artırmak için değişiklik yapılması gerekir. İki geçişli fan algoritması, noktaların kütle merkezinin belirlenmesinde gereksizdir. OX veya OY kullanarak bir nokta kütle merkezinin koordinatını belirlerken, çok sayıda noktayla aritmetik ortalamanın değerini hesaplamak uygun değildir ve ne zaman büyük değerler noktaların koordinatları, veri taşması meydana gelebilir, bu da bir hataya veya programın çökmesine neden olur. Bu nedenle, üçgenleme noktalarının tüm değerlerinin X ekseni boyunca aralıklara Δx 1, Δx 2, Δx 3 ... Δx n'ye ve Y ekseni boyunca Δy 1, Δy 2, Δy 3'e bölünmesi tavsiye edilir. ... Δy n. X ve Y eksenleri boyunca karşılık gelen aralıklara ait noktaların sayısını da belirlemek gerekir. Noktaların kütle merkezini elde etmek için elde edilen formüller aşağıdaki forma sahiptir:

• x c – kütle merkezi noktasının x koordinatı;
• Δх ben – i-inci aralık X ekseninde;
• Maksimum X – maksimum değer tüm üçgenleme noktaları arasında X ekseni boyunca;
• X min – tüm üçgenleme noktaları arasında X ekseni boyunca minimum değer;

• y c – kütle merkezi noktasının y koordinatı;
• n i - i'inci aralıktaki noktaların sayısı;
• Δy i – Y eksenindeki i-inci aralık;
• Y max – tüm üçgenleme noktaları arasında Y ekseni boyunca maksimum değer;
• Y min – tüm üçgenleme noktaları arasında Y ekseni boyunca minimum değer.

Üçgenlemenin sonraki aşamaları klasik fan algoritmasına göre uygulanır. Geliştirilen değiştirilmiş yelpaze şeklindeki Delaunay üçgenleme algoritmasının diyagramı Şekil 1'de gösterilmektedir. 1.

Sunulan şemadaki en emek yoğun aşamalar, üçgenlemeyi dışbükey olarak sıralama ve oluşturma aşamalarıdır. Sıralama algoritması olarak birleştirme algoritması, dışbükey üçgenleme algoritması olarak da Graham algoritması seçildi. Her iki algoritma da çalışır kabul edilebilir süre temsilcileri arasında pratik açıdan en çok tercih edilenlerdir.

Değiştirilmiş yelpaze şeklindeki Delaunay üçgenleme algoritmasının analizi

Şekil 2'de gösterilenden. Diyagramın 1'i, değiştirilmiş fan algoritmasını kullanarak üçgenleme oluşturmaya yönelik zaman değerinin şu ifadeyle belirlendiğini göstermektedir:

• T 1 , T 2 - sırasıyla X ve Y eksenleri boyunca en uygun aralık sayısını hesaplamak için zaman değerleri;
• T 3 , T 4 - sırasıyla X min ve X max hesaplama süresinin değerleri;
• T 5 , T 6 - sırasıyla Y min ve Y max hesaplama süresinin değerleri;
• T 7 , T 8 - sırasıyla X ve Y eksenleri boyunca aralık değerlerinin hesaplanması için zaman değerleri;
• T 9 – dizinin her noktasının A(Xc,Yc) noktasına göre kutup açısını hesaplamak için zaman değeri;
• T 10 – tüm noktaların A(Xc ,Yc) noktasına göre kutup açılarına göre birleştirilmesiyle elde edilen sıralama süresi değeri;
• T 11 – dizinin her noktasından A(Xc ,Yc) noktasına kadar bir kenar oluşturmak için zaman değeri;
• T 12 – üçgenlemeyi dışbükey olana tamamlamak için zaman değeri;
• T 13 – Delaunay koşulunu karşılayan üçgenleme yeniden yapılandırma süresinin değeri;
• n – nokta koordinat değerleri dizisi.

Her zaman bağımlılığını ayrı ayrı ele alalım.

X ve Y ekseni boyunca optimum aralık sayısını belirlerken, n aralık sayısının şu şekilde belirlendiği Sturges kuralını kullanırız:

• N, miktarın toplam gözlem sayısıdır;
• [X] - bütün kısım sayılarx.

T 1 ve T 2 zaman bağımlılıklarının sabit c 1 ve c 2 temsillerine sahip olduğu açıktır.

X min , X max , Y min , Y max değerlerinin belirlenmesi aşamalarında sözde kod şöyle görünecektir:

X min ← M

i ← 1 için uzunluk(M) – 1

Eğer Xmin › M[i]

Xmin ← M[i]

Xmaks ← M

i ← 1 için uzunluk(M) – 1

Xmax ise< M[i]

Xmaks ← M[i]

Ymin ← M

i ← 1 için uzunluk(M) – 1

Eğer Ymin › M[i]

Ymin ← M[i]

Ymaks ← M

i ← 1 için uzunluk(M) – 1

Ymax ise< M[i]

Ymaks ← M[i]

Yukarıdaki sözde koddan maksimumu bulma süresinin veya minimum değer x veya y'nin sahip olduğu değerler doğrusal bağımlılık O(N), dolayısıyla, T 3 (n), T 4 (n), T 5 (n), T 6 (n), sırasıyla bir O(N) zaman karakteristiğine sahiptir.

X ekseni boyunca aralıkların değerlerini belirleme şeması Şekil 2'de gösterilmektedir. 2.

Yukarıda sunulan diyagramdan O(N)'nin doğrusal zamana bağımlılığı da görülebilir çünkü Nokta dizisinin değerlerinin tüm koordinat seti, değerlerin belirlenmesinde rol oynar. Y ekseni boyunca aralıkların değerlerini belirleme şeması benzer bir yapıya ve zaman özelliklerine sahiptir, bu nedenle T7 (n) ve T8 (n) için zamana bağımlılık O(N) şeklindedir.

İlk nokta dizisi için kutup açısı değerlerini belirleme şeması Şekil 2'de gösterilmektedir. 3.

Sahte kod olarak bu şemaşöyle görünecek:

puanlar için puanlar için

# Nokta 1. ve 4. çeyrekler arasındaki koordinat ekseninde bulunuyorsa

Eğer nokta.x ≥ Xc ve nokta.y = Yc ise

Nokta.açı ← 0

# Eğer konu kesinlikle ilk çeyreğe aitse

Aksi halde nokta.x > Xc ve nokta.y > Yc ise

Temel ← |point.x – Xc|

Nokta.açı ← yay(dik/temel)

# Nokta 1. ve 2. çeyrekler arasındaki koordinat ekseninde bulunuyorsa

Aksi halde nokta.x = Xc ve nokta.y > Yc ise

Nokta.açı ← p/2

# Eğer konu kesinlikle ikinci çeyreğe aitse

Aksi takdirde point.x< Xc and point.y >Yc

Temel ← |point.y – Yc|

Nokta.açı ← p/2 + arktg(dik/temel)

# Nokta II ve III çeyrekleri arasındaki koordinat ekseninde bulunuyorsa

Eğer nokta.x< Xc and point.y = Yc

Nokta.açı ← p

# Eğer konu kesinlikle üçüncü çeyreğe aitse

Eğer nokta.x< Xc and point.y >Yc

Temel ← |point.x – Xc|

Dik ← |nokta.y – Yc|

Nokta.açı ← p + arktan(dik/temel)

# Nokta III ve IV çeyrekleri arasındaki koordinat ekseninde bulunuyorsa

Eğer nokta.x = Xc ve nokta.y ise< Yc

Nokta.açı ← 3p/2

# Eğer konu kesinlikle IV çeyrekte ise

Eğer nokta.x > Xc ve nokta.y ise< Yc

Temel ← |point.y – Yc|

Dik ← |nokta.x – Xc|

Nokta.açı ← 3p/2 + arktg(dik/temel)

Açıkçası, orijinal nokta koordinat dizisi için kutup açısı değerlerini belirlemek için zaman karakteristiği O(N) biçimindedir, dolayısıyla T 9 (n) = O(N).

'de gösterildiği gibi, birleştirme sıralamasının zamana bağımlılığı O(N) biçimindedir, dolayısıyla T10(n) = O(NlnN).

Orijinal dizinin noktalarını birleştiren bir kenar oluşturma diyagramı Şekil 2'de gösterilmektedir. 4.

Yukarıdaki devrenin sözde kodu şöyle görünecektir:

i ← 0 için uzunluk (Puan) – 1

Draw(Xc,Yc,Noktalar[i].x, Noktalar[i].y)

Zaman tepkisi de doğrusaldır, dolayısıyla T11(n) = O(N).

Ortaya çıkan üçgenlemenin dışbükey olana kadar tamamlanması Graham'ın algoritmasına göre gerçekleştirilir. Prosedürün giriş verileri Q noktaları kümesidir; burada |Q|≥3. İçeriğini değiştirmeden S yığınının en üstündeki noktayı döndüren Top(S) fonksiyonunu çağırır. Ek olarak, S yığınında en üst noktanın bir konum altında yer alan bir noktayı döndüren NextToTop(S) işlevi de kullanılır; S yığını değişmeden kalır.

Graham(S)

p 0, Q kümesinden minimum koordinatlı bir nokta olsun.

‹p 1 , p 2 ,...,p N › – Q kümesinin noktaları sıralanmış olsun

Artan kutup açısına göre.

İt(p 0 ,S)

İt(p 1 ,S)

i=2'den N'ye kadar

NextToTop(S), Top(S) ve pi noktalarının oluşturduğu açı,

Sola olmayan bir dönüş oluşturun

# bunların oluşturduğu kırık bir çizgi boyunca hareket ederken

# nokta, hareket düz veya sağa doğru gerçekleştirilir

Pop(S) Yap

İtme(pi,S)

dönüş S

Graham prosedürünün çalışma süresi O(NlnN), burada N=uzunluk(Q). While döngüsünün O(N) zaman alacağını ve kutup açılarını sıralamanın O(NlnN) zaman alacağını göstermek kolaydır, bu Graham prosedürünün genel asimptotik davranışını ima eder, dolayısıyla T 12 (n) = O (NlnN).

Delaunay koşulunu karşılayan bir üçgenlemenin yeniden inşasının zaman karakteristiği, 'de gösterildiği gibi, O(N) doğrusal bir bağımlılığa sahiptir, dolayısıyla T13(n) = O(N).

Bulunan tüm zaman özelliklerini ifade (3)'te değiştirirsek, ortaya çıkan zamana bağımlılık şöyle görünecektir:

T(n) = c 1 +c 2 +O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+ +O(NlnN )+O(N)+O(NlnN)+O(N)

T(n) = O(NlnN)

Yürütülen teorik analiz Değiştirilmiş Delaunay üçgenleme algoritmasının zaman özellikleri, önerilen algoritmanın verimliliğini ve yüksek performansını doğrulamaktadır.

Sonuçlar

Pratik olarak popüler Delaunay üçgenleme algoritmalarının karşılaştırmalı analizinin bir sonucu olarak, dikkate alınan yöntemlerin, dinamik üç boyutlu nesnelerin önceden gerçek zamanlı olarak oluşturulmasına yönelik gereksinimleri karşılamadığı gösterilmiştir. belli bir dereceye kadar ayrıntıdır ve bu nedenle bunların değiştirilmesine pratik bir ihtiyaç vardır. Fan iki geçişli Delaunay üçgenleme algoritmasının bir modifikasyonu önerilmiştir, işlevsel özellik bu, nokta dizisini X ve Y eksenleri boyunca alt kümelere bölerek üçgenleme noktalarının koordinat dizisinin kütle merkezi değerlerini hesaplamaktır. Değiştirilmiş Delaunay üçgenleme algoritmasının zaman özelliklerinin analizi gerçekleştirilmiştir. dışarı. Belirtilen hesaplamalar Kütle merkezi noktasının koordinatlarını belirlerken çok çeşitli noktalarda performansı önemli ölçüde artırmanıza ve veri taşmasını ve dolayısıyla yazılım uygulamasındaki hataları önlemenize olanak tanır.

1. Knut D.E. Programlama sanatı. Cilt 1. Temel algoritmalar. – M.: Williams, 2008. – 680 s.
2. Knut D.E. Programlama sanatı. Cilt 3. Sıralama ve arama. – M.: Williams, 2008. – 800 s.
3. Mandelbrot B. Doğanın fraktal geometrisi. – M.: Bilgisayar Araştırma Enstitüsü, 2002. – 656 s.
4. Skvortsov A.V. Delaunay üçgenlemesi ve uygulaması. – Tomsk: Yayınevi Tomsk Üniversitesi, 2002. – 128 s.
5. Skvortsov A.V. Doğrusal zamanda Delaunay üçgenlemesinin inşası. – Tomsk: Tomsk Üniversitesi Yayınevi, 1999. – S.120-126.
6. Skvortsov A.V., Mirza N.S. Üçgenlemeyi oluşturmak ve analiz etmek için algoritmalar. – Tomsk: Tomsk Üniversitesi Yayınevi, 2006. – 168 s.
7. Thomas H. Corman, Charles I. Leiseron, Ronald L. Rivest, Clifford Stein. Algoritmalar: yapı ve analiz, 3. baskı: Çev. İngilizce'den – M.: Williams, 2013. – 1328 s.
8. Shaidurov V.V. Çok ızgaralı sonlu elemanlar yöntemleri. – M.: Nauka, 1989. – 288 s.
9. Sturges H. (1926). Sınıf aralığı seçimi. J. Amer. Devletçi. Doç., 21, 65-66.

Anahtar kelimeler: sanal gerçeklik, belirli bir nokta dizisi üzerinde üçgenleme, Delaunay üçgenlemesi, dinamik üç boyutlu nesnelerin inşası.

Değiştirilmiş Delaunay'ın üçgenleme algoritması

Teplov A.A., Lisans, MSTU Bauman, "Yazılım ve Bilgi Teknolojileri" Bölümü, Moskova, [e-posta korumalı]

Maykov K.A., Teknik Bilimler Doktoru, Profesör, MSTU Bauman, "Yazılım ve Bilgi Teknolojileri" Bölümü, Moskova, [e-posta korumalı]

Soyut: Bu makalede, Delaunay'ın yüksek performans ve düşük kaynak tüketimi ile üçgenlemesinin neredeyse popüler yöntemlerinin karşılaştırmalı analizinin sonuçları açıklanmaktadır. Dinamik 3 boyutlu nesnelerin gerçek zamanlı olarak belirli bir ayrıntı düzeyiyle oluşturulması amacıyla daha fazla modernizasyon için yöntemin seçimi haklıdır. Fiberli iki geçişli Delaunay üçgenleme algoritmasının ana aşamalarından biri değiştirildi. Algoritmanın önerisi var için Dağıtım yoğunluğuna uygun olarak üçgenlemenin hücre dizisinin aralıklı bölümlenmesi, donanım uygulamasındaki hataların önlenmesine olanak tanır.

Anahtar Kelimeler: sanal gerçeklik, belirli bir hücre dizisinde üçgenleme, Delaunay üçgenlemesi, dinamik 3 boyutlu nesnelerin oluşturulması.

Uzamsal Delaunay üçgenlemesi

Üst üste binmeyen üçgenlerden oluşan bir ağ oluşturma görevi temel görevlerden biridir. hesaplamalı geometri ve yaygın olarak kullanılmaktadır makine grafikleri Ve coğrafi bilgi sistemleri yüzey modelleme ve mekansal problemlerin çözümü için.

Üst üste binmeyen üçgenlerden oluşan bir ağ oluşturma sorunu ilk kez 1934'te çalışmada ortaya atıldı. Sovyet matematikçiİlgili koşulları formüle eden B. N. Delaunay.

Matematikte, belirli noktalardan üçgenleme oluşturma görevi, bunları çiftler halinde kesişmeyen bölümlerle birleştirerek bir üçgen ağı oluşturma görevidir. Ana elemanları şunlardır (Şekil 5.3): düğümler (üçgenin köşeleri), kenarlar (yanlar) ve yüzler (üçgenlerin kendileri). Oluşturulan üçgenleme dışbükey (modelleme alanını kaplayan minimal bir çokgen ise), dışbükey olmayan (üçgenleme dışbükey değilse) ve optimal (tüm kenarların uzunluklarının toplamı minimum ise) olabilir.

Bu tür üçgenlerden oluşan bir ağ, belirli koşulları karşılıyorsa Delaunay üçgenlemesi olarak adlandırılır:

Orijinal noktaların hiçbiri herhangi bir üçgenin çevrelediği dairenin içine girmez (Şekil 5.3);

Üçgenleme dışbükeydir ve yukarıda formüle edilen Delaunay koşulunu karşılar;

Tüm üçgenlerin minimum açılarının toplamı, olası tüm üçgenlemelerin maksimumudur;

Üçgenlerin etrafında tanımlanan dairelerin yarıçaplarının toplamı, tüm olası üçgenlemeler arasında minimumdur.

Dairesel olarak adlandırılan bir Delaunay üçgenlemesi oluşturmak için yukarıdaki kriterlerden ilki ana kriterlerden biridir ve ortak yüzlere sahip herhangi bir üçgen çifti için kontrol edilir. Kriterin matematiksel yorumu Şekil 2'den gelmektedir. 5.3:

(5.2)

En popülerlerden biri olan Delaunay üçgenlemesini oluşturmanın birçok yolu vardır. son zamanlardaÜçgenleme ağı oluşturma yöntemleri. Birçok CBS sisteminde kabartma modeller oluşturmak için kullanılır.

İki boyutlu uzaya uygulandığında şu şekilde formüle edilir: Birbiriyle bağlantılı, örtüşmeyen üçgenlerden oluşan bir sistem, eğer köşelerden hiçbiri oluşturulan üçgenlerin etrafında tanımlanan dairelerin herhangi birinin içine girmiyorsa, en küçük çevreye sahiptir (Şekil 5.4).

Pirinç. 5.4. Delaunay üçgenlemesi

Bu, böyle bir üçgenlemeye sahip ortaya çıkan üçgenlerin eşkenar üçgenlere mümkün olduğu kadar yakın olduğu ve ortaya çıkan üçgenlerin karşı tepe noktasından her bir tarafının, karşılık gelen yarım düzlemin tüm olası noktalarından maksimum açıda görülebileceği anlamına gelir. Bu tam olarak kenarlar boyunca genellikle yapılan en uygun üçgenlemedir. doğrusal enterpolasyon izolinler oluşturmak.

Delaunay üçgenlemesini oluşturmaya yönelik birçok algoritma aşağıdaki teoremi kullanır.

Teorem 1. Delaunay üçgenlemesi, komşu nokta çiftlerini sırayla yeniden düzenleyerek aynı nokta sistemini kullanan diğer herhangi bir üçgenlemeden elde edilebilir. ABC üçgenleri ve Delaunay koşulunu sağlamayan BCD, ABD ve ACD üçgen çiftlerine bölünür (Şekil 5.5).

Pirinç. 5.5.. Delaunay koşulunu sağlamayan üçgenlerin yeniden oluşturulması

Bu yeniden inşa işlemine genellikle çevirme denir. Bu teoremönce bir miktar üçgenleme oluşturarak ve ardından bunu Delaunay koşulu anlamında art arda geliştirerek bir Delaunay üçgenlemesini sırayla oluşturmanıza olanak tanır. Bitişik üçgen çiftleri için Delaunay koşulunu kontrol ederken, tanımı doğrudan kullanabilirsiniz, ancak bazen yukarıda listelenen koşullara dayalı olarak başka yöntemler de kullanılır.

Bu koşullarda, hangisinin bir Delaunay üçgenlemesinin elde edilebileceğini optimize ederek tüm üçgenlemenin toplam özelliği (minimum açıların toplamı veya yarıçapların toplamı) ortaya çıkar.

Yukarıda bahsedildiği gibi üçgenleme yapılırken gerçekleştirilen en önemli işlemlerden biri Delaunay koşulunun kontrol edilmesidir. Verilen çiftlerüçgenler. Delaunay üçgenlemesinin tanımına ve ilgili koşullara bağlı olarak, pratikte genellikle birkaç doğrulama yöntemi kullanılır:

– çevrel çember denklemini kontrol edin;

– önceden hesaplanmış çevrelenmiş bir daire ile kontrol edin;

– zıt açıların toplamının kontrol edilmesi;

– Zıt açıların toplamının değiştirilmiş kontrolü.

Birçok sistem testi önceden hesaplanmış bir çevre çemberi ile gerçekleştirir. Önceden hesaplanmış daireler aracılığıyla doğrulama algoritmasının ana fikri, oluşturulan her üçgen için çevresinde açıklanan dairenin merkezini ve yarıçapını önceden hesaplamaktır; ardından Delaunay koşulunun kontrol edilmesi, merkeze olan mesafenin hesaplanmasına indirgenecektir. bu dairenin hesaplanması ve sonucun yarıçapla karşılaştırılması. Etrafında tanımlanan dairenin merkezi ve yarıçapı r , , , r 2 = (b 2 + c 2 - 4аd)/4а 2 olarak bulunabilir; burada değerler a, b, c, d formüller (5.3) ile belirlenir

(5.3)

Bu çemberin denkleminin başka bir girdisi:

(5.5.)

(5.6)

O zaman Delaunay koşulu ancak diğer herhangi bir üçgenleme noktası için şu şekilde karşılanacaktır:

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

Şu anda Delaunay üçgenlemesini oluşturmak için birçok algoritma vardır. çoğu bilinen algoritmalar Delaunay üçgenlemesinin tanımını şu şekilde kullanın: ikincil semptomüçgenleme. Bu nedenle bu tür algoritmalarda aşağıdaki zayıf noktalara dikkat edilir:

– algoritmalar sürekli olarak hesaplanan trigonometrik fonksiyonları kullanır ve bu da süreci önemli ölçüde yavaşlatır;

– noktalar ile taban parçası arasındaki ilişkiyi incelerken çok küçük açılar ortaya çıkar ve trigonometrik fonksiyonlar Bilgisayardaki veri temsillerinin sınırlı doğruluğu nedeniyle sürekli olarak sıranın kaybolması ve 0'a bölünmesi tehlikesi vardır; bu durum sürekli ek işlem gerektirir.

En ünlü yazılım ürünleriÜçgen oluşturmanın temel ilkesi olarak boş top teoremini kullanarak Delaunay üçgenlemesini oluşturun. Algoritma şuna benzer:

– noktaların tamamı üçgenlere bölünmüştür, yani. üç noktanın kombinasyonları oluşturulur;

– her kombinasyon için çevrelenen daire ve merkezinin koordinatları bulunur;

– mevcut kombinasyonun çemberi içinde tek bir nokta bile kalmamışsa, o zaman bu kombinasyon bir üçgendir - Delaunay üçgenlemesinin bir parçasıdır.

Bu algoritmanın avantajları şunları içerir:

– inşaat sürecini yavaşlatmayan trigonometrik fonksiyonların kullanılmaması;

- herhangi bir ön inşaat olmaksızın Delaunay üçgenlemesinin doğrudan inşası;

– tüm hesaplamaların ve dönüşümlerin basitliği;

– sonuç olarak üçgenleme ızgarası tek tek çizgiler yerine birçok üçgenle temsil edilir.

Bu şekilde oluşturulan üçgenleme geometrik temel izolinler oluşturmak.

Delaunay üçgenlemesini oluşturmaya yönelik algoritmalar, kullanılan girdi verilerinin yapısına, hesaplama işlemlerinin hacmine, ilk öncüllere vb. göre farklılık gösteren bir dizi gruba ayrılabilir. Bunlardan bazılarını ele alalım.

Birleştirme algoritmaları, bir dizi kaynak noktasını alt kümelere bölmeyi, bunların her biri üzerinde bir üçgenleme oluşturmayı ve ardından bunları tek bir ağda birleştirmeyi içerir. Bu algoritmalardan birinin özü aşağıdakilere inmektedir.

Başlangıç ​​noktaları kümesi bölünmüştür dikey çizgiler iki veya daha fazla parçaya bölünür, ardından her biri yatay ve dikey çizgilerle yaklaşık olarak eşit parçalara bölünür. Sonuç olarak, başlangıç ​​noktalarının tüm alanı, boyunca bir veya iki üçgenin oluşturulduğu üç veya dört noktadan oluşan ilkellere bölünür (Şekil 2.4).

Bu üçgenlerin tek bir ağda birleştirilmesi iki taban çizgisi oluşturularak yapılır. (P 0 P 1 ve P 2 P 3, pirinç. 5.7.a), merkezli değişken yarıçaplı daireler çizme dik açıortay taban çizgisine (Şekil 5.7, b), daireye düşen bir düğümü arayın (nokta A, pirinç. 5.7. c) ve yeni bir üçgenin inşası (P 0 P 1 A). Bu durumda mevcut bir üçgenin silinmesi gerekebilir (örneğin, P 0 AB).

Yinelemeli algoritmalar, Delaunay kriterlerine uygun olarak eş zamanlı iyileştirme ve yeniden yapılandırma ile kısmen oluşturulmuş bir üçgenlemeye noktaların sıralı olarak eklenmesi fikrine dayanmaktadır. İÇİNDE genel görünüm birkaç adım içerirler ve ilk üç başlangıç ​​noktası üzerinde bir üçgen oluşturmaya ve bir sonraki noktayı yerleştirmek için çeşitli seçenekleri keşfetmeye kadar uzanırlar. Özellikle modelleme alanının sınırlarının dışına çıkması, mevcut bir düğüm veya kenara düşmesi, oluşturulmuş bir üçgenin içine düşmesi vb. seçenekler dikkate alınır. Bu seçeneklerin her biri belirli bir işlemin gerçekleştirilmesini içerir: bir kenarı ikiye bölmek, yüzleri ikiye bölmek üç vb.; bundan sonra ortaya çıkan üçgenlerin Delaunay koşuluna uygunluğu ve gerekli yeniden yapılandırmalar kontrol edilir.

İki geçişli algoritmalar öncelikle Delaunay koşullarını göz ardı ederek bir çeşit üçgenleme oluşturmayı ve daha sonra bu koşullara uygun olarak yeniden yapılandırmayı içerir. Algoritmanın uygulanmasına bir örnek Şekil 2'de gösterilmektedir. 5.8.

Oluşturulan kabartma modelini gerçek olana yaklaştırmak için, doğrusal ve alansalını hesaba katan ve gösteren ek unsurlar eklenmiştir. yapısal elemanlar. Bu tür ek unsurlar, topografyada yaygın olarak kullanılan ve "kabartma iskeletini" tanımlayan yapısal çizgilerdir: su havzaları, talvegler, sırtlar, uçurumlar, çıkıntılar, göller, vadiler, kıyı şeridi, sınırlar yapay yapılar ve diğerleri, bunların bütünlüğü Delaunay üçgenlemesinin çerçevesini oluşturuyor. Bu kesme çizgileri, üçgenlerin kenarları olarak üçgenlemeye dahil edilir ve modelleme bu şekilde sağlanır. gerçek unsurlar genel eşitsizliğin arka planına karşı rahatlama dünyanın yüzeyi. Bu tür kenarlara yapısal (sabit, yeniden yapılandırılamaz) denir, diğer üçgenlerin kenarlarıyla kesişmez ve sonradan değişmez.

Kesme çizgilerini hesaba katan bir yüzey modeli oluşturma problemine, eğer kesme çizgileriyle ayrılmayan herhangi bir komşu üçgen çifti için Delaunay koşulları sağlanıyorsa, kısıtlı Delaunay üçgenlemesi adı verilir. Araştırmacılar, en etkili yolun yinelemeli algoritmalar kullanarak böyle bir üçgenleme oluşturmak olduğuna inanıyor.

Delaunay üçgenlemesini oluşturmaya yönelik algoritmalar, düğümlerin koordinatlarının gerçek veya tamsayı temsiliyle uygulanır; bu, işlemenin hızını ve doğruluğunu önemli ölçüde artırabilir, ancak eşleşen düğümlerin aranması ve hariç tutulması sorunlarına yol açar.

TIN modeli, düğümleri hareket ettirerek, yenilerini ekleyerek, mevcut olanları silerek, bir veya birkaç kenarın konumunu değiştirerek, yeni yapısal çizgiler ekleyerek vb. kolayca düzenlenebilir. Bu tür değişiklikler her zaman küçük bir bitişik üçgen grubunu etkiler, yapının yeniden inşa edilmesini gerektirmez. tüm ağda gerçekleştirilir ve imlecin ilgili öğeye yönlendirilmesiyle çevrimiçi olarak gerçekleştirilir.

Doğruluk hakkında:

Karakteristik kabartma elemanlarının (örneğin su havzaları ve talvegler) üzerine kazıklar yerleştirerek boşluklardaki daha küçük elemanları göz ardı ediyoruz. Bu tür üçgen kenarları boyunca kontur çizgileri1 oluştururken, arazinin düzgünsüzlüğüne ve arazinin eğim açısına bağlı olarak bir hata meydana gelir. Örneğin, ortalama hata Rölyef ölçümü, 2 ila 10 derece arasındaki yüzey eğim açılarında kabartma kesitinin 1/3'ünü aşmamalıdır. 0,5 m'lik bir rölyef kesiti ile kaçırılan pürüzlülüğün maksimum değerinin (yani dünya yüzeyinin bitişik kazıklardan geçen düz bir çizgiden sapması) (0,5/3)*cos10°'yi aşmaması gerektiği hesaplanabilir. =0,16 m.

Taşınan toprağın hacminin belirlenmesinin doğruluğu için, rölyef detayının dikkate alınmadan kapladığı alan da önemlidir. Diyelim ki iki çift kazık arasında 20x20 m'lik bir karede silindirik bir dışbükeylik var. maksimum yükseklik 0,15 m. Belirli bir yüzeyi yalnızca iki üçgenle temsil ederken bunu dikkate almamanın yaklaşık 40 m3'lük bir hataya yol açacağını hesaplamak kolaydır. Çok fazla değil, ancak bir tepe üzerinde veya eğimin üst (genellikle dışbükey) kısmında yer alan 1 hektarlık bir arsa için 40 * 25 = 1000 m3 fazla toprak elde edersiniz. Kazıkları iki kat daha sık alırsanız (yani her 10 m'de bir), hata dört kat azalacak ve hektar başına 250 m3'e ulaşacaktır. Bu faktör önceden dikkate alınabilir, çünkü pozitif formlar Düz araziler genellikle dışbükey bir şekle sahipken, negatif olanlar içbükey bir şekle sahiptir. İncelenecek alanın kabartma hakkında yaklaşık verileri varsa, yüzeyin eğrilik yarıçapı ve gerekli kazık yoğunluğu, kontur çizgilerinin veya bireysel yüksekliklerin değerlerinden kolayca hesaplanabilir.

Temel tanımlar ve özellikler

Üçgenleme, iç bölgelerinin tamamı üçgen olan düzlemsel bir grafiktir.

Özellikler:

· Delaunay üçgenlemesi aynı noktalar kümesi için Voronoi diyagramına birebir karşılık gelir.

· Sonuç olarak: eğer aynı çember üzerinde dört nokta bulunmuyorsa, Delaunay üçgenlemesi benzersizdir.

· Delaunay üçgenlemesi, oluşturulan tüm üçgenlerin tüm açıları arasındaki minimum açıyı maksimuma çıkarır, böylece "ince" üçgenlerden kaçınılır.

· Delaunay üçgenlemesi, yazılı kürelerin yarıçaplarının toplamını maksimuma çıkarır.

· Delaunay üçgenlemesi ayrık Dirichlet fonksiyonelini en aza indirir.

· Delaunay üçgenlemesi, minimum ortam küresinin maksimum yarıçapını en aza indirir.

· Düzlemdeki Delaunay üçgenlemesi, tüm olası üçgenlemeler arasında üçgenlerin etrafında tanımlanan dairelerin yarıçaplarının minimum toplamına sahiptir.

Şekil 1. Üçgenleme.

Dışbükey üçgenleme, tüm üçgenleri çevreleyen minimum çokgenin dışbükey olduğu bir üçgenlemedir. Dışbükey olmayan bir üçgenlemeye dışbükey olmayan denir.

Verilen iki boyutlu noktalardan üçgenleme oluşturma problemine bağlantı problemi denir. verilen puanlar kesişmeyen bölümler, böylece bir üçgenleme oluşturulur.

Verilen üçgenleme noktalarından hiçbiri oluşturulmuş herhangi bir üçgenin etrafında çevrelenen dairenin içine girmiyorsa, bir üçgenlemenin Delaunay koşulunu karşıladığı söylenir.

Bir üçgenleme dışbükeyse ve Delaunay koşulunu sağlıyorsa Delaunay üçgenlemesi olarak adlandırılır.

Şekil 2. Delaunay üçgenlemesi.

Delaunay boş top yöntemi. Genel durumda inşaat

Hareket ettireceğimiz boş bir topu sistemin (A) noktalarına değecek şekilde boyutunu değiştirerek kullanalım, ancak her zaman boş kalsın.

O halde boş bir Delaunay topunu (A) nokta sistemine yerleştirelim. Yeterince küçük bir top seçerseniz bu her zaman mümkündür. Topun merkezini yerinde bırakarak yarıçapını artırmaya başlayalım. Bir noktada topun yüzeyi sistemin (A) bir i noktasıyla buluşacaktır. Bu kesinlikle gerçekleşecektir çünkü sistemimizde sonsuz büyüklükte boşluklar yoktur. Boş topun yarıçapını i noktası yüzeyinde kalacak şekilde artırmaya devam edeceğiz. Bunu yapmak için topun merkezini i noktasından hareket ettirmeniz gerekecek. Er ya da geç top yüzeyi ile sistemdeki başka bir noktaya (A) ulaşacaktır.

Şekil 3

Delaunay simpleksleri boşluk veya örtüşme olmadan alanı doldurur.

Herhangi bir simpleksin açıklanan küresi, kendi içinde sistemin diğer noktalarını içermez.

Bu j noktası olsun. Her iki noktayı da yüzeyinde tutarak topumuzun yarıçapını artırmaya devam edelim. Top arttıkça sistemin üçüncü bir noktasına, k noktasına ulaşacaktır. İÇİNDE iki boyutlu durum“boş çemberimiz” şu anda sabitlenecek, yani. Çemberi boş tutarak yarıçapını daha da artırmak imkansız hale gelecektir. Aynı zamanda, belirli bir üçgeni tanımlayan üç noktanın (i, j, k) temel iki boyutlu konfigürasyonunu belirliyoruz; bunun özelliği, çevrel çemberi içinde sistemin (A) başka noktalarının bulunmamasıdır. İÇİNDE üç boyutlu uzay top üç noktayla tanımlanmaz. Yüzeyinde bulunan üç noktayı da koruyarak yarıçapını artırmaya devam edelim. Bu, topun yüzeyi sistemin dördüncü noktası l ile buluşana kadar mümkün olacaktır. Bundan sonra boş topun hareketi ve büyümesi imkansız hale gelecektir. Bulunan dört nokta (i,j,k,l), tetrahedronun köşelerini tanımlar; bu, sınırlandırılmış küresinin içinde sistemin (A) başka hiçbir noktasının bulunmaması ile karakterize edilir. Böyle bir tetrahedron Delaunay simpleks olarak adlandırılır.

Matematikte simpleks denir en basit şekil belirli bir boyuttaki bir uzayda: tetrahedron - üç boyutlu uzayda; üçgen - iki boyutlu. Sistemin aynı düzlemde yer almayan rastgele üç (dört) noktası her zaman belirli bir simpleks tanımlar. Bununla birlikte, yalnızca tanımlanan küresi boşsa Delaunay simpleks olacaktır. Başka bir deyişle, Delaunay basitlikleri, (A) sistemindeki noktaların özel bir üçlü (dörtlü) seçimiyle belirlenir.

Bir Delaunay simpleks oluşturduk, ancak boş topu farklı yerlere yerleştirip aynı prosedürü tekrarlayarak diğerlerini de tanımlayabiliriz. (A) sisteminin tüm Delaunay basitliklerinin kümesinin, alanı örtüşmeler ve boşluklar olmadan doldurduğu belirtilmektedir; uzayın bölünmesini bu sefer tetrahedronlara bölüyor. Bu bölüme denir Delaunay fayans(Şekil 3).

Delaunay üçgenlemesinin uygulanması

Delaunay üçgenlemeleri Öklid uzayında sıklıkla kullanılır. Öklid minimum yayılma ağacının Delaunay üçgenlemesinde yer alması garanti edilir, bu nedenle bazı algoritmalar üçgenlemeyi kullanır. Ayrıca Delaunay üçgenlemesi yoluyla Öklidci gezgin satıcı problemi yaklaşık olarak çözülmüştür.

2 boyutlu enterpolasyonda, Delaunay üçgenlemesi düzlemi mümkün olan en kalın üçgenlere bölerek çok keskin ve geniş açılardan kaçınır. Bu üçgenleri kullanarak örneğin çift doğrusal enterpolasyon oluşturabilirsiniz.

Jeoenformatikte sıklıkla karşılaşılan bir diğer sorun ise şev görünümlerinin oluşturulmasıdır. Burada ana yönlere göre yamaçların hakim yönlerini belirlemek ve yüzeyi belli bir yönün hakim olduğu bölgelere bölmek gerekir. Yüzeyin yatay alanları için poz belirlemenin bir anlamı olmadığından yatay veya hafif eğime sahip alanlar ayrı bir bölgeye tahsis edilir, örneğin<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Şekil 4.

Eğim maruziyetlerini hesaplama problemi genellikle Dünya'nın aydınlatmasını analiz etmek için kullanılır. Bu bağlamda, genellikle Güneş'in mevcut konumunu ek olarak hesaba katmaya ihtiyaç vardır; pozlama, üçgenin normali ile Güneş yönü arasındaki yön olarak hesaplanır.

Böylece her üçgenleme üçgeni belirli bir bölgeye ait olma ilkesine göre sınıflandırılabilmektedir. Bundan sonra bölge seçim algoritmasını çağırmanız yeterli.

Ders yapısı Tanımlar Tanımlar Uygulama alanları Uygulama alanları Delaunay üçgenlemesinin özellikleri Delaunay üçgenlemesinin özellikleri Delaunay üçgenlemesi oluşturma yöntemleri Delaunay üçgenlemesi oluşturma yöntemleri Adım adım giriş yöntemleri Adım adım giriş yöntemleri Adım adım örnekleme yöntemleri Adım adım adım örnekleme yöntemleri Ayrıştırma yöntemleri Ayrıştırma yöntemleri Tarama yöntemleri Tarama yöntemleri İki geçişli yöntemler İki geçişli yöntemler

Üçgenleme Üçgenleme, iç bölgelerinin tamamı üçgen olan düzlemsel bir grafiktir. Üçgenleme, iç bölgelerinin tamamı üçgen olan düzlemsel bir grafiktir. "Üçgenleme" terimi "Üçgenleme" terimi bir grafiktir; grafik; Grafik oluşturma süreci. Grafik oluşturma süreci. Bir S noktaları kümesi için üçgenleme problemi, bir S kümesinin tüm noktalarını bir üçgenleme grafiği elde etmek için ayrık bölümlerle birleştirme sorunudur. Bir S noktaları kümesi için üçgenleme problemi, bir S kümesinin tüm noktalarını bir üçgenleme grafiği elde etmek için ayrık bölümlerle birleştirme sorunudur. Üçgenlemenin tanımı S noktaları kümesi

Optimum üçgenleme, grafiğin tüm kenarlarının uzunluklarının minimum toplamına sahip bir üçgenlemedir. Optimum üçgenleme, grafiğin tüm kenarlarının uzunluklarının minimum toplamına sahip bir üçgenlemedir. ! Popüler fakat çok zaman alan bir problem O(2 n)! Pratikte, optimal üçgenleme için yaklaşımlar (yaklaşımlar) kullanılır: “Açgözlü” üçgenleme O(N 2 *logN) “Açgözlü” üçgenleme O(N 2 *logN) Delaunay üçgenlemesi O(N*logN) Delaunay üçgenlemesi O(N*logN) ) Tanım optimal üçgenleme

Delaunay üçgenlemesi (DT(S)) Delaunay koşulunu karşılayan bir dışbükey üçgenlemedir: Delaunay üçgenlemesi (DT(S)) Delaunay koşulunu karşılayan bir dışbükey üçgenlemedir: grafiğin köşelerinden hiçbiri etrafı çevrelenen dairenin içine girmemelidir üçgenlerinden herhangi biri. Grafiğin köşelerinden hiçbiri, üçgenlerden herhangi birinin çevrelediği dairenin içine girmemelidir. Delaunay üçgenlemesinin tanımı Delaunay koşulu sağlandı Delaunay koşulu sağlanmadı B.N. Delaunay()

Delaunay üçgenlemesinin uygulanması Diğer VG problemlerinde Diğer VG problemlerinde Bir nokta kümesinin minimum yayılması Bir nokta kümesinin minimum yayılması Tampon bölgelerin inşası Tampon bölgelerin inşası Bir Voronoi diyagramının inşası (yakınlık bölgeleri) Bir Voronoi diyagramının inşası (yakınlık) Bölgeler) Maksimum boş daireyi bulma Maksimum boş daireyi bulma vb. vb. CG, GIS, GM'deki CAD uygulamalarında CG, GIS, GM'deki CAD uygulamalarında Yüzeylerin çokgen modelleri Yüzeylerin çokgen modelleri GIS'teki rölyefler, heykeller , endüstriyel modeller, oyun modelleri, CBS'de kabartmalar, heykeller, endüstriyel modeller, oyun modelleri, Modellerin sayısal analizi Modellerin sayısal analizi İzolinler, İzoklinler, FEM. İzolinler, İzoklinler, FEM.

Herhangi bir dışbükey üçgenlemenin özellikleri 1. m'nin iç olduğu n noktalı bir küme için Üçgenleme üçgen sayısı = n + m – 2 Üçgenleme üçgeni sayısı = n + m – 2 Üçgenleme kenarlarının sayısı 3n – 6 Üçgenleme kenarlarının sayısı 3n – 6 Örnek: Noktalar (n) – 13 Noktalar (n) – 13 İç (m) – 4 İç (m) – 4 Üçgenler – 15 = Üçgenler – 15 = Kenarlar – 26 3*13-6 = 33 Kenarlar – 26 3 *13-6 = 33

Delaunay üçgenlemesinin özellikleri 2. Delaunay üçgenlemesi, tüm olası üçgenlemeler arasında tüm üçgenlerin minimum açılarının maksimum toplamına sahiptir. 3. Delaunay üçgenlemesi, tüm olası üçgenlemeler arasında üçgenlerin etrafında tanımlanan dairelerin yarıçaplarının minimum toplamına sahiptir. Delaunay üçgenlemesi Delaunay üçgenlemesi DEĞİL

Delaunay üçgenlemesini oluşturma yöntemleri Adım adım giriş yöntemleri Adım adım giriş yöntemleri Yinelemeli algoritmalar () Yinelemeli algoritmalar () Adım adım örnekleme yöntemleri Adım adım örnekleme yöntemleri Doğrudan (adım adım) oluşturma algoritmalar (3) Doğrudan (adım adım) oluşturma algoritmaları (3) Ayrıştırma yöntemleri Ayrıştırma yöntemleri Birleştirme algoritmaları (2) Birleştirme algoritmaları (2) Tarama yöntemleri Tarama yöntemleri Değişen nokta ekleme sırasına sahip yinelemeli algoritmalar (1.4) ile yinelemeli algoritmalar nokta ekleme sırası değiştirildi (1.4) İki geçişli algoritmalar (4) İki geçişli algoritmalar (4)

Adım adım giriş yöntemleri Yinelemeli algoritmalar () Delaunay üçgenlemesini oluşturmak için yinelemeli algoritmaların genel şeması 1. İlk üç noktada bir üçgen oluşturun 2. S kümesinin geri kalan tüm p i noktaları arasında döngü yapın 3. Noktaya en yakın t j üçgenini bulun Mevcut üçgenlemenin p i'si 4. Eğer p i noktası t j üçgeninin dışındaysa, en yakın kenara üçgenler oluşturun. 5. Eğer p i noktası t j üçgeninin içindeyse, üçgeni üçe bölün. 6. Eğer p i noktası bir kenardaysa, komşu üçgenleri çiftlere bölün. 7. Komşular için Delaunay koşulu ihlal edilirse komşu üçgenleri yeniden oluşturun. Üçgen aramayı hızlandırmaya yönelik seçenekler: Üçgen indeksleme (ağaçlar) – O(log n) Üçgen indeksleme (ağaçlar) – O(log n) Üçgeni önbelleğe alma (mesh) – O(s) Üçgeni önbelleğe alma (mesh) – O(s)

Adım adım örnekleme yöntemleri Doğrudan (adım adım) inşaat algoritmaları (3) Daha önce yapılmış olanı yeniden inşa etmeden gerekli üçgenleri hemen inşa edin. Delaunay üçgenlemesinin doğrudan oluşturulması için genel algoritma şeması İşlenmemiş kenarlardan oluşan bir yığının kullanılması uygundur. 1. Bir dizi S noktasının dışbükey gövdesinin herhangi bir q kenarını bulun. 2. q kenarını işlenmemiş kenarlar yığınına itin. 3. Ham kenar yığını boşalana kadar döngü yapın. 4. Yığındaki v kenarını açın. 5. v kenarı için, Delaunay koşulunu karşılayan bir p noktası bulun (Delaunay komşusu) 6. Eğer Delaunay komşusu p bulunursa, 7. v kenarından p noktasına kadar bir üçgen oluşturun. 8. Yeni üçgenin yeni kenarlarını işlenmemiş kenar yığınının üzerine itin. Delaunay komşu aramasını hızlandırmaya yönelik seçenekler: Bir k-D-ağacı ile noktaları indeksleme – O(log n) Bir k-D-ağacı ile noktaları indeksleme – O(log n) Noktaların hücresel indekslenmesi – O(c) Noktaların hücresel indekslenmesi – O(c) )

Açgözlü Delaunay üçgenleme algoritmasının süreci

Ayrıştırma yöntemleri Birleştirme algoritmaları (2) Alt kümelere bölme, bağımsız işleme, sonuçları birleştirme. Birleştirme algoritmalarının genel şeması 0. S kümesinde 3'ten fazla nokta yoksa doğrudan oluşturun 1. S noktaları kümesini yaklaşık olarak eşit alt kümelere bölün. 1. S noktaları kümesini yaklaşık olarak eşit alt kümelere bölün. 2. Alt kümeler için üçgenlemenin oluşturulması. 2. Alt kümeler için üçgenlemenin oluşturulması. 3. Ortaya çıkan üçgenlemeleri tek bir üçgende birleştirmek. 3. Ortaya çıkan üçgenlemeleri tek bir üçgende birleştirmek. Alt kümelere bölme yöntemleri Dik düz çizgiler Dik düz çizgiler Dışbükey gövdenin çapına göre Dışbükey gövdenin çapına göre Şeritler Şeritler

Birleştirme algoritmaları (2) Üçgenlemeleri birleştirme yöntemleri “Sil ve Oluştur” (inşaat öncesi kontrol) “Sil ve İnşa” (inşaat öncesi kontrol) “İnşa Et ve Yeniden İnşa Et” (inşaat sonrası kontrol) “İnşa Et ve Yeniden İnşa Et” (inşaat sonrası kontrol) “ İnşa et, yeniden inşa et" (inşaat sırasında kontrol et) "İnşa et, yeniden inşa et" (inşaat sırasında kontrol et)

Nokta eklemenin değiştirilmiş sırasına göre yinelemeli yöntemlerin genel şeması 1. Noktaları düzenleyin (olay noktalarının bir listesini oluşturun) 2. Tüm olay noktaları boyunca tarama döngüsü yapın 3. Her pi noktası için, önceki üçgene üçgenler oluşturun. 4. Komşular için Delaunay koşulu ihlal edilirse komşu üçgenleri yeniden oluşturun. Tarama yöntemleri Değiştirilmiş nokta ekleme sırasına sahip yinelemeli algoritmalar (1.4)

Tarama yöntemleri Olay noktalarını sıralama yöntemleri Doğrusal Doğrusal Kutupsal (dairesel, yelpaze şeklinde) Kutupsal (dairesel, yelpaze şeklinde) Şerit Şerit Kare Kare Hilbert eğrisine göre Hilbert eğrisine göre Z koduna göre Z koduna göre Hedefler: Hemen maksimum iyi üçgenler Derhal maksimum sayıda iyi üçgen oluşturun Şerit değiştirme sayısını en aza indirin Şerit değiştirme sayısını en aza indirin

Delaunay üçgenleme yöntemlerinin özet özellikleri Üçgenleme yöntemi Ortalama süre En kötü zaman Zaman sn / t Uygulama kolaylığı. Adım adım giriş yöntemleri Adım adım giriş yöntemleri Yinelemeli algoritmalar () Yinelemeli algoritmalar ()O(n)- O(n 3/2) O(n 2) 1,5-9,2 2-5 Adım adım örnekleme yöntemleri Adım adım örnekleme yöntemleri Doğrudan oluşturma yöntemi (3) Doğrudan oluşturma yöntemi (3) O(n)- O(n 2) O(n 2) -2 Ayrıştırma yöntemleri Ayrıştırma yöntemleri Birleştirme yöntemleri (2) Birleştirme yöntemleri ( 2) O(n)- O(nlogn) O (nlogn)- O(n 2) 2.5-4.52-3 Tarama yöntemleri Tarama yöntemleri Değişen ekleme noktaları sırası ile yinelemeli (1.4) Değişen ekleme noktaları sırası ile yinelemeli ( 1.4)O(n) O(n 2) 1 ,9-5,34-5 İki geçişli yöntemler (4) İki geçişli yöntemler (4) O(n)- O(n 2) O(nlogn)- O (n 2) 2.2-15.41-5 Skvortsov şunları önermektedir: dinamik önbelleğe alma ile yinelemeli algoritma

Bugün neyle ilgili? Delaunay üçgenlemesi hakkında! Tanım Tanım Tanım Uygulama alanları Uygulama alanları Delaunay üçgenlemesinin özellikleri Delaunay üçgenlemesinin özellikleri Delaunay üçgenlemesi oluşturma yöntemleri Delaunay üçgenlemesi oluşturma yöntemleri Adım adım giriş yöntemleri Adım adım giriş yöntemleri Adım adım örnekleme yöntemleri Adım adım -adımlı örnekleme yöntemleri Ayrıştırma yöntemleri Ayrıştırma yöntemleri Tarama yöntemleri Tarama yöntemleri İki geçişli yöntemler İki geçişli yöntemler