#!/usr/bin/env catnip
# Point-in-Polygon avec pré-filtre bounding box
#
# Algorithme : ray casting (Jordan curve theorem)
# Un rayon horizontal vers +x depuis le point test.
# Nombre d'intersections impair => intérieur.
#
# Optimisation : bounding box check en O(1) avant
# le test O(n) du ray casting.

struct Point { x; y; }

struct BBox {
    xmin; ymin; xmax; ymax;

    # Test rapide : point dans la bounding box ?
    contains(self, p) => {
        p.x >= self.xmin and p.x <= self.xmax and p.y >= self.ymin and p.y <= self.ymax
    }

    # Construit la bounding box d'un polygone
    @static
    from_polygon(polygon) => {
        xmin = polygon[0].x
        ymin = polygon[0].y
        xmax = xmin
        ymax = ymin
        i    = 1
        while i < len(polygon) {
            p = polygon[i]
            if p.x < xmin { xmin = p.x }
            if p.x > xmax { xmax = p.x }
            if p.y < ymin { ymin = p.y }
            if p.y > ymax { ymax = p.y }
            i = i + 1
        }
        BBox(xmin, ymin, xmax, ymax)
    }
}

# Ray casting : rayon horizontal vers +x
# Parcourt chaque arête (i, j) du polygone fermé.
# Condition de croisement :
#   - les deux sommets encadrent py en ordonnée
#   - l'intersection du rayon avec l'arête est à droite de px
ray_cast = (p, polygon) => {
    n = len(polygon)
    inside = False
    j = n - 1
    i = 0
    while i < n {
        pi = polygon[i]
        pj = polygon[j]
        if (pi.y > p.y) != (pj.y > p.y) {
            x_inter = (pj.x - pi.x) * (p.y - pi.y) / (pj.y - pi.y) + pi.x
            if p.x < x_inter {
                inside = not(inside)
            }
        }
        j = i
        i = i + 1
    }
    inside
}

# Version combinée : bbox d'abord, ray casting si nécessaire
point_in_polygon = (p, polygon, bb) => {
    if not bb.contains(p) {
        False
    } else {
        ray_cast(p, polygon)
    }
}

# --- Démo ---

# Polygone en L (non convexe)
polygon = list(Point(0, 0), Point(4, 0), Point(4, 2), Point(2, 2), Point(2, 5), Point(0, 5))

bb = BBox.from_polygon(polygon)
print("Bounding box :", bb)

# Points de test
tests = list(
    Point(1, 1),   # intérieur (branche basse du L)
    Point(1, 4),   # intérieur (branche haute du L)
    Point(3, 3),   # extérieur (creux du L)
    Point(3, 1),   # intérieur (branche basse)
    Point(5, 1),   # extérieur (hors bbox)
    Point(-1, 0),  # extérieur (hors bbox)
    Point(2, 0),   # sur l'arête (comportement limite)
)

for p in tests {
    r = point_in_polygon(p, polygon, bb)
    print("  ", p, "=>", r)
}