Algoritma Douglas-Peucker


Algoritma Douglas-Peucker adalah algoritma yang dapat digunakan untuk optimasi saat pengolahan citra. Contoh yang dibahas kali ini adalah mengenai pengurangan jumlah titik yang perlu digambar dalam sebuah jalur.
Algoritma ini biasanya berfungsi pada saat terdapat penggambaran jalur pada sebuah peta dimana peta tersebut memiliki fitur zoom. Jika zoom diperkecil (zoom out), maka jalur yang perlu digambar akan menjadi lebih kecil sehingga tidak perlu menggunakan semua titik, melainkan hanya titik-titik yang dianggap penting saja yang disimpan untuk mewakili gambar dari jalur tersebut

Diasumsikan gambar jalur yang perlu digambar adalah sebagai berikut
dp-awal


Langkah-langkah penggunaan algoritma ini adalah

1. Simpan titik pertama dan titik terakhir pada jalur tersebut

2. Lakukan pencarian Titik sebelumnya sampai ditemukan titik yang tidak sama dengan titik pertama

3. Lakukan proses pengurangan jumlah titik menggunakan Douglas-Peucker
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Memasuki perhitungan utama pada fungsi DouglasPeuckerReduction

3a. Lakukan perhitungan pada masing-masing titik dalam daftar
Hitung jarak tegak lurus antara titik awal, titik tujuan, dan titik terpilih
Simpan indeks titik yang memiliki jarak terjauh
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

* Gunakan fungsi ini untuk menghitung jarak tegak lurus antara 3 titik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

3b. Jika jarak terjauh melebihi batas toleransi
maka tambahkan titik terjauh yang melebihi nilai toleransi
dan lakukan proses ini kembali menggunakan titik terjauh sebagai input

4. Urutkan daftar titik yang ditemukan dalam perhitungan
Kemudian simpan nilainya sebagai jawaban

* Selanjutnya tinggal menggambar garis antara titik-titik tersebut pada layar


Hasil akhir adalah: (klik untuk perbesar gambar)

Dalam contoh ini digunakan jalur yang memiliki 352 titik.
Dengan batas toleransi 0, maka titik yang perlu digambar dikurangi menjadi 181 titik saja
dp-toleransi-0

Dengan batas toleransi 0.5, maka titik yang perlu digambar dikurangi menjadi 144 titik saja
dp-toleransi-0-5

Demikian seterusnya apabila nilai toleransi ditambah, maka jumlah titik yang disimpan akan terus berkurang. Dan tentu saja gambar jalur akan menjadi semakin halus dengan nilai kesalahan akan semakin besar. Berikut adalah hasil perhitungan dengan batas toleransi 1, 2, 3, 5, 10, dan jumlah titik akan terus menerus berkurang sampai dengan 10 titik.
dp-toleransi-1

dp-toleransi-2

dp-toleransi-3

dp-toleransi-5

dp-toleransi-10

Dan tentu saja apabila batas toleransi dinaikkan terus menerus, maka akhirnya jalur hanya memerlukan 2 titik saja, tetapi tentu saja gambar jalur tersebut sudah tidak sesuai dengan gambar awal.
dp-toleransi-66-25


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *