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

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ü Şablon:Diller arası bağlantı, 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 π}{3 \sqrt{3}} \approx 2.418$ 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]

\begin{matrix} | \begin{matrix} 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{matrix} | = | \begin{matrix} 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{matrix} | \\ = & | \begin{matrix} 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{matrix} | > 0 \end{matrix}

Ayrıca bakınız

Şablon:Div sütunu

Şablon:Div sütunu-son

Kaynakça

Şablon:Kaynakça

Dış bağlantılar

Hesaplamalı Geometri Algoritmaları Kitaplığı olan CGAL'de Delaunay üçgenlemesi:
- Mariette Yvinec . 2D Üçgenleştirme Şablon:Webarşiv . 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 Şablon:Webarşiv". Wolfram MathWorld. Erişim tarihi: Nisan 2010.
"Poly2Tri: Artımlı kısıtlı Delaunay üçgenlemesi Şablon:Webarşiv. Açık kaynak C ++ uygulaması. Erişim tarihi: 3 Ocak 2021.
"Böl ve Fethet Delaunay nirengi yapısı Şablon:Webarşiv ". Açık kaynak C99 uygulaması. Erişim tarihi: 3 Ocak 2021.
Şablon:Web kaynağı
Şablon:Web kaynağı

[Delaunay1934-1] Şablon:Akademik dergi kaynağı

[2] Şablon:Ansiklopedi kaynağı

[3] Şablon:Akademik dergi kaynağı

[4] Şablon:Akademik dergi kaynağı. As cited by Şablon:Akademik dergi kaynağı

[5] Şablon:Akademik dergi kaynağı

[6] Şablon:Akademik dergi kaynağı

[7] Şablon:Akademik dergi kaynağı

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Delaunay üçgenleme

İçindekiler

Özellikleri

Ayrıca bakınız

Kaynakça

Dış bağlantılar

Gezinti menüsü

Delaunay üçgenleme

Özellikleri

Ayrıca bakınız

Kaynakça

Dış bağlantılar

Gezinti menüsü

Ara