"""Private polygon geometry fallbacks."""

from __future__ import annotations

from typing import Any

import numpy as np
import numpy.typing as npt


def _as_points(contour: npt.NDArray[Any]) -> npt.NDArray[np.float64]:
    """Normalize an OpenCV contour to an ``(N, 2)`` float64 array."""
    points = np.asarray(contour)
    if points.size == 0:
        return np.empty((0, 2), dtype=np.float64)
    if points.ndim not in (2, 3) or points.shape[-1] != 2:
        raise ValueError("Contours must have shape (N, 2) or (N, 1, 2)")
    return points.reshape(-1, 2).astype(np.float64, copy=False)


def _contour_area(contour: npt.NDArray[Any], oriented: bool = False) -> float:
    """Compute a contour's signed or absolute shoelace area."""
    points = _as_points(contour)
    if len(points) < 3:
        return 0.0
    x = points[:, 0]
    y = points[:, 1]
    area = 0.5 * float(np.dot(x, np.roll(y, -1)) - np.dot(y, np.roll(x, -1)))
    return area if oriented else abs(area)


def _simplify_slices(
    points: npt.NDArray[np.float64], epsilon_squared: float, closed: bool
) -> npt.NDArray[np.float64]:
    """Run OpenCV's stack-based Douglas-Peucker slice traversal."""
    count = len(points)
    stack: list[tuple[int, int]] = []
    output: list[npt.NDArray[np.float64]] = []

    if closed or np.array_equal(points[0], points[-1]):
        closed = True
        position = 0
        right_start = 0
        start_point = points[0]
        within_epsilon = False
        for _ in range(3):
            position = (position + right_start) % count
            start_point = points[position]
            maximum_distance = 0.0
            right_start = 0
            for offset in range(1, count):
                point = points[(position + offset) % count]
                difference = point - start_point
                distance = float(np.dot(difference, difference))
                if distance > maximum_distance:
                    maximum_distance = distance
                    right_start = offset
            within_epsilon = maximum_distance <= epsilon_squared

        if within_epsilon:
            output.append(start_point)
        else:
            split = (position + right_start) % count
            stack.extend(((split, position), (position, split)))
    else:
        stack.append((0, count - 1))

    while stack:
        start, end = stack.pop()
        start_point = points[start]
        end_point = points[end]
        position = (start + 1) % count
        maximum_distance = 0.0
        split = start

        if position != end:
            segment = end_point - start_point
            while position != end:
                point = points[position]
                distance = abs(
                    float(
                        (point[1] - start_point[1]) * segment[0]
                        - (point[0] - start_point[0]) * segment[1]
                    )
                )
                if distance > maximum_distance:
                    maximum_distance = distance
                    split = position
                position = (position + 1) % count
            segment_length_squared = float(np.dot(segment, segment))
            within_epsilon = (
                maximum_distance * maximum_distance
                <= epsilon_squared * segment_length_squared
            )
        else:
            within_epsilon = True

        if within_epsilon:
            output.append(start_point)
        else:
            stack.extend(((split, end), (start, split)))

    if not closed:
        output.append(points[-1])
    return np.asarray(output, dtype=np.float64)


