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.

Belirli bir iki boyutlu nokta kümesinden üçgenleme oluşturma sorunu, belirli noktaları kesişmeyen bölümlerle bir üçgenleme oluşturacak şekilde bağlama sorunudur.

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 boş bir Delaunay topunu (A) nokta sistemine yerleştirelim. 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şecek çünkü sistemimizde sonsuz büyüklükte boşluklar yok. 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.

Şekil 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 bulunmaması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(Şekil 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 görev 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ğime sahip 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.

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, belirli 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)

Son zamanlarda üçgenleme ağı oluşturmanın en popüler yöntemlerinden biri olan Delaunay üçgenlemesini oluşturmanın birçok yolu vardır. 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 dairelerin 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 üçgenlere 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 karşı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 belirtildiği gibi üçgenleme yapılırken gerçekleştirilen en önemli işlemlerden biri verilen üçgen çiftleri için Delaunay koşulunun kontrol edilmesidir. 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 açıklanan dairenin merkezini ve yarıçapını önceden hesaplamaktır; ardından 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 segmenti arasındaki ilişkiyi incelerken çok küçük açılar ortaya çıkar ve trigonometrik fonksiyonları kullanırken, bilgisayardaki veri temsillerinin sınırlı doğruluğu nedeniyle her zaman sıranın kaybolması ve 0'a bölünmesi tehlikesi vardır; sürekli ek işlem.

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ı, boyunca 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ıralı olarak eklenmesi fikrine dayanmaktadır. Genel olarak, birkaç adım içerirler ve ilk üç başlangıç ​​noktasında bir üçgen oluşturmaya ve bir sonraki noktayı yerleştirmek için çeşitli seçenekleri araştırmaya kadar özetlenirler. Ö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 üçgenlemesini oluşturmaya yönelik algoritmalar, düğümlerin koordinatlarının gerçek veya tamsayı 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 kabartma bölümü ile, kaçırılan pürüzlülüğün maksimum değerinin (yani, zemin yüzeyinin bitişik kazıklardan geçen düz bir ç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.

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 katsayısı:

Nasıl 1'e yaklaştıkça daha yüksek ağırlığa sahip noktalar dikkate alınır.

Bu IDW yöntemidir - uzundur, 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. Bunun için çoğu şey noktayı belirlemedeki düzensizliğe bağlıdır;
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; Uzayı ö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 sayısı.

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ı kapladığı belli olan 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.

Çevrel çember denklemi yoluyla Delaunay koşulunu kontrol etmek için algoritmanın optimizasyonu ve uygulaması

İki üçgen için Delaunay koşulunun hızlı bir şekilde nasıl kontrol edileceğine dair size bir sır vereceğim.
Aslında optimizasyonun kendisi biraz daha aşağıda anlatılıyor (bkz. “Çevrel çember denklemi aracılığıyla Delaunay koşulunu kontrol etmek için algoritmanın optimizasyonu”), ancak size her şeyi sırayla anlatacağım.

Benim durumumda, görüntü izlemede düzlemi ilkel sektörlere (üçgenler) bölmek için üçgenleme kullanılıyor. Bildiğiniz gibi bu aynı zamanda birkaç aşamaya da bölünmüştür: ayarlama, sınırları belirleme, sınırların etrafında dolaşma, konturları süpürme. Bu en genel anlamdadır. Sanırım en zor aşamada durmak istiyorum: uçağı süpürmek.

Girişte

Şekil 1

Ne yapalım

Aramak

Algoritma

Şekil 2

Şekil 3

Şekil 4

Bir şey daha: Bir sonraki üçgeni kaydederken, köşeleri saat yönünde (doğru koordinat sisteminde) kaydetmeniz gerekir. Bu gelecekte bilgi işlem kaynaklarını azaltmak için yararlı olacaktır.

2) Tüm düzlemi tarayana kadar 1. adımı tekrarlayın.

