 Python'da dışbükey gövde algoritmasını uygulayın - bir dizi nokta verildiğinde, dışbükey gövde kümesini döndürün.
Elbette! İşte Graham'ın tarama yaklaşımı kullanılarak dışbükey gövde algoritmasının bir Python uygulaması: ``` import math def direction(p, q, r): """ Sıralı üçlünün (p, q, r) yönünü bulun. Dönüş: 0 p, q, r doğrusal ise 1 saat yönünde ise 2 saat yönünün tersine ise """ val = (q[1] - p[1]) * (r[0] - q[0]) - \ (q[0] - p[0]) * (r[1] - q[1]) if val == 0: dönüş 0 # eşdoğrusal elif val > 0: dönüş 1 # saat yönünde aksi: dönüş 2 # saat yönünün tersine def convex_hull(points): "" " Bir nokta kümesinin dışbükey gövdesini bulun. Args: puanlar: Noktaları temsil eden demetlerin listesi, örneğin [(0,0), (1,1), (2,-1)] Döndürür: Bir demet kümesi dışbükey gövdenin köşelerini saat yönünde temsil eden """ # Noktaları x-koordinatlarına ve ardından y-koordinatlarına göre sırala noktalar = sıralanmış(set(noktalar)) if len(points) <= 1: dönüş noktaları else: # Bul alt gövde lower_hull = [] noktalar için nokta: len(lower_hull) >= 2 ve oryantasyon(lower_hull[-2], lower_hull[-1], nokta) == 1: lower_hull.pop() lower_hull.append(nokta ) # Tersine çevrilmiş(noktalar): len(upper_hull) >= 2 ve oryantasyon(upper_hull[-2], Upper_hull[-1], point) == 1: Upper_hull.pop( ) Upper_hull.append(nokta) # Alt ve üst gövdeleri birleştirin ve kopyaları çıkarın hull = lower_hull[:-1] + Upper_hull[:-1] hull = list(set(hull)) # Tepe noktalarını saat yönünde sıralayın hull.sort( key=lambda p: math.atan2(p[1]-lower_hull[0][1], p[0]-lower_hull[0][0])) dönüş hull ``` Bu işlevi `convex_hull'u çağırarak kullanabilirsiniz. (noktalar)` burada "noktalar", noktaları temsil eden demetlerin bir listesidir. Dışbükey gövdenin köşelerini saat yönünde temsil eden bir dizi demet döndürür.