Delaunay üçgenleme
Delaunay üçgenleme (aynı zamanda bir Delone nirengi olarak da bilinir), Matematik ve Hesaplamalı geometride, bir düzlem içindeki farklı izole noktalardan 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 Boris Delaunay'ın adını almıştır.[1]
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.[2]
Özellikleri değiştir
- Nirengi içindeki tüm basitliklerin birleşimi, noktaların dışbükey gövdesidir.
- Delaunay üçgenlemesi O (n⌈d / 2⌉) basitliklerini içerir.[3]
- 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 Poisson sürecine 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.[4]
- 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.[5] 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 paraboloid üzerine izdüşümünün dışbükey gövdesinin 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 yakın komşu grafiği, Delaunay üçgenlemesinin bir alt grafiğidir.
- Delaunay üçgenlemesi bir geometrik anahtardır: Yani düzlemde (d = 2), Delaunay kenarları boyunca iki köşe arasındaki en kısa yol, Öklid mesafesinin katından fazla olamaz.[6]
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:[7]
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cc0ac5434b461663e2279546cae7c1deb787c57)
Ayrıca bakınız değiştir
Kaynakça değiştir
- ^ 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.
- ^ Güdükbay, Uğur; Sinop, Ali Kemal (1995). "Hesaplamaya Dayalı Geometri". Türkiye Bilişim Ansiklopedisi. 5. Ankara: Bilkent Üniversitesi.
- ^ Seidel (1995). "The upper bound theorem for polytopes: an easy proof of its asymptotic version". Computational Geometry dergisi (İngilizce). 5 (2): 115-116. doi:10.1016/0925-7721(95)00013-Y.
- ^ "Interface area, edge length, and number of vertices in crystal aggregates with random nucleation" (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.
- ^ "An O(n2 log n) time algorithm for the minmax angle triangulation" (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.
- ^ "Classes of graphs which approximate the complete Euclidean graph" (İngilizce). 7 (1). 1992: 13-28. doi:10.1007/BF02187821.
- ^ Guibas (1985). "Primitives for the manipulation of general subdivisions and the computation of Voronoi". ACM Transactions on Graphics (İngilizce). 4 (2): 74-123. doi:10.1145/282918.282923.
Dış bağlantılar değiştir
- Hesaplamalı Geometri Algoritmaları Kitaplığı olan CGAL'de Delaunay üçgenlemesi:
- Mariette Yvinec . 2D Üçgenleştirme23 Haziran 2013 tarihinde Wayback Machine sitesinde arşivlendi. . 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 arşivlendi.". Wolfram MathWorld. Erişim tarihi: Nisan 2010.
- "Poly2Tri: Artımlı kısıtlı Delaunay üçgenlemesi 27 Kasım 2020 tarihinde Wayback Machine sitesinde arşivlendi.. 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 arşivlendi. ". 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 arşivlendi (PDF). Erişim tarihi: 3 Ocak 2021.
- "Heyelanların İzlenmesinde Esnek Hesaplama Yöntemleri". Ulusal Tez Merkezi. 19 Ocak 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 3 Ocak 2021.