Geri Dön

Sayısal arazi modellerinde eğri yerleştirme yöntemleri

Curve fitting methods in digital terrain models

  1. Tez No: 18824
  2. Yazar: ERGİN TARI
  3. Danışmanlar: PROF.DR. ORHAN BAYKAL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Jeodezi ve Fotogrametri, Geodesy and Photogrammetry
  6. Anahtar Kelimeler: Eğri yerleştirme yöntemleri, Sayısal arazi modelleri, Curve fitting methods, Digital terrain models
  7. Yıl: 1991
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

ÖZET Sayısal Arazi Modeli, arazi üzerinde dağılmış koordinatları ve yükseklikleri bilinen noktalardan yararlanarak bilgisayar yardımı ile arazinin sayısal olarak gösterilmesidir. Sayısal arazi modeli, sayısal durum modeli ve sayısal yükseklik modelinden oluşur. Bir çok çalışmaya altlık oluşturan sayısal arazi modelinin etkin bir şekilde oluşturulması gerekir. Sayısal arazi modelinin oluşturulmasında kullanılan yazılım bu etkinliği sağlayan temel unsurdur. Yazılımın etkinliğini ise bellek ve hız para metrelerinin uygun kullanımı sağlar. Hız parametresini etkileyen en önemli faktör de bilgilere ulaşımdır. Bilgilere ulaşımın en hızlı şekilde yapılabilmesi ise bu bilgilerin belli bir düzende sıralanmış olmasına bağlıdır. Sayısal arazi modeli gibi bilgileri tekrar tekrar sıralamayı gerektiren uygulamalarda ise sıralama işleminin bellek ve hız optimizasyonunu sağlaması önemlidir. Sayısal yükseklik modelinde enterpolasyon sonucu elde edilen aynı kotlu noktaların birleştirilmesi işlemi bir eğri yerleştirme işlemidir. Eğri yerleştirme, en küçük kareler yöntemi ile 2. dereceden bir polinom, 3. ve daha yüksek dereceli bir polinom veya trigonometrik polinomlar kullanılarak gerçekleştirilebilir. Polinomlar ile eğri yerleştirmenin polinom salınımı adı verilen bir sakıncası Spline Fonksiyonlarının kullanılmasını gerektirir. Spline fonksiyonlarında da temelde polinom yaklaşımı kullanılır. Ardışık noktalar arasında oluşturulan grafik parçalarını birleştirmek temelinden yola çıkarak ortaya konan spline fonksiyonlarının en çok kullanılan. kübik spline fonksiyonlarıdır. önemi nedeni ile burada sıralama ve eğri yerleştirme yöntemleri üzerinde ayrıntılı bir biçimde durulmuştur. Literatürde verilen sıralama yöntemleri hız açısından karşılaştırılmış hangisinin Sayısal Arazi modeli için uygun ola cağı araştırılmış ayrıca sıralama için bir yöntem verilmiş tir. Sayısal yükseklik modelinde enterpolasyon sonucu elde edilen aynı kotlu noktalardan dengeleyen polinomların geçirilmesi sakıncası bir örnek ile gösterilmiştir. v

Özet (Çeviri)

