Bilişim dünyasına kaliteli, özgün ve Türkçe içerikler kazandırmayı hedefleyen bir platform..

Douglas–Peucker Algoritması Nedir?

Douglas–Peucker algoritması, bir çizgi veya eğriyi oluşturan nokta sayısını azaltırken genel şekli korumayı amaçlayan en yaygın çizgi sadeleştirme algoritmalarından biridir. 1973 yılında David Douglas ve Thomas Peucker tarafından geliştirilen bu yöntem, özellikle çok sayıda noktadan oluşan karmaşık çizgilerin daha az veri ile temsil edilmesini sağlar.

Algoritma, çizginin başlangıç ve bitiş noktaları arasında düz bir doğru oluşturur. Daha sonra bu doğruya en uzak ara noktayı belirler. Eğer bu noktanın doğruya olan uzaklığı önceden belirlenen tolerans değerinden büyükse, nokta korunur ve algoritma aynı işlemi yeni oluşan alt segmentler üzerinde tekrarlar. Uzaklık tolerans değerinden küçükse, ilgili ara noktalar kaldırılır. Bu işlem sonucunda gereksiz noktalar elenirken çizginin temel geometrik yapısı korunmuş olur.

Douglas–Peucker Algoritması Nasıl Çalışır?

Algoritmanın çalışma mantığı özyinelemeli (recursive) bir yaklaşıma dayanır. İlk olarak çizginin iki uç noktası birleştirilir ve tüm ara noktaların bu doğruya olan dik uzaklıkları hesaplanır. En büyük uzaklığa sahip nokta belirlenir. Bu uzaklık tolerans eşiğini aşarsa, söz konusu nokta yeni bir köşe noktası olarak kabul edilir ve süreç iki yeni alt parça üzerinde tekrar uygulanır. Böylece yalnızca şeklin korunması için gerekli olan noktalar bırakılır.

Douglas–Peucker Algoritmasının Kullanım Alanları

Douglas–Peucker algoritması, coğrafi bilgi sistemlerinden (GIS) bilgisayar grafiklerine kadar birçok alanda kullanılmaktadır. En yaygın kullanım alanlarından biri harita uygulamalarıdır. GPS cihazları ve mobil harita servisleri, binlerce koordinat noktasından oluşan rota verilerini sadeleştirerek hem depolama alanından tasarruf eder hem de haritaların daha hızlı görüntülenmesini sağlar.

Bilgisayar destekli tasarım (CAD) ve grafik uygulamalarında da el çizimi veya serbest çizimlerden oluşan karmaşık çizgilerin daha düzgün ve yönetilebilir hale getirilmesinde kullanılır. Ayrıca vektörel grafiklerin optimize edilmesi, sınır çizgilerinin sadeleştirilmesi, görüntü işleme uygulamalarında kontur azaltımı ve drone ya da uydu görüntülerinden elde edilen şekillerin işlenmesi gibi alanlarda da önemli bir rol oynar.

Douglas–Peucker Algoritmasının Avantajları

Bu algoritmanın en önemli avantajı, veri miktarını önemli ölçüde azaltırken şeklin karakteristik özelliklerini koruyabilmesidir. Böylece depolama maliyetleri düşer, veri işleme hızlanır ve görselleştirme performansı artar. Ayrıca uygulanması nispeten basit olup farklı veri türlerine kolaylıkla uyarlanabilir.

Günümüzde GPS rotaları, dijital haritalar, çizim uygulamaları, robot navigasyonu ve görüntü işleme sistemlerinde yaygın olarak kullanılan Douglas–Peucker algoritması, büyük miktardaki geometrik verilerin daha verimli yönetilmesini sağlayan temel yöntemlerden biri olarak kabul edilmektedir.

Örnek bir Python kodu

import numpy as np

def perpendicular_distance(point, line_start, line_end):
    """
    Bir noktanın doğru parçasına olan dik uzaklığını hesaplar.
    """
    point = np.array(point)
    line_start = np.array(line_start)
    line_end = np.array(line_end)

    if np.all(line_start == line_end):
        return np.linalg.norm(point - line_start)

    return np.abs(
        np.cross(line_end - line_start,
                 line_start - point)
    ) / np.linalg.norm(line_end - line_start)


def douglas_peucker(points, epsilon):
    """
    Douglas-Peucker çizgi sadeleştirme algoritması
    """
    if len(points) < 3:
        return points

    start = points[0]
    end = points[-1]

    max_distance = 0
    index = 0

    for i in range(1, len(points)-1):
        distance = perpendicular_distance(
            points[i], start, end
        )

        if distance > max_distance:
            index = i
            max_distance = distance

    if max_distance > epsilon:
        left = douglas_peucker(points[:index+1], epsilon)
        right = douglas_peucker(points[index:], epsilon)

        return left[:-1] + right
    else:
        return [start, end]
    



points = [
    (0, 0),
    (1, 0.1),
    (2, -0.1),
    (3, 5),
    (4, 6),
    (5, 7),
    (6, 8.1),
    (7, 9),
    (8, 9),
    (9, 9)
]

epsilon = 1.0

simplified = douglas_peucker(points, epsilon)

print("Orijinal nokta sayısı:", len(points))
print("Sadeleştirilmiş nokta sayısı:", len(simplified))
print("\nKalan noktalar:")
for p in simplified:
    print(p)
    



import matplotlib.pyplot as plt

points_np = np.array(points)
simplified_np = np.array(simplified)

plt.figure(figsize=(8,5))

plt.plot(points_np[:,0],
         points_np[:,1],
         'o-',
         label='Orijinal Çizgi')

plt.plot(simplified_np[:,0],
         simplified_np[:,1],
         'ro--',
         linewidth=2,
         markersize=8,
         label='Douglas-Peucker')

plt.legend()
plt.grid(True)
plt.title("Douglas-Peucker Çizgi Sadeleştirme")
plt.xlabel("X")
plt.ylabel("Y")
plt.show()