3) Birkaç dizi varsa, ör. bir ve içinde bir veya daha fazla iç kontur var (Şekil 1). Burada her diziyi ayrı ayrı ele almak gerekir. Başka bir iç kontur alalım. Bir harici ve bir dahili olarak iki tek devre yapacağız. Bunu yapmak için bir devreden diğerine iki "bağlantı noktası" bulmanız gerekir. “Limanlar” için şart: birbirleriyle kesişmemeleri (uçları bile birbirine değmemelidir) ve eşyükselti çizgileri ile kesişmemeleri gerekir (Şekil 5).

Şekil 5

Şekil 6
4) Daha sonra, önceden oluşturulmuş dizilere, birbirinden ayrılmış olarak tüm iç dizileri tek tek girmelisiniz (nokta 3). Yenisini içeren ile birleştirmeniz gerekir. Tanım gereği, hiçbir iç sıra diğerlerine (hem dış hem de olası tüm iç sıralara) dokunmaz veya onlarla kesişmez, bu nedenle her şey sorunsuz ilerleyecektir.
Bağlantı noktalarını bulduktan sonra (Şekil 6), yeni diziler oluşturmak ve mevcut algoritmanın 1. ve 2. noktalarını kullanarak bunları atlamak kolaydır (Şekil 7).

Şekil 7

5) 4. aşamadan sonra elimizde bir üçgen listesi var (Şekil 8). Sanki görev zaten tamamlanmış gibi ama geriye kalan tek şey resmi güzelleştirmek: Delaunay koşulunun yerine getirilip getirilmediğini kontrol etmek (Şekil 9).

Şekil 8

Şekil 9

6) İleriye baktığımda size altıncı noktayı anlatacağım. 5 numaralı adımı kullanarak elde edilen üçgenler listesinden sırayla geçmeyi içerir. Öncelikle tüm üçgenleri “kirli” olarak işaretliyoruz. Her çevrimde her üçgen için Delaunay koşulunu kontrol ediyoruz. Koşul karşılanmazsa, komşuları ve mevcut üçgeni yeniden inşa edip "kirli" olarak işaretliyoruz. Koşul karşılanırsa temiz olarak işaretliyoruz. Algoritmanın uygulanmasında her üçgenin komşularıyla bir bağlantısı vardır. Bu durumda 6. nokta en hızlı şekilde çalışır.

Beşinci aşama hakkında daha fazla bilgi

Hesaplama gücü #1: 10 çarpma/bölme ve 13 toplama/çıkarma.
Bilgi işlem gücü #2: 29 çarpma/bölme işlemi ve 24 toplama/çıkarma işlemi.

Örneğin kitapta hesaplanan bilgi işlem gücü açısından 1 numaralı seçenek daha karlı. Olmasaydı uygulardım... (Şekil 10). Anlaşıldığı üzere, bu yöntemi "taşıyıcıya" yerleştirdikten sonra belirsizlik ortaya çıktı. Bu, A açısının 180 dereceden fazla olduğu durumlarda bir seçenektir. Kitapta bireysel özel yöntemlerden biri olarak değerlendiriliyor. Ve bununla birlikte tüm zarafeti, şeffaflığı ve performansı ortadan kalkıyor. Ayrıca daha sonra 2 numaralı yöntemin çok önemli ölçüde optimize edilebileceği ortaya çıktı.

Şekil 10

Çevrel daire denklemi yoluyla Delaunay koşulunu kontrol etmek için algoritmanın optimizasyonu

Yani elimizde:
M(X, Y) noktasının koşulunun A(x1, y1), B(x2, y2), C(x3, y3) noktalarından geçen bir dairenin denklemiyle kontrol edilmesi şu şekilde yazılabilir:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ işaret a ≥ 0

Ayrıntıları mükemmel kitapta bulabilirsiniz. (Hayır, yazar değilim)
Yani, a işareti çapraz yön işaretidir, en başından beri üçgenleri saat yönünde oluşturdum, böylece ihmal edilebilir (bire eşittir).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Şekil 11

Basit değil mi?

Kitaba göre yine

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Elimizde: 15 çarpma/bölme işlemi ve 14 toplama/çıkarma işlemi var.

İlginiz için teşekkür ederiz. Eleştiri bekliyorum.

Kullanılmış literatür listesi

Teplov A.A., Lisans, MSTU, N.E. Bauman, Bilgisayar Yazılımı ve Bilgi Teknolojileri Bölümü, Moskova, [e-posta korumalı]

MAYKOV K.A., Teknik Bilimler Doktoru, Profesör, Moskova Devlet Teknik Üniversitesi N.E. Bauman, Bilgisayar Yazılımı ve Bilgi Teknolojileri Bölümü, Moskova, [e-posta korumalı]

Değiştirilmiş algoritma
Delaunay üçgenlemesi

Yüksek performanslı ve düşük kaynak tüketimine sahip Delaunay üçgenleme yöntemlerinin karşılaştırmalı analizinin sonuçları sunulmaktadır. Daha sonraki modernizasyon için bir prototip seçimi, dinamik üç boyutlu nesnelerin gerçek zamanlı olarak pratik olarak gerekli ayrıntı derecesine sahip inşasıyla bağlantılı olarak doğrulanır. Dağıtım yoğunluğuna uygun olarak bir dizi üçgenleme noktasının aralıklı bölümlenmesi için, donanım uygulamasındaki hataların önlenmesine olanak tanıyan bir algoritma önerilmiştir. Önerilen değiştirilmiş Delaunay üçgenleme algoritmasının analizi gerçekleştirilir

giriiş

Belirli bir ayrıntı düzeyine sahip dinamik 3 boyutlu nesneler oluşturmanın kaynak yoğunluğunu belirleyen aşamalardan biri üçgenlemedir. Uygulamada, yüksek performans ve düşük kaynak yoğunluğu şartlarını karşılayan bir üçgenleme yönteminin prototipinin belirlenmesine ve ardından belirli bir problem sınıfı için modifikasyon yapılmasına ihtiyaç vardır.

Çözülecek görevlerin belirlenmesi

Bir dizi pratik problem, bilinmeyen bir dağıtım yasasına sahip karşılık gelen bir dizi nokta tarafından tanımlanan 3 boyutlu nesnelerin modellenmesi ihtiyacıyla karakterize edilir. Bu tür problemlerin bir örneği, yükseklikleri önceden uzaktan algılama ile elde edilen bir dağ sırasının veya karmaşık ve düzensiz yüzey yapılarının modellenmesidir. Bu durumda, minimum toplam değerine sahip "ince" üçgenlerin yapısının hariç tutulmasıyla karakterize edilen, üçgenlerin en yüksek "doğruluk derecesini" sağlayarak orijinal nokta kümesi üzerinde üçgenleme yapmak gerekir. çevrelenmiş dairelerin yarıçapları.

Üçgenlerin "düzenlilik derecesi" sorunu, Delaunay koşulunu sağlayan üçgenleme ile çözülür.

Bilinen Delaunay üçgenleme algoritmaları şu dört kategoriye ayrılabilir: yinelemeli algoritmalar, birleştirme algoritmaları, iki geçişli algoritmalar ve adım adım; Bu algoritmaların temel özellikleri aşağıda tartışılmaktadır.

Delaunay üçgenlemesini oluşturmak için yinelemeli algoritmalar

