Dışbükey zarf

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.

Örnek çözümü göster

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)]))

Kendini test et

zarıftan çıkarma

while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= ____:
    lower.pop()

Cevabı göster

while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
    lower.pop()

Andrew yönteminin karmaşıklığı nedir?
```
pts = sorted(set(points))
```
- O(n log n)
- O(n)
- O(n²)
- O(2ⁿ)
Cevabı göster

O(n log n) — Sıralama O(n log n), tarama O(n); toplam O(n log n).
Dışbükey zarf kavramları

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

Sıradaki ders: İki doğru kesişimi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler