UNIVERSITAS BINA NUSANTARA _______________________________________________________________________ Program Ganda Teknik Informatika-Matematika Skripsi Sarjana Komputer – Sarjana Sains Semester ganjil 2006/2007
ANALISIS PERBANDINGAN PERANCANGAN DIAGRAM VORONOI MENGGUNAKAN ALGORITMA FORTUNE DAN ALGORITMA HALFPLANE Leonardus Henry NIM : 0600664446
Abstrak Diagram Voronoi mempunyai aplikasi yang sangat luas pada kehidupan. Dari berbagai algoritma yang ada untuk merancang diagram Voronoi, algoritma Fortune dan algoritma Halfplane yang menganut paradigma divide-and-conquer, merupakan dua algoritma yang paling umum digunakan. Pada skripsi ini dilakukan penelitian terhadap kedua algoritma diatas, yaitu algoritma Fortune dan algoritma Halfplane. Penelitian yang dilakukan adalah membandingkan kedua algoritma tersebut dan mencari metode yang mampu merancang diagram Voronoi dengan waktu tercepat. Penelitian dilakukan dengan menggunakan bantuan NetBeans yang berbasis bahasa pemrograman Java untuk membantu dalam penghitungannya. Dari penelitian yang dilakukan, diperoleh kesimpulan bahwa algoritma Halfplane cenderung lebih baik bila digunakan untuk memerancang diagram Voronoi, terutama untuk data dengan jumlah titik yang relatif besar. Kata kunci : diagram Voronoi, algoritma Fortune, algoritma Halfplane, divide-and-conquer
iv
KATA PENGANTAR
Puji syukur kepada Tuhan Yang Maha Esa karena hanya dengan berkat-Nya penulis dapat menyusun dan menyelesaikan Skripsi yang berjudul : “ANALISIS
PERBANDINGAN
PERANCANGAN
DIAGRAM
VORONOI
MENGGUNAKAN ALGORITMA FORTUNE DAN ALGORITMA HALFPLANE ” sebagai syarat untuk memperoleh gelar kesarjanaan pada Program Ganda, jurusan Teknik Informatika – Matematika, Jenjang Pendidikan Strata 1. Dalam proses penyusunan skripsi ini, penulis banyak sekali memperoleh bimbingan, dorongan semangat, dan fasilitas dari berbagai pihak yang mendukung penulis untuk menyelesaikan tugas tersebut tepat waktu. Ucapan terima kasih yang tulus penulis sampaikan kepada : •
Bapak Prof. Dr. Gerardus Polla, M.App.Sc., selaku Rektor Universitas Bina Nusantara, yang telah memberikan banyak kesempatan kepada mahasiswa untuk menerapkan segala sesuatu yang telah dipelajari selama mengikuti kegiatan perkuliahan dengan mengadakan program studi Skripsi.
•
Bapak Wikaria Gazali, S.Si., M.T., selaku Dekan Fakultas MIPA, atas dorongan semangatnya dan selalu memacu kreatifitas mahasiswanya.
•
Bapak Drs. Ngarap Imanuel Manik, M.kom., selaku ketua jurusan Matematika dan Statistika, yang telah memberikan persetujuan terhadap topik skripsi yang diajukan dan telah menunjuk para pembimbing terbaik untuk penulis.
•
Bapak Rojali, S.Si., selaku sekretaris jurusan Matematika dan Statistika.
v
•
Bapak Stanislaus S. Uyanto, Ph. D., selaku Dosen Pembimbing pertama, yang tiada henti-hentinya meluangkan banyak waktu, memberikan saran, ide, semangat serta dukungan moral, dan telah banyak sekali memberikan dukungan kepada penulis dari mulai persiapan pemilihan topik, penulisan skripsi sampai penyelesaian skripsi ini.
•
Bapak Tri Djoko Wahjono, Ir. M.Sc , selaku Dosen Pembimbing kedua, yang telah memberikan saran dan ide, mengajukan pertanyaan-pertanyaan yang mendorong penulis untuk menjadi lebih baik.
•
Civitas akademika Universitas Bina Nusantara yang secara langsung maupun tidak langsung memberikan dukungan kepada penulis. Ucapan terima kasih penulis haturkan juga kepada kedua orang tua serta Irene Vimala Tisnabudi yang telah membekali penulis dengan semangat juang, kepercayaan, pengertian, sehingga penulis dapat menyelesaikan Skripsi ini. Meskipun penulis telah berusaha sebaik-sebaiknya, namun penulis menyadari bahwa Skripsi ini jauh dari sempurna. Kritik dan saran akan penulis terima dengan senang hati. Kiranya Skripsi ini bermanfaat bagi para pembaca dan pihak-pihak yang membutuhkan. Terima kasih.
Jakarta, Januari 2007
Penulis
vi
DAFTAR ISI
Halaman PENGESAHAN HARDCOVER ..........………………………………
iii
ABSTRAK ……………………………………………………………
iv
KATA PENGANTAR
……………………………………………..
v
DAFTAR ISI …………………………………………………………
vii
DAFTAR TABEL ……………………………………………………
x
DAFTAR GAMBAR …………………………………………………
xi
DAFTAR LAMPIRAN ……………………………………………….
xii
BAB 1 PENDAHULUAN.......................................................................
1
1.1 Latar Belakang Masalah ………………………………………….
1
1.2 Ruang Lingkup……………………………………………………
2
1.3 Tujuan dan Manfaat……………………………………………….
3
1.4 Sistematika Penulisan .....................................................................
4
1.5 Pembatasan Istilah...........................................................................
5
BAB 2 LANDASAN TEORI..................................................................
6
2.1 Diagram Voronoi.............................................................................
6
2.2 Algoritma Fortune...........................................................................
7
2.2.1 Site Event...................................................................................
7
2.2.2 Circle Event...............................................................................
8
2.2.3 Parabola......................................................................................
9
2.2.3.1 Definisi Parabola..................................................................
9
2.2.3.2 Persamaan Parabola.............................................................
10
2.2.3.2.1 Persamaan Parabola dengan Sumbu Simetri Vertikal...
10
2.2.3.2.2 Persamaan Parabola dengan Sumbu Simetri Horisontal
10
2.2.3.2 Pepotongan Dua Parabola....................................................
11
2.2.4 Lingkaran...................................................................................
11
2.2.4.1 Definisi Lingkaran...............................................................
11
vii
2.2.4.2 Persamaan Lingkaran...........................................................
12
2.2.4.3 Pembentukan Lingkaran dari Tiga Titik..............................
12
2.3 Algoritma Halfplane........................................................................
13
2.3.1 Pembagian (Divide)...................................................................
13
2.3.2 Penggabungan (Merge)..............................................................
16
2.4 Garis.................................................................................................
17
2.4.1 Definisi Garis.............................................................................
17
2.4.2 Persamaan Garis.........................................................................
18
2.4.3 Perpotongan Antar Dua Garis....................................................
18
2.4.4 Garis Saling Tegak Lurus..........................................................
18
2.5 NetBeans..........................................................................................
19
2.5.1 Java............................................................................................
19
2.6 Rekayasa Perangkat Lunak..............................................................
21
2.6.1 Pengertian Perangkat Lunak......................................................
21
2.6.2 Model Waterfall.........................................................................
21
2.7 Rata-rata (Mean)..............................................................................
23
BAB 3 METODOLOGI PENELITIAN ...............................................
24
3.1 Metodologi Penelitian .....................................................................
24
3.2 Teknik Pembangkitan Titik..............................................................
24
3.3 Teknik Analisis ...............................................................................
25
3.3.1 Proses pada Algoritma Fortune.................................................
25
3.3.2 Proses pada Algoritma Halfplane..............................................
26
3.3.3 Mencari Rata-rata Waktu Proses...............................................
26
3.4 Teknik Perbandingan ......................................................................
26
3.5 Spesifikasi Perangkat Keras (Hardware) dan Perangakat Lunak (Software)........................................................................................
27
3.5.1 Spesifikasi Perangkat Keras (Hardware)...................................
27
3.5.2 Spesifikasi Perangkat Lunak (Software) ...................................
27
viii
BAB 4 HASIL DAN PEMBAHASAN ..................................................
28
4.1 Percobaan dengan 500 Titik.............................................................
28
4.2 Percobaan dengan 1000 Titik...........................................................
30
4.3 Percobaan dengan 2000 Titik...........................................................
32
4.4 Percobaan dengan 3000 Titik...........................................................
34
4.5 Hasil dan Pembahasan.....................................................................
36
BAB 5 SIMPULAN DAN SARAN........................................................
37
5.1 Simpulan .........................................................................................
37
5.2 Saran................................................................................................
37
DAFTAR ACUAN..................................................................................
xiii
DAFTAR PUSTAKA .............................................................................
xv
DAFTAR RIWAYAT HIDUP...............................................................
xvii
LAMPIRAN
ix
DAFTAR TABEL Halaman Tabel 4.1 Tabel 4.2 Tabel 4.3 Tabel 4.4
Waktu Proses dengan 500 Titik........................................... Waktu Proses dengan 1000 Titik......................................... Waktu Proses dengan 2000 Titik......................................... Waktu Proses dengan 3000 Titik.........................................
x
28 30 32 34
DAFTAR GAMBAR
Halaman Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 2.6 Gambar 2.7 Gambar 2.8 Gambar 2.9 Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8
Diagram Voronoi........................................................ Site Event.................................................................... Circle Event................................................................ Convex Hull................................................................ Support Line Atas dan Rantai Penghubung................ Rantai Penghubung..................................................... Support Line Bawah dan Rantai Penghubung............ Penghapusan Diagram................................................ Model Waterfall.......................................................... Pembangkitan 500 Titik.............................................. Diagram Voronoi dari 500 Titik................................. Pembangkitan 1000 Titik............................................ Diagram Voronoi dari 1000 Titik............................... Pembangkitan 2000 Titik............................................ Diagram Voronoi dari 2000 Titik............................... Pembangkitan 3000 Titik............................................ Diagram Voronoi dari 3000 Titik...............................
xi
6 8 8 14 14 15 15 16 22 29 29 31 31 33 33 35 35
DAFTAR LAMPIRAN
Halaman LAMPIRAN A
LISTING PROGRAM………………...
L. 1
A.1 MainGuiVoronoi......................................
L. 1
A.2 Package fortune.......................................
L. 6
A.2.1 ArcNode.java..................................
L. 6
A.2.2 ArcTree.java....................................
L. 10
A.2.3 CirclePoint.java..............................
L. 11
A.2.4 EventPoint.java...............................
L. 12
A.2.5 EventQueue.java.............................
L. 13
A.2.6 Main.java.........................................
L. 14
A.2.7 MyCanvas.java................................
L. 15
A.2.8 MyLine.java....................................
L. 17
A.2.9 MyPoint.java...................................
L. 18
A.2.10 Paintable.java................................
L. 18
A.2.11 ParabolaPoint.java.........................
L. 19
A.2.12 Voronoi.java..................................
L. 20
A.3 Package halfPlane....................................
L. 22
A.3.1 Main.java.........................................
L. 22
A.3.2 MyConvexHull.java........................
L. 24
A.3.3 MyList.java.....................................
L. 28
A.3.4 MyPoint.java...................................
L. 30
A.3.5 MySegment.java.............................
L. 31
A.3.6 MyVertex.java.................................
L. 33
A.3.7 MyVoronoi.java..............................
L. 34
A.3.8 MyVoronoiSegment.java................
L. 43
xii
