Yol ve Dış Bükey Gövde (Path & Convex Hull) Algoritması

1function convexHullGraham(points: [number, number][]): [number, number][] {
2  if (points.length < 3) return [...points];
3  
4  // 1. Pivot bul (y en küçük, eşitse x en küçük)
5  let pivot = points[0];
6  let pivotIdx = 0;
7  for (let i = 1; i < points.length; i++) {
8    if (points[i][1] < pivot[1] || (points[i][1] === pivot[1] && points[i][0] < pivot[0])) {
9      pivot = points[i];
10      pivotIdx = i;
11    }
12  }
13
14  // 2. Polar açıya göre sırala
15  const copy = [...points];
16  copy.splice(pivotIdx, 1);
17  copy.sort((a, b) => {
18    const orient = ccw(pivot, a, b);
19    if (orient === 0) {
20      const distA = (a[0] - pivot[0]) ** 2 + (a[1] - pivot[1]) ** 2;
21      const distB = (b[0] - pivot[0]) ** 2 + (b[1] - pivot[1]) ** 2;
22      return distA - distB;
23    }
24    return orient > 0 ? -1 : 1;
25  });
26
27  // 3. Graham Scan yığın adımları
28  const stack: [number, number][] = [pivot, copy[0], copy[1]];
29  for (let i = 2; i < copy.length; i++) {
30    while (stack.length >= 2) {
31      const top = stack[stack.length - 1];
32      const nextToTop = stack[stack.length - 2];
33      if (ccw(nextToTop, top, copy[i]) > 0) {
34        break; // Sol dönüş bulduk
35      }
36      stack.pop(); // Sağ dönüş veya doğrusal ise at
37    }
38    stack.push(copy[i]);
39  }
40  return stack;
41}