Yinelemeli algoritmalar, kısmen oluşturulmuş bir Delaunay üçgenlemesine noktaların sıralı olarak eklenmesini uygular. Yinelemeli Delaunay algoritmalarının karmaşıklığı O(N2) olarak tanımlanır ve noktaların düzgün dağılımı durumunda - O(N). Yinelemeli Delaunay algoritmalarının dezavantajları, çok sayıda yinelemeli döngü olması, sıralama algoritmasının kaynak verinin yapısına bağımlılığı ve her döngüde Delaunay koşulunun kontrol edilmesi gerekliliğidir. Yinelemeli Delaunay algoritmalarının avantajları, uygulama kolaylığı ve belirli bir giriş verisi kümesine dayalı olarak etkili bir sıralama algoritması seçmenin yüksek hızıdır.

Birleştirme yoluyla Delaunay üçgenlemesini oluşturmaya yönelik algoritmalar

Birleştirme algoritmaları, orijinal nokta kümesinin bir dizi alt kümeye bölünmesini uygular; burada bir dizi çözümün daha sonra birleştirilmesiyle üçgenlemeler oluşturulur. Birleştirme algoritmalarının ortalama karmaşıklığı O(N)'dir. Birleştirme algoritmaları, "dar" şeritler için dışbükey alanlar oluşturma ihtiyacı ve sonuç olarak birleştirme sırasında yeniden oluşturulan uzun, "dar" üçgenlerin oluşumu ile belirlenen artıklık ile karakterize edilir. Birleşme algoritmaları, pratik avantajlarını belirleyen yüksek performansa sahiptir.

Delaunay üçgenlemesini oluşturmak için iki geçişli algoritmalar

İki geçişli algoritmaların avantajlı özelliği, ilk çevrimde, ikinci aşamada Delaunay koşuluna göre değiştirilen Delaunay koşulu dikkate alınmadan belirli bir üçgenlemenin oluşturulmasıdır. İki geçişli algoritmaların karmaşıklığı ortalama olarak O(N) ve en az tercih edilen durumda – O(N 2)'dir. İki geçişli Delaunay algoritmalarının dezavantajı, her şerit için çok sayıda sıralamaya ihtiyaç duyulmasıdır. Aynı zamanda bu algoritma yüksek performansla karakterize edilir, çünkü Üçgenlemeye giren bir sonraki üçgen, önemli donanım kaynakları gerektiren Delaunay koşulunun karşılanması açısından kontrol edilmez.

Delaunay üçgenlemesini oluşturmak için adım adım algoritmalar

Adım adım oluşturma algoritmaları yalnızca son üçgenlemede Delaunay koşulunu karşılayan üçgenleri uygular ve bu nedenle yeniden yapılandırma gerektirmez. Noktaların çok yoğun olduğu durumlarda adım adım hücresel algoritmanın kullanılması pratik değildir. Bu algoritmanın karmaşıklığı ortalama olarak O(N) ve en kötü durumda – O(N 2)'dir.

Delaunay üçgenlemesini değiştirmek için bir prototip seçme

Gerçek zamanlı olarak dinamik 3 boyutlu nesneler oluşturma probleminin pratik özellikleri, Delaunay üçgenleme algoritmaları için yüksek performans ve düşük kaynak yoğunluğu gibi gereksinimleri belirler. Yukarıdaki analiz sonuçlarından da anlaşılacağı üzere, dikkate alınan algoritmalar bu gereksinimleri tam olarak karşılamamaktadır. Bu nedenle, üçgenleme alanının, üçgenlemenin noktalarını içeren temel öğelere bölünmesine bağlı olmayan ve mevcut üçgenin orijinal üçgenlemeye eklenmesinin her yinelemesinde Delaunay koşulunun kontrol edilmesini gerektirmeyen bir algoritma oluşturmaya ihtiyaç vardır. .

Karşılaştırmalı analizin yukarıdaki sonuçlarından, iki geçişli Delaunay üçgenleme algoritmalarının, özellikle de iki geçişli fan algoritmasının, yüksek performans ve düşük kaynak yoğunluğu kriterlerini yalnızca kısmen karşıladığı sonucu çıkmaktadır.

