PENERAPAN METODE FAST MARCHING PADA PERHITUNGAN GEODESIC DISTANCE PERMUKAAN OBYEK TRIANGULAR MESH
Abstract: Dalam makalah ini
akan dibahas penerapan algoritma perhitungan geodesic distance pada permukaan
obyek triangular mesh untuk dibuktikan tingkat keakuratan dan efisiensinya.
Algoritma yang diterapkan adalah Fast Marching Method on Triangulated Domain
(FMM on TD) yang berjalan dengan kompleksitas waktu O(n lg n), dimana n adalah
jumlah titik pada permukaan. Inti dari algoritma ini adalah melakukan front
propagation dari titik awal ke segala arah yang mungkin sampai diperoleh titik
akhir. Setiap bergerak maju algoritma ini selalu menghitung nilai jarak suatu
titik terhadap titik awal. Setelah proses perhitungan geodesic distance
selesai, dilakukan proses pembuatan geodesic path. Inti dari proses ini adalah
melakukan back propagation pada permukaan dari titik akhir sampai diperoleh
titik awal. Berdasarkan uji coba, tingkat keakuratan algoritma FMM on TD adalah
lebih dari 95%. Keakuratan ini dipengaruhi oleh jumlah segitiga pembentuk
permukaan. Semakin banyak segitiga semakin akurat geodesic distance yang
dihasilkan, tetapi waktu yang dibutuhkan untuk melakukan proses perhitungan
menjadi semakin lama.
Kata kunci: computational
geometry, geodesic distance, geodesic path, triangular mesh, fast marching
method on triangulated domain, front propagation, back propagation
Penulis: Rully Soelaiman, Eddy
Tjandra, I Made Agus Setiawan
Kode Jurnal: jptinformatikadd060010
