import numpy as np
from typing import Tuple


def find_baseline(mask: np.ndarray) -> Tuple[
                Tuple[int, int], Tuple[int, int]]:
    """Funkcja wyznacza punkty baseline na podstawie carti i bony roof.
    Algorytm znajduje najbardziej wysunięty na prawo punkt carti roof i na
    jego współrzędnej x +1 definiuje początek prawego punktu. Współrzędna y
    prawego punktu to współrzędna y bony roof na górnym obrysie na podanej
    współrzędnej x. Jeżeli dochodzi do wypadku gdzie carti roof jest dłuższe
    w poziomie od bony roof, to jako prawy punkt ustalany jest najbardziej
    wysunięty punkt górnego obrysu bony roof. Następnie szukana jest linia,
    posiadająca największe pokrycie z górnym obrysem bony roof. Do obliczania
    pokrycia pomijany jest górny obrys znajdujący się po prawo od wyznaczonego
    prawego punktu. Jako lewy punkt funkcja obiera ostatni punkt linii
    z największym pokryciem znajdujący się na górnym obrysie.

    Args:
        mask (np.ndarray): maska w formacie png

    Returns:
        Tuple[Tuple[int, int], Tuple[int, int]]: współrzędne prawego i lewego
                                                                punktu baseline
    """
    height, width = mask.shape
    label_upper_contour_bony = 5  # bony roof
    label_upper_contour_carti = 4  # cartilagineous roof

    binary_mask_bony = (mask == label_upper_contour_bony).astype(np.uint8)
    binary_mask_carti = (mask == label_upper_contour_carti).astype(np.uint8)

    upper_contour_bony = [
        (x, np.where(binary_mask_bony[:, x])[0][0]) for x in range(width)
        if np.any(binary_mask_bony[:, x])
    ]

    x_max_carti = max((x for x in range(width) if np.any(
        binary_mask_carti[:, x])), default=-1
        )
    if x_max_carti == -1:
        return (None, None), (None, None)

    # Ustalanie prawego punktu na podstawie przesunięcia
    rightmost_point_x = x_max_carti + 1
    if rightmost_point_x >= width or not upper_contour_bony:
        return (None, None), (None, None)

    bony_point_y = next(
        (y for x, y in upper_contour_bony if x == rightmost_point_x), None
    )
    if bony_point_y is None:
        rightmost_point_x, bony_point_y = upper_contour_bony[-1]

    # Wstępny punkt prawy przed przesunięciem
    original_rightmost_point = (rightmost_point_x, bony_point_y)

    best_line = []
    max_overlap = 0
    best_shift = 0  # Dodanie zmiennej do śledzenia najlepszego przesunięcia

    # Przechodzi przez każde przesunięcie od -10 do +5 pikseli
    for y0 in range(bony_point_y - 10, bony_point_y + 5):
        if not (0 <= y0 < height):
            continue
        current_shift = y0 - bony_point_y

        for angle in range(360):
            angle_rad = np.radians(angle)
            sin_angle = np.sin(angle_rad)
            cos_angle = np.cos(angle_rad)

            n = np.arange(2 * (width + height))
            x = rightmost_point_x + n * cos_angle
            y = y0 - n * sin_angle

            x_rounded = np.round(x).astype(int)
            y_rounded = np.round(y).astype(int)
            valid_mask = (x_rounded >= 0) & (x_rounded < width) & \
                         (y_rounded >= 0) & (y_rounded < height)

            line_points = list(
                zip(x_rounded[valid_mask], y_rounded[valid_mask])
                )

            overlap = len(
                set(line_points) &
                set(p for p in upper_contour_bony if p[0] <= rightmost_point_x)
            )

            if overlap > max_overlap:
                max_overlap = overlap
                best_line = line_points
                best_shift = current_shift

    adjusted_rightmost_point = (
        original_rightmost_point[0], original_rightmost_point[1] + best_shift
        )

    leftmost_point = None
    if best_line:
        for point in best_line:
            x, y = point
            if mask[y, x] == label_upper_contour_bony:
                if leftmost_point is None or x < leftmost_point[0]:
                    leftmost_point = (x, y)

    if leftmost_point is None:
        leftmost_point = (None, None)

    return adjusted_rightmost_point, leftmost_point