| 321 | } |
| 322 | |
| 323 | function convexHull(points: p5.Vector[]) { |
| 324 | points.sort(comparison) |
| 325 | const L: p5.Vector[] = [] |
| 326 | for (let i = 0; i < points.length; i++) { |
| 327 | while ( |
| 328 | L.length >= 2 && |
| 329 | cross(L[L.length - 2], L[L.length - 1], points[i]) <= 0 |
| 330 | ) { |
| 331 | L.pop() |
| 332 | } |
| 333 | L.push(points[i]) |
| 334 | } |
| 335 | const U: p5.Vector[] = [] |
| 336 | for (let i = points.length - 1; i >= 0; i--) { |
| 337 | while ( |
| 338 | U.length >= 2 && |
| 339 | cross(U[U.length - 2], U[U.length - 1], points[i]) <= 0 |
| 340 | ) { |
| 341 | U.pop() |
| 342 | } |
| 343 | U.push(points[i]) |
| 344 | } |
| 345 | L.pop() |
| 346 | U.pop() |
| 347 | return L.concat(U) |
| 348 | } |