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

Langkah-langkah penggunaan algoritma ini adalah

1. Simpan titik pertama dan titik terakhir pada jalur tersebut

daftarIdxTitik.Add(idxTitikAwal)
daftarIdxTitik.Add(idxTitikTujuan)

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

While daftarTitik(idxTitikAwal).Equals(daftarTitik(idxTitikTujuan))
	idxTitikTujuan -= 1
End While

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

DouglasPeuckerReduction(daftarTitik, idxTitikAwal, idxTitikTujuan, toleransi, daftarIdxTitik)

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

For idx As Int32 = idxTitikAwal To idxTitikTujuan - 1
	Dim jarak As Double = hitungJarakTegakLurus(daftarTitik(idxTitikAwal), daftarTitik(idxTitikTujuan), daftarTitik(idx))
	If jarak > maksJarak Then
		maksJarak = jarak
		idxTerjauh = idx
	End If
Next

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

Public Shared Function hitungJarakTegakLurus(titik1 As Titik, titik2 As Titik, titik3 As Titik) As Double
	'Hitung area segitiga dengan rumus 
	'Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|
	Dim area As Double = Math.Abs(0.5 * (titik1.X * titik2.Y + titik2.X * titik3.Y + titik3.X * titik1.Y - titik2.X * titik1.Y - titik3.X * titik2.Y - titik1.X * titik3.Y))

	'Hitung sisi bawah segitiga dengan rumus
	'sisiBawah = √((x1-x2)²+(x1-x2)²)
	Dim sisiBawah As Double = Math.Sqrt(Math.Pow(titik1.X - titik2.X, 2) + Math.Pow(titik1.Y - titik2.Y, 2))

	'Hitung tinggi segitiga dengan rumus
	'Tinggi = Area/.5/sisiBawah
	Dim tinggi As Double = area / sisiBawah * 2

	Return tinggi
End Function

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

If maksJarak > toleransi AndAlso idxTerjauh <> 0 Then
	daftarIdxTitik.Add(idxTerjauh)

	DouglasPeuckerReduction(daftarTitik, idxTitikAwal, idxTerjauh, toleransi, daftarIdxTitik)
	DouglasPeuckerReduction(daftarTitik, idxTerjauh, idxTitikTujuan, toleransi, daftarIdxTitik)
End If

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

Dim hasil As New List(Of Titik)()
daftarIdxTitik.Sort()
For Each idx As Int32 In daftarIdxTitik
	hasil.Add(daftarTitik(idx))
Next

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

If isHitungDouglasPeucker Then
	Dim daftarTitikDP As List(Of Titik) = DouglasPeucker.ProsesDouglasPeucker(daftarTitik, Convert.ToDouble(numToleransi.Value))

	daftarTitikTergambar = New List(Of System.Drawing.Point)()
	For Each titik As Titik In daftarTitikDP
		daftarTitikTergambar.Add(New System.Drawing.Point(Convert.ToInt32(titik.X), Convert.ToInt32(titik.Y)))
	Next

	'e.Graphics.DrawLines(New Pen(Brushes.Blue, 4), daftarTitikTergambar.ToArray())
	lblTitikHasilAkhir.Text = daftarTitikTergambar.Count.ToString()

	Dim bmp As Bitmap = New Bitmap(PictureBox1.Width, PictureBox1.Height)
	Dim gr As Graphics = Graphics.FromImage(bmp)
	gr.DrawLines(New Pen(Brushes.Red, 4), daftarTitikTergambar.ToArray())

	PictureBox1.Image = bmp.Clone
	bmp.Dispose()
End If

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

Dengan batas toleransi 0.5, maka titik yang perlu digambar dikurangi menjadi 144 titik saja

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.

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.

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.