Ancak bu tür algoritmalar, gerçek zamanlı problemlere uygulanabildiğinde performansı artırmak için değişiklik yapılmasını gerektirir. İki geçişli fan algoritması, noktaların kütle merkezinin belirlenmesinde gereksizdir. OX veya OY kullanarak bir nokta kütle merkezinin koordinatını belirlerken, çok sayıda nokta ile aritmetik ortalamanın değerini hesaplamak uygun değildir ve nokta koordinatlarının büyük değerleri ile veri taşması meydana gelebilir; programın hatasına veya başarısızlığına yol açacaktır. Bu nedenle, üçgenleme noktalarının tüm değerlerinin X ekseni boyunca aralıklara Δx 1, Δx 2, Δx 3 ... Δx n'ye ve Y ekseni boyunca Δy 1, Δy 2, Δy 3'e bölünmesi tavsiye edilir. ... Δy n. X ve Y eksenleri boyunca karşılık gelen aralıklara ait noktaların sayısını da belirlemek gerekir. Noktaların kütle merkezini elde etmek için elde edilen formüller aşağıdaki forma sahiptir:

• x c – kütle merkezi noktasının x koordinatı;
• Δх i – X eksenindeki i-inci aralık;
• X max – tüm üçgenleme noktaları arasında X ekseni boyunca maksimum değer;
• X min – tüm üçgenleme noktaları arasında X ekseni boyunca minimum değer;

• y c – kütle merkezi noktasının y koordinatı;
• n i - i'inci aralıktaki noktaların sayısı;
• Δy i – Y ekseninde i-inci aralık;
• Y max – tüm üçgenleme noktaları arasında Y ekseni boyunca maksimum değer;
• Y min – tüm üçgenleme noktaları arasında Y ekseni boyunca minimum değer.

Üçgenlemenin sonraki aşamaları klasik fan algoritmasına göre uygulanır. Geliştirilen değiştirilmiş yelpaze şeklindeki Delaunay üçgenleme algoritmasının diyagramı Şekil 1'de gösterilmektedir. 1.

Sunulan şemadaki en emek yoğun aşamalar, üçgenlemeyi dışbükey olarak sıralama ve oluşturma aşamalarıdır. Sıralama algoritması olarak birleştirme algoritması, dışbükey üçgenleme algoritması olarak da Graham algoritması seçildi. Her iki algoritma da kabul edilebilir bir sürede çalışır ve temsilcileri arasında pratik açıdan en çok tercih edilenlerdir.

Değiştirilmiş yelpaze şeklindeki Delaunay üçgenleme algoritmasının analizi

Şekil 2'de gösterilenden. Diyagramın 1'i, değiştirilmiş fan algoritması kullanılarak üçgenleme oluşturmaya yönelik zaman değerinin şu ifadeyle belirlendiğini göstermektedir:

• T 1 , T 2 - sırasıyla X ve Y eksenleri boyunca en uygun aralık sayısını hesaplamak için zaman değerleri;
• T 3 , T 4 - sırasıyla X min ve X max hesaplama süresinin değerleri;
• T 5 , T 6 - sırasıyla Y min ve Y max hesaplama süresinin değerleri;
• T 7 , T 8 - sırasıyla X ve Y eksenleri boyunca aralık değerlerinin hesaplanması için zaman değerleri;
• T 9 – dizinin her noktasının A(Xc,Yc) noktasına göre kutup açısını hesaplamak için zaman değeri;
• T 10 – tüm noktaların A(Xc ,Yc) noktasına göre kutup açılarına göre birleştirilmesiyle elde edilen sıralama süresi değeri;
• T 11 – dizinin her noktasından A(Xc ,Yc) noktasına kadar bir kenar oluşturmak için zaman değeri;
• T 12 – üçgenlemeyi dışbükey olana tamamlamak için zaman değeri;
• T 13 – Delaunay koşulunu karşılayan üçgenleme yeniden yapılandırma süresinin değeri;
• n – nokta koordinat değerleri dizisi.

