Uzamsal Delaunay üçgenlemesi
Üst üste binmeyen üçgenlerden oluşan bir ağ oluşturma problemi, hesaplamalı geometrideki temel problemlerden biridir ve yüzey modelleme ve mekansal problemlerin çözümü için bilgisayar grafikleri ve coğrafi bilgi sistemlerinde yaygın olarak kullanılmaktadır.
Üst üste binmeyen üçgenlerden oluşan bir ağ oluşturma sorunu ilk kez 1934'te karşılık gelen koşulları formüle eden Sovyet matematikçi B. N. Delone'nin çalışmasında ortaya atıldı.
Matematikte, verilen 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 kendisi). 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 dairelerden 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 olanlara 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, izolinleri oluşturmak için genellikle doğrusal enterpolasyonun yapıldığı kenarlar boyunca optimal üçgenlemedir.
Delaunay üçgenlemesini oluşturmaya yönelik birçok algoritma aşağıdaki teoremi kullanır.
Teorem 1. Delaunay üçgenlemesi, Delaunay koşulunu sağlamayan komşu ABC ve BCD üçgen çiftlerinin ABD ve ACD üçgen çiftleri halinde sırayla yeniden düzenlenmesiyle aynı nokta sistemini kullanan diğer herhangi bir üçgenlemeden elde edilebilir (Ş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şturularak ve daha sonra Delaunay koşulu anlamında art arda geliştirilerek Delaunay üçgenlemesinin sırayla oluşturulmasına izin verir. 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, bunlardan biri kritik operasyonlarÜçgenleme oluşturulurken uygulanan yöntem, verilen üçgen çiftleri için Delaunay koşulunu kontrol etmektir. Delaunay üçgenlemesinin tanımına ve ilgili koşullara bağlı olarak, pratikte genellikle birkaç doğrulama yöntemi kullanılır:
– çevrel çember denkleminin kontrol edilmesi;
– ö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 tanımlanan dairenin merkezini ve yarıçapını önceden hesaplamaktır; bundan sonra 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 halde 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. Tanınmış algoritmaların çoğu, Delaunay üçgenleme tanımını ikincil üçgenleme özelliği olarak kullanır. Bu nedenle, bu tür algoritmalarda aşağıdaki zayıflıklar dikkat çekmektedir:
– 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 ve 0'a bölümün kaybolma tehlikesi vardır; bu durum sürekli ek işlem gerektirir.
En iyi bilinen yazılım ürünleri, üçgen oluşturmanın ana, temel ilkesi olarak boş top teoremini kullanarak Delaunay üçgenlemesini oluşturur. Algoritma şuna benzer:
– noktaların tamamı üçgenlere bölünmüştür; üç 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, izolinlerin oluşturulmasının geometrik temelidir.
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.
Bir dizi başlangıç noktası dikey çizgilerle 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ı, 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), taban çizgisine dik açıortay üzerinde ortalanmış değişken yarıçaplı daireler çizerek (Şekil 5.7, b), daireye düşen bir düğümü arayarak (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ırayla eklenmesi fikrine dayanmaktadır. İÇİNDE Genel görünüm birkaç adım içerirler ve ilk üçte bir üçgen oluşturmaya kadar giderler Başlangıç noktaları ve bir sonraki noktayı yerleştirmek için çeşitli seçenekleri araştırmak. Ö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 rölyef modelini gerçeğe yaklaştırmak için, doğrusal ve alansal yapısal elemanlarının dikkate alınmasını ve görüntülenmesini sağlamak için içine ek unsurlar eklenmiştir. 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ı şeritleri, yapay yapıların sınırları vb. Delaunay üçgenlemesinin çerçevesi. Bu yapısal çizgiler, üçgenlerin kenarları olarak üçgenlemeye dahil edilir; bu, gerçek kabartma elemanlarının, dünya yüzeyinin genel düzgünsüzlüğünün arka planına karşı modellenmesini sağlar. 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 üçgenlemesinin ek elemanları içeren bir parçası Şekil 2'de gösterilmektedir. Şekil 5.9'da düğümler, kenarlar, kenarlar ve yapısal çizgiler sağda, arazinin yapısal çizgileri (sahil şeritleri, dağ geçidi kenarları vb.) ve bilinen işaretlere sahip noktalar ise solda gösterilmektedir.
Delaunay üçgenlemesini oluşturmaya yönelik algoritmalar, düğümlerin koordinatlarının gerçek veya tam sayı 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, kabartmayı ölçmedeki ortalama hata, 2 ila 10 derecelik yüzey eğim açılarında kabartma kesitinin 1/3'ünü geçmemelidir. 0,5 m'lik bir rölyef kesiti ile gözden kaçırılan pürüzlülüğün maksimum değerinin (yani zemin yüzeyinin bitişik kazıklardan geçen düz ç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, hesaplanmayan rölyef detayının kapladığı alan da önemlidir. Diyelim ki iki çift kazık arasında 20x20 m'lik bir karede maksimum yüksekliği 0,15 m olan silindirik bir dışbükeylik var, bu yüzeyi sadece iki üçgenle temsil ederken bunu dikkate almamanın bir sonuç doğuracağını hesaplamak kolaydır. yaklaşık 40 m3 hata. Ç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. Düz kabartmanın pozitif formları genellikle dışbükey bir şekle sahip olduğundan, negatif formlar içbükey bir şekle sahip olduğundan, bu faktör önceden dikkate alınabilir. İ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 (A) nokta sistemine yerleştirelim. boş top Delaunay. 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.
Şek. 3
Delaunay simpleksleri boşluk veya örtüşme olmaksızın 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ı arttırmaya devam edelim. Top arttıkça sistemin üçüncü bir noktasına, k noktasına ulaşacaktır. İki boyutlu durumda “boş dairemiz” şu anda sabit olacaktır, 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 olmamasıdır. Üç boyutlu uzayda 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, bir simpleks, belirli bir boyuttaki bir uzaydaki en basit şekildir: bir 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(Şek. 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ğimli 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.
Üçgenleme, modellenmiş bir nesnenin yüzeyinin, belirli bir belirli değeri (6) aşmayan bir mesafede aralıklı üçgen plakalarla yaklaştırılmasıdır. Tüm üçgen plakalar birbirine birleştirilmelidir. Üstleri yüzeyde yatıyor. Bir dizi üçgen plakayla çalışmak genel bir yüzeyden daha kolaydır. Üçgen plakalara üçgen diyeceğiz. Bir üçgen için, uzayda belirli bir noktaya veya belirli bir çizgiyle kesişme noktasına olan mesafe hızlı bir şekilde hesaplanır. Geometrik modelin görsel olarak algılanması için yüzlerin üçgenlenmesi yapılarak üçgenlerin kenarları gözün kıvrımları fark edemeyeceği şekilde seçilmiştir.
Geometrik nesneleri parametrik yüzey düzlemleri üzerinde üçgenlerle görüntülerken, uzaydaki bir nokta dizisi ve bu noktalardaki vücut yüzlerinin bir dizi normali hesaplanarak gövde yüzlerinin uzaysal bir üçgenlenmesi oluşturulmalıdır. iki boyutlu noktalar: Gövdeleri hızlı bir şekilde görüntülemek için yüzleri, üzerine inşa edilmiş üçgen plakalarla yaklaşık olarak hesaplanır. Vücudun yüzleriyle etkileşime giren ışık ışınlarının davranışını belirlemek için normal noktalar gerekir. Önceki bölümlerdeki ve bu bölümdeki ton çizimleri üçgenleme kullanılarak yapılmıştır.
Yüzey üçgenlemenin bir sonucu olarak, parametrik bir düzlem üzerinde iki boyutlu noktalardan oluşan bir diziye ve ilk bahsedilen dizideki nokta sayıları olan bir tamsayı üçlü dizisine sahip olmak istiyoruz. Böylece parametre dizisinde her üçgen köşelerinin üç sayısıyla temsil edilecektir. Parametrik alanın her iki boyutlu noktası için, yüzey üzerindeki uzaysal bir nokta ve bunun içindeki yüzey normali hesaplanabilir. Uzamsal noktalar ve normaller, 2 boyutlu nokta dizisine benzer dizilerde saklanabilir.
Bazı üçgenleme yöntemlerine bakalım. Düz yüzeyler için yüzeyin sınır noktalarında üçgenler oluşturulan ve parametrik bölge içinde nokta aramaya gerek olmayan, uygun maliyetli üçgenleme yöntemleri mevcuttur.
Delaunay üçgenlemesi.
Düzlemdeki bazı alanları düşünelim. Sınırı boyunca hareket ederken yalnızca bir yöne (yalnızca sola veya yalnızca sağa) dönmeniz gerekiyorsa, bir alanı dışbükey olarak adlandıracağız. Delaunay algoritması dışbükey düzlemsel bölgeleri üçgenlemek için kullanılabilir. Bu algoritmayı serbest biçimli yüzeyleri üçgenlemek için doğrudan uygulayamayacağız, ancak üçgen oluşturmak için onun yöntemini kullanacağız.
Pirinç. 9.7.1. İçinde belirli noktalar bulunan dışbükey bölge
Kapalı bir kesikli çizgiyle sınırlanan iki boyutlu dışbükey bir bölge ve bu bölgenin içindeki bir dizi nokta verilsin (Şekil 9.7.1).
Belirtilen alanı, köşeleri alan içinde verilen noktalar ve onu sınırlayan kesikli çizginin köşeleri olan üçgenlere bölmek gerekir. Üçgenler üst üste gelmemelidir ve kenarları yalnızca köşelerde kesişebilir.
Belirli bir alanı doldurmak için birkaç farklı üçgen seti oluşturulabilir. Her durumda üçgen sayısı eşittir; burada K sınırlayıcı sürekli çizginin köşe sayısıdır, I ise bölge içindeki belirli noktaların sayısıdır.
Pirinç. 9.7.2. Delaunay algoritmasının üçüncü noktasının seçilmesi
Bir bölgenin üçgenlemesi, her üçgenin etrafında tanımlanan dairenin içinde başka üçgenlerin köşeleri yoksa Delaunay üçgenlemesi olacaktır. Delaunay üçgenlemesi mümkün olduğunca eşkenar üçgenlere yakın üçgenler oluşturur (makul olmayan şekilde uzatılmış üçgenlerin oluşturulmasına izin vermez).
Dengeli denilebilir. Aynı daire üzerinde dört köşe bulunmuyorsa Delaunay üçgenlemesi benzersiz olacaktır.
Delaunay üçgenlemesini ele alalım. Bölgeyi sınırlayan çoklu çizginin köşelerine ve bölge içinde verilen noktalara üçgenlemenin köşeleri adını vereceğiz. Üçgenlerin kenarlarına kenar diyeceğiz. Kenarlar arasından, sınır kenarları diyeceğimiz sınırlayıcı sürekli çizginin bölümlerini seçiyoruz. Tüm sınır kenarlarını, dışbükey bölge her kenarın solunda kalacak şekilde yönlendirelim. Şekil 2'de gösterilen, tarafı AB sınır kenarı olan bir üçgen inşa etmek gerekli olsun. 9.7.2.
A, B köşeleri ve onlarla aynı çizgide yer almayan herhangi bir köşe boyunca bir daire çizilebilir. Üçgenin üçüncü köşesi olarak, V tepe noktasını seçiyoruz, karşılık gelen daire, V noktasının bulunduğu AB doğru parçasına göre aynı tarafta başka köşeler içermiyor. Bir sınır kenarı için, genel durumda, böyle bir köşe olabilir bulunan. Biz buna en yakın olanı diyeceğiz. A, B ve V noktalarından geçen bir dairenin merkezi, AB, BV ve VA doğru parçalarının orta noktalarına dik olanların kesişme noktasında yer alır. Çemberin merkezinin konumu, AB kenarına dik, eşit uzunlukta ve AB kenarının ortasından geçen MN segmentinin t parametresi ile karakterize edilecektir.
Pirinç. 9.7.3. Delaunay üçgenleme süreci
AB segmentinin solundaki tüm köşeler için en yakın köşe, en küçük t parametresine sahiptir. En yakın köşeye karşılık gelen daire, AB doğru parçasının solunda başka köşeler içermez. A, B ve V köşelerinin sırasıyla iki boyutlu yarıçap vektörleriyle tanımlanmasına izin verin. AB ve BV segmentlerinin orta noktalarının yarıçap vektörleri eşit olacaktır
A, B ve V noktalarından geçen dairenin merkezinin üzerindeki konumuna karşılık gelen çizginin t parametresinin değeri şuna eşittir:
AB segmentinin soluna en yakın tepe noktası için t parametresi minimum değere sahiptir.
Tüm sınır kenarlarını, üçgenlenecek alan her birinin solunda kalacak şekilde yönlendirelim. Herhangi bir sınır kenarından üçgen oluşturmaya başlıyoruz. Karşılık gelen çemberi başka köşeler içermeyen en yakın köşeyi bulalım. AB sınır kenarı için en yakın V köşesini bulalım, sonra bir ABV üçgeni oluşturup AB kenarını aktif olmayan kategorisine aktarıyoruz. Üçgenleme algoritmasına katılmayan aktif olmayan kenar ve köşeleri çağıracağız. Sınır kenarları arasında BV kenarı yoksa, VB doğru parçası üzerinde yeni bir sınır kenarı oluştururuz. Sınır kenarları arasında bir BV kenarı varsa, onu ve B köşe noktasını aktif olmayan kategorisine aktarırız. Sınır kenarları arasında VA kenarı yoksa AV doğru parçası üzerinde yeni bir sınır kenarı oluşturacağız. Sınır kenarları arasında bir VA kenarı varsa, onu ve A tepe noktasını aktif olmayan kategorisine aktarırız. Üçgenleme işlemi Şekil 2'de gösterilmektedir. 9.7.3.
Pirinç. 9.7.4. Delaunay üçgenlemesi
Tüm köşeler ve kenarlar devre dışı kaldığında üçgenlemeyi bitiririz. Belirli bir alanın üçgenlenmesinin sonucu Şekil 2'de gösterilmektedir. 9.7.4.
Düzeltme yöntemiyle üçgenleme.
Parametreleri belirlemek için belirli bir yüzeyin dikdörtgen bir alanla üçgenlenmesini düşünelim.Yüzey parametrelerini tanımlayan alanı iki boyutlu çizgilerle dikdörtgen hücrelere bölüyoruz.Bu çizgiler dikdörtgen bir ızgara oluşturuyor. Formül (9.4.7)'ye göre bitişik çizgiler arasındaki parametrik mesafeleri eşit olarak alalım.
Formül (9.4.8)'e göre bitişik çizgiler arasındaki parametrik mesafeleri eşit olarak alalım.
Tüm dikdörtgen hücrelerde köşegenler oluşturarak yüzeyde bir üçgenleme elde ederiz (gereksinimleri karşılayan bir dizi üçgen elde ederiz). İncirde. 9.7.5, açıklanan yöntemi kullanarak dönüş yüzeyinin üçgenlenmesini göstermektedir.
Bir yüzeyin keyfi bir sınırla üçgenlenmesini düşünelim. Parametrelerin belirlenmesi için dikdörtgen bir alanla yukarıda açıklanan yüzey üçgenlemesinin sınır konturları ile düzeltilmesi üzerine üçgenleme yöntemini oluşturacağız.
Pirinç. 9.7.5. Parametreleri tanımlamak için bir yüzeyin dikdörtgen alanlı üçgenlenmesi
Parametre tanımlama alanındaki yüzey sınırının birbiriyle kesişmeyen birkaç iki boyutlu konturla (2.12.7) tanımlanmasına izin verin. Konturlardan biri dıştır ve kalan konturları içerir. Her bir konturun pozitif yönü için, yüzey normaline doğru bakıldığında, yüzey tanımlama alanının her zaman konturun solunda olacağı yönü alacağız. Yüzey tanımlama alanının sınır konturlarının pozitif yönünde çokgenler oluşturalım. Sınır çokgenleri oluşturmak için, yüzeyin sınır konturları boyunca değişken adımlarla yürümeniz ve koordinatları yüzey parametreleri olan iki boyutlu noktaların bir dizisini doldurmanız gerekir. Parametrik bir düzlem üzerindeki noktalardan bir çokgen oluşturacağız, ancak bir noktadan diğerine hareket ederken atılacak adım uzaysal geometriden, yani eğri yayının bitişik noktalar arasındaki sapmasının belirli bir değerden fazla olmaması koşulundan belirlenecektir. değer. Formül (9.4.4)'ü kullanarak yüzey sınır kontur eğrisi için bir çokgen oluşturmaya yönelik parametrik adımları hesaplıyoruz.
Her çokgen, sıralı iki boyutlu noktalardan oluşur. Bir çokgenin her bölümü, iki bitişik nokta üzerine inşa edilmiş iki boyutlu bir düz çizgi parçası olarak düşünülebilir. Bu tür alanları sınır kenarları olarak kullanacağız ve çokgenlerin kenarların dayandığı noktaları üçgenleme köşeleri olarak kullanacağız. Yüzey parametrelerini belirleme alanı sınır çokgenlerinin solunda yer aldığından, her sınır üçgenleme kenarı için üçgenler oluştururken, kenarın solundaki üçgenin üçüncü tepe noktasını aramalısınız.
Hangi düğümlerin sınır çokgenlerinin içinde, hangilerinin sınırda veya yüzey tanımlama alanının dışında bulunduğunu belirleyelim. Bu bilgiyi kullanarak dikdörtgen ızgara hücrelerini iki gruba ayırıyoruz. Birinci grup, tamamen yüzey parametrelerinin belirlendiği alanın içinde kalan hücreleri içerir (hücrelerin sınır poligonlarına değmemesi gerekir). İkinci grup, kalan hücreleri içerir (yüzey tanımlama alanının dışında kalan veya sınır çokgenleriyle kesişen).
Pirinç. 9.7.6. Bitmemiş yüzey üçgenlemesi
Birinci grubun her hücresinin içinde bir köşegen kullanarak iki üçgen oluşturacağız. Böylece tamamlanmamış bir üçgenleme elde ederiz. Konturlarla sınırlı bir dönme yüzeyi için birinci grubun hücrelerinde üçgenler oluşturmanın bir örneği, Şekil 2'de gösterilmektedir. 9.7.6.
İkinci gruptaki hücrelerin kesişmeyen taraflarına sınır kenarları oluşturup, karşılık gelen hücre kenarın solunda olacak şekilde yönlendireceğiz. Birinci grubun hücrelerinin etrafına, kapalı bir kesikli çizgi (muhtemelen birkaç kapalı çizgi) inşa edeceğiz, böylece onun boyunca hareket ederken, alanın üçgenlere bölünmeyen kısmı, normal yüzeye bakarken solda kalır. . Bu kesikli çizginin düz kısımlarını da sınır kenarları olarak kullanacağız. Tüm kenarların eşit olduğunu düşüneceğiz. Üçgenlemeyi tamamlamak için sınır kenarları arasında üçgenler oluşturmamız gerekir. Her kenar için solunda bulunan ve bir üçgen oluşturmak için kullanılabilecek bir tepe noktası arayacağız. Bir köşeyi yalnızca kenarla aynı hücrede bulunan köşeler arasında arayacağız. Bir köşe seçmek için yukarıda açıklanan ve Şekil 2'de gösterilen Delaunay yöntemini kullanırız. 9.7.2. Böyle bir tepe noktası bulunursa, üçgenin iki yeni kenarının herhangi bir sınır kenarıyla kesişip kesişmediğini kontrol etmelisiniz. AB sınır kenarı için en yakın V tepe noktasının bulunmasına izin verin ve BV ve VA parçalarının diğer sınır kenarlarıyla kesişmediğini kontrol edin. Daha sonra ABV üçgenini oluşturacağız ve AB kenarını aktif olmayan kategoriye aktaracağız. Sınır kenarları arasında BV kenarı yoksa, VB doğru parçası üzerinde yeni bir sınır kenarı oluşturacağız, ancak sınır kenarları arasında bir BV kenarı varsa, onu ve B köşe noktasını aktif olmayan kategorisine aktaracağız. Sınır kenarları arasında VA kenarı yoksa, AV doğru parçası üzerinde yeni bir sınır kenarı oluşturacağız, ancak sınır kenarları arasında bir VA kenarı varsa, onu ve A tepe noktasını aktif olmayanlar kategorisine aktaracağız.
Bir segment veya VA diğer sınır kenarlarıyla kesişirse, başka bir sınır kenarı için en yakın tepe noktasını aramaya devam ederiz. Tüm kenarlar ve köşeler pasif olarak sınıflandırıldıktan sonra üçgenleme tamamlanacaktır.
Pirinç. 9.7.7. Düzeltme yöntemiyle üçgenleme
İncirde. 9.7.7, sınır konturlarıyla kesişen hücrelerdeki üçgenleri düzeltme yöntemiyle yüzey üçgenlemesini gösterir. İncirde. 9.7.8'de ortaya çıkan üçgenleme kullanılarak yüzeyin kendisi görüntülenir.
Sınır çokgenleri ve yüzey bir miktar simetriye sahipse, düzeltme yöntemiyle üçgenleme de benzer bir simetriye sahip olacaktır.
Absorbsiyon yöntemiyle üçgenleme.
Başka bir üçgenleme yöntemini ele alalım. Hız açısından Delaunay üçgenlemesinden ve modifikasyonlarından daha düşüktür. Nirengi işlemine başlamak için yüzey sınırını kapalı çokgenler şeklinde temsil etmek gerekir. Nirengi işlemi sırasında yüzey parametrelerine göre adımları belirlememiz gerekecek. Bilinen bir hareket yönü ile bu adımlar formüller (9.4.6) ile belirlenir. Yüzey parametreleri için yaklaşık adımlar aşağıdaki gibi bulunabilir. Parametre düzleminde belirli bir nokta etrafında, bu bölgedeki noktadan noktaya herhangi bir uzaysal parçanın yüzeyden verilen belirli bir S değerinden daha uzak olmayacağı şekilde bir bölge tanımlayalım.
Bunu yapmak için koordinat çizgileri boyunca izin verilen parametre artışlarını hesaplıyoruz
noktasındaki yüzeyin birinci ve ikinci ikinci dereceden formlarının katsayıları nerede? İstenilen bölgenin sınırı olarak bir noktada merkezi ve yarı eksenleri olan bir elips alıyoruz. Bu elipsin denklemi var
Düzlemde ve ekseni ile açının verdiği yönde bir noktanın yanındaki bir noktayı bulmak istiyorsanız, parametreleri şu şekilde olacaktır:
İlk olarak, yüzey parametrelerinin alanı bir dış konturla sınırlı olduğunda daha basit bir durumu ele alalım. Yüzey sınırına parametrik alanda kapalı bir çokgenle yaklaşırız. Üçgenlemeyi oluştururken, bu durumda dış konturun çokgeni olarak alacağımız çalışma çokgenini kullanacağız. Ortaya çıkan iki boyutlu noktalar dizisine çokgen noktalarını ekleyeceğiz. Çalışma alanının kenarından üçgenler oluşturup, çalışma alanında yalnızca üç nokta kalana kadar daraltacağız.
Çalışma çokgeninde bölgeye dönüştüğü bir tepe noktası bulalım. Böyle bir nokta her zaman mevcuttur ve bu noktadaki dönme açısı daha küçüktür. Bu noktayı O, parametrelerini de gösterelim. Bu noktaya yakın bir yerde dönme açısına bağlı olarak bir veya iki üçgen oluşturacağız. Açı daha küçükse bu üç noktanın üzerine bir üçgen oluşturacağız (Şekil 9.7.9). Aksi takdirde bunun üzerine iki komşu ve bir yeni nokta olmak üzere iki üçgen oluşturacağız (Şekil 9.7.11). Yeni nokta P ile gösterilir. B OS P paralelkenarının köşegeninde P noktasını arayacağız. Paralelkenarın tepe noktası elipsin içinde yer alıyorsa (Şekil 9.7.10), o zaman onu P noktası olarak alacağız. Aksi takdirde elipsin paralelkenarın köşegeniyle kesişimini P noktası olarak alacağız. İkinci durumda, elipsin ve parçanın kesişimini aramak hiç de gerekli değildir.
P noktasının koordinatları O BC noktalarının koordinatları aracılığıyla belirlenir.
OP segmentinin yatay ile açısı eşitlikle belirlenir
(9.7.8)
Bu veriler, P noktasının elipse (9.7.5) göre konumunun belirlenmesini mümkün kılar.
Şekil 2'de gösterilen durumda. 9.7.9'da bir üçgen oluşturalım (köşelerinin sayısını hatırlayalım) ve çalışma alanındaki O noktasını silelim. 9.7.11'de iki üçgen oluşturacağız ve çalışma alanında O noktasını P noktasıyla değiştireceğiz ve ikincisini ortaya çıkan noktalar dizisine yerleştireceğiz. İncirde. Şekil 9.7.12, iki üçgen oluşturup O noktasını ortadan kaldırdıktan sonra elde edilen çokgeni göstermektedir. Her iki durumda da O noktası çalışma çokgeninden çıkarılacak ve çalışma çokgeni daralacaktır. Üçgenlerin yalnızca çalışma alanı daraltıldıktan sonra kendisiyle kesişmediğinde oluşturulabileceğini unutmayın.
Pirinç. 9.7.9. Bir üçgen inşaatı
Pirinç. 9.7.10. Sonuç çokgeni
Pirinç. 9.7.11. İki üçgen inşaatı
Pirinç. 9.7.12. Sonuç çokgeni
Bu tür durumlar Şekil 2'de gösterilmektedir. 9.7.13. Oluşturulan üçgenlerin kenarları, çalışma alanının kendilerine bitişik olmayan kenarlarıyla kesiştiğinde ortaya çıkabilirler. Şekil 2'de gösterildiği gibi yeni bir üçgen oluşturmadan önce. 9.7.9 ve Şekil 9'da gösterilen durumda. 9.7.11'de ortaya çıkan çokgenin kendisiyle kesişmediğinden emin olmak için bir kontrol yapılmalıdır.
Ayrıca P noktasının konumu belirlenirken çalışma alanının diğer noktalarından yeterli uzaklıkta olması ve alanın noktalarını birleştiren segmentlere yaklaşmaması önemlidir. Aksi takdirde ileride üçgen yapılırken zorluklar ortaya çıkabilir. Bu nedenle, çalışma çokgenini daraltmadan önce, ortaya çıkan çokgeni kendi kendine kesişme açısından kontrol etmelisiniz. O noktasının yakınında bir üçgen (üçgenler) oluşturmak mümkün değilse, bunun yerine çokgenin konturun içine diğerlerinden daha fazla sarıldığı başka bir nokta bulmalı ve burada açıklanan eylemleri gerçekleştirmelisiniz.
Daha sonra değiştirilmiş çalışma alanıyla az önce tanımladığımız eylemlerin aynısını gerçekleştireceğiz. Çalışma poligonunda alanın içinde diğer noktalardan daha fazla döndüğü bir nokta bulalım, bir veya iki üçgen oluşturarak içindeki poligonu daraltma olasılığını kontrol edelim ve çokgeni daraltalım.
Pirinç. 9.7.13. Bu köşeye üçgen oluşturamazsınız.
Bu işleme devam ederek iki boyutlu nokta dizisini ve üçgen dizisini genişleteceğiz, aynı zamanda çalışma çokgenini daraltarak kapladığı alanı ve nokta sayısını azaltacağız. Bu eylemlerin bir aşamasında üç noktadan oluşan çalışan bir çokgen alacağız. Bu noktalara son üçgeni oluşturup çalışma alanını ortadan kaldıralım ve üçgenlemeyi bitirelim. Tarif edilen üçgenleme yönteminde, çalışma alanıyla sınırlanan alan, üçgenlerin kesilmesiyle adeta ortadan kaldırılmaktadır.
Yüzey parametrelerinin alanının bir dış kontur ve tamamen dış konturun içinde yer alan birkaç iç kontur ile sınırlandığı genel durumu ele alalım. Yüzey sınırını parametrik alanda kapalı çokgenlerle yaklaşık olarak hesaplıyoruz. Her kontur için kendi poligonumuzu oluşturacağız. Konturlarda olduğu gibi, üzerlerine inşa edilen çokgenlerde de karşılıklı yönelim kuralının yerine getirilmesi gerekir. İç çokgenlerin yönü dış çokgenin yönüne zıt olmalıdır. Dış kontur çokgeniyle üçgenlemeyi oluşturmaya başlayalım. Noktalarını ortaya çıkan iki boyutlu noktalar dizisine koyalım ve çokgenin kendisini çalışan bir poligona dönüştürelim.
Basit bağlantılı bölge durumunda olduğu gibi üçgenler oluşturacağız. Çalışma alanında O noktasını bulalım, orada çalışma alanının daralma olasılığını kontrol edip alanı daraltalım. İç konturlar varsa, seçilen noktada çalışma alanının daraltılma olasılığını kontrol etmek daha zor hale gelir. Üçgenlerin kenarlarının çalışma alanının kenarları ile kesişimine ilişkin açıklanan kontrollere ek olarak, üçgenlerin kenarlarının tüm iç çokgenlerin kenarları ile kesişimlerinin de kontrol edilmesi gerekir.
O noktasında iki üçgen oluşturma olasılığını kontrol edelim (Şekil 9.7.11) ve yeni P noktasının oluşturulduktan sonra iç çokgenlerden birinin içine düşeceğini veya parçalarına kabul edilemez bir yakınlıkta olacağını bulalım. Bu durumda P noktasını oluşturmayacağız, bunun yerine Şekil 2'de gösterilen iki üçgeni oluşturarak bu iç çokgeni çalışma çokgenine dahil edeceğiz. 9.7.14.
İç çokgenlerden birinin noktalarını çalışma çokgenine dahil etmek için, iç çokgenin noktaları arasında çalışma çokgenin C noktasına (O noktasına bitişik) en yakın noktayı buluruz.
OCF ve CEF noktalarında ve çalışma alanının O ve C noktaları arasına, F noktasından başlayıp E noktasıyla biten iç çokgenin noktalarını ekleyen üçgenler oluşturalım. Böylece, OS segmentindeki çalışma alanını kıracağız, EF segmentindeki iç poligonu oluşturun ve bunları OF ve AB segmentleriyle birleştirin.
Pirinç. 9.7.14. İki üçgen inşaatı
Pirinç. 9.7.15. Dış ve iç çokgenleri birleştirme
Birleşmenin sonucu Şekil 2'de gösterilmektedir. 9.7.15. Elbette dış ve iç çokgenleri birleştirmeden önce bu işlemin doğruluğundan emin olmak için kontrollerin yapılması gerekir.
Daha sonra kendimizi başka bir iç alanın yakınında bulana ve onu çalışma alanına dahil edene kadar çalışma alanını anlatılan şekilde daraltmaya devam edeceğiz. Sonuç olarak, tüm iç çokgenler, son üç noktaya kadar daraltılması gereken çalışma çokgenine dahil edilecektir. Sonuç olarak yüzey parametrelerinin belirlenmesi için çoklu bağlantılı bölgenin tamamı üçgenlerle kaplanacaktır.
Pirinç. 9.7.16. Bu köşeye üçgen oluşturamazsınız.
Verilen çokgenler üzerinde tek bir üçgen oluşturmanın imkansız olduğu durumlar olabilir. İncirde. Şekil 9.7.16'da her biri dört parçadan oluşan iki çokgenle sınırlanan bir alan gösterilmektedir. Dış çokgen için üçgenlemeye devam edemiyoruz çünkü iç çokgen yolu kapatıyor. Bu durumda, bir HRV üçgeni oluşturabileceğimiz çokgenin iki komşu B ve C noktasını bulacağız. P noktası BC kenarının ortasına yansıtılır ve ondan yeni üçgenin çokgenlerle kesişmeyeceği kadar uzakta bulunur.
Diğer üçgenleme yöntemleri.
Üçgenlemenin başka yolları da var. Örneğin, yüzey tanımlama alanının dış ve iç konturlarının çokgenlerini oluşturduktan sonra, üçgen oluşturmak için farklı bir strateji seçilebilir. Diğer bir seçenek ise üçgenlemeye başlamadan önce dış ve iç çokgenleri tek bir çokgende birleştirmektir. Belirli bir algoritma kullanarak parametre tanımlama alanı içindeki noktaları “çizebilirsiniz” ve bunları ve sınır kontur poligonlarının noktalarını kullanarak Delaunay üçgenlemesi gerçekleştirebilirsiniz. Önce büyük üçgenler oluşturan, sonra bunları yönetilebilir boyutlara bölen algoritmalar var.
Vücut üçgenlemesi.
Bir cismin üçgenlenmesi, yüzlerinin yüzeylerinin üçgenlenmesiyle elde edilen bir üçgenler kümesidir. Bireysel yüzeylerin üçgenlenmesi, gövde yüzlerinin üçgenlenmesinden farklıdır; ikinci durumda, bitişik yüzler için sınır çokgenleri tutarlı olmalıdır (Şekil 9.7.17).
Pirinç. 9.7.17. Gövde Yüzü Sınır Poligon Tutarlılığı
Ortak kenarlar boyunca geçen bitişik yüzlerin çokgenlerinin bölümleri, noktaları uzayda çakışırsa tutarlı olacaktır.
Üçgenleme uygulaması.
Üçgenleme sonucu oluşturulan üçgenler tonlu görüntüler elde etmek için kullanılır. İncirde. Şekil 9.7.18 ve 9.7.19, ton görüntüsü Şekil 2'de gösterilen bir levha gövdenin yüzünün üçgenlemelerini göstermektedir. 6.5.1.
Pirinç. 9.7.18. Düzeltme yöntemini kullanarak vücut yüzünün üçgenlenmesi
Yüzey parametrelerini belirleme alanının üçgenlere bölünmesi, cisimlerin geometrik özellikleri hesaplanırken (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) integrallerinde kullanılabilir. . Sayısal entegrasyon sırasında, eğriler için parametrik adım formül (8.11.5) kullanılarak, yüzeyler için ise parametrik adımlar (8.11.1) ve (8.11.2) formülleri kullanılarak hesaplanmalıdır.
Sonlu bir S noktaları kümesi için üçgenleme, S kümesinin tüm noktalarını kapsayan dışbükey gövde CH(S)'nin üçgenlenmesi sorunudur. Üçgenlemedeki düz çizgi parçaları kesişemez; yalnızca S kümesine ait ortak noktalarda buluşabilirler. düz çizgi parçaları yakın üçgenler, bunları kaburga olarak değerlendireceğiz. İncirde. Şekil 1, aynı nokta kümesi için iki farklı üçgenleme versiyonunu göstermektedir (bu şekillerde çizilen daireleri geçici olarak göz ardı edeceğiz).
Pirinç. 1
Belirli bir S noktaları kümesi için, S kümesindeki tüm noktaların sınır noktalarına (dışbükey gövde CH(S)'nin sınırında yer alan noktalar) ve dışbükey gövdenin içinde yer alan iç noktalara bölünebileceğini görebiliriz. gövde CH(S). Ayrıca S üçgenlemesi sonucunda elde edilen kenarları şu şekilde sınıflandırabilirsiniz: kabuk kaburga Ve iç kaburgalar. Gövde kenarları, dışbükey gövde CH(S)'nin sınırı boyunca yer alan kenarları içerir ve iç kenarlar, dışbükey gövde içinde bir üçgen ağı oluşturan diğer tüm kenarları içerir. Her kabuk kenarının iki bitişik sınır noktasını birbirine bağladığını, iç kenarların ise herhangi türden iki noktayı bağlayabildiğini unutmayın. Özellikle, eğer bir iç kenar iki sınır noktasını birbirine bağlıyorsa, bu durumda bu, dışbükey gövde CH(S)'nin bir kirişidir. Ayrıca üçgenlemenin her kenarının iki bölgenin sınırı olduğuna dikkat edin: her iç kenar iki üçgen arasındadır ve kabuğun her kenarı bir üçgen ile sonsuz bir düzlem arasındadır.
Bazı önemsiz durumlar dışında herhangi bir nokta kümesi birden fazla üçgenleme yöntemine izin verir. Ancak dikkate değer bir özellik var: Belirli bir küme için herhangi bir üçgenleme yöntemi aynı sayıda üçgeni belirler, bu da teoremden çıkar:
Bir dizi noktanın üçgenlenmesine ilişkin bir teorem. S noktaları kümesinin n>3 nokta içerdiğini ve hepsinin aynı doğrultuda olmadığını varsayalım. Ek olarak, bunlardan gelen i noktaları içseldir (yani dışbükey gövde CH(S)'nin içinde yer alır. Bu durumda, S kümesinin herhangi bir üçgenleme yöntemi tam olarak n + i - 2 üçgenle sonuçlanacaktır.
Teoremi kanıtlamak için öncelikle n-i sınır noktalarının üçgenlenmesini ele alıyoruz. Bunların hepsi dışbükey bir çokgenin köşeleri olduğundan, bu tür bir üçgenleme (n - i) - 2 üçgenle sonuçlanacaktır. (Bunu doğrulamak zor değildir ve ayrıca herhangi bir üçgenlemenin mümkün olduğu gösterilebilir. keyfi M kenarlı bir çokgen (dışbükey veya dışbükey olmayan) m - 2 üçgen içerir). Şimdi kalan i iç noktalarını her seferinde birer tane olmak üzere eklerken üçgenlemeye ne olacağını kontrol edelim. Bu tür noktaların her birinin eklenmesinin üçgen sayısını iki kat artırdığını iddia ediyoruz. Bir iç nokta eklerken, Şekil 2'de gösterilen iki durum ortaya çıkabilir. 2. Öncelikle nokta bir üçgenin içinde olabilir ve daha sonra böyle bir üçgenin yerini üç yeni üçgen alır. İkinci olarak, eğer bir nokta üçgenleme kenarlarından birine denk geliyorsa, bu kenara bitişik olan iki üçgenin her birinin yerini iki yeni üçgen alır. Tüm i noktaları toplandıktan sonra toplam üçgen sayısı (n - i - 2) + (2i) veya basitçe n + i - 2 olacaktır.
Pirinç. 2
Bu bölümde Delaunay üçgenlemesi olarak bilinen özel bir üçgenleme türü oluşturmak için bir algoritma sunacağız. Bu üçgenleme, oluşan üçgenlerin eş açılı olma eğiliminde olması açısından iyi dengelenmiştir. Örneğin, Şekil 2'de gösterilen üçgenleme. Şekil 1a, Delaunay üçgenleme tipine atfedilebilir ve Şekil 1a'da yer almaktadır. 1b üçgenlemesi oldukça uzun birkaç üçgen içerir ve Delaunay tipine atfedilemez. İncirde. Şekil 3, çok sayıda noktadan oluşan bir dizi için Delaunay üçgenlemesinin bir örneğini göstermektedir.
Pirinç. 3
Delaunay üçgenlemesini oluşturmak için birkaç yeni tanıma ihtiyacımız var. Kümedeki tüm noktaların üzerinde bulunduğu bir daire varsa, noktalar kümesi dairesel olarak kabul edilir. Böyle bir daire belirli bir nokta kümesi için çevrelenecektir. Bir üçgenin çevrelenmiş dairesi, onun üç (doğrusal olmayan) köşesinin hepsinden geçer. Çemberin içinde S kümesinden hiçbir nokta yoksa, bir çemberin belirli bir S noktaları kümesine göre noktasız olacağı söylenir, ancak S kümesindeki noktalar şu çember üzerinde yerleştirilebilir: çoğu puansız.
Bir dizi S noktasının üçgenlemesi, eğer her üçgenin çevrel çemberi noktalardan arınmışsa, bir Delaunay üçgenlemesi olacaktır. Üçgenleme diyagramında Şekil. Şekil 1a, içlerinde açıkça başka noktalar bulunmayan iki daireyi göstermektedir (diğer üçgenlerin de kümenin noktalarından bağımsız olduğundan emin olmak için daireler çizebilirsiniz). Şekil 2'deki diyagramda bu kural gözlenmemiştir. 16 - başka bir üçgenin bir noktası çizilen dairenin içine düşüyor, dolayısıyla bu üçgenleme Delaunay tipine ait değil.
Üçgenleme algoritmasını basitleştirmek için S kümesindeki noktalar hakkında iki varsayım yapılabilir. İlk olarak, üçgenlemenin var olabilmesi için, S kümesinin en az üç nokta içerdiğini ve bunların eşdoğrusal olmadıklarını varsaymamız gerekir. İkincisi, Delaunay üçgenlemesinin benzersiz olması için S kümesinden hiçbir dört noktanın aynı çevrel çember üzerinde bulunmaması gerekir. Böyle bir varsayım olmadan Delaunay üçgenlemesinin benzersiz olmayacağını görmek kolaydır çünkü sınırlı bir daire üzerindeki 4 nokta iki farklı Delaunay üçgenlemesini gerçekleştirmemize izin verir.
Algoritmamız, mevcut üçgenlemeyi her seferinde bir üçgen olacak şekilde sürekli olarak büyüterek çalışır. Başlangıçta mevcut üçgenleme kabuğun tek bir kenarından oluşur; algoritmanın sonunda mevcut üçgenleme bir Delaunay üçgenlemesi haline gelir. Her yinelemede algoritma, birbirine bağlanan yeni bir üçgen arar. sınır mevcut üçgenleme.
Sınırın tanımı şunlara bağlıdır: aşağıdaki diyagram Delaunay üçgenlemesinin kenarlarının mevcut üçgenlemeye göre sınıflandırılması. Her kenar olabilir uyuyor, canlı veya ölü:
- uyku kaburgaları: Delaunay üçgenlemesinin bir kenarı eğer algoritma tarafından henüz tespit edilmemişse hareketsizdir;
- canlı kaburga: Kaburga bulunursa canlıdır, ancak yalnızca bir bitişik alan bilinmektedir;
- ölü kaburgalar: Bir kenar bulunursa ve her iki bitişik alan da biliniyorsa ölü kabul edilir.
Başlangıçta, dışbükey i lobuna ait olan tek kenar canlıdır; ona bitişik sınırsız bir düzlem vardır ve diğer tüm kenarlar hareketsizdir. Algoritma çalışırken kenarlar uykudan canlıya ve ölüye doğru gider. Her aşamadaki sınır bir dizi canlı kenardan oluşur.
Her yinelemede, sınırın kenarlarından herhangi biri seçilir ve e kenarının ait olduğu bilinmeyen bir bölgenin aranmasını içeren işleme tabi tutulur.Eğer bu bölge, ile tanımlanan bir f üçgeni olursa, e kenarının ve bazı üçüncü köşe v'nin uç noktaları, o zaman e kenarı ölü hale gelir, çünkü ona bitişik her iki alan da artık bilinmektedir. T üçgeninin diğer iki kenarının her biri şu duruma aktarılır: uykudan canlıya veya canlıdan ölüye. Burada köşe v çağrılacak birleşik e kenarı ile Aksi halde, bilinmeyen bölgenin sonsuz bir düzlem olduğu ortaya çıkarsa, o zaman e kenarı basitçe ölür. Bu durumda e kenarının eşlenik bir tepe noktası yoktur.
İncirde. Şekil 4, eylemin yukarıdan aşağıya ve zaferin sağa doğru gerçekleştiği algoritmanın çalışmasını göstermektedir. Her aşamadaki kenarlık kalın bir çizgiyle vurgulanır.
Algoritma delaunayTriangulate programında uygulanır. Programa n noktadan oluşan bir dizi verilir ve Delaunay üçgenlemesini temsil eden üçgenlerin bir listesini döndürür. Uygulama, Geometrik Veri Yapısı bölümündeki dairesel liste sınıfını ve sınıflarını kullanır. Dictionary sınıfı, gerekli işlemleri destekleyen herhangi bir sözlük olabilir. Örneğin, #define Dictionary RandomizedSearchTree öğesini geçersiz kılabilirsiniz.
Liste
Pirinç. 4
Üçgen oluşturan üçgenler üçgen listesine yazılır. Sınır, sınırda yaşayan kenarların bir sözlüğüyle temsil edilir. Her kenar, kendisi için bilinmeyen bölge (belirlenecek olan) kenarın sağında kalacak şekilde yönlendirilir. EdgeCmp karşılaştırma işlevi sözlüğe bakmak için kullanılır. İki kenarın başlangıç noktalarını karşılaştırır; eğer eşitse bitiş noktaları karşılaştırılır:
Int edgeCmp (Edge *a, Edge *b) ( if (a->org)< b->org) dönüş 1; if (a->org > b->org) 1 değerini döndürür; if (a->hedef< b->hedef) dönüş -1; if (a->hedef > b->hedef) 1 değerini döndürür; 0 değerini döndür; )
Kenarlık bir adımdan diğerine nasıl değişir ve updateFrontier işlevi bu değişiklikleri yansıtacak şekilde kenarlığın kenar sözlüğünü nasıl değiştirir? Sınıra yeni bir t üçgeni bağlandığında üçgenin üç kenarının durumları değişir. Sınıra bitişik olan üçgen kenarı t canlıdan ölüye dönüşür. updateFrontier işlevi bu kenarı yok sayabilir çünkü RemoveMin işlevi çağrıldığında bu kenarın zaten sözlükten kaldırılması gerekir. Üçgen t'nin geri kalan iki kenarının her biri, eğer daha önce sözlüğe kaydedilmemişse, durumunu uykudan canlıya veya kenar zaten sözlükteyse canlıdan ölüye değiştirir. İncirde. Şekil 5 her iki durumu da göstermektedir. Şekle göre af canlı kenarını işliyoruz ve b noktasının eşleniği olduğunu bulduktan sonra mevcut üçgenlemeye afb üçgenini ekliyoruz. Daha sonra sözlükte fb kenarını ararız ve henüz orada olmadığı ve ilk kez keşfedildiği için durumu uykudan canlıya değişir. Sözlüğü düzenlemek için fb kenarını, yanındaki bilinmeyen bölge sağında kalacak şekilde döndüreceğiz ve bu kenarı sözlüğe yazacağız. Daha sonra sözlükte ba kenarını bulacağız - içinde olduğu için zaten canlıdır (buna bitişik bilinen alan abc üçgenidir). Bilinmeyen bölge afb üçgeni yeni keşfedildiğinden bu kenar sözlükten kaldırılmıştır.
updateFrontier işlevi, a noktasından b noktasına kadar kenarın durumunun değiştiği sınır sözlüğünü düzenler:
Pirinç. 5
Güncellemeyi geçersiz kıl Frontier (Sözlük
hullEdge işlevi, s dizisindeki n nokta arasında bir gövde kenarı bulur. Bu işlev aslında başlatma adımını ve hediye paketleme yönteminin ilk yinelemesini kullanır:
Edge *hullEdge (Nokta s, int n) ( int m = 0; for (int i = 1; i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }
Üçgen işlevi, kendisine parametre olarak iletilen üç nokta için basitçe bir çokgen oluşturur ve döndürür:
Çokgen *üçgen (Nokta &a, Nokta &b, Nokta &c) ( Çokgen *t = yeni Çokgen; t->insert (a); t->insert (b); t->insert (c); return t; )
GRID modelleri normal hücrelerin modelleridir.
Koordinat sisteminin tanıtılmasına izin verin 
Ve 
Ve 
. Kullanıcı setleri 
ve örnekleme adımları 
.
,
- noktanın fiziksel koordinatları.
Hesaplıyoruz 
Ve 
,
- bit ızgarası.
- nicelenmiş değerler. Gerçek:
- algoritma parametresi – nokta sayısı, 
- ağırlık. Nokta ne kadar yakınsa ağırlık da o kadar fazla olur.
- mesafe derecesi (1 veya 2).
Normalleştirme faktörü: 
Nasıl 
1'e yaklaştıkça daha yüksek ağırlığa sahip noktalar dikkate alınır.
Bu IDW yöntemidir - uzun, her biri için komşuları bulmak gerekir. Komşular kümesi verimli bir şekilde bulunabilir - en yakın. Her nokta belirli bir yükseklikte bir "sabit" oluşturur. Çoğu şey noktayı belirlemedeki düzensizliğe bağlıdır, bunun için 
veya 
onlar. sektörlere bölünmüş ve civarda inşa noktaları.
Avantaj- basitlik
Kusur:
------Bilet 14. Teneke model. Delaunay üçgenleme algoritmaları------
1) Üçgenleme (kalay).
Nirengi– parçalı doğrusal fonksiyonlar kümesi şeklinde bir fonksiyonun oluşturulması
Nirengi– dışbükey bir bölge içinde enterpolasyon.
Nirengi– tüm iç kenarları üçgen olan düzlemsel bir grafik; Alanı örtüşmeden birbirine bitişik üçgenler şeklinde temsil etmenin bir yolu. Üçgenleme, çeşitli şekillerde bir dizi nokta üzerine kuruludur.
Optimum üçgenlemeyi oluşturmak için bir algoritmaya ihtiyaç vardır.
3 noktadan geçen bir uçak.
1) Bir üçgen bulun 
;
2)
- düzlemin denklemini oluşturun.
Noktaların üçgenin içinde olup olmadığını kontrol etmek için, değeri çizgilerin (üçgenin kenarları) denkleminde değiştirmeniz gerekir. Eğer 3 denklemin tümü > 0 ise, o zaman içeride.
Sunum yapısı:
Her üçgenleme aynı sayıda üçgen içerir.
, Nerede 
– dahili noktaların sayısı, 
- puan miktarı.
Açgözlü üçgenleme.
Tüm noktaları kenarlarla birleştirip minimumu seçip üçgenlemeye ekliyoruz. Daha sonra, öncekilerle kesişmeyen bir sonraki minimumu alıyoruz, vb. Sonuç açgözlü üçgenlemedir.
Delaunay üçgenlemesi.
Herhangi bir üçgenin çevrelediği bir dairenin içi diğer üçgenlerin noktalarını içermez. Tek şekilde inşa edilmiştir.
Çevirme, kenarların aktarılmasıdır. Geleneksel üçgenlemeden Delaunay üçgenlemeye geçmenizi sağlar. Bir noktanın bir daireye ait olup olmadığını kontrol etmek için: if yerine< R, то внутри.
Delaunay durumu.
Üç noktadan geçen çemberin denklemi:
Sıfırdan küçükse, o zaman harici, aksi takdirde dahili.
– Delaunay koşulu.
Delaunay üçgenlemesini oluşturmak için algoritma:
1) İncelenen noktaların eklenmesi– basit bir yinelemeli algoritma:
Bir set var 
üçgene eklenir, inşaat yapılır 
üçgen bölme 
yeniden inşa etmek. Sıfır aşamasında zarfımızı kaplayan 3-4 hayali noktayı, içerideki tüm noktaları ekliyoruz. Daha sonra noktayı atıyoruz, hangi üçgene çarptığına bakıyoruz, 3'e bölüyoruz, her üçgen için Delaunay koşulunu kontrol edip kenarların ters çevrilmesini gerçekleştiriyoruz. Ortalama şerit değiştirme sayısı üçtür.
Teorik karmaşıklık 
2) Hızlandırma yöntemleri.İstatistiksel olarak bağımlı noktalara dayanmaktadır. Tohum üçgeni, önceki noktanın düştüğü üçgendir. Sonra iki noktayı birleştiriyoruz - önceki ve yeni.
İlk noktadan diğerine geçiyoruz.
