Convex hull, sweep line ve geometrik sağlamlık

Convex hull, noktaları kapsayan en küçük dışbükey çokgendir, çember değildir. Andrew monotone chain önce noktaları sıralar, sonra alt ve üst zincir kurar. Üç noktanın yönünü cross product ile ölçeriz; yanlış dönüş yapan son nokta çıkarılır. Her nokta en fazla bir kez eklenip çıkarıldığı için zincir kurulması doğrusaldır. Graham scan aynı fikri kutupsal sıralamayla uygular; Jarvis march çıktıdaki h köşe için O(nh) çalışır.

Geometride işaret hatası bütün topolojiyi değiştirebilir. Floating-point değerlerine rastgele epsilon eklemek her ölçekte doğru değildir. Tam sayı koordinatlarında taşmayı önle; kayan noktalarda robust orientation predicates veya uygun exact arithmetic kullan. Tekrarlanan noktalar, bütün noktaların doğrusal olması ve sınırdaki doğrusal noktaların korunması sözleşmede belirtilmelidir.

Sweep line, x boyunca ilerleyen olaylar ve aktif küme üzerinden kesişim/alan problemlerini çözer. Olayların aynı x'te sıralanması ve aktif kümenin karşılaştırıcısı kritik ayrıntıdır. Voronoi/Delaunay yakınlık ilişkilerini modeller; her geometrik problem hull değildir. Mesafe karesiyle karşılaştırmak karekökten kaçınır ama koordinat taşmasını ortadan kaldırmaz.

def hull(points):
    points = sorted(set(points))
    if len(points) <= 1: return points
    def cross(a,b,c): return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])
    def chain(ps):
        out=[]
        for p in ps:
            while len(out)>1 and cross(out[-2],out[-1],p)<=0: out.pop()
            out.append(p)
        return out
    return chain(points)[:-1]+chain(points[::-1])[:-1]
assert len(hull([(0,0),(1,0),(1,1),(0,1),(.5,.5)]))==4