Java Programming‎ > ‎Graphics 2D‎ > ‎

Penyederhanaan Polyline dengan Algoritma Douglas-Peucker

posted Aug 28, 2011, 8:11 AM by Editor KursusInternet   [ updated Sep 9, 2011, 8:41 PM ]

Pendahuluan

Algoritma Douglas-Peucker adalah algoritma yang umum digunakan untuk menyederhanakan titik-titik garis polyline. Penyederhanaan diperlukan karena berbagai hal, seperti menghilangkan detil yang tidak perlu dan pengecilan ukuran file penyimpan titik vector grafis.

Ide dasar algoritma ini adalah jarak titik antara yang bersifat garis lurus ke garis penghubung antara 2 titik yang diamati, kemudian jarak tersebut akan dibandingkan dengan sebuah nilai epsilon - yang sebenarnya merupakan ukuran lebar - untuk memutuskan apakah titik antara tersebut dihilangkan atau tidak.

Untuk lebih jelasnya bagian berikut di bawah ini akan mengilustrasikan cara kerja algoritma ini untuk 2 kasus.

Ilustrasi Cara Kerja Algoritma : Kasus 1

Gambar berikut di bawah ini mencoba mengilustrasikan proses penyederhaan titik-titik polyline berdasarkan algoritma Douglas Peucker, dimana pada akhirnya tidak ada titik yang dihilangkan untuk kasus ini.



Pada awalnya kita memiliki 4 titik (A, B, C dan D) yang coba disederhanakan. Epsilon atau lebar antar titik menjadi bidang acuan untuk menghilangkan titik. 

Pertama, kita akan menarik titik A dan D sebagai titik ujung dari polyline tersebut. Dengan lebar epsilon yang kita tempatkan pada sepanjang garis A-D maka tidak ada titik yang dicapai oleh bidang epsilon tersebut, untuk ini tidak ada titik yang dihilangkan.

Proses selanjutnya adalah dari titik-titik antara A dan D, yaitu B dan C, diambil titik yang memiliki panjang maksimum ke garis A dan D, yaitu B. Dengan pengambilan titik ini kita bertujuan memecah polyline ke dua garis lurus baru dengan B sebagai titik ujung baru. Pada akhirnya kita dapatkan garis A-B dan garis B-D.

Kita ulangi lagi penempatan bidang epsilon pada garis A-B dan kembali tidak ada yang menjadi cakupan bidang epsilon sehingga tidak ada titik yang dihilangkan. Demikian juga untuk garis B-D, tidak ada titik yang dihilangkan untuk alasan yang sama.

Dan karena masih ada titik antara pada garis B-D, kita ulangi lagi proses pembagian garis dan penempatan bidang epsilon pada garis B-C dan C-D. Dan tetap tidak ada titik yang menjadi bagian bidang epsilon sehingga penghilangan titik tidak terjadi.

Ilustrasi Cara Kerja Algoritma : Kasus 2

Gambar berikut di bawah ini mencoba mengilustrasikan proses penyederhaan titik-titik polyline berdasarkan algoritma Douglas Peucker, dimana pada akhirnya ada titik yang dihilangkan untuk kasus ini.



Pada awalnya kita memiliki 4 titik (A, B, C dan D) yang coba disederhanakan. Epsilon atau lebar antar titik menjadi bidang acuan untuk menghilangkan titik. 

Pertama, kita akan menarik titik A dan D sebagai titik ujung dari polyline tersebut. Dengan lebar epsilon yang kita tempatkan pada sepanjang garis A-D ada titik yang dicapai oleh bidang epsilon tersebut (C), tetapi karena tersisa satu titik yang tidak dicakup yaitu titik B maka titik C belum bisa dihilangkan.

Proses selanjutnya adalah dari titik-titik antara A dan D, yaitu B dan C, diambil titik yang memiliki panjang maksimum ke garis A dan D, yaitu B. Dengan pengambilan titik ini kita bertujuan memecah polyline ke dua garis lurus baru dengan B sebagai titik ujung baru. Pada akhirnya kita dapatkan garis A-B dan garis B-D.

Masing-masing garis tersebut ditempatkan bidang epsilon. Untuk garis A-B tidak ada titik antara sehingga titik-titik pada garis tersebut tidak dihilangkan. Sedangkan titik antara pada B-D kena bidang epsilon, yaitu C sehingga akhirnya C dihilangkan.

Karena tidak ada lagi titik antara yang tersisa maka proses tersebut selesai. Dan hasil akhir titik-titik yang tertinggal adalah A, B dan D.

Contoh Penerapan : Penyederhanaan Titik Peta

Berikut adalah contoh penerapan nyata dari algoritma Douglas Peckeur yaitu penggambaran garis pantai dengan rincian yang disederhanakan sesuai kebutuhan.





Sumber Referensi

Comments