Her zaman bağımlılığını ayrı ayrı ele alalım.

X ve Y ekseni boyunca optimum aralık sayısını belirlerken, n aralık sayısının şu şekilde belirlendiği Sturges kuralını kullanırız:

• N, miktarın toplam gözlem sayısıdır;
• [x] – x sayısının tamsayı kısmı.

T 1 ve T 2 zaman bağımlılıklarının sabit c 1 ve c 2 temsillerine sahip olduğu açıktır.

X min , X max , Y min , Y max değerlerinin belirlenmesi aşamalarında sözde kod şöyle görünecektir:

X min ← M

i ← 1 için uzunluk(M) – 1

Eğer Xmin › M[i]

Xmin ← M[i]

Xmaks ← M

i ← 1 için uzunluk(M) – 1

Xmax ise< M[i]

Xmaks ← M[i]

Ymin ← M

i ← 1 için uzunluk(M) – 1

Eğer Ymin › M[i]

Ymin ← M[i]

Ymaks ← M

i ← 1 için uzunluk(M) – 1

Ymax ise< M[i]

Ymaks ← M[i]

Yukarıdaki sözde koddan, x veya y'nin maksimum veya minimum değerini bulma süresinin O(N) doğrusal bir bağımlılığa sahip olduğu açıkça görülmektedir, dolayısıyla T 3 (n), T 4 (n), T 5 (n) , T6(n), sırasıyla O(N) zaman karakteristiğine sahiptir.

X ekseni boyunca aralıkların değerlerini belirleme şeması Şekil 2'de gösterilmektedir. 2.

Yukarıda sunulan diyagramdan O(N)'nin doğrusal zamana bağımlılığı da görülebilir çünkü Nokta dizisinin değerlerinin tüm koordinat seti, değerlerin belirlenmesinde rol oynar. Y ekseni boyunca aralıkların değerlerini belirleme şeması benzer bir yapıya ve zaman özelliklerine sahiptir, bu nedenle T7 (n) ve T8 (n) için zamana bağımlılık O(N) şeklindedir.

Orijinal nokta dizisi için kutup açısı değerlerini belirleme şeması Şekil 2'de gösterilmektedir. 3.

Sözde kod biçiminde bu diyagram şöyle görünecektir:

puanlar için puanlar için

# Nokta 1. ve 4. çeyrekler arasındaki koordinat ekseninde bulunuyorsa

Eğer nokta.x ≥ Xc ve nokta.y = Yc ise

Nokta.açı ← 0

# Eğer konu kesinlikle ilk çeyreğe aitse

Aksi takdirde nokta.x > Xc ve nokta.y > Yc ise

Temel ← |point.x – Xc|

Nokta.açı ← yay(dik/temel)

# Nokta 1. ve 2. çeyrekler arasındaki koordinat ekseninde bulunuyorsa

Aksi halde nokta.x = Xc ve nokta.y > Yc ise

Nokta.açı ← p/2

# Eğer konu kesinlikle ikinci çeyreğe aitse

Aksi takdirde point.x< Xc and point.y >Yc

Temel ← |point.y – Yc|

Nokta.açı ← p/2 + arktg(dik/temel)

# Nokta II ve III çeyrekleri arasındaki koordinat ekseninde bulunuyorsa

Eğer nokta.x< Xc and point.y = Yc

Nokta.açı ← p

# Eğer konu kesinlikle üçüncü çeyreğe aitse

Eğer nokta.x< Xc and point.y >Yc

Temel ← |point.x – Xc|

Dik ← |nokta.y – Yc|

Nokta.açı ← p + arktan(dik/temel)

# Nokta III ve IV çeyrekleri arasındaki koordinat ekseninde bulunuyorsa

Eğer nokta.x = Xc ve nokta.y ise< Yc

Nokta.açı ← 3p/2

# Eğer konu kesinlikle IV çeyrekte ise

