ANALISIS PENCARIAN JALUR JALAN DALAM KAMPUS ITB DENGAN MENGGUNAKAN BASIS DATA SPASIAL 3 DIMENSI
TUGAS AKHIR Karya tulis sebagai salah satu syarat untuk memperoleh gelar Sarjana
Oleh GINANJAR 151 02 037
Program Studi Teknik Geodesi dan Geomatika
Fakultas Ilmu dan Teknologi Kebumian
INSTITUT TEKNOLOGI BANDUNG 2008
Lembar Pengesahan Tugas Akhir Sarjana
ANALISIS PENCARIAN JALUR JALAN DALAM KAMPUS ITB DENGAN MENGGUNAKAN BASIS DATA SPASIAL 3 DIMENSI Adalah benar dibuat oleh saya sendiri dan belum pernah dibuat dan diserahkan sebelumnya, baik sebagian maupun seluruhnya, baik oleh saya maupun orang lain, baik di ITB maupun di institusi pendidikan lainnya. Bandung, Juni 2008 Penulis
Ginanjar NIM. 151 02 037 Bandung, Juni 2008 Pembimbing
Dr. Ir. Deni Suwardhi, MT. NIP. 132 148 073 Mengetahui: Program Studi Teknik Geodesi dan Geomatika Ketua,
Dr. Ir. Wedyanto Kuntjoro, M.Sc. NIP. 131 690 328
i
You only see what your eyes want to see
“… Allah akan meninggikan orang-orang yang beriman di antaramu dan orangorang yang diberi ilmu pengetahuan beberapa derajat. Dan Allah Maha Mengetahui apa yang kamu kerjakan.” (Al-Mujaadilah: 11)
"…Tuhanku, tambahkanlah kepadaku ilmu pengetahuan." (Thaahaa: 114)
Ku persembahkan untuk keluarga tercinta : Papah, Mamah, Bilan, Rery.
ii
KATA PENGANTAR
Alhamdulilahrobbil‟alamin, puji syukur penulis panjatkan ke hadirat Allah SWT yang telah melimpahkan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan tugas akhir ini. Tugas akhir dengan judul “Analisis Pencarian Jalur Jalan Dalam Kampus ITB Dengan Menggunakan Basis Data Spasial 3 Dimensi” semoga dapat memberi kontribusi nyata bagi setiap individu khususnya untuk keperluan pengembangan SIG 3D. Tugas akhir ini tidak terlepas dari bantuan dan dukungan banyak pihak. Untuk itu penulis sangat berterimakasih kepada : 1. Dr. Ir. Deni Suwardhi, MT. selaku pembimbing yang telah meluangkan banyak waktunya untuk berdiskusi. 2. Dr.Ir. Bambang Setyadji, MT. selaku dosen wali penulis yang banyak membantu penulis selama masa perkuliahan. 3. Dr.Ir. D. Muhally Hakim, M.Sc., Dr.Ir. Agung Budi Harto, M.Eng, dan Dr.Ir. Bambang Setyadji, MT. selaku dosen penguji yang telah banyak memberikan kritik dan masukan. 4. Dr.Ir. Wedyanto Kuntjoro, M.Sc selaku Ketua Program Studi Teknik Geodesi dan Geomatika. 5. Dosen-dosen Program Studi Teknik Geodesi dan Geomatika. 6. Staf tata usaha dan perpustakaan Program Studi Teknik Geodesi dan Geomatika. Penulis menyadari perkembangan teknologi tidak akan terlepas dari koreksi dan revisi. Oleh karenanya, penulis mengharapkan berbagai koreksi membangun agar dapat diperbaiki untuk penelitian berikutnya.
Bandung, Juni 2008
Penulis
iii
LEMBAR PENGHARGAAN
Selama pengerjaan tugas akhir ini, penulis mendapatkan bantuan, dorongan, bimbingan dan pengarahan dari berbagai pihak. Oleh karena itu pada kesempatan ini penulis mengucapkan rasa terima kasih dan penghargaan kepada: 1. Papah&Mamah yang telah memberikan segalanya lahir dan bathin, entah dengan apa ku membalas, rasanya 100thn umur ku tuk mengabdi tiada kan cukup. 2. Kedua adik ku: Bilan&Rery yang selalu memberikan warna hidup yang berbeda. Tanpa kalian hidup ku terasa hampa. 3. Keluarga besar Papah&Mamah, DayeuhKolot dan Banjaran. Almarhum (ma‟nini) ta‟kan kulupakan segala nasehat yang diberikan. 4. IMG atas tempatnya untuk belajar dan bermain. Takan kulupakan seluruh kejadian selama bersama mu (IMG). Seluruh Kamerad IMG, mulai kamerad yang telah lama ada dan kamerad yang baru... Dan kepada semua pihak yang memiliki konstribusi dalam penyusunan tugas akhir ini yang tidak dapat penulis sebutkan satu persatu, penulis ucapkan terima kasih.
iv
ABSTRAK Pencarian jalur jalan merupakan salah satu analisis yang dilakukan dalam SIG. Analisis penelusuran jalur saat ini masih menggunakan data 2D yang tidak mencukupi untuk melakukan analisis keadaan dunia nyata (3D), karena objek 3D yang direpresentasikan dalam 2D akan mengalami kekurangan informasi spasial beserta hubungan dengan objek lainnya. Penelusuran jalur pada SIG secara konseptual memiliki prinsip dasar yang sama, yaitu menerapkan teori Graf kedalam jaringan jalan. Untuk melakukan analisis pencarian jalur jalan, digunakan algoritma Dijkstra, A* dan Shooting*. Kemudian dibentuk sebuah purwarupa database untuk keperluan navigasi di kampus ITB. Dari proses ini pencarian jalur 3D dapat dilakukan dalam sebuah SIG. Kata kunci : SIG, 3D, basis data, algoritma pencarian jalur.
v
ABSTRACT Seeking of a path is one of analysis performed within SIG. Now days, the shortest path analysis using data 2D is still insufficient to do analysis of real world (3D) conditions, because 3D objects representation in 2D will be lack it‟s spasial information and its relation with other objects. Shortest path in GIS conceptually has the same basic principle that is applying graph theory on street network. To do seeking analysis of road, applied algorithm Dijkstra, A* and Shooting*. Then is formed a prototype database for navigation in campus ITB. From this process seeking of line 3D can be done in GIS. Key word : GIS, 3D, database, algorithm shortest path.
vi
DAFTAR ISI Halaman LEMBAR PENGESAHAN .................................................................................... i KATA PENGANTAR .......................................................................................... iii LEMBAR PENGHARGAAN ............................................................................. iv ABSTRAK ............................................................................................................. v ABSTRACT .......................................................................................................... vi DAFTAR ISI ........................................................................................................ vii DAFTAR GAMBAR ............................................................................................ ix DAFTAR TABEL................................................................................................. xi BAB 1 PENDAHULUAN ..................................................................................... 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7
Latar Belakang ............................................................................................ 1 Rumusan Masalah ....................................................................................... 2 Maksud dan Tujuan ..................................................................................... 2 Ruang Lingkup ............................................................................................ 2 Kemanfaatan ............................................................................................... 3 Metodologi Penelitian ................................................................................. 3 Sistematika Pembahasan ............................................................................. 4
BAB 2 TEORI DASAR ......................................................................................... 6 2.1 Pemodelan Basis Data ................................................................................. 6 2.1.1 Model Entity-Relationship (ER) ......................................................... 6 2.1.2 Diagram Entity Relationship (ER) .................................................... 10 2.2 Pengenalan Peta Dijital ............................................................................. 10 2.2.1 Model Data Vektor............................................................................ 11 2.2.1.1 Model Data Spaghetti................................................................ 11 2.2.1.2 Model Data Vektor Dengan Topologi....................................... 12 2.3 Teori Graf .................................................................................................. 15 2.3.1 Jenis Graf .......................................................................................... 16 2.3.2 Representasi Graf .............................................................................. 18 2.4 Algoritma Pencarian Lintasan Terpendek ................................................. 20 2.4.1 Algoritma Dijkstra ............................................................................ 21 2.4.2 Algoritma A* .................................................................................... 24 2.4.3 Algoritma Shooting* ......................................................................... 26 BAB 3 DESAIN DAN IMPLEMENTASI ANALISIS PENCARIAN JALUR JALAN DALAM BASIS DATA SPASIAL 3D ................................................. 28 3.1 Perancangan Basis Data Jalur Jalan Kampus ITB .................................... 28 3.1.1 Tahapan eksternal.............................................................................. 28 3.1.2 Tahap Konseptual.............................................................................. 30
vii
3.1.2.1 Entity Relationship .................................................................... 32 3.1.2.2 Tabel Skeleton........................................................................... 39 3.1.3 Tahap Implementasi .......................................................................... 40 3.1.3.1 Perangkat Pembangun ............................................................... 40 3.1.3.2 Pembuatan Basis Data ............................................................... 40 3.1.3.3 Pembuatan Tabel-tabel .............................................................. 41 3.2 Pengolahan Data........................................................................................ 41 3.2.1 Pengumpulan data ............................................................................. 41 3.2.2 Dijitasi jalur jalan .............................................................................. 46 3.2.3 Konversi *.dxf ke format *.sql .......................................................... 48 3.3 Implementasi PgRouting dalam basis data 3D.......................................... 49 3.3.1 Aplikasi PgRouting ........................................................................... 49 3.3.2 Memodifikasi fungsi-fungsi Pgrouting ............................................. 50 3.3.3 Uji coba perbandingan algoritma ...................................................... 51 3.3.4 Pembuatan topologi ........................................................................... 52 3.4 Uji coba desain dan implementasi PgRouting untuk analisis pencarian jalur jalan 3D ..................................................................................................... 53 3.4.1 Query deskripsi ................................................................................. 53 3.4.2 Query dengan menggunakan fungsi shortest path ............................ 56 BAB 4ANALISIS ................................................................................................. 58 4.1 Analisis Perancangan Model Basis Data jalur jalan 3D Kampus ITB ...... 58 4.2 Analisis terhadap Sumber Data ................................................................. 59 4.3 Analisis desain dan implementasi perancangan sistem basis data jalur jalan 3D Kampus ITB ................................................................................................ 59 4.4 Analisis implementasi aplikasi Pgrouting dalam sistem basis data jalur jalan 3D ............................................................................................................. 60 4.5 Analisis deskripsi dan grafis ..................................................................... 60 BAB 5KESIMPULAN DAN SARAN ................................................................ 61 5.1 Kesimpulan ............................................................................................... 61 5.2 Saran.......................................................................................................... 61 Daftar Referensi .................................................................................................. 63 Lampiran A Daftar Data Definition Languange (DDL) .................................. 64 Lampiran B Daftar Structure Query Languange (SQL) ................................ 81 Lampiran C Daftar Grafis dan Deskripsi ......................................................... 84
viii
DAFTAR GAMBAR Halaman Gambar 1.1 Diagram Metodologi penelitian ......................................................... 4 Gambar 2.1 Tingkat relasi satu ke satu.................................................................. 8 Gambar 2.2 Tingkat relasi satu ke banyak ............................................................ 8 Gambar 2.3 Tingkat relasi banyak ke satu ............................................................ 9 Gambar 2.4 Tingkat relasi banyak ke banyak ....................................................... 9 Gambar 2.5 Koordinat dan Posisi-posisi Nodes .................................................. 13 Gambar 2.6 Arcs dan nodes ................................................................................. 14 Gambar 2.7 Topologi poligon ............................................................................. 14 Gambar 2.8 Contiguity ........................................................................................ 15 Gambar 2.9 Graf dengan 6 node dan 7 edge ...................................................... 16 Gambar 2.10 Graf berdasarkan ada tidaknya sisi gelang atau sisi ganda, (a). Graf Sederhana, (b). Graf ganda, (c). Graf semu .................................................. 17 Gambar 2.11 (a) graf berarah, (b) graf-ganda berarah ........................................ 17 Gambar 2.12 Contoh Matriks Ketetanggaan ...................................................... 19 Gambar 2.13 Contoh Matriks Besisisan .............................................................. 19 Gambar 2.14 Contoh Senarai Ketetanggaan........................................................ 20 Gambar 2.15 : (a). Simpul A berlabel sementara dengan jarak 0, (b). Simpul B berlabel permanen dengan jarak 7................................................................. 22 Gambar 2.16 Inisialisasi awal.............................................................................. 22 Gambar 2.17 Nilai simpul B menjadi permanen ................................................. 23 Gambar 2.18 Nilai simpul C berubah .................................................................. 23 Gambar 2.19 Semua nilai simpul menjadi permanen .......................................... 24 Gambar 2.20 inisialisasi awal .............................................................................. 25 Gambar 2.21pencarian nilai dari simpul A .......................................................... 25 Gambar 2.22 pemcarian nilai dari simpul B ........................................................ 26 Gambar 2.23 inisialisasi awal .............................................................................. 26 Gambar 2.24 pencarian nilai dari sisi A .............................................................. 27 Gambar 2.25 pencarian nilai dari sisi C .............................................................. 27 Gambar 3.1 Relasi antara Entitas-entitas............................................................. 39 Gambar 3.2 Skematik Pengumpulan dan Pengolahan Data ................................ 42 Gambar 3.3 Koneksi dengan server basis data Peta Kampus ITB (http://petakampus.itb.ac.id).......................................................................... 43 Gambar 3.4 Hasil Query pada aplikasi Quantum GIS......................................... 44 Gambar 3.5 Titik-titik tinggi dalam format shapefile.......................................... 45 Gambar 3.6 TIN kampus ITB .............................................................................. 45 Gambar 3.7 overlay layer data jalan dan TIN ..................................................... 46 Gambar 3.8 Pendijitasian Jalur Jalan di Autocad ................................................ 47 Gambar 3.9 Hasil Pendijitasian Jalur pada gedung Labtek IXC ......................... 47 Gambar 3.10 Aplikasi Koverter dengan menggunakan Visual Basic ................. 48 Gambar 3.11 Cara kerja Pgrouting (http://pgrouting.postlbs.org/wiki/WorkshopFOSS4G2007) ........................ 49 Gambar 3.12 Perbandingan Algoritma Dijkstra, A*, dan Shooting* .................. 52
ix
Gambar 3.13 Hasil query Shortest path ............................................................... 53 Gambar 3.14 Diagram alur penentuan deskripsi arah ......................................... 54 Gambar 3.15 Besaran selisih sudut dan deskripsi arah ....................................... 55 Gambar 3.16 besaran arah vertikal ...................................................................... 55 Gambar 3.17 Contoh hasil pencarian jalur jalan jalur (Labtex III ke Labtex IX C) ....................................................................................................................... 57 Gambar 3.18 Contoh hasil atribut pencarian jalur (Labtex III ke Labtex IX C) . 57
x
DAFTAR TABEL Halaman Tabel 2.1 Notasi atau simbol yang digunakan dalam diagram ER ....................... 10 Tabel 3.1daftar entitas titik ................................................................................... 29 Tabel 3.2 daftar entitas garis ................................................................................. 30 Tabel 3.3 Tabel entitas-entitas basis data jalur jalan kampus ITB beserta atributnya....................................................................................................... 31
xi
