Analisis Performa Algoritma Route Segmentation dalam Mengidentifikasi Area Perimeter Sekitar Rute Perjalanan

Aplikasi navigasi seperti Google Maps belum menyediakan cara langsung untuk mencari Point of Interest (POI) di sepanjang sebuah rute perjalanan, hanya di sekitar satu titik. RouteBoxer — pendekatan yang ada — berjalan dengan kompleksitas O(n³) sehingga lambat untuk rute panjang. Studi ini mengusulkan RouteSegmentation: menghasilkan poligon perimeter (gabungan persegi panjang dan setengah lingkaran) di sepanjang setiap segmen rute, lalu menggabungkannya melalui operasi union poligon, dengan kompleksitas O(n).

Tidak ada cara efisien untuk mengidentifikasi area perimeter di sepanjang seluruh rute perjalanan (bukan hanya satu titik) guna pencarian POI, karena pendekatan RouteBoxer yang ada terlalu lambat (O(n³)) untuk rute dengan banyak titik.

RouteSegmentation membentuk poligon perimeter di setiap segmen rute (persegi panjang + setengah lingkaran di ujungnya), lalu menggabungkan seluruh poligon menjadi satu area perimeter menggunakan tiga strategi union yang dibandingkan: Overlay Union, Unary Union, dan Cascaded Union.

Diuji pada rute sepanjang 10,1 km di Kota Malang (350 titik dari Google Maps Directions API), dipecah menjadi 70 subset rute berisi 5 hingga 350 titik. Setiap subset diukur 30 kali (total 2100 pengukuran) di Android emulator (4-core CPU, API 34).

Pembuatan segmen rata-rata memakan waktu kurang dari 1 milidetik. Unary Union dan Cascaded Union sama-sama mengungguli Overlay Union dalam waktu eksekusi dan penggunaan memori, hasil yang signifikan secara statistik (uji Wilcoxon, p<0,001).

Memperkenalkan RouteSegmentation sebagai alternatif O(n) dari RouteBoxer untuk mengidentifikasi area perimeter di sepanjang rute perjalanan, membuka jalan bagi pencarian POI di sepanjang rute, bukan hanya di sekitar satu titik.

Perilaku garbage collector yang tidak dapat diprediksi memengaruhi akurasi pengukuran memori selama eksperimen.