Eğer nokta.x > Xc ve nokta.y ise< Yc

Temel ← |point.y – Yc|

Dik ← |nokta.x – Xc|

Nokta.açı ← 3p/2 + arktg(dik/temel)

Açıkçası, orijinal nokta koordinat dizisi için kutup açısı değerlerini belirlemek için zaman karakteristiği O(N) biçimindedir, dolayısıyla T 9 (n) = O(N).

'de gösterildiği gibi, birleştirme sıralamasının zamana bağımlılığı O(N) biçimindedir, dolayısıyla T10(n) = O(NlnN).

Orijinal dizinin noktalarını birleştiren bir kenar oluşturma diyagramı Şekil 2'de gösterilmektedir. 4.

Yukarıdaki devrenin sözde kodu şöyle görünecektir:

i ← 0 için uzunluk (Puan) – 1

Draw(Xc,Yc,Noktalar[i].x, Noktalar[i].y)

Zaman tepkisi de doğrusaldır, dolayısıyla T11(n) = O(N).

Ortaya çıkan üçgenlemenin dışbükey olana kadar tamamlanması Graham'ın algoritmasına göre gerçekleştirilir. Prosedürün giriş verileri Q noktaları kümesidir; burada |Q|≥3. İçeriğini değiştirmeden S yığınının en üstündeki noktayı döndüren Top(S) fonksiyonunu çağırır. Ek olarak, S yığınında bulunan, üst noktanın bir konum altındaki bir noktayı döndüren NextToTop(S) işlevi de kullanılır; S yığını değişmeden kalır.

Graham(S)

p 0, Q kümesinden minimum koordinatlı bir nokta olsun.

‹p 1 , p 2 ,...,p N › – Q kümesinin noktaları sıralanmış olsun

Artan kutup açısına göre.

İt(p 0 ,S)

İt(p 1 ,S)

i=2'den N'ye kadar

NextToTop(S), Top(S) ve pi noktalarının oluşturduğu açı,

Sola olmayan bir dönüş oluşturun

# bunların oluşturduğu kırık bir çizgi boyunca hareket ederken

# nokta, hareket düz veya sağa doğru gerçekleştirilir

Pop(S) Yap

İtme(pi,S)

dönüş S

Graham prosedürünün çalışma süresi O(NlnN), burada N=uzunluk(Q). While döngüsünün O(N) zaman alacağını ve kutup açılarını sıralamanın O(NlnN) zaman alacağını göstermek kolaydır, bu Graham prosedürünün genel asimptotiklerini ifade eder, dolayısıyla T 12 (n) = O( NlnN).

Delaunay koşulunu karşılayan bir üçgenlemenin yeniden inşasının zaman karakteristiği, 'de gösterildiği gibi, O(N) doğrusal bir bağımlılığa sahiptir, dolayısıyla T13(n) = O(N).

Bulunan tüm zaman özelliklerini ifade (3)'te değiştirirsek, ortaya çıkan zamana bağımlılık şöyle görünecektir:

T(n) = c 1 +c 2 +O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+ +O(NlnN )+O(N)+O(NlnN)+O(N)

T(n) = O(NlnN)

Değiştirilmiş Delaunay üçgenleme algoritmasının zaman özelliklerinin teorik analizi, önerilen algoritmanın verimliliğini ve yüksek performansını doğrulamaktadır.

Sonuçlar

