Thiessen Poligon

Thiessen Poligon,Juga dikenal sebagai Voronoi

jaringan dan Delaunay triangulations poligon Thiessen

secara independen ditemukan di beberapa bidang studi,

termasuk klimatologi dan geografi. Mereka diberi nama

setelah climatologist yang digunakan mereka untuk

melakukan transformasi dari titik stasiun iklim DAS.

Poligon Thiessen dapat digunakan untuk menggambarkan daerah pengaruh

sebuah titik dalam satu set poin. Jika Anda mengambil satu set poin dan

menghubungkan setiap titik ke tetangga terdekat, Anda memiliki apa yang disebut

jaringan tidak teratur Triangulasi (TIN). Jika Anda membagi dua masing-masing

menghubungkan segmen garis tegak lurus dan membuat poligon tertutup dengan

bisectors tegak lurus, hasilnya akan menjadi serangkaian poligon Thiessen. Daerah

yang terkandung dalam setiap poligon adalah lebih dekat ke titik poligon yang

didasarkan daripada titik lain di dataset.

Apa Apakah Mereka Digunakan Untuk?

Jika Anda memiliki kumpulan fitur atau peristiwa yang digambarkan sebagai

titik dan Anda ingin menentukan wilayah pengaruh setiap peristiwa atau fitur ini,

Anda dapat membuat satu set poligon Thiessen berdasarkan poin.

Sebuah Contoh

Misalkan Anda bekerja untuk sebuah kota dan Anda ingin tahu daerah

tangkapan air untuk setiap perpustakaan di kota Anda - yaitu, daerah yang berasal dari

pengguna perpustakaan. Jika Anda memiliki sebuah perpustakaan dengan daerah

tangkapan air yang sangat besar, Anda mungkin ingin mempertimbangkan untuk

membangun sebuah perpustakaan baru.

Ada beberapa cara berbeda anda dapat menghitung ini, tergantung pada

seberapa banyak Anda tahu tentang masing-masing perpustakaan dan berapa banyak

waktu dan uang yang Anda miliki.

Anda bisa saja mengatakan bahwa daerah tangkapan air untuk masing-masing

perpustakaan adalah sebuah lingkaran dengan radius 5 kilometer, berpusat pada

masing-masing perpustakaan. Namun, jika Anda memiliki dua perpustakaan lebih

dekat daripada 5 kilometer satu sama lain, Anda telah tumpang tindih, yang mungkin

akurat, tapi tidak memberikan Anda sebuah zona eksklusif untuk masing-masing

perpustakaan. Jika perpustakaan tersebar, Anda akan memiliki area yang tidak berada

dalam zona tangkapan untuk setiap perpustakaan - sebenarnya, jika Anda tidak dapat

tumpang tindih lingkaran, akan selalu ada daerah yang tidak dalam setiap daerah

tangkapan. Jadi, sementara itu mudah untuk membuat lingkaran (dan Anda bahkan

tidak memerlukan komputer untuk membuat mereka), hasilnya akan menjadi miskin,

di terbaik.

Anda dapat melakukan survei pelanggan perpustakaan untuk mencari tahu di

mana mereka tinggal. Kemudian Anda dapat merencanakan titik-titik dan mencoba

untuk menciptakan sebuah choropleth peta . The downside ke ini adalah bahwa Anda

harus memastikan orang-orang hanya merespons pada satu perpustakaan. Masalah lain

termasuk fakta bahwa beberapa orang tidak suka survei untuk alasan apapun dan tidak

akan menjawab atau akan berbohong tentang di mana mereka tinggal. Survei juga

mahal dan membutuhkan waktu untuk melakukan. Anda juga harus

mempertimbangkan waktu dalam tahun karena mungkin ada musiman. Anda mungkin

juga menerima tanggapan dari orang-orang yang pergi ke perpustakaan yang sedang

dalam perjalanan untuk bekerja, bukan satu yang terdekat ke rumah mereka. Sebuah

survei yang dikelola dengan baik dapat memberikan data berkualitas sangat tinggi,

tapi pada biaya waktu dan uang.

Atau Anda dapat membuat poligon Thiessen untuk masing-masing

perpustakaan. Ini bisa menunjukkan perpustakaan di mana Anda mungkin ingin

menjalankan sebuah survei untuk lebih baik menentukan daerah resapan untuk

cabang-cabang itu pada khususnya. Sebenarnya melakukan operasi poligon Thiessen

dalam suatu sistem informasi geografis (GIS) adalah masalah yang relatif sepele

sekali Anda memiliki poin Anda, jadi Anda mungkin akan memaksimalkan

pengembalian waktu dan uang, yang keduanya akan menjadi kecil dibandingkan

dengan berjalan survei. Dan jika Anda ingin memperbaiki kualitas daerah tangkapan

