Delaunay üçgenleme

sağ|küçükresim|280x280pik| Düzlemde çemberlerin gösterildiği bir Delaunay üçgenlemesi 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. 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 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.. As cited by * 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 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ü , 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 \frac{4\pi}{3\sqrt{3}} \approx 2.418 katından fazla olamaz. küçükresim|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: : \begin{align} & \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{align} == Ayrıca bakınız == * Devler Kaldırımı * Kuazi kristal == Kaynakça == == Dış bağlantılar == * Hesaplamalı Geometri Algoritmaları Kitaplığı olan CGAL'de Delaunay üçgenlemesi: ** Mariette Yvinec . 2D Üçgenleştirme . 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 ". Wolfram MathWorld. Erişim tarihi: Nisan 2010. * "Poly2Tri: Artımlı kısıtlı Delaunay üçgenlemesi . Açık kaynak C ++ uygulaması. Erişim tarihi: 3 Ocak 2021. * "Böl ve Fethet Delaunay nirengi yapısı ". Açık kaynak C99 uygulaması. Erişim tarihi: 3 Ocak 2021. * * Kategori:Geometrik algoritmalar Kategori:Nirengi (geometri)