Dışbükey zarf
- Algoritmalar kursu
- Uzman seviye
- Ders 20/41
- 4 dk
Dışbükey zarf bulma algoritmasını öğrenirsin.
Dışbükey zarf
Dışbükey zarf, bir nokta kümesinin tüm noktalarını içine alan en küçük dışbükey poligondur. Lastik bandı noktaların etrafına gerdiğinizde oluşan şekle benzer.
Sık kullanılan algoritma Andrew monoton zincir yöntemidir: noktaları x'e göre sıralar, alt ve üst zarfı ayrı ayrı kurar.
Her adımda çapraz çarpım ile sağa dönük noktaları zarıftan çıkarırız. Karmaşıklık O(n log n)'dir.
Monoton zincir
Andrew yönteminde önce noktaları x'e (eşitse y'ye) göre sıralarız. Sonra alt zarfı soldan sağa, üst zarfı sağdan sola kurarız.
Alt zarıfta her yeni nokta eklenirken, son üç nokta sağa dönük veya doğrusalsa ortadakını çıkarırız. Bu, çapraz çarpım ile sınanır.
Sonunda alt ve üst zarfın son noktaları (başlangıç ve bitiş) aynı olduğundan, birer eleman çıkarıp birleştiririz.
Uygulama convex_hull fonksiyonu
convex_hull(points) yaz. Nokta listesinin dışbükey zarfını saat yönünün tersine döndür. print(convex_hull([(0,0), (4,0), (4,3), (0,3), (2,1)])) ile [(0, 0), (4, 0), (4, 3), (0, 3)] yazdır.
Başlangıç kodu
def convex_hull(points):
# Dışbükey zarfı döndürÖrnek çözüm
def convex_hull(points):
# Dışbükey zarfı döndür
pts = sorted(set(points))
if len(pts) <= 1:
return pts
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
lower = []
for p in pts:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
upper = []
for p in reversed(pts):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
print(convex_hull([(0,0), (4,0), (4,3), (0,3), (2,1)]))Beklenen çıktı
[(0, 0), (4, 0), (4, 3), (0, 3)]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 zarıftan çıkarma
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= ____:
lower.pop()while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()Açıklama: 0 ile sağa dönük veya doğrusal noktalar çıkarılır.
2 Andrew yönteminin karmaşıklığı nedir?
pts = sorted(set(points))- O(n log n) Doğru cevap
- O(n)
- O(n²)
- O(2ⁿ)
Açıklama: Sıralama O(n log n), tarama O(n); toplam O(n log n).
3 Dışbükey zarf kavramları
| Kavram | Anlamı |
|---|---|
monoton zincir |
Andrew yöntemi |
O(n log n) |
Karmaşıklık |
sağa dönük |
Zarıftan çıkar |
sıralama |
İlk adım |