#!/usr/bin/env catnip
# Quickhull 2D
#
# Entrée : liste de Point{x, y}
# Sortie : enveloppe convexe dans le sens anti-horaire
# Complexité : O(n log n) moyen, O(n²) pire cas (points sur un cercle)
#
# Divide & conquer analogue à quicksort : on partitionne les points
# par rapport à la droite formée par les extrêmes, puis on récurse
# sur chaque côté en cherchant le point le plus éloigné.
#
# Ref : https://en.wikipedia.org/wiki/Quickhull
# Voir aussi : convex_hull.cat (scan de Graham, O(n log n) garanti)

struct Point {
    x; y;

    # Comparaison lexicographique (x puis y)
    op <(self, rhs) => { self.x < rhs.x or (self.x == rhs.x and self.y < rhs.y) }
    op >(self, rhs) => { self.x > rhs.x or (self.x == rhs.x and self.y > rhs.y) }

    # Produit vectoriel orienté (self→a) × (self→b)
    # Positif si b est à gauche de la droite self→a
    cross(self, a, b) => {
        (a.x - self.x) * (b.y - self.y) - (a.y - self.y) * (b.x - self.x)
    }
}

# Filtre les points strictement à gauche de la droite a→b
left_of = (points, a, b) => {
    fold(points, list(), (acc, p) => { if a.cross(b, p) > 0 { acc + list(p) } else { acc } })
}

# Point le plus éloigné de la droite a→b
# (le cross product est proportionnel à la distance signée)
farthest = (points, a, b) => {
    reduce(points, (best, p) => { if a.cross(b, p) > a.cross(b, best) { p } else { best } })
}

# Récursion : hull des points à gauche de a→b
# Trouve le point c le plus éloigné de a→b, puis récurse sur a→c et c→b.
# Les points à l'intérieur du triangle abc sont éliminés par left_of.
hull_rec = (points, a, b) => {
    if len(points) == 0 {
        list()
    } else {
        c = farthest(points, a, b)
        left_ac = left_of(points, a, c)
        left_cb = left_of(points, c, b)
        hull_rec(left_ac, a, c) + list(c) + hull_rec(left_cb, c, b)
    }
}

quickhull = (points) => {
    if len(points) <= 1 {
        points
    } else {
        # Extrêmes gauche/droite en un seul pass
        (min_p, max_p) = fold(
            points,
            tuple(points[0], points[0]),
            (acc, p) => {
                (lo, hi) = acc
                tuple(if p < lo { p } else { lo }, if p > hi { p } else { hi })
            }
        )
        upper = left_of(points, min_p, max_p)
        lower = left_of(points, max_p, min_p)
        # Assemblage CCW : min → upper hull → max → lower hull
        list(min_p) + hull_rec(upper, min_p, max_p) + list(max_p) + hull_rec(lower, max_p, min_p)
    }
}

# Démo (même jeu de points que convex_hull.cat)
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),
)

hull = quickhull(points)

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