Delaunay triangulation by divide- and -conquer technique
Başlık çevirisi mevcut değil.
- Tez No: 15748
- Danışmanlar: PROF.DR. SELAHATTİN KURU
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Arazi modelleme, Delaunay üçgenleme, Nirengi ağları, Thiessen tessellasyonu, Terrain modelling, Delaunay triangulation, Triangulation network, Thiessen tessellation
- Yıl: 1991
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET Üçgenleştirilmiş Düzensiz Ağlarının Coğrafîk Veri Tabanlarında yüzey modellemesi amacıyla kullanımı gittikçe artmaktadır. Üçgenleştirilmiş Düzensiz Ağlar, üçgenlerin kesişmemesi ve modellenen arazideki düzensizlikleri tanımlayabilme özellikleri nedeni ile tercih edilmektedir. Arazi modellemesi için bu özellikleri sağlayan Delaunay uçgenlemesi yeterince uygundur. Delaunay üçgenlemesi doğrudan Thiessen tessellasyondaki komşuluklar kullanılarak oluşturulabilir yani eşçözümlerdir. Thiessen tessellasyonu bir düzlemdeki ana noktalara göre düzlemin etki alanlarına bölünmesidir. Şöyleki her ana noktaya ait olan düzlem parçası bu ana noktaya diğer ana noktalardan daha yakın olan konveks bir kapak bölgedir. Bu tezde verilen bir noktalar kümesi için düzlemi etki-bölgelerine ayıran bir algoritma tasarlanmış ve gerçeklenmiştir. Algoritmada Green ve Sibson'ın [1] önerdikleri bölümleme metodunun bir benzeri kullanılmıştır ve problemi parçalara ayırarak çözme tekniği eklenmiştir. Bu yöntemde etki-bölgelerine ayrılacak düzlem parçası ardışık olarak dörde bölünür, istenen küçüklüğe ulaşan alt düzlem parçası etki-bölgelerine ayrılır ve sonunda bitişik düzlem parçalan birleştirilerek nihai çözüm elde edilir. Algoritmanın performans ölçümleri ve alt parçalara ayırmadan yapılan tessellasyon ile karşılaştırması için değişik nokta kümeleri ile testler yapılmıştır. Bu testler sonunda önerilen algoritmanın böl-ve-çöz yöntemi ile performansının arttığı ve mertebesinin O(NlogN) olduğu bulunmuştur. Ayrıca böl-ve-çöz yöntemini kullanan algoritmanın gerçeklenmesi dörtlü ağaç veri yapışırım katkısı ile daha verimli sonuçlar verdi. Algoritma üzerinde gelecekte yapılabilecek çalışmalar olarak çoklu işlem yapan ortamlarda gerçeklenmesi ve analizinin yapılması önerilmektedir.
Özet (Çeviri)
IV ABSTRACT Triangulated Irregular Networks (TIN) are extensively used to represent surfaces in Geographic Information Systems. The surface is represented as a set of non-overlapping and irregularly shaped triangular facets. Delaunay triangulation satisfies such properties and is therefore considered well- suited as a basis for a surface model. Delaunay triangulation of a set of points is defined as the straight-planar dual of Thiessen tessellation which is a subdivision of the plane into polygons, each belonging to a point and defined as the planar region which is closer to the point than to any other point in the set. In this thesis-, we design and implement an algorithm which produces Thiessen tessellation of a planar region for a data set of points. The algorithm uses the idea of tessellation algorithm proposed by Green and Sibson [1] and introduces a divide-and-conquer technique. This technique divides the region into subregions, then tessellates the subregionsi and merges the resulting tessellation of the subregions. Several tests are performed on different data sets of points to see the performance of the algorithm and to compare the results of divide-and-conquer technique with the results of the method without decomposition. Comparison of the test results have shown that the proposed tessellation method by divide-and-conquer technique performed much better with order O(NlogN). A quadtree data structure is adopted to support devide-and-conquer technique. Implementation of the algorithm on a parallel proccessing environment is suggested as further studies.
Benzer Tezler
- Delaunay-based represantation of non-convex, multiply-connected planar domanis
Başlık çevirisi yok
UĞUR HAKAN ERES
Yüksek Lisans
İngilizce
1994
Makine MühendisliğiBoğaziçi ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. VAHAN KALENDEROĞLU
- Yükseklik eğrilerinin basitleştirilmesinde yeni bir yaklaşım
A New approach to simplification of contours
TÜRKAY GÖKGÖZ
Doktora
Türkçe
1999
Jeodezi ve FotogrametriYıldız Teknik ÜniversitesiJeodezi ve Fotogrametri Mühendisliği Ana Bilim Dalı
PROF.DR. MEHMET SELÇUK
- Development of a mesh generation software for computational electromagnetics
Bilişimsel elektromanyetik uygulamaları için bir ağ üretme yazılımının geliştirilmesi
BEKİR BARIŞ DÜNDAR
Yüksek Lisans
İngilizce
2000
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA KUZUOĞLU
- Unstructured grid genertion
Yapısız çözüm ağı üretimi
MEHMET COŞKUN
Yüksek Lisans
İngilizce
1994
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET Ş. ÜÇER
- Sayısal arazi modellerinden hacim hesaplarında en uygun enterpolasyon yönteminin araştırılması
Research of the most suitable interpolation method for volume determination in digital terrain models
MUSTAFA YANALAK
Doktora
Türkçe
1997
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiJeodezi ve Fotogrametri Mühendisliği Ana Bilim Dalı
PROF. DR. ORHAN BAYKAL
- A General unstructured mesh generation algorithm with its use in CFD applications
Hesaplama akışkanlar mekaniğindeki uygulamaları ile genel bir düzensiz ağ üretimi algoritması
B. KAAN KARAMETE
Doktora
İngilizce
1996
Mühendislik BilimleriOrta Doğu Teknik ÜniversitesiMühendislik Bilimleri Ana Bilim Dalı