def _cleanup_approximation(
    points: npt.NDArray[np.float64], epsilon_squared: float, closed: bool
) -> npt.NDArray[np.float64]:
    """Remove OpenCV's final near-collinear points from an approximation."""
    count = len(points)
    if count <= 2:
        return points

    destination = points.copy()
    new_count = count
    position = count - 1 if closed else 0
    start_point = destination[position]
    position = (position + 1) % count
    write_position = position
    point = destination[position]
    position = (position + 1) % count
    index = 0 if closed else 1
    stop = count if closed else count - 1

    while index < stop and new_count > 2:
        end_point = destination[position]
        position = (position + 1) % count
        segment = end_point - start_point
        offset = point - start_point
        distance = abs(float(offset[0] * segment[1] - offset[1] * segment[0]))
        inner_product = float(np.dot(offset, end_point - point))
        removable = (
            distance * distance
            <= 0.5 * epsilon_squared * float(np.dot(segment, segment))
            and segment[0] != 0
            and segment[1] != 0
            and inner_product >= 0
        )
        if removable:
            new_count -= 1
            destination[write_position] = end_point
            start_point = end_point
            write_position = (write_position + 1) % count
            point = destination[position]
            position = (position + 1) % count
            index += 2
            continue

        destination[write_position] = point
        start_point = point
        write_position = (write_position + 1) % count
        point = end_point
        index += 1

    if not closed:
        destination[write_position] = point
    return np.asarray(destination[:new_count], dtype=np.float64)


def _approx_poly_dp(
    contour: npt.NDArray[Any], epsilon: float, closed: bool
) -> npt.NDArray[Any]:
    """Approximate a contour with the supported OpenCV polygon contract."""
    if epsilon < 0:
        raise ValueError("epsilon must be non-negative")
    points = _as_points(contour)
    if len(points) == 0:
        dtype = np.asarray(contour).dtype
        return np.empty((0, 1, 2), dtype=dtype)

    epsilon_squared = float(epsilon) ** 2
    simplified = _simplify_slices(points, epsilon_squared, closed)
    simplified = _cleanup_approximation(simplified, epsilon_squared, closed)

    dtype = np.asarray(contour).dtype
    return simplified.astype(dtype, copy=False).reshape(-1, 1, 2)


def _cross(edge: npt.NDArray[np.float64], point: npt.NDArray[np.float64]) -> float:
    """Return the two-dimensional cross product of two vectors."""
    return float(edge[0] * point[1] - edge[1] * point[0])


def _intersect_convex_convex(
    first: npt.NDArray[Any],
    second: npt.NDArray[Any],
    handle_nested: bool = True,
) -> tuple[float, npt.NDArray[Any]]:
    """Clip two convex polygons and return their intersection area and vertices."""
    del handle_nested
    subject = _as_points(first)
    clip = _as_points(second)
    output = subject
    if len(subject) < 3 or len(clip) < 3:
        return 0.0, np.empty((0, 1, 2), dtype=np.float32)

    orientation = 1.0 if _contour_area(clip, oriented=True) >= 0 else -1.0
    for index, clip_start in enumerate(clip):
        clip_end = clip[(index + 1) % len(clip)]
        edge = clip_end - clip_start
        input_points = output
        if len(input_points) == 0:
            break
        output_points: list[npt.NDArray[np.float64]] = []
        previous = input_points[-1]
        previous_inside = orientation * _cross(edge, previous - clip_start) >= 0
        for current in input_points:
            current_inside = orientation * _cross(edge, current - clip_start) >= 0
            if current_inside != previous_inside:
                direction = current - previous
                denominator = _cross(edge, direction)
                if denominator != 0:
                    factor = _cross(edge, clip_start - previous) / denominator
                    output_points.append(previous + factor * direction)
            if current_inside:
                output_points.append(current)
            previous = current
            previous_inside = current_inside
        output = np.asarray(output_points, dtype=np.float64)

    if len(output) == 0:
        dtype = np.asarray(first).dtype
        result_dtype = dtype if np.issubdtype(dtype, np.floating) else np.float32
        return 0.0, np.empty((0, 1, 2), dtype=result_dtype)

    output = output[np.r_[True, np.any(np.diff(output, axis=0) != 0, axis=1)]]
    if len(output) > 1 and np.array_equal(output[0], output[-1]):
        output = output[:-1]
    area = _contour_area(output)
    dtype = np.asarray(first).dtype
    result_dtype = dtype if np.issubdtype(dtype, np.floating) else np.float32
    return area, output.astype(result_dtype, copy=False).reshape(-1, 1, 2)
