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

Graham Scan Algoritması, düzlemde verilen bir nokta kümesinin convex hull’unu (dış sınırını) bulmak için kullanılan klasik bir yöntemdir.

Convex Hull Nedir?

Convex hull, tüm noktaları içine alan en küçük dış çerçevedir. Bunu şöyle düşünebilirsin: Noktaların etrafına bir lastik bant geçiriyorsun; bant hangi noktaların üzerinden geçerek geriliyorsa, o noktalar convex hull’u oluşturur.

Algoritma Adım Adım Ne Yapıyor?

• Başlangıç Noktasını Seçer
• En küçük y koordinatına sahip noktayı seçer.
• Eğer birden fazla varsa, en küçük x koordinatına sahip olan seçilir.
• Bu nokta “anchor” (referans noktası) olur.

Noktaları Sıralar

• Diğer tüm noktalar, anchor noktasına göre kutupsal açılarına (polar angle) göre sıralanır.
• Böylece noktalar saat yönünün tersine doğru düzenlenmiş olur.

Stack (Yığın) Kullanarak Taramaya Başlar

• İlk iki nokta stack’e konur.
• Sonraki her nokta için:
• Stack’teki son iki nokta ile yeni noktanın oluşturduğu dönüş yönüne bakılır.

Dönüş Yönü Kontrolü (Orientation Check)

• Eğer dönüş saat yönünün tersine (counterclockwise) ise → nokta hull’un parçasıdır.
• Eğer dönüş saat yönünde (clockwise) ise → ortadaki nokta içeride kalıyordur, stack’ten çıkarılır.
• Bu kontrol, convex yapı bozulmayana kadar devam eder.

Sonuç

• Tüm noktalar işlendiğinde stack’te kalan noktalar convex hull’u oluşturur.

Nerelerde Kullanılır?

• Robotik (engel çevreleme)
• Bilgisayar grafikleri
• Harita ve mekânsal analiz
• Çarpışma tespiti
• Geometrik modelleme

  import matplotlib.pyplot as plt
  
  # 2 nokta ve 1 referans noktası ile yön tayini (cross product)
  def orientation(p, q, r):
      return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])
  
  # Mesafe (sıralama için)
  def distance(p, q):
      return (p[0] - q[0])**2 + (p[1] - q[1])**2
  
  def graham_scan(points):
      # En alt (y), eşitse en sol (x)
      start = min(points, key=lambda p: (p[1], p[0]))
  
      # Açısal sıralama
      sorted_points = sorted(points, key=lambda p: (
          -orientation(start, p, (start[0]+1, start[1])),  # açı
          distance(start, p)
      ))
  
      # Hull oluşturma
      hull = []
      for p in sorted_points:
          while len(hull) >= 2 and orientation(hull[-2], hull[-1], p) <= 0:
              hull.pop()
          hull.append(p)
  
      return hull
  
  # Örnek noktalar
  points = [
      (0, 2), (1, 1), (2, 8), (4, 4),
      (0, 0), (1, 2), (3, 1), (3, 3)
  ]
  
  hull = graham_scan(points)
  
  # Görselleştirme
  x_all = [p[0] for p in points]
  y_all = [p[1] for p in points]
  
  x_hull = [p[0] for p in hull] + [hull[0][0]]
  y_hull = [p[1] for p in hull] + [hull[0][1]]
  
  plt.scatter(x_all, y_all, label="Noktalar")
  plt.plot(x_hull, y_hull, 'r-', label="Convex Hull")
  plt.legend()
  plt.title("Graham Scan Convex Hull")
  plt.show()