BAB 2 LANDASAN TEORI
2.1
Diagram Voronoi Penggunaan diagram voronoi, sebelum orang tahu apa itu diagram voronoi, sudah dapat diketemukan pada tahun 1644 oleh Descartes. Dirichlet menggunakan diagram voronoi 2 dimensi dan 3 dimensi pada pembelajarannya terhadap bentuk-bentuk kuadrat pada tahun 1850. Fisikawan Inggris John snow menggunakan diagram voronoi pada tahun 1854 untuk mengilustrasikan bagaimana mayoritas orang yang meninggal dalam epidemi kolera di Soho tinggal lebih dekat dengan pompa air yang terinfeksi dari pompa air lain. Diagram voronoi dinamakan atas seorang matematikawan Rusia Georgy Fedoseevich Voronoi (atau Voronoy) yang mendefinisikan dan mempelajari kasus umum n-dimensional pada tahun 1908.
Gambar 2.1 Diagram Voronoi Misalkan P = { p1 , p 2 , p3 ,K, p n } suatu himpunan titik di suatu bidang (atau dalam ruang berdimensi lain), yang disebut sites. Didefinisikan V(pi), sel
6
7 Voronoi untuk pi, sebagai himpunan titik q yang lebih dekat ke pi dibandingkan ke site lainnya. Sehingga, sel Voronoi untuk pi didefinisikan dengan: V(pi) = {q | jarak(pi, q) < jarak(pj, q, untuk j ≠ i) Jadi Diagram Voronoi dari suatu himpunan titik merupakan pembagian planar oleh sel-sel Voronoi dari titik-titik tersebut. (anonim, 5 Januari 2007, http://www.cs.wustl.edu/~pless/546/lectures/l16.html)
2.2
Algoritma Fortune Pada algoritma Fortune digunakan sebuah garis lurus menyapu bidang dari kiri ke kanan atau atas ke bawah dan sebaliknya. Ada satu kurva lagi yang akan dihasilkan oleh garis penyapu tersebut yang disebut garis pantai (beach line). Garis pantai terdiri dari kurva-kurva parabolik, yang dihubungkan dari ujung ke ujung pada titik pecah (break point). Algoritma Fortune mensimulasikan pergerakan garis pantai dan melacak jalur titik-titik pecah yang terjadi. Pada algoritma Fortune terjadi 2 jenis events yang penting. Pertama adalah point events, terjadi ketika garis penyapu menemui sebuah site baru. Kedua adalah circle events terjadi ketika
dua titik pecah pada garis pantai
bertemu, menghasilkan sebuah titik dari diagram Voronoi.
2.2.1
Site Event Sebuah site event terjadi ketika garis penyapu menemui sebuah site. Pada saat garis tersebut menyentuh site tersebut, tarik sebuah garis dari titik tersebut sampai ke permukaan garis pantai yang tegak lurus dengan garis penyapu. Sejalan
8 dengan majunya garis penyapu, garis tersebut akan melebar menjadi kurva parabolik sepanjang garis pantai, membagi garis pantai di atasnya menjadi dua. Kurva ini akan bergabung membentuk sebuah garis pantai baru. Site event ini tidaklah sulit untuk dideteksi karena setelah mengurutkan titik-titik yang ada berdasarkan posisinya, semua events diketahui.
Gambar 2.2 Site Event
2.2.2
Circle Event
Gambar 2.3 Circle Event
Kontras dengan site events, circle events muncul secara dinamis seiring dengan berjalannya program. Anggap 3 titik pi, pj, dan pk, kurva-kurva paraboliknya bersebelahan pada garis pantai. Ketiga titik tersebut dapat membentuk sebuah lingkaran dimana titik-titik itu berada pada lingkaran. Harus
9 dipastikan apakah ada titik lain yang berada dalam lingkaran atau tidak, karena jika ada maka akan mengganggu pembentukan titik potong. Ketika garis penyapu tepat menjadi garis singgung lingkaran tersebut, maka pada saat itulah titik tengah dari lingkaran itu aktif menjadi berjarak sama dari ketiga titik serta dari garis penyapu. Maka ketiga kurva parabolik akan melewati titik tengah lingkaran tersebut, berakibat kurva dari pj hilang dari garis pantai. Dalam konteks Diagram Voronoi, garis pembagi (pi, pj) dan (pj, pk) saling bertemu di titik tengah lingkaran tersebut, yang akan kita sebut Voronoi vertex. Dan satu garis pembagi (pi, pk) tersisa.
2.2.3
Parabola
2.2.3.1 Definisi Parabola Parabola (berasal dari sebuah kata dalam bahasa Yunani παραβολή) adalah sebuah bagian menyerupai kerucut yang dihasilkan dari perpotongan dari sebuah permukaan konik dan sebuah bidang yang paralel dengan salah satu bagian permukaan tersebut. Sebuah parabola dapat juga didefinisikan sebagai kumpulan titik-titik pada sebuah bidang yang berjarak sama terhadap sebuah titik tertentu (fokus) dan sebuah garis tertentu (direktris). (anonim, 9 Januari 2007, http://en.wikipedia.org/wiki/Parabola) Grafik dari persamaan-persamaan kuadrat adalah kurva-kurva berbentuk cup yang disebut parabola. (Varberg et al. 2000, 31)
10 2.2.3.2 Persamaan Parabola
2.2.3.2.1
Persamaan Parabola dengan Sumbu Simetri Vertikal
( x − h )2 = 4 p ( y − k ) y = a(x − h ) + k 2
y = ax 2 + bx + c dimana a =
1 h2 4ac − b 2 −h −b ;b = ;c = ;k = + k; h = 4p 2p 4p 2a 4a
x(t ) = 2 pt + h; y (t ) = pt 2 + k Keterangan : Puncak (h, k) Fokus (h, k+p) Sumbu simetri x = h Garis direktris y = k – p
2.2.3.2.2
Persamaan Parabola dengan Sumbu Simetri Horisontal
( y − k )2 = 4 p ( x − h ) x = a( y − k ) + h 2
x = ay 2 + by + c 1 k2 4ac − b 2 −k −b ;b = ;c = ;h = + h; k = dimana a = 4p 2p 4p 2a 4a
x(t ) = pt 2 + h; y (t ) = 2 pt + k
11 Keterangan : Puncak (h, k) Fokus (h+p, k) Sumbu simetri y = k Garis direktris x = h – p
2.2.3.3 Perpotongan Dua Parabola
Titik potong P (a, b) antara dua parabola, dapat dihitung dengan
memecahkan kedua persamaan parabola
(x1 − h1 )2 = 4 p1 ( y1 − k1 ) dan (x2 − h2 )2 = 4 p2 ( y2 − k 2 ) atau
( y1 − k1 )2 = 4 p1 (x1 − h1 ) dan ( y2 − k 2 )2 = 4 p2 (x2 − h2 ) secara bersamaan dengan mensubstitusi dan mengeliminasi persamaan yang ada.
2.2.4
Lingkaran
2.2.4.1 Definisi Lingkaran
Pada geometri Euclid, sebuah lingkaran adalah kumpulan dari semua titik pada sebuah bidang dengan jarak tertentu, disebut jari-jari, dari sebuah titik tertentu, titik pusat. (Varberg et al. 2000, 20) Lingkaran adalah sebuah kurva tertutup sederhana, membagi sebuah bidang menjadi interior dan eksterior. Apabila muncul kata lingkaran, biasanya yang dimaksud adalah bagian interior, dengan lingkaran itu sendiri disebut
12 circumference(C). Biasanya circumference berarti panjang dari lingkaran, dan interior lingkaran disebut sebuah disk. Arc adalah bagian kontinu dari sebuah lingkaran. (anonim, 10 Januari 2007, http://en.wikipedia.org/wiki/Circle).
2.2.4.2 Persamaan Lingkaran
Sebuah lingkaran pada bidang kartesius dengan pusat (a, b) dan jari-jari r mempunyai persamaan:
( x − a )2 + ( y − b )2 = r 2
2.2.4.3 Pembentukan Lingkaran dari Tiga Titik
Dari tiga titik P( x1 , y1 ), Q( x 2 , y 2 ) dan R ( x3 , y 3 ) , dapat dibentuk suatu persamaan lingkaran dimana ketiga titik tersebut terletak pada lingkaran itu. Untuk mendapatkan persamaan lingkaran, pertama-tama titik P, Q, dan R dimasukkan ke dalam persamaan lingkaran
( x − a )2 + ( y − b )2 = r 2
didapat :
(x1 − a )2 + ( y1 − b )2 = r 2 atau x1 − 2ax1 + a 2 + y1 − 2by1 + b 2 − r 2 = 0 ... (1) 2
2
( x 2 − a )2 + ( y 2 − b )2 = r 2 atau x 2 − 2ax 2 + a 2 + y 2 − 2by 2 + b 2 − r 2 = 0 ... (2) 2
2
( x 3 − a )2 + ( y 3 − b )2 = r 2 atau x3 − 2ax3 + a 2 + y 3 − 2by 3 + b 2 − r 2 = 0 ... (3) 2
2
sehingga
13 Setelah melewati proses eliminasi dan substitusi terhadap persamaan (1), (2), dan (3), maka akan didapat nilai a dan b. Nilai a dan b yang didapat kemudian dimasukkan kedalam persamaan (1), (2), atau (3), maka akan didapat nilai r. Setelah mendapatkan nilai a, b, dan r, maka persamaan lingkaran yang baru sudah didapat, dengan nilai a, b, dan r yang sudah berupa angka.
2.3 Algoritma Halfplane
Algoritma halfplane didasarkan pada paradigma divide-and-conquer, dimana sebuah masalah dibagi menjadi beberapa masalah kecil yang lebih sederhana. Solusi dari masalah utamanya didapat dengan menggabungkan solusisolusi yang dari masalah-masalah kecil tadi.
2.3.1
Pembagian (Divide)
Algoritma ini disebut halfplane karena dalam membangun diagram Voronoi, himpunan titik-titik yang ada dibagi menjadi dua himpunan bagian
dengan besar yang lebih kurang sama, lalu secara rekursif himpunan-himpunan bagian itu dibagi menjadi dua himpunan bagian yang lebih kurang sama besarnya. Setelah titik-titik yang ada terbagi, setiap himpunan bagian akan mempunyai satu atau dua titik.
14
Gambar 2.4 Convex Hull
Gambar 2.5 Support Line Atas dan Rantai Penghubung
15
Gambar 2.6 Rantai Penghubung
Gambar 2.7 Support Line Bawah dan Rantai Penghubung
16
Gambar 2.8 Penghapusan Diagram
2.3.2
Penggabungan (Merge)
Selanjutnya akan dibangun diagram Voronoi dari himpunan bagian SL, salah satu himpunan bagian yang dihasilkan sebelumnya. Diagram Voronoi itu dibentuk dari garis yang membagi dua dan tegak lurus garis penghubung dua titik pada himpunan bagian itu. Langkah yang sama diterapkan pada SR, himpunan bagian berikutnya. Kemudian dicari convex hull dari masing-masing himpunan bagian. Selanjutnya kedua convex hull tersebut akan digabungkan. Pertama-tama dicari dua support line, yaitu suport line atas dan bawah. Support line adalah garis yang menghubungkan convex hull dari SL dan SR menjadi satu convex hull besar. Tarik garis dari infinity yang membagi dua support line atas yang diapit titik uL1 dari SL dan titik uR1 dari SR, serta tegak lurus dengan support line itu sampai
17 dengan diagram Voronoi terdekat, misal diagram Voronoi dari titik uL1. Garis itu disebut rantai penghubung. Kemudian dicari garis yang menghubungkan uR1 dengan titik yang bertetangga dengan uL1 yang berbagi diagram Voronoi yang tadi, misal disebut uL2, rantai penghubung diteruskan dengan menarik garis yang tegak lurus dengan
garis antara titik uL2 dengan uR1. Langkah ini dilanjutkan sampai rantai penghubung ini menemui support line bawah. Diagram Voronoi yang melewati rantai penghubung sesuai asal diagram tersebut dihapus, misal berasal dari himpunan bagian sebelah kanan rantai penghubung maka semua diagram yang berasal dari himpunan bagian ini yang berada di sebelah kiri rantai penghubung dihapus. Penggabungan diteruskan dengan mengulang langkah-langkah ini terhadap himpunan bagian lain dan himpunan bagian baru yang merupakan hasil gabungan, maka akan didapatkan diagram Voronoi secara menyeluruh.
2.4
Garis
2.4.1
Definisi Garis
Sebuah garis bisa dideskripsikan sebagai sebuah kurva sangat tipis yang lurus sempurna dengan panjang tak berhingga. Pada geometri Euclid, hanya terdapat tepat satu garis yang melewati dua titik sembarang. Garis itu merupakan jarak terpendek diantara kedua titik. (anonim, 10 Januari 2007, http://en.wikipedia.org/wiki/Line)
18 2.4.2
Persamaan Garis
y = mx + b
Keterangan : m : derajat kemiringan garis b : y-intercept (kedudukan y pada garis x = 0) dari garis x : variabel bebas dari fungsi y
2.4.3
Perpotongan Antar Dua Garis
Titik potong dari dua garis didapatkan dengan substitusi. Misal terdapat dua garis: y1 = m1 x1 + b1 , dan y 2 = m2 x 2 + b2
berpotongan di titik (x, y), berarti pada titik ini y1 = y2 dan x1 = x2. maka, m 2 x 2 + b2 = m1 x1 + b1
x=
b1 − b2 m2 − m1
setelah didapatkan x, dengan memasukkannya pada salah satu persamaan garis di atas akan didapat y. Titik potong (x, y) didapat.
2.4.4
Garis Saling Tegak Lurus
Dua garis, y1 = m1 x1 + b1 dan y 2 = m2 x 2 + b2 , dikatakan saling tegak lurus jika memenuhi syarat: m1 ⋅m2 = −1
19 2.5
NetBeans
NetBeans merujuk pada baik sebuah platform yang digunakan untuk
pengembangan aplikasi desktop Java, dan sebuah integrated development environment (IDE) yang dikembangkan menggunakan Netbeans Platform. NetBeans Platform memungkinkan aplikasi untuk dikembangkan dari
sekelompok komponen piranti lunak modular yang disebut modules. Sebuah module adalah sebuah Java archive file yang mengandung kelas-kelas Java yang
ditulis untuk berinteraksi dengan NetBeans Open APIs dan sebuah file yang mengidentifikasikannya sebagai sebuah module. Aplikasi yang dibangun berbasiskan modules bisa diperluas dengan menambahkan modules baru. Karena modules bisa dikembangkan secara independen, aplikasi berbasiskan NetBeans platform bisa dengan mudah dikembangkan oleh pengembang pihak ketiga. NetBeans dimulai pada tahun 1997 sebagai Xelfi, sebuah proyek
mahasiswa dibawah bimbingan Faculty of Mathematics and Physics di Charles University di Praha. Sebuah perusahaan kemudian didirikan atas proyek itu dan memproduksi versi komersil dari NetBeans IDE sampai perusahaan tersebut dibeli oleh Sun Microsystems pada 1999. Sun lalu menyatakan bahwa NetBeans IDE open-source pada bulan Juni tahun berikutnya.
2.5.1
Java
Sun Microsystems pada tahun 1991 membiayai sebuah proyek internal perusahaan bernama Green, yang menghasilkan sebuah bahasa pemrograman berbasiskan C++ yang oleh penciptanya, James Gosling, diberi nama Oak atas
20 sebuah pohon oak di luar ruang kerjanya di Sun. Ternyata sudah ada sebuah bahasa komputer dengan nama Oak. Ketika sekelompok dari pegawai Sun mengunjungi sebuah coffee shop lokal, sebuah nama, Java, tercetus dan akhirnya dipakai. Proyek Green lalu menemui beberapa kesulitan. Pasar untuk alat-alat elektronik di awal 1990-an tidak berkembang secepat yang Sun harapkan. Proyek itu berada di ambang kehancuran. Hanya karena keberuntunganlah, World Wide Web meledak kepopulerannya pada tahun 1993, dan orang-orang Sun melihat potensi dalam menggunakan Java untuk menambah isi dinamis, seperti interaktivitas dan animasi, pada halaman-halaman Web. Hal ini meniupkan angin segar pada proyek itu. Sun lalu mengumumkan Java secara resmi pada sebuah konferensi besar pada Mei 1995. Java menarik perhatian komunitas bisnis karena ketertarikan fenomenal
pada
World
Wide
Web.
Java
sekarang
digunakan
untuk
mengembangkan aplikasi perusahaan berskala besar, untuk meningkatkan fungsionalitas dari Web servers, menyediakan aplikasi bagi perangkat konsumen (seperti telepon seluler dan personal digital asistants) serta banyak tujuan lainnya. Java merupakan sebuah bahasa pemrograman berbasis obyek. Aplikasi-
aplikasi Java biasanya di-compiled menjadi bytecode yang bisa di-compiled menjadi native machine code pada saat runtime. (Deitel 2005, 9)
21 2.6
Rekayasa Perangkat Lunak
2.6.1
Pengertian Perangkat Lunak
Pengertian perangkat lunak adalah: •
Instruksi pada komputer yang bila dijalankan akan memberikan fungsi dan hasil yang diinginkan.
•
Dokumen yang menjelaskan operasi dan penggunaan program.
•
Struktur data yang menjadikan program dapat memanipulasi suatu informasi. (Pressman 1992, 45) Dengan demikian dapat disimpulkan bahwa rekayasa perangkat lunak
adalah instruksi, dokumen, dan struktur data yang menyediakan metode logika dan prosedur yang diinginkan.
2.6.2
Model Waterfall
Model Waterfall merupakan model proses yang digunakan penulis dalam
penelitian.
Model
ini
merupakan
sebuah
pendekatan
kepada
pengembangan perangkat lunak yang sistematik dan sekuensial yang dimulai dengan analisis, desain, pengembangan, pengujian, dan pemeliharaan terhadap sistem yang akan dibuat. Urutan kerjanya disajikan dalam gambar ini:
22 ANALISIS
DESAIN
CODING DAN DEVELOPMENT IMPLEMENTASI / TESTING MAINTENANCE
Gambar 2.9 Model Waterfall
Penjelasan tahapan dalam model Waterfall adalah sebagai berikut: a. Analisis Kebutuhan Proses pengumpulan kebutuhan diintensifkan dan difokuskan, khususnya pada perangkat lunak. Tujuan tahap ini adalah untuk mengetahui kebutuhan piranti lunak, sumber informasi piranti lunak, fungsi-fungsi yang dibutuhkan, kemampuan piranti lunak dan antarmuka piranti lunak tersebut. b. Desain Proses desain merupakan representasi kebutuhan ke bentuk perangkat lunak yang dapat dinilai kualitasnya sebelum dilakukan pengkodean. Tahap ini meliputi perancangan struktur data, perancangan arsitektur piranti lunak, perancangan rincian prosedur dan perancangan user interface.
23 c. Pengembangan Desain harus dapat diterjemahkan ke dalam bentuk bahasa pemrograman yang bisa dibaca. d. Implementasi dan Pengujian Setelah program aplikasi selesai dikode, program akan diujicobakan dan juga dilakukan pengujian. Pengujian dilakukan secara menyeluruh hingga semua perintah dan fungsi telah diuji sampai output yang dihasilkan oleh program sesuai dengan yang diharapkan. e. Pemeliharaan Pemeliharaan perangkat lunak dilakukan karena sering terjadinya perubahan atau peningkatan fungsi piranti lunak. Hal ini sesuai permintaan pemakai, maka pirati lunak yang telah selesai dibuat perlu dipelihara agar dapat mengantisipasi permintaan pemakai terhadap fungsi-fungsi baru. Bila terjadi perubahan berarti membalikkan tahapan ke tahapan yang lebih awal.
2.7 Rata – rata (Mean) i =n
x=
∑x i =1
i
n
Keterangan : x = rata – rata
xi = data ke i n = banyak data
