Выпуклая оболочка

1function convexHull(pts: Array<[x: number, y: number]>): Array<[x: number, y: number]> {
2  // старт — самая нижняя-левая; сортировка по полярному углу
3  const start = pts.reduce((m, p) => (p[1] < m[1] || (p[1] === m[1] && p[0] < m[0])) ? p : m)
4  const sorted = pts.filter((p) => p !== start)
5    .sort((a, b) => angle(start, a) - angle(start, b))
6 
7  const stack: typeof pts = [start]
8  for (const p of sorted) {
9    // правый поворот? верхушка была ошибкой
10    while (stack.length > 1 && cross(stack.at(-2)!, stack.at(-1)!, p) <= 0) {
11      stack.pop()
12    }
13    stack.push(p)
14  }
15  return stack
16}
17 
18function cross(o: P, a: P, b: P): number {
19  return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
20}