SUMMARY CURVE FITTING METHODS IN DIGITAL TERRAIN MODELS Digital terrain model is a digital representation of the terrain, based on measurements on the reference points by means of a detailed computer program series named software. Digital terrain model software which serves for a wide range engineering, area must be planned for using optimum computer memory and providing maximum speed. Using computer memory is the subject of modern memory storing methods. Providing maximum speed depends on the form of arranging of the knowledge. In our study know ledge is generally in the form of numbers which are x,y planimetric coordinates or h coordinates. The best way to get over the problem of loosing time is arranging the knowledge in a desired order. This arranging procedure is called sorting. If an element in an unsorted list of n elements is searched, the maximum number of comparisons is n. When a sorted list of n elements is searched for an element, the maximum number of comparisons in a searching method called“binary search”is, (k is the number of comparison) k= log2n This number k is very attractive and always desired. Sorting must be managed properly in order to make searching so fast. In the studies, which require sorting many times, like digital terrain model the speed of sorting is very important. There are some algorithms for making faster sort. They can be written as follows, 1. Bubble Sort 2. Selection Sort 3. Insertion Sort 4. Shell Sort 5. Heap Sort 6. Quick Sort vi1- Bubble. Sort This algorithm is the best known and the most infamous sorting algorithm. Its popularity is derived from its catchy name and its simplicity. The bubble sort algorithm uses the exchange method of sorting. The general concept behind the bubble sort is the repeated comparisons and, if necessary, exchanges of adjacent elements. 2- Selection Sort In this algorithm, the element with the lowest value is selected and exchanged with the first element. Then from the remaining elements, the element with the least key is found and exchanged with the second element, and so forth, up to the last two elements. 3- Insertion Sort This algorithm initially sorts the first two members of the array. Next, the algorithm inserts the third member into its suitable position in relation to the first two members. Then, the fourth element is inserted into the list of three elements. And the process continues until all elements have been sorted. 4- Shell Sort This algorithm, derived from insertion sort, is based on diminishing increments. In this algorithm, all elements that are n/2 positions (n is the number of elements of array) apart are sorted. Then all elements that are n/4 positions apart from the first step are sorted. The process continues and finally, all those adjacent to each other (1 positions apart) are sorted. 5- Heap Sort First we have to define what a heap is. If an array a, given with n elements, satisfies the relation a. > a. for 1 < j/2 <j <N then this array is said“heap”. If rearranging the array into an order that forms a heap is managed, then sorting becomes very easy. The top of the heap, which is the largest element yet unsorted is pulled off. Then its largest underling is promoted to the top of the heap. Next its largest underling is promoted, and so on. 6- Quick Sort This algorithm is the best sorting algorithm currently available. Algorithm's basic idea is partition. vııThe general procedure is to select a value and then to partition the array into two parts with all elements greater than or equal to the partition value on one side and those less than the partition value on the other. This process is then repeated for each remaining part until the array is sorted. In digital terrain models, after the interpolation in digital elevation model/ interpolation of curves is considered. In general, interpolation of curves is said curve fitting. The best known curve fitting method is the method of least-squares curve fitting. This method can be extended to many nonlinear cases. These cases can be written as exponential fitting and polynomial fitting. The exponential fitting requires the data to fit an exponential function like y=C.exp (Ax). But this is not an efficient way for contouring which does not fit in any function. A product of polynomial fitting, which is called spline function, have the solution of the problem of polynomial wiggle. Polynomial wiggle becomes an important constraint not to use a polynomial of degree 6 or above unless it is known that the true function, which is studied, is a polynomial. A polynomial of degree N can have N-l relative maxima and minima and the graph can wiggle in order to pass through the points. Another method is to“piece together”the graphs of lower degree polynomials S, (x) and inter polate between the successive nodes (x,,y, ) and (x,,,y, i ). (Figure 1) The reason of using lower degree polynomials is preventing the polynomial wiggle. <**. f*l 1*0. K0> YU-\i («i.K|l (*». KW) *0 *2 **f! *tt-\ *1 Figure 1. Piecewise Polynomial Interpolation VlllThe two adjacent portions of the curve y=S, (x) and y=Sk+1(x), which lie above lxk>xk+1l and, lxk+1'xk+2l' respectively, pass through the common knot (x,, /yk + -i ). The two portions of the graph are“tied together”at the knot (x,+,,y,+,) and the set of functions Is, (x) } form a piecewise polynomial curve which is denoted by S (x). Mathematically, it is possible to construct a cubic functions S, (x) on each interval |x,,x,. | so that the resulting piecewise curve y=S(x) and its first and second derivatives are all continous on the larger interval |x,x |. The continuity of S' (x) means that the graph Y=S (x) will not have sharp corners. The continuity of S“ (x) means that the ”radius of curvature“ is defined at each point. Let us consider the N+l points{s (x,,y,) } where the abscissas are ordered x < x. <...<xN. The function S (x) is called a cubic ° spline if there exist N cubic polynomials S, (x) such that: I- S(x)=Sk(x)=Sk/0 + Skfl(x-xk)+Sk^(x-xk)2 +.3 +Sk,3(x_xk) for x in |xkrXk+1| and k=0,l,...,N-1 II- S(xk)=yk for k=0,l,...,N The spline passes through each data point. Ill- sk(xk+1)=sk+1(xk+1) for k=0,l,...,N-2. The spline forms a continuous function IV- sk(xk+1)=Sk+1(xk+1) for k=0,l,...,N-2 The spline forms a smooth function. V”Sk(xk+l)=Sk+l(xk+l} for k=0,l,...,N-2. The second derivative is continuous. Since S (x) is piecewise cubic, its second derivative S“ (xlJ is piecewise linear on |x fXN|. The linear lagrange interpolation formula gives the following representation for S”(x) =SJ“ (x) : X-X x-X, S”(x)=S“(x ) J-i +S”(x.+1) ^ x x y _x,, k+1 v _y Xk Ak+1 Xk+1 -Xk IXUsing mk=s;'(x ), mk+1=S« (xk+1) and hk=xk+1-xk in this equation yields, mk mk+l sk(x)= h^ (xk+ı“xî+-h7 {x-xk} for x.« x «xv, and k=0, 1,...,N-1. Integrating last equation twice will gives two constants of integration, and the result can be manipulated so that it has the form, sk(x)= \ (3W-*>3± ^(x-xk)3+Pk(xk+i-x) + +qk(x-Xk) Substituting xk and xk+^ into equation and using the values Yk=Sk(xk) and yk+1=Sk (x..,) yields the following equations that involve p, and q,, respectively: mk 2 ”hc+l 2 *k= ~6 hk+Pkhk- and ^1= -6~ hk 4 %hK Solving these two equations for p, and q;- -results the following expression for the cubic fonction S. (x) : k k k k + (5sîL.-3s±A,(M, \ 6 MX xk; Using the derivatives of these equation, an ^equation involving the unknown coefficients m,.,, m,, m, can be written as follows: K~1 K k+1 VlV-l*2 ^k-l^k^^k^l^k where Uk=6 (dk;-dk_1) for k=l,2,,N-1. After the coefficients ü\} are determined by using above equation and endpoint constraints, the spline coefficients {Sk.} for S^(x) are computed using the formulas; hk(2mk+mk+l) \,o~ yk ' Sk,l“ dk 6 s 5k q Vi”^ ök,2~ 2 ' bk,3= 6h^ xEach cubic polynomial S, (x) can be written in nested multiplication from: Sk(x)t=|(Sk 3w+Sk 2)w"sk il w+yk wnere w=x-xk arid S, (x) is used on the internal x,g x ^x,.. XI

Benzer Tezler

  1. Tez No

    34794

    Klasik jeodezik ölçmelerle sayısal arazi modelleri

    Başlık çevirisi yok

    MÜNEVVER ÇETİNER

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Jeodezi ve FotogrametriYıldız Teknik Üniversitesi

    Jeodezi ve Fotogrametri Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET SELÇUK

  2. Tez No

    90665

    A Remole sensing and geopraphic information systems approach in hydrologic modeling-a case study

    Hidrolojik modellemede uzaktan algılama ve coğrafi bilgi sistem tekniklerinin kullanılması-bir uygulama çalışması

    ALİ ARDA ŞORMAN

    Yüksek Lisans

    İngilizce

    İngilizce

    1999

    İnşaat MühendisliğiOrta Doğu Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. ALİ ÜNAL ŞORMAN

  3. Tez No

    34367

    Sayısal arazi modellerinde hassasiyet analizi ve enterpolasyon yöntemleri

    Height interpolation and accuracy analyst of contour for digital terrain model

    TANER ÜSTÜNTAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Jeodezi ve FotogrametriSelçuk Üniversitesi

    Jeodezi ve Fotogrametri Ana Bilim Dalı

    PROF. ÖMER HALİS TOMBAKLAK

  4. Tez No

    34746

    Sayısal arazi modellerinde kullanılan kayan yüzeyler ve doğrusal enterpolasyon uygulamaları

    Başlık çevirisi yok

    UĞUR ACAR

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Jeodezi ve FotogrametriYıldız Teknik Üniversitesi

    Kartoğrafya Ana Bilim Dalı

    PROF. DR. MEHMET SELÇUK

  5. Tez No

    68886

    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

    Türkçe

    1997

    Jeodezi ve Fotogrametriİstanbul Teknik Üniversitesi

    Jeodezi ve Fotogrametri Mühendisliği Ana Bilim Dalı

    PROF. DR. ORHAN BAYKAL

Geri Dön