gambaran, Anda dapat memberlakukan Anda jaringan jalan kota sehingga daerah

resapan ditentukan oleh jalan daripada batas-batas poligon murni.

Catatan: Bagian ini menggunakan simbol-simbol yang mungkin tidak ditampilkan

dengan benar di semua browser.

Boots (lihat Bibliografi bawah) secara resmi poligon Thiessen menjelaskan demikian:

Pertimbangkan satu set, S, n dicap poin dalam pesawat, di mana

S = { p 1 , p 2 , … p n } S = (p 1, p 2, ... p n)

Dengan masing-masing titik, p i, dalam S kita kaitkan semua lokasi, x, di

pesawat yang lebih dekat dengan p i daripada titik lainnya, p j, di S (j ≠ i). Hasilnya

adalah untuk menciptakan sebuah poligon Thiessen, P i.Lebih formal, jika d (x, i)

adalah jarak Euclidean dari x ke p i lalu

P i = { x|d(x,i) ≤ d(x,j); j ∈ S, j ≠ i} P i = (x | d (x, i) ≤ d (x, j); j ∈ S, j ≠ i)

Ada kemungkinan bahwa x adalah jarak yang sama dari sepasang poin, dalam

hal ini akan terletak pada batasan dari P i. Selain itu, x mungkin akan berjarak sama

dari tiga atau lebih titik sehingga membentuk salah satu simpul dari P i.

Jika poligon Thiessen diciptakan untuk semua titik dalam S, maka dihasilkan set

poligon

{ P 1 , P 2 , … P n }, (P 1, P 2, ... P n),

bentuk yang unik, susunan ruang-lengkap tessellation dikenal sebagai Thiessen

(Voronoi) diagram S, V (S).

Dengan kata lain, daerah yang terkandung dalam poligon Thiessen cenderung

lebih representatif dari titik poligon yang didasarkan dari titik lain dalam himpunan

tersebut.

Membangun Thiessen Poligon Wizard

Membangun Thiessen Poligon dari lapisan fitur

Thiessen (Voronoi) poligon define daerah masing-masing pengaruh sekitar

masing-masing satu set poin. Poligon Thiessen adalah poligon yang menentukan

batas-batas wilayah yang terdekat dengan setiap titik relatif terhadap semua poin

lainnya. Mereka secara matematis didefinisikan oleh bisectors

Input:

Fitur lapisan (Point, Polyline, Polygon)

Keluaran

Fitur poligon kelas baru.

o Jika atribut Lampirkan pilihan tersebut ditetapkan, atribut dari fitur

sumber ditransfer ke tabel atribut baru.

Catatan:

Proses berjalan melalui beberapa langkah

o Mengumpulkan poin dari lapisan titik (simpul jika sumber adalah

Polyline atau poligon layer)

o Duplikat bersih poin

o Menghasilkan Convex Hull

o Menciptakan struktur TIN

o Tegak lurus menghasilkan timah bisectors untuk setiap tepi.

o Membangun poligon Thiessen

o Klip poligon Thiessen fitur di kelas dengan hull cembung.

Untuk mencapai hasil terbaik ketika membuat Poligon Thiessen dari lapisan

Polyline menggunakan polylines generalisasi Polyline Densify Wizard atau

Wizard (sebelum menjalankan prosedur Poligon Thiessen) untuk menghapus

atau menambahkan titik-titik yang tidak perlu menunjuk ke segmen lurus

panjang

Secara default adalah poligon Thiessen dijepitkan di Convex Hull dari fitur

input. Ada pilihan untuk buffer yang cembung lambung sebelum kliping

dengan itu.

Kelas Fitur yang dihasilkan dapat dijepit (Klip Layer Wizard) dengan lapisan

poligon untuk mach bentuk lapisan ini.

Jika sumber adalah poligon Polyline atau lapisan, hanya atribut pertama

ditemukan di dalam masing-masing fitur poligon Thiessen akan ditransfer.

Fungsi harus bekerja tanpa masalah pada dataset dengan sampai 2 juta poin.

Contoh-contoh penggunaannya:

Mendefinisikan daerah perdagangan

Dari satu set titik-titik pengambilan contoh tanah untuk mendefinisikan

poligon non tumpang tindih untuk masing-masing jenis tanah

Contoh:

Point Koleksi Cembung Hull Thiessen Poligon

Breaklines

Sebuah breakline adalah fitur Polyline mewakili baris atau saluran sungai,

punggung bukit atau fitur lain yang ingin Anda mempertahankan di TIN. Dengan kata

lain, sebuah breakline adalah serangkaian tepi bahwa segitiga harus sesuai. Breaklines

dapat sangat berguna ketika mencoba untuk menghilangkan lubang-lubang yang tidak

