Delaunay triangulation by divide- and -conquer technique

Abstract

Ö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.

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.