Studi dan eksplorasi CGAL

Abstract

Komputasi geometris adalah studi yang mempelajari algoritma dan struktur data mengenai objek geometri, yang bertujuan untuk menyelesaikan permasalahan geometri. Komputasi geometris memiliki peran yang penting dalam berbagai macam teknologi maju pada saat ini. Banyak aplikasi modern yang memanfaatkan komputasi geometris, seperti grafika komputer, Geographic Information System (GIS), robotik, dan pencitraan medis. Namun, terdapat banyak rintangan yang ditemukan jika algoritma dan struktur data komputasi geometris diimplementasikan dari awal. Salah satu rintangan yang sering dihadapi dalam proses pengimplementasian adalah presisi. Untuk mendapatkan solusi permasalahan geometri yang benar, implementasi harus memiliki presisi yang tinggi(atau cukup tinggi untuk menghasilkan output yang diinginkan). Di samping presisi, algoritma yang diimplementasi juga harus bisa mengatasi degenerate cases pada komputasi geometris. Selain memiliki beberapa rintangan, beberapa algoritma dan struktur komputasi geometris juga merupakan bagian dari algoritma komputasi geometris lainnya. Oleh dari itu, untuk mempermudah menyelesaikan pemasalahan geometri, penggunaan library yang terpercaya sangat dianjurkan. Salah satu library komputasi geometris adalah CGAL. Computational Geometry Algorithms Library (CGAL) adalah sebuah proyek open source berbentuk C++ library, yang menyediakan berbagai algoritma dan stuktur data, untuk membantu menyelesaikan permasalahan komputasi geometris. Agar dapat memanfaatkan CGAL dengan baik, studi dan eksplorasi terhadap CGAL perlu dilakukan. Terdapat beberapa prasyarat yang dianjurkan sebelum studi dan eksplorasi dilakukan. Karena CGAL merupakan library bahasa pemgrograman C++ untuk permasalahan komputasi geometris, maka sangat disarankan untuk mengetahui dasar-dasar C++ dan komputasi geometris sebelum melakukan studi dan eksplorasi. Pada penelitian ini, telah dilakukan studi dan eksplorasi dengan cara membangun dua buah program yang memanfaatkan CGAL. Program pertama adalah implementasi algoritma divide and conquer convex hull, untuk mencari convex hull. Convex hull adalah convex set terkecil yang melingkupi kumpulan titik. Sedangkan program kedua yang dibangun adalah surface reconstruction from point clouds (SRPC). SRPC adalah pembangunan model permukaan objek tiga dimensi yang didefinisikan oleh sekumpulan titik. Kedua program yang dibangun memanfaatkan struktur data dan algoritma yang didefinisikan oleh CGAL. Dengan membangun program yang memanfaatkan CGAL, fitur-fitur CGAL yang tersedia dapat dipelajari dan diketahui secara sekaligus. Karena untuk mempelajari sesuatu dalam programming, cara yang direkomendasikan pada umumnya adalah mengimplementasikan hal tersebut. Setelah studi dan eksplorasi dilakukan, CGAL benar menyediakan fitur-fitur yang penting (umum digunakan pada implementasi permasalahan komputasi geometris). Klaim ini didasarkan oleh keberhasilan pembangunan kedua program yang telah dilakukan. CGAL berperan berat dalam pengimplementasian permasalahan-permasalahan geometri tersebut. Proses pembangunan program menjadi jauh lebih sederhana berkat pemanfaatan fitur-fitur CGAL. Selain kedua permasalahan yang diimplementasikan, CGAL juga menyediakan banyak algoritma untuk menyelesaikan permasalahan-permasalahan komputasi geometris lainnya yang relatif kompleks.