diinginkan pada interior sebuah TIN.

Breaklines dapat diproses menggunakan Segitiga | Sisipkan Breakline (s)

perintah dari menu TIN. Sebelum memilih perintah, satu atau lebih rangkaian simpul

mendefinisikan breakline (s) harus dipilih menggunakan simpul Pilih alat di Tool

Palette.

Breakline Pilihan

Pilihan - Pilihan Breakline dikontrol dalam TIN Pilihan dari menu TINS.

Dialog ini membolehkan Anda untuk menetapkan baik untuk interpolasi nilai z dari

TIN yang ada atau untuk mendapatkan nilai z dari fitur busur. Di ketinggian vertices

baru didasarkan pada interpolasi linear dari segmen breaklineLokasi simpul baru

ditentukan sedemikian rupa sehingga kriteria Delauney puas.

Delaunay Triangulasi

Seperti yang saya bahas dalam posting sebelumnya, TIN (Segitiga Irregular

Network) penciptaan adalah suatu seni. Tapi seni berakar tertanam kuat di

matematika.

Triangulasi pertama program jaringan tidak teratur ditulis oleh Randolph

Franklin di Simon Fraser University di tahun 1973 dan didasarkan pada konsep

Triangulasi Delaunay. Metode triangulasi adalah bagaimana membangun 3D Sipil

TIN.

Triangulasi metode yang diciptakan oleh Boris Delaunay pada tahun 1934.

Berdasarkan definisinya, yang circumcircle (Lingkaran yang melewati semua vertices

dari sebuah poligon, dalam kasus ini, sebuah segitiga) dari sebuah segitiga yang

dibentuk oleh tiga poin tidak dapat berisi poin (atau simpul) selain dari tiga yang

mendefinisikannya. Poin lain hanya diperbolehkan di perimeter, atau "perbatasan" dari

permukaan.

Circumcircle

Triangulasi Delaunay

Kegunaan Triangulasi Delaunay hanya sebaik poin dianalisis secara

matematis. Lebih poin = lebih baik triangulasi (untuk gelar, tentu saja). Untuk tujuan

kita, itu berarti lebih mewakili gambar yang diambil di lapangan medan yang

sebenarnya, semakin baik triangulasi. Bad shots = bad triangulation. Buruk tembakan

= buruk triangulasi. Tujuan dari survei topografi yang baik adalah untuk

mengumpulkan sebanyak mungkin informasi tentang perubahan fitur mungkin. Sipil

3D, titik-titik tersebut dianalisis oleh berbagai algoritma matematika, dan hasilnya

adalah Delaunay Triangulasi. Breaklines dan perbatasan ditambahkan secara manual

(atau melalui perintah angka) sebagai sarana untuk membangun jalan setidaknya dua

sudut dari sebuah segitiga harus mengambil, bahkan jika yang mengarah pada

pelanggaran Delaunay.

Algoritma yang melakukan matematika melakukan bagian yang sulit.

Perhatikan Aku sudah tidak membuat perbedaan antara "ada" segitiga, atau

"diusulkan" segitiga. Perangkat lunak tidak peduli, itu hanya melakukan analisis

matematis. Oleh karena itu, ketika pemodelan medan, anda dapat menggunakan

semua alat yang Anda miliki ke model kedua. Dalam pemodelan tanah yang ada,

Anda dibatasi oleh fitur yang ada secara fisik. Dalam mengusulkan pemodelan tanah,

Anda hanya dibatasi oleh pendekatan kreatif dan pengetahuan tentang perangkat

lunak, dan alat analisis yang digunakannya.

Delaunay triangulasi adalah dihargai secara luas dan diselidiki model

matematika untuk permukaan topografi perwakilan. Setelah beberapa deskripsi

teoretis, enam mungkin algoritma dasar untuk membangun sebuah triangulasi

Delaunay dianalisis dan properti yang dapat dimanfaatkan untuk pengolahan data

multibeam echosounder diselidiki. Dua konsep akan diperlakukan secara lebih

mendalam: yang membagi-dan-menaklukkan konstruksi algoritma dan metode

inkremental. Perhitungan kecepatan membagi-dan-metode menaklukkan membuat

calon yang ideal untuk membangun awal dari multibeam triangulasi data. Kinerja

runtime nya dibandingkan dengan algoritma inkremental untuk menunjukkan hal ini.

Algoritma's menggabungkan langkah tampaknya juga berguna di bidang Triangulasi

menggantikan yang ada triangulations oleh data baru. Algoritma Kenaikan tampaknya

tidak metode konstruksi yang efektif tetapi dapat dengan mudah disesuaikan untuk

mengakomodasi individu penyisipan simpul ke triangulasi dan yang sudah ada, karena

itu berguna untuk keperluan pengeditan.

Interpolasi

