#!/usr/bin/env catnip
# Convex hull 2D (scan de Graham)
#
# Entrée : liste de Point{x, y}
# Sortie : enveloppe convexe dans le sens anti-horaire
# Complexité : O(n log n) (tri polaire) + O(n) (scan)
#
# Variantes non implémentées ici :
#   - Monotone chain (Andrew, 1979) : tri lexicographique au lieu de polaire,
#     évite atan2. Même complexité, meilleure stabilité numérique.
#   - Chan's algorithm (1996) : O(n log h), output-sensitive.
#     Combine Graham sur des sous-groupes + Jarvis wrapping.
# Voir aussi : quickhull.cat (divide & conquer, O(n log n) moyen)

builtins = import('builtins')
math = import('math')

struct Point {
    x; y;

    # Produit vectoriel orienté (self→a) × (self→b)
    cross(self, a, b) => {
        (a.x - self.x) * (b.y - self.y) - (a.y - self.y) * (b.x - self.x)
    }

    # Distance carrée à un autre point
    sqdist(self, other) => {
        dx = self.x - other.x
        dy = self.y - other.y
        dx * dx + dy * dy
    }

    op ==(self, rhs) => { self.x == rhs.x and self.y == rhs.y }
}

# Point pivot : y minimal, puis x minimal
find_pivot = (points) => {
    reduce(points, (p, q) => {
            if q.y < p.y or (q.y == p.y and q.x < p.x) { q }
            else { p }
        })
}

graham_hull = (points) => {
    if len(points) <= 1 {
        points
    } else {
        pivot = find_pivot(points)

        # Tri par angle polaire puis distance au pivot.
        # Pour points colinéaires au même angle, le plus éloigné reste après le scan.
        sorted_pts = builtins.sorted(
            points,
            key=(p) => {
                tuple(
                    math.atan2(p.y - pivot.y, p.x - pivot.x),
                    pivot.sqdist(p),
                )
            })

        stack = list()
        i = 0
        while i < len(sorted_pts) {
            p = sorted_pts[i]
            # Ignore les duplicatas exacts consécutifs
            if len(stack) > 0 {
                last = stack[len(stack) - 1]
                if last == p {
                    i = i + 1
                    continue
                }
            }
            while len(stack) >= 2 and stack[len(stack) - 2].cross(stack[len(stack) - 1], p) <= 0 {
                stack = stack[:len(stack) - 1]
            }
            stack = stack + list(p)
            i = i + 1
        }
        stack
    }
}

# Démo
points = list(
    Point(0, 0),
    Point(1, 1),
    Point(2, 2),
    Point(2, 0),
    Point(2, 4),
    Point(3, 3),
    Point(4, 2),
    Point(0, 3),
    Point(1, 2),
    Point(2, 2),  # doublon
    Point(4, 2),  # doublon
)

hull = graham_hull(points)

print("Points d'entrée :", len(points))
print("Hull (CCW) :", hull)
print("Taille hull :", len(hull))