Convex Hull

Computes the smallest convex polygon that encloses a set of points in the plane. Common approaches include Graham Scan and Jarvis March, widely used in computer graphics, GIS, and collision detection.

Convex Hull Visualization

LentoRápido
🔊 Sound
Aguardando0 pontos
🖱 arrastar para mover ponto🖱 botão direito para excluir ponto
● Pivô● Escaneando● Na stack (hull)● Hover— Aresta do hull

Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Pseudocode

function convexHull(points):
  if len(points) <= 3:
    return points
  sort points by x, then y
  lower = empty list
  for p in points:
    while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
      remove last element from lower
    append p to lower
  upper = empty list
  for p in reversed(points):
    while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
      remove last element from upper
    append p to upper
  remove last element from lower
  remove last element from upper
  return lower + upper

function cross(o, a, b):
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)