Pratik olarak popüler olan Delaunay üçgenleme algoritmalarının karşılaştırmalı analizinin bir sonucu olarak, dikkate alınan yöntemlerin, önceden belirlenmiş bir ayrıntı derecesine sahip gerçek zamanlı olarak dinamik üç boyutlu nesneler oluşturma gereksinimlerini karşılamadığı ve bu nedenle pratik bir çözüm olduğu gösterilmiştir. bunların değiştirilmesine ihtiyaç vardır. Fan şeklindeki iki geçişli Delaunay üçgenleme algoritmasının bir modifikasyonu önerilmiştir; bunun işlevsel özelliği, nokta dizisini alt kümelere bölerek üçgenleme noktalarının koordinat dizisinin kütle merkezinin değerlerini hesaplamaktır. X ve Y eksenleri Değiştirilmiş Delaunay üçgenleme algoritmasının zaman özellikleri analiz edilir. Bu hesaplamalar, kütle merkezi noktasının koordinatlarını belirlerken geniş bir nokta dizisindeki performansı önemli ölçüde artırmayı ve veri taşmasını ve dolayısıyla yazılım uygulamasındaki hataları önlemeyi mümkün kılar.

1. Knut D.E. Programlama sanatı. Cilt 1. Temel algoritmalar. – M.: Williams, 2008. – 680 s.
2. Knut D.E. Programlama sanatı. Cilt 3. Sıralama ve arama. – M.: Williams, 2008. – 800 s.
3. Mandelbrot B. Doğanın fraktal geometrisi. – M.: Bilgisayar Araştırma Enstitüsü, 2002. – 656 s.
4. Skvortsov A.V. Delaunay üçgenlemesi ve uygulaması. – Tomsk: Tomsk Üniversitesi Yayınevi, 2002. – 128 s.
5. Skvortsov A.V. Doğrusal zamanda Delaunay üçgenlemesinin inşası. – Tomsk: Tomsk Üniversitesi Yayınevi, 1999. – S.120-126.
6. Skvortsov A.V., Mirza N.S. Üçgenlemeyi oluşturmak ve analiz etmek için algoritmalar. – Tomsk: Tomsk Üniversitesi Yayınevi, 2006. – 168 s.
7. Thomas H. Corman, Charles I. Leiseron, Ronald L. Rivest, Clifford Stein. Algoritmalar: yapı ve analiz, 3. baskı: Çev. İngilizce'den – M.: Williams, 2013. – 1328 s.
8. Shaidurov V.V. Çok ızgaralı sonlu elemanlar yöntemleri. – M.: Nauka, 1989. – 288 s.
9. Sturges H. (1926). Sınıf aralığı seçimi. J. Amer. Devletçi. Doç., 21, 65-66.

Anahtar kelimeler: sanal gerçeklik, belirli bir nokta dizisi üzerinde üçgenleme, Delaunay üçgenlemesi, dinamik üç boyutlu nesnelerin inşası.

Değiştirilmiş Delaunay'ın üçgenleme algoritması

Teplov A.A., Lisans, MSTU Bauman, "Yazılım ve Bilgi Teknolojileri" Bölümü, Moskova, [e-posta korumalı]

Maykov K.A., Teknik Bilimler Doktoru, Profesör, MSTU Bauman, "Yazılım ve Bilgi Teknolojileri" Bölümü, Moskova, [e-posta korumalı]

Soyut: Bu makalede, Delaunay'ın yüksek performans ve düşük kaynak tüketimi ile üçgenlemesinin neredeyse popüler yöntemlerinin karşılaştırmalı analizinin sonuçları açıklanmaktadır. Dinamik 3 boyutlu nesnelerin gerçek zamanlı olarak belirli bir ayrıntı düzeyiyle oluşturulması amacıyla daha fazla modernizasyon için yöntemin seçimi haklıdır. Fiberli iki geçişli Delaunay üçgenleme algoritmasının ana aşamalarından biri değiştirildi. Dağıtımın yoğunluğuna uygun olarak üçgenlemenin hücre dizisinin aralıklı bölümlenmesine yönelik bir algoritma önerisi mevcut olup, donanım uygulamasındaki hataların önlenmesine olanak sağlar.

Anahtar Kelimeler: sanal gerçeklik, belirli bir hücre dizisinde üçgenleme, Delaunay üçgenlemesi, dinamik 3 boyutlu nesnelerin oluşturulması.