Interpolasi adalah prosedur untuk menduga nilai-nilai yang tidah diketahui

dengan menggunakan nilai yang berdekatan. Titik-titik yang berdekatan tersebut dapat

teratur atau tidak teratur. Gambar 8.8 merupakan contoh sederhana penerapan fungsi

interpolasi yang digambarkan dalam bentuk layer raster. Suatu fungsi linier sederhana

digunakan untuk menurunkan nilai-nilai sel yang belum diketahui berdasarkan nilai-

nilai sel yang diketahui. Program-program interpolasi telah banyak dikembangkan

seperti regresi polinomial, seri fourier, fungsi, pergerakan rata-rata, kriging, dan

sebagainya.

Mempelajari berbagai metode Interpolasi yang ada untuk menentukan titiktitik

antara dari n buah titik dengan menggunakan suatu fungsi pendekatan tertentu.

Metode Interpolasi yang dipelajari :

1. Interpolasi Linier

2. Interpolasi Kuadratik

3. Interpolasi Polinomial

4. Interpolasi Lagrange

Interpolasi Linier

Menentukan titik-titik antara dari 2 buah titik dengan menggunakan garis

lurus.

Persamaan garis lurus yang melalui 2 titik P1(x1,y1) dan P2(x2,y2) dapat dituliskan

dengan:

Sehingga diperoleh persamaan dari interpolasi linier sebagai berikut:

Algoritma Interpolasi Linier :

(1) Tentukan dua titik P1 dan P2 dengan koordinatnya masing-masing (x1,y1) dan

(x2,y2)

(2) Tentukan nilai x dari titik yang akan dicari

(3) Hitung nilai y dengan :

(4) Tampilkan nilai titik yang baru Q(x,y)

Interpolasi Kuadratik

Interpolasi Kuadratik digunakan untuk mencari titik-titik antara dari 3 buah

titik P1(x1,y1), P2(x2,y2) dan P3(x3,y3) dengan menggunakan pendekatan fungsi

kuadrat.

Untuk memperoleh titik Q(x,y) digunakan interpolasi kuadratik sebagai berikut:

Algoritma Interpolasi Kuadratik:

(1) Tentukan 3 titik input P1(x1,y1), P2(x2,y2) dan P3(x3,y3)

(2) Tentukan nilai x dari titik yang akan dicari

(3) Hitung nilai y dari titik yang dicari menggunakan rumus dari interpolasi kuadratik:

(4) Tampilkan nilai x dan y

Interpolasi Polinomial

Interpolasi polynomial digunakan untuk mencari titik-titik antara dari n buah

titik P1(x1,y1), P2(x2,y2), P3(x3,y3), …, PN(xN,yN) dengan menggunakan

pendekatan fungsi polynomial pangkat n-1:

Masukkan nilai dari setiap titik ke dalam persamaan polynomial di atas dan diperoleh

persamaan simultan dengan n persamaan dan n variable bebas:

Penyelesaian persamaan simultan di atas adalah nilai-nilai a0, a1, a2, a3, …,

an yang merupakan nilai-nilai koefisien dari fungsi pendekatan polynomial yang akan

digunakan.

Dengan memasukkan nilai x dari titik yang dicari pada fungsi polinomialnya, akan

diperoleh nilai y dari titik tersebut.

Algoritma Interpolasi Polynomial :

(1) Menentukan jumlah titik N yang diketahui.

(2) Memasukkan titik-titik yang diketahui Pi = (xi , yi) untuk i=1,2,3,…,N

(3) Menyusun augmented matrik dari titik-titik yang diketahui sebagai berikut:

(4) Menyelesaikan persamaan simultan dengan augmented matrik di atas dengan

menggunakan metode eliminasi gauss/Jordan.

(5) Menyusun koefisien fungsi polynomial berdasarkan penyelesaian persamaan

simultan di atas.

(6) Memasukkan nilai x dari titik yang diketahui

(7) Menghitung nilai y dari fungsi polynomial yang dihasilkan

(8) Menampilkan titik (x,y)

Interpolasi Lagrange

Interpolasi polynomial digunakan untuk mencari titik-titik antara dari n buah

titik P1(x1,y1), P2(x2,y2), P3(x3,y3), …, PN(xN,yN) dengan menggunakan

pendekatan fungsi polynomial yang disusun dalam kombinasi deret dan didefinisikan

dengan:

Algoritma Interpolasi Lagrange :

(1) Tentukan jumlah titik (N) yang diketahui

(2) Tentukan titik-titik Pi(xi,yi) yang diketahui dengan i=1,2,3,…,N

(3) Tentukan x dari titik yang dicari

(4) Hitung nilai y dari titik yang dicari dengan formulasi interpolasi lagrange

(5) Tampilkan nilai (x,y)