Delaunay üçgenleme

Delaunay üçgenleme (aynı zamanda bir Delone nirengi olarak da bilinir), Matematik ve Hesaplamalı geometride, bir düzlem içindeki farklı oluşan belirli bir P seti nirengi DT(P) p, bir anlamı içinde olduğu şekilde çevrel çember herhangi bir üçgen DT(P). Delaunay üçgenlemeleri, üçgenlemedeki üçgenlerin tüm açılarının minimum açısını maksimize eder; şerit üçgenlerden kaçınma eğilimindedirler. Nirengi, bu konudaki 1934 tarihli çalışması nedeniyle 'ın adını almıştır.

Düzlemde çemberlerin gösterildiği bir Delaunay üçgenlemesi

Hesaplamalı geometride en çok kullanılan yöntemlerden biri Voronoi çizeneği diğeri de Delaunay üçgenlemesidir. Yapay zekâdan günlük hayattaki pek çok problemin çözümünde önemli işlevleri bulunur.

Özellikleri

• Nirengi içindeki tüm basitliklerin birleşimi, noktaların dışbükey gövdesidir.
• Delaunay üçgenlemesi O (n^{⌈d / 2⌉}) basitliklerini içerir.
• Düzlemde (d = 2), dışbükey gövde üzerinde b köşeleri varsa, o zaman noktaların herhangi bir nirengi, en fazla 2n − 2 − b (artı bir dış yüz) üçgenlere sahiptir. (bkz. Euler özelliği)
• Noktalar düzlemde göre sabit yoğunlukta dağıtılırsa, her köşe ortalama olarak altı çevreleyen üçgene sahiptir. Daha genel olarak, d boyutlarındaki aynı süreç için ortalama komşu sayısı sadece d'ye bağlı olarak sabittir.
• Düzlemde, Delaunay üçgenlemesi minimum açıyı maksimize eder. Noktaların diğer herhangi bir nirengi ile karşılaştırıldığında, Delaunay üçgenlemesindeki en küçük açı, en az herhangi bir diğerindeki en küçük açı kadar büyüktür. Bununla birlikte, Delaunay üçgenlemesinin maksimum açıyı minimuma indirmesi gerekmez. Delaunay nirengi, kenarların uzunluğunu da minimuma indirmez.
• Herhangi bir Delaunay üçgenini çevreleyen bir daire, iç kısmında başka herhangi bir giriş noktası içermez.
• Giriş noktalarının ikisinden geçen bir dairenin içinde başka herhangi bir giriş noktası bulunmuyorsa, iki noktayı birleştiren segment, verilen noktaların bir Delaunay üçgenlemesinin bir kenarını oluşturur.
• D-boyutlu uzaylarda bir noktalar kümesinin bir Delaunay üçgenlemesinin her bir üçgeni, noktaların a (d + 1) boyutlu üzerine izdüşümünün bir yüzüne veya tersine karşılık gelir.
• Herhangi bir p noktasına en yakın komşu b, Delaunay üçgenlemesinde bir bp kenarı üzerindedir, çünkü  [en], Delaunay üçgenlemesinin bir alt grafiğidir.
• Delaunay üçgenlemesi bir : Yani düzlemde (d = 2), Delaunay kenarları boyunca iki köşe arasındaki en kısa yol, Öklid mesafesinin ${\displaystyle {\frac {4\pi }{3{\sqrt {3}}}}\approx 2.418}$ katından fazla olamaz.

D noktasının A, B, C noktalarınin çemberi üzerinde yer alıp almadığını tespit etmek için sağlam ve hızlı bir yola ihtiyaç vardır.

Delaunay üçgenlemelerini hesaplamak için birçok algoritma, bir noktanın bir üçgenin çemberinde olup olmadığını tespit etmek için hızlı işlemlere ve üçgenleri ve kenarları depolamak için verimli bir veri yapısı olmasına dayanır. İki boyutta, D noktasının A, B, C çemberinde olup olmadığını tespit etmenin bir yolu determinantını değerlendirmektir:

${\displaystyle {\begin{aligned}&{\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}={\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}^{2}-D_{x}^{2})+(B_{y}^{2}-D_{y}^{2})\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}^{2}-D_{x}^{2})+(C_{y}^{2}-D_{y}^{2})\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}>0\end{aligned}}}$

Ayrıca bakınız

• Devler Kaldırımı
• Kuazi kristal

Kaynakça

1. ^ Delaunay (1934). "Sur la sphère vide". Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles (İngilizce). 6: 793-800. 
2. ^ Güdükbay, Uğur; Sinop, Ali Kemal (1995). "Hesaplamaya Dayalı Geometri". Türkiye Bilişim Ansiklopedisi. 5. Ankara: Bilkent Üniversitesi.  |erişim-tarihi= kullanmak için |url= gerekiyor ()
3. ^ Seidel (1995). "The upper bound theorem for polytopes: an easy proof of its asymptotic version". dergisi (İngilizce). 5 (2): 115-116. doi:10.1016/0925-7721(95)00013-Y. 
4. ^ (PDF). 8. 1953: 270-290. 8 Mart 2017 tarihinde kaynağından (PDF) arşivlendi. . As cited by "Higher-dimensional Voronoĭ diagrams in linear expected time" (İngilizce). 6 (4). 1991: 343-367. doi:10.1007/BF02574694. 
5. ^ (PDF) (İngilizce). 13 (4). 1992: 994-1008. doi:10.1137/0913058. 9 Şubat 2017 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 24 Ekim 2017. 
6. ^ "Classes of graphs which approximate the complete Euclidean graph" (İngilizce). 7 (1). 1992: 13-28. doi:10.1007/BF02187821. 
7. ^ Guibas (1985). "Primitives for the manipulation of general subdivisions and the computation of Voronoi". (İngilizce). 4 (2): 74-123. doi:10.1145/282918.282923. 

Dış bağlantılar

• Hesaplamalı Geometri Algoritmaları Kitaplığı olan CGAL'de Delaunay üçgenlemesi:
  • Mariette Yvinec . 2D Üçgenleştirme23 Haziran 2013 tarihinde Wayback Machine sitesinde . . Erişim tarihi: Nisan 2010.
  • Pion, Sylvain; Teillaud, Monique . 3D Üçgenler . Erişim tarihi: Nisan 2010.
  • Hornus, Samuel; Devillers, Olivier; Jamin, Clément. dD Üçgenler .
  • Hert, Susan; Seel, Michael. dD Konveks Gövdeler ve Delaunay Nirengi . Erişim tarihi: Nisan 2010.
• "Delaunay nirengi 2 Ocak 2021 tarihinde Wayback Machine sitesinde .". Wolfram MathWorld. Erişim tarihi: Nisan 2010.
• "Poly2Tri: Artımlı kısıtlı Delaunay üçgenlemesi 27 Kasım 2020 tarihinde Wayback Machine sitesinde .. Açık kaynak C ++ uygulaması. Erişim tarihi: 3 Ocak 2021.
• "Böl ve Fethet Delaunay nirengi yapısı 12 Kasım 2020 tarihinde Wayback Machine sitesinde . ". Açık kaynak C99 uygulaması. Erişim tarihi: 3 Ocak 2021.
• Şişman, Doç. Dr. Aziz. "Eş Yükseklik Eğrileri" (PDF). 19 Ocak 2021 tarihinde kaynağından (PDF). Erişim tarihi: 3 Ocak 2021. 
• "Heyelanların İzlenmesinde Esnek Hesaplama Yöntemleri". Ulusal Tez Merkezi. 19 Ocak 2021 tarihinde kaynağından . Erişim tarihi: 3 Ocak 2021.