1function cross(O, A, B) {
2 return (A[0] - O[0]) * (B[1] - O[1])
3 - (A[1] - O[1]) * (B[0] - O[0]);
4}
5function convexHull(points) {
6 const pts = [...points].sort((a, b) => a[0] - b[0] || a[1] - b[1]);
7 const lower = [];
8 for (const p of pts) {
9 while (lower.length >= 2 &&
10 cross(lower[lower.length - 2], lower[lower.length - 1], p) <= 0)
11 lower.pop();
12 lower.push(p);
13 }
14 const upper = [];
15 for (let i = pts.length - 1; i >= 0; i--) {
16 while (upper.length >= 2 &&
17 cross(upper[upper.length - 2], upper[upper.length - 1], pts[i]) <= 0)
18 upper.pop();
19 upper.push(pts[i]);
20 }
21 lower.pop(); upper.pop();
22 return lower.concat(upper);
23}