Konvexní obal

O(n log n)

Konvexní obal množiny bodů je nejmenší konvexní mnohoúhelník, který je všechny uzavře — představ si gumičku nataženou kolem hřebíků na desce, která se nechá stáhnout. Andrewův monotone chain ho najde efektivně: seřaď body zleva doprava, pak jedním průchodem postav spodní hranu a dalším horní hranu. U každého nového bodu zkontroluje zatáčku, kterou s ním tvoří poslední dva body obalu — pokud to není levá zatáčka (vektorový součin je nula nebo záporný, tedy rovně nebo doprava), prostřední bod nemůže být roh, takže se odebere. Spojení obou řetězců dá obal. Dominuje řazení, takže běží v O(n log n). Konvexní obaly stojí za detekcí kolizí, analýzou tvarů a jako první krok mnoha dalších geometrických algoritmů. Klikni do roviny a přidej vlastní body.

Klikni do roviny pro přidání bodu
Body
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Seřaď body zleva doprava (shody podle y).
  2. Projdi zleva doprava a postav spodní hranu.
  3. Odeber každý bod, kde poslední tři tvoří pravou zatáčku (nemůže být roh).
  4. Projdi zpět zprava doleva pro horní hranu; spojené řetězce jsou obal.

Pseudokód

1convexHull(points):                 # O(n log n)2  sort points by x, then y3  lower = []                          # build the bottom edge4  for p in points (left → right):5    while last two + p turn right (or straight): pop6    lower.push(p)7  upper = []  (same sweep, right → left)8  hull = lower (drop last) + upper (drop last)