JURNAL TEKNIK POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print)
1
Desain dan Analisis Algoritma Pembangkitan Convex Hull 3 Dimensi dan Visualisasinya Andi Muh. Primabudi, Arya Yudhi Wijaya dan Rully Soelaiman Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia e-mail:
[email protected] AbstrakβMasalah Convex Hull merupakan salah satu masalah yang trivial pada persoalan komputasi geometri. Secara umum, masalah Convex Hull dapat dinyatakan dengan adanya sejumlah titik, di mana titik-titik tersebut akan dibungkus dengan sebuah objek yang convex dan memiliki luas/volume sekecil mungkin. Convex Hull tidak hanya sebatas 2-dimensi saja, terdapat pula Convex Hull 3-dimensi yang dikenal sebagai Convex Polyhedron. Beberapa algoritma yang dapat digunakan untuk menyelesaikan masalah ini adalah algoritma Brute-Force, GiftWrapping, Incremental dan masih banyak lagi. Tiap algoritma memiliki kompleksitas yang berbeda-beda, hal ini tentu saja bergantung pada metode atau pendekatan apa yang digunakan pada algoritma tersebut. Dalam publikasi ini dilakukan studi dan implementasi algoritma pembentukan Convex Hull 3-dimensi beserta visualisasinya dengan bahasa C++. Hasil uji coba menunjukkan program menghasilkan Convex Hull yang benar dan memiliki pertumbuhan waktu eksekusi secara kuadratik dengan kompleksitas waktu πΆ(ππ) pada π buah titik, dan π buah sisi. Kata Kunciβ Convex Hull, algoritma Incremental, komputasi geometri 3-dimensi.
I. PENDAHULUAN Masalah Convex Hull merupakan salah satu masalah yang trivial pada persoalan computational geometry. Permasalahan Convex Hull memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola, penelitian operasi dan lain-lain. Secara umum, masalah Convex Hull dapat dinyatakan dengan adanya sejumlah titik, di mana titik-titik tersebut akan dibungkus dengan sebuah objek yang convex dan memiliki luas/volume sekecil mungkin. Hasil akhir yang diperoleh adalah titik-titik mana saja yang menjadi boundary/titik terluar dan luas/volume dari Convex Hull tersebut jika diperlukan. Convex Hull tidak hanya sebatas 2-dimensi saja, terdapat pula Convex Hull 3dimensi yang dikenal sebagai Convex Polyhedron. Beberapa algoritma yang dapat digunakan untuk menyelesaikan masalah ini adalah algoritma Brute-Force, GiftWrapping, Grahamβs Scan, Incremental dan Divide-andConquer. Tiap algoritma memiliki kompleksitas yang berbedabeda, hal ini tentu saja bergantung pada metode atau pendekatan apa yang digunakan pada algoritma tersebut. Pada publikasi ini, penulis akan mencoba membahas penyelesaian permasalahan Convex Hull ini dengan metode Incremental serta visualisasinya, khususnya untuk Convex Hull 3-dimensi. Hasil yang diharapkan dalam publikasi ini adalah proses komputasi untuk menyelesaikan masalah Convex Hull 3-
dimensi dengan konsumsi waktu dan memory yang efisien. Tentisualunya dilakukan analisis yang komprehensif terlebih dahulu dalam menentukan algoritma yang digunakan untuk menyelesaikan masalah ini. II. ULASAN ALGORITMA A. Convex Hull Pada sebuah set yang berisi titik-titik misalnya π = {π΄, π΅, πΆ, π·, πΈ, πΉ}, Convex Hull adalah bidang convex terkecil yang mencakup semua titik yang ada pada set π [1]. Jika setiap titik pada set π dihubungkan satu sama lain dengan garis lurus, maka Convex Hull π adalah garis terluar dari sejumlah garis lurus yang dihasilkan (Gambar 1). B. Permasalahan Convex Hull 3-dimensi Convex Hull juga dapat direpresentasikan dalam bidang 3dimensi(biasa disebut Convex Hull 3D atau convex polyhedron). Mengacu pada Gambar 2 (a), sebuah Convex Hull 3D terdiri atas: -
Titik (A, B, C dan D). Garis (AB, AC, AD, BC, BD dan CD). Sisi segitiga (ABC, ACD dan BCD).
Gambar 1. Bidang poligon ABCDEF merupakan sebuah Convex Hull
Gambar 2 Contoh Convex Hull 3D yang paling sederhana
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print) Secara umum, permasalahan Convex Hull 3-dimensi ini adalah diberikan masukan berupa sejumlah n titik dalam sebuah bidang 3-dimensi, lalu temukan Convex Hull dari titik-titik ini dengan keluaran: 1. List yang berisikan sisi-sisi segitiga mana saja yang menjadi boundary dari Convex Hull 3D yang telah dibentuk. 2. Luas permukaan dari Convex Hull 3D yang telah dibentuk. 3. Volume dari Convex Hull 3D yang telah dibentuk.
Gambar 5. Titik π1 dan π2 yang valid
Ilustrasi permasalahan Convex Hull 3D dapat dilihat pada Gambar 3. Untuk mendapatkan list sisi-sisi segitiga mana saja yang menjadi boundary dari Convex Hull 3D, penulis akan mengimplementasikan algoritma Incremental. Sedangkan untuk menghitung luas permukaan dan volume, dapat digunakan operasi vektor seperti Dot Product, Cross Product dan Triple Product [2].
Gambar 6. Titik π3 yang vaild
C. Algoritma Incremental Algoritma Incremental adalah salah satu algoritma yang dapat digunakan untuk menyelesaikan permasalahan Convex Hull 3D [1]. Ide dari algoritma ini adalah membentuk Convex Hull secara bertahap, mulai dari empat titik hingga π titik (π β₯ 4). Ilustrasi algoritma ini dapat dilihat pada Gambar 4. Jika diberikan sebuah set π = {π1 , π2 , π3 , π4 , π5 , β¦ , ππ }, algoritma yang memiliki kompleksitas π(ππ) ini bekerja dengan langkah sebagai berikut: 1. Untuk membentuk sebuah Convex Hull 3D, dibutuhkan mimimal 4 titik yang tidak berada di bidang yang sama, atau dengan kata lain bisa dijadikan sebuah tetrahedron. Cara mencari keempat titik tersebut (π1 , π2 , π3 ,π4 β π) yaitu: a. π1 Untuk titik pertama, bebas dipilih titik mana saja. b. π2 Untuk titik kedua, dipilih titik yang tidak berada pada posisi yang sama dengan π1 atau jika π1 dihubungkan dengan π2 menjadi sebuah vektor ββββββββ ββββββββ π1 π2 maka akan memiliki |π 1 π2 | > 0 seperti pada Gambar 5.
Gambar 7. Titik π4 yang vaild
c.
π3 Untuk titik ketiga, dipilih titik yang jika dihubungkan dengan π1 menjadi sebuah vektor ββββββββ π1 π3 , vektor tersebut tidak sejajar/segaris dengan ββββββββ π1 π2 . Dua vektor yang sejajar akan menghasilkan vektor cross product yang memiliki nilai skalar = 0 atau disebut juga vektor nol (lihat Gambar 6). Maka dari itu π3 dipilih jika memenuhi syarat pada Persamaan 1. ββββββββ ββββββββ |π 1 π2 Γ π1 π3 | ! = 0
d.
Gambar 3. Ilustrasi permasalahan Convex Hull 3D
2.
(1)
π4 Untuk titik ke empat, dipilih titik yang jika dihubungkan dengan π1 menjadi sebuah vektor ββββββββ π1 π4 , garis tersebut tidak berada pada bidang yang sama dengan segitga/sisi π1 π2 π3 yang dibentuk oleh π1 , π2 dan π3 (lihat Gambar 7). Jika sebuah titik π4 berada pada bidang yang sama dengan sisi ββββββββ π1 π2 π3 , maka nilai dot product dari π 1 π4 dengan ββββββββ hasil cross product sisi π1 π2 π3 (π1 π2 Γ ββββββββ π1 π3 ) akan menghasilkan nilai nol. Maka dari itu π4 dapat dipilih jika memenuhi syarat pada Persamaan 2. ββββββββ π1 π4 βββββββββββββ β (π1 π2 Γ ββββββββ π1 π3 ) ! = 0
Gambar 4. Ilustrasi algoritma Incremental
2
(2)
Membentuk empat sisi dari tetrahedron sedemikian rupa, sehingga semua bagian yang berada di dalam tetrahedron tersebut merupakan bagian belakang dari
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print)
3.
keempat sisi tersebut (lihat Gambar 8). Misalkan salah satu sisi yaitu π1 π2 π3 yang dibentuk dari π1, π2 dan π3 . Titik yang lain (π4 ) harus berada di belakang sisi tersebut, atau dengan kata lain ββββββββ π1 π4 βββββββββββββ β (π1 π2 Γ ββββββββ π1 π3 ) harus lebih kecil dari 0. Jika ternyata π4 berada di βββββββββββββ ββββββββ ββββββββ depan sisi tersebut (π 1 π4 β (π1 π2 Γ π1 π3 ) > 0), maka sisi tersebut harus diubah menjadi π1 π3 π2 , karena nilai dari ββββββββ π1 π4 βββββββββββββ β (π1 π3 Γ ββββββββ π1 π2 ) pasti lebih kecil dari 0. Hal tersebut juga berlaku untuk ke tiga sisi lainnya (π1 π2 π4 , π1 π3 π4 dan π2 π3 π4 ). Jika ke empat sisi telah dibentuk, maka Convex Hull 3D dengan empat titik telah dibentuk. Jika set S memiliki titik lebih dari empat, maka akan dibentuk Convex Hull setiap penambahan satu titik mulai dari titik kelima hingga titik terakhir. Saat penambahan titik baru, misalnya titik π (π β π dan π ! = π1 , π2 , π3 , π4 ). Harus ditemukan dulu sisi-sisi mana saja yang berhadapan dengan titik π (titik π berada di depan sisi tersebut). Jika titik π tersebut berada di depan sebuah sisi, maka sisi tersebut akan dihapus. Setelah itu akan dibentuk sisi-sisi baru dengan cara menghubungkan titik π ke titik-titik pembentuk sisi yang dihapus tadi. Ada kemungkinan, lebih dari satu sisi yang berhadapan dengan titik π tersebut. Untuk mencari sisi mana saja yang berhadapan dengan titik π. Caranya bisa diibaratkan seperti orang yang berdiri di posisi titik π dan melihat ke arah Convex Hull, maka terdapat beberapa sisi yang terlihat oleh mata, sedangkan beberapa sisi yang lain tidak terlihat. Pada Gambar 9 sisi yang berwarna putih merupakan sisi yang berhadapan dengan titik π, sedangkan sisi yang berwarna abu-abu merupakan sisi yang tidak berhadapan dengan titik π (berada di belakang). Semua sisi yang berwarna putih nantinya akan dihapus kemudian akan dibentuk sisi-sisi baru seperti yang ditunjukkan pada Gambar 10.
Gambar 8. Bagian dalam tetrahedron
3
Gambar 9. Convex Hull sebelum penambahan titik π
Gambar 10. Convex Hull setelah penmbahan titik π
Gambar 11, 12 dan 13 merupakan pseudocode dari proses pembentukan Convex Hull untuk titik kelima sampai titik terakhir. ConstructCH3D Input : F : A set contain with 4 faces P : A set of points n : Total of point count : Total of faces right now Output: F : A set of faces 1. for i=4 to n-1 do 2. for j=0 to count-1 do 3. if(F[j].visible=true PointPositionFromFace( P[i],F[j]>0) do 4. DFS(i,j) 5. break 6. endfor 7. endfor Gambar 11. Pseudocode fungsi ConstructCH3D DFS Input : noP : current point index noF : current face index F : a set of face Output: 1. F[noF].visible β false 2. CHECK(noP, F[noF].b, F[noF].a) 3. CHECK(noP, F[noF].c, F[noF].b) 4. CHECK(noP, F[noF].a, F[noF].c) Gambar 12. Pseudocode fungsi DFS
&
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print) CHECK Input : noP : current point index x : first point y : second point count : Total of faces right now Output: 1. f β to[x][y] 2. temp β Γ 3. if(F[f].visible == true) then 4. if(PointPositionFromFace(P[noP],F[f])>0) then 5. DFS(noP,f) 6. else 7. temp.a β y 8. temp.b β x 9. temp.c β noP 10. temp.visible β true 11. to[noP][y] β count 12. to[y][x] β count 13. to[x][noP] β count 14. F[count] β temp 15. count β count + 1 Gambar 13. Pseudocode fungsi DFS
Gambar 14. Umpan balik dari situs SPOJ
III. HASIL UJI COBA Pada bab ini akan dijelaskan mekanisme uji coba yang dilakukan. Pertama akan dilakukan uji coba dengan mengunggah kode sumber dari program yang telah di buat ke situs penilaian daring SPOJ. Uji coba selanjutnya yaitu uji coba kebenaran dari implementasi program yang telah dibuat. Kemudian uji coba yang ketiga yaitu uji coba kinerja dari program yang telah dibuat.. Uji coba keempat yaitu uji coba visualisasi dan yang terakhir adalah analisis kompleksitas. A.
Uji Coba Melalui SPOJ Dalam uji coba ini, kode sumber dari progam yang telah dibuat diunggah ke situs penilaian daring SPOJ pada soal yang berjudul βConvex Hull 3Dβ [3]. Ketentuan-ketentuan dari soal telah disesuaikan dengan yang diminta pada soal tersebut. Setelah kode sumber diunggah, situs SPOJ akan memberikan umpan balik. Jika hasil keluaran program sesuai dengan ketentuan pada soal, maka situs SPOJ akan menampilkan umpan balik berupa tulisan βAcceptedβ, tetapi jika sebaliknya, maka akan muncul umpan balik berupa tulisan βWrong Answerβ, βTime Limit Exceededβ atau βRuntime Errorβ. Dari uji coba ini, didapatkan bahwa kode program hasil implementasi pada publikasi ini mendapat umpan balik βAcceptedβ seperti pada Gambar 14 yang berarti program berjalan dengan benar dengan menggunakan memori sebesar 6.5 MB dan waktu eksekusi program terhadap masukan SPOJ sebesar 0.58 detik. B.
Uji Coba Kebenaran Pada uji coba ini akan dilakukan pengujian program dengan data masukan berupa objek 3-dimensi dengan jumlah titik yang sedikit. Uji coba kebenaran dilakukan dengan cara membandingkan hasil keluaran program dengan hasil keluaran
4
yang didapatkan dengan algoritma naif/bruteforce (Gambar 15) [1]. Dengan menggunakan program yang telah diimplementasikan pada publikasi ini, jika diberikan data masukan seperti pada Gambar 16, luas permukaan dan volume Convex Hull yang dihasilkan adalah seperti yang tertera pada Gambar 17. Hasil ini akan dibandingkan dengan hasil keluaran algoritma naif jika diberikan masukan yang sama. BruteForceConvexHull3D Input : S : A set of points in the plane. Output: E : A list of convexhull(S) faces. 1. 2. 3. 4. 5. 6. 7. 8. 9.
E β Γ for all pair (A,B,C) Ο΅ S & A != B != C do valid β true for all points D Ο΅ S & D not equal to A|B|C if D lies to the front of face ABC then valid β false endfor if valid β true then add face ABC to E 10. Endfor Gambar 15. Pseudocode algoritma Convex Hull 3D secara naif 1 8 5 3 7 -5 3 -7 9 -3 2 1 8 -4 -5 0 6 -5 -5 -5 0 0 0 5 -7 -3 Gambar 16. Data masukan untuk uji coba kebenaran 543.53 814.67 Gambar 17. Hasil keluaran program
0 2 3 0 3 4 0 4 2 1 3 7 1 4 3 1 5 4 1 7 5 2 4 7 2 7 3 4 5 7 Gambar 18. Hasil keluaran algoritma naif Tabel 1. Tabel perhitungan luas permukaan and volume setiap sisi pada hasil keluaran algoritma naif Sisi Luas Permukaan Volume 0 1 2 3 4 5 6 7 8 9 Total
55.66 64.27 45.22 60.49 54.51 49.00 41.67 54.82 55.39 62.50 543.53
103.17 93.67 64.50 89.67 79.67 81.67 73.33 67.17 85.17 76.67 814.67
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print)
5
Hasil perhitungan pada Tabel 1 menghasilkan nilai keluaran yang sesuai dengan nilai keluaran pada Gambar 18, maka terbukti bahwa hasil implementasi program dalam publikasi ini adalah benar. C.
Analisis Kompleksitas Pada subbab ini, akan dilakukan analisis kompleksitas terhadap algoritma pembentukan Convex Hull 3D yang telah dirancang dengan tujuan untuk dibandingkan dengan kompleksitas hasil uji coba kinerja pada subbab berikutnya. Pada algoritma Incremental yang telah dirancang, proses penambahan titik ke-5 hingga titik terakhir merupakan proses yang memiliki proses perulangan yang paling banyak. Maka dari itu, pseudocode pada Gambar 13 perlu dianalisis biayanya untuk menentukan kompleksitas pada algoritma ini. Pada Tabel 2, dapat disimpulkan bahwa kompleksitas dari algoritma pembentukan Convex Hull 3D yang telah dirancang pada publikasi ini yaitu π(π β πππ’ππ‘) atau π(ππ) untuk π buah titik dan π buah sisi. Uji Coba Kinerja Pada subbab ini akan dilakukan uji coba kinerja program dengan melakukan beberapa kali pengujian dengan data masukan berupa objek 3-dimensi dengan jumlah titik yang berbeda untuk masing-masing pengujian. Uji coba ini bertujuan untuk menunjukkan pengaruh banyaknya titik dan sisi terhadap waktu eksekusi program. Pada Tabel 3 setiap uji coba dilakukan berulang-ulang sebanyak 100 kali dengan tujuan agar waktu eksekusi program dapat diamati. Hasil uji coba pada Tabel 3 dapat digambarkan ke dalam bentuk grafik seperti yang ditunjukkan pada Gambar 19.
Gambar 19 Grafik pengaruh waktu eksekusi program terhadap jumlah titik
D.
Tabel 2. Analisis kompleksitas pseudocode pada Gambar 13 ConstructCH3D Banyak Biaya Biaya eksekusi per eksekusi for i=4 to n-1 do n-4 1 n-4 for j=0 to count-1 do n-4 * count 1 n-4 * count if(F[j].visible=true & n-4 * count 1 n-4 * count PointPositionFromFace( P[i],F[j]>0) do DFS(i,j) break endfor Endfor Kompleksitas
n-4 * count n-4 * count
count 1
n-4 * count n-4 * count
O(n count)
Tabel 3. Tabel pengaruh jumlah titik terhadap waktu eksekusi program
No
1 2 3 4 5 6 7 8 9 10
n
100 200 300 400 500 600 700 800 900 1000
F
271 317 356 383 416 443 476 503 536 563
Banyaknya testcase 100 100 100 100 100 100 100 100 100 100
Waktu eksekusi program (detik) 0.02 0.06 0.11 0.16 0.24 0.32 0.40 0.51 0.61 0.73
Gambar 20 Tampilan objek sebelum dan setelah pembentukan Convex Hull 3D
Gambar 21 Tampilan di dalam objek setelah pembentukan Convex Hull 3D
Seperti yang dapat dilihat pada Gambar 19, grafik pertumbuhan waktu cenderung mendekati kurva kuadratik. Hal ini sesuai dengan kompleksitas dari algoritma Incremental yang dibahas pada publikasi ini. E.
Uji Coba Visualisasi Pada subbab ini akan dilakukan uji coba dari program visualisasi Convex Hull 3D yang telah diimplementasikan. Salah satu fitur dari visualisasi Convex Hull 3D adalah menampilkan tampilan objek sebelum dan setelah pembentukan Convex Hull 3D yang ditunjukkan pada Gambar 20. Kemudian pada Gambar 21 diperlihatkan area di dalam Convex Hull, dimana terdapat titik-titik yang bukan merupakan boundary. IV. KESIMPULAN DAN SARAN Berdasarkan hasil uji coba yang telah dilakukan, terdapat tiga kesimpulan yang bisa diambil, yaitu: 1) Pada hasil uji coba kebenaran dan hasil uji coba pada situs SPOJ, ditunjukkan bahwa hasil dari pembentukan Convex Hull 3D yang dihasilkan oleh program sesuai dengan hasil yang diinginkan. Hal tersebut membuktikan bahwa hasil implementasi pembentukan algoritma Convex Hull 3D dengan algoritma Incremental pada publikasi ini dapat menghasilkan keluaran yang benar.
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print) 2)
3)
Pada hasil uji coba kinerja dan analisis kompleksitas ditunjukkan bahwa pertumbuhan waktu eksekusi program bersifat kuadratik dengan kompleksitas Ξ(ππ) pada π buah titik dan π sisi. Hasil uji coba visualisasi menunjukkan bahwa visualisasi Convex Hull 3D yang dihasilkan oleh program sesuai dengan hasil yang diinginkan. Hal tersebut membuktikan bahwa hasil implementasi visual Convex Hull 3D pada publikasi ini menghasilkan keluaran yang benar.
Pada publikasi ini, batasan jumlah titik pada satu objek 3dimensi hanya 1000 titik. Maka dari itu algoritma dengan kompleksitas Ξ(ππ) masih dapat berjalan dengan cepat. Tetapi pada kenyataannya terdapat objek yang memiliki lebih dari 1000 titik. Pada pengembangan publikasi ini, dapat dilakukan studi mengenai pengembangan algoritma-algoritma pembentukan Convex Hull lainnya yang memiliki kompleksitas Ξ(π log π) yang dapat menyelesaikan permasalahan Convex Hull 3D pada objek yang memiliki lebih dari 1000 titik dengan waktu yang lebih efisien. UCAPAN TERIMA KASIH Penulis mengucapkan puji syukur kepada Allah SWT yang melimpahkan rahmat dan hidayahnya sehingga penulis dapat menyelesaikan penelitian ini dengan lancar. Penulis juga mengucapkan terima kasih kepada Bapak Rully Soelaiman dan Bapak Arya Yudhi Wijaya yang telah membantu penulis dalam menyelesaikan penelitian ini dengan lancar. Penulis juga mengucapkan terima kasih kepada pihak-pihak lain yang turut membantu kelancaran penelitian ini. DAFTAR PUSTAKA [1] M. d. Berg, O. Cheong, M. v. Kreveld dan M. Overmars, Computational Geometry: Algorithms and Application, 2008. [2] D. G. Zill dan M. R. Cullen, Advanced Engineering Mathematics, 2006. [3] SPOJ, β760. Convex Hull 3D,β November 2005. [Online]. Available: http://www.spoj.com/problems/CH3D/.
6
