"""Preenchimento de polígonos: varredura (*scan-line*) e *boundary-fill*.

Aula 03 — Visualização 2D: rasterização.
Exemplo em Python com PySide6 e PyOpenGL (pipeline fixed-function).

Execute com:

    python raster_poligonos.py

A mesma grade grossa de ``raster_linhas.py``: uma unidade do mundo é um
pixel do dispositivo imaginário, e "acender um pixel" é um ``GL_POINTS`` no
centro da célula.

Os dois algoritmos resolvem o mesmo problema por caminhos opostos:

  * **scan-line** parte da *geometria*: para cada linha horizontal, calcula
    onde ela cruza as arestas e pinta entre os pares de interseções;
  * **boundary-fill** parte de um *ponto interno* e se espalha até encontrar
    a cor da borda — não olha a geometria, olha a imagem já rasterizada.

Teclas:

    1        scan-line
    2        boundary-fill
    Espaço   avança um passo (uma linha de varredura / uma rodada da pilha)
    A        completa o preenchimento
    R        recomeça
    G        mostra ou esconde a grade
    Esc      fecha

Clique dentro do polígono para escolher outra semente do boundary-fill.

Ideias para experimentar: mova um vértice de ``POLIGONO`` até o contorno se
autointerseccionar e observe o que cada algoritmo faz; coloque a semente
fora do polígono; abra um "vazamento" de um pixel na borda.
"""

from __future__ import annotations

import math
import sys

from PySide6.QtCore import Qt
from PySide6.QtGui import QSurfaceFormat
from PySide6.QtWidgets import QApplication
from PySide6.QtOpenGLWidgets import QOpenGLWidget

from OpenGL.GL import *
from OpenGL.GLU import gluOrtho2D

COLUNAS = 36
LINHAS = 26

# Polígono côncavo: as linhas de varredura que passam pelo "vão" produzem
# quatro interseções em vez de duas, que é o caso interessante.
POLIGONO = [
    (4.0, 3.0),
    (17.0, 12.0),
    (30.0, 3.0),
    (32.0, 21.0),
    (24.0, 15.0),
    (17.0, 23.0),
    (10.0, 15.0),
    (3.0, 21.0),
]
SEMENTE = (18, 11)      # bem no meio da faixa larga do polígono

COR_BORDA = (0.92, 0.92, 0.95)
COR_INTERIOR = (0.35, 0.55, 0.95)
COR_VARREDURA = (0.95, 0.70, 0.25)


# ---------------------------------------------------------------------------
# Os algoritmos
# ---------------------------------------------------------------------------

def bresenham(x0: int, y0: int, x1: int, y1: int) -> list[tuple[int, int]]:
    """Mesmo algoritmo de ``raster_linhas.py`` — repetido de propósito.

    Cada exemplo do módulo é autocontido: o aluno baixa um arquivo e ele
    roda, sem depender de nenhum outro.
    """
    dx, dy = abs(x1 - x0), abs(y1 - y0)
    passo_x = 1 if x0 < x1 else -1
    passo_y = 1 if y0 < y1 else -1
    erro = dx - dy

    pixels = []
    x, y = x0, y0
    while True:
        pixels.append((x, y))
        if x == x1 and y == y1:
            return pixels
        erro_dobrado = 2 * erro
        if erro_dobrado > -dy:
            erro -= dy
            x += passo_x
        if erro_dobrado < dx:
            erro += dx
            y += passo_y


def rasterizar_contorno(poligono: list[tuple[float, float]]) -> set[tuple[int, int]]:
    """Converte as arestas do polígono em pixels de borda."""
    borda: set[tuple[int, int]] = set()
    for k in range(len(poligono)):
        x0, y0 = poligono[k]
        x1, y1 = poligono[(k + 1) % len(poligono)]
        borda.update(bresenham(round(x0), round(y0), round(x1), round(y1)))
    return borda


def intersecoes_da_linha(poligono: list[tuple[float, float]], y: float) -> list[float]:
    """Onde a linha horizontal ``y`` cruza as arestas do polígono.

    A regra ``min <= y < max`` conta cada vértice **uma única vez**: sem ela,
    uma linha que passa exatamente por um vértice geraria duas interseções no
    mesmo ponto e o pareamento sairia trocado dali em diante.
    """
    xs: list[float] = []
    for k in range(len(poligono)):
        x0, y0 = poligono[k]
        x1, y1 = poligono[(k + 1) % len(poligono)]
        if y0 == y1:
            continue                       # aresta horizontal: ignorada
        if min(y0, y1) <= y < max(y0, y1):
            xs.append(x0 + (y - y0) * (x1 - x0) / (y1 - y0))
    return sorted(xs)


def varrer_linha(poligono: list[tuple[float, float]], j: int) -> list[tuple[int, int]]:
    """Pixels acesos pela linha de varredura da fileira ``j``."""
    y = j + 0.5                            # centro da fileira de pixels
    xs = intersecoes_da_linha(poligono, y)

    pixels = []
    for k in range(0, len(xs) - 1, 2):
        # Pinta os pixels cujo CENTRO cai dentro do intervalo. É o que evita
        # que o preenchimento vaze meio pixel para fora do contorno.
        inicio = math.ceil(xs[k] - 0.5)
        fim = math.floor(xs[k + 1] - 0.5)
        for i in range(max(0, inicio), min(COLUNAS - 1, fim) + 1):
            pixels.append((i, j))
    return pixels


def passo_boundary_fill(pilha: list[tuple[int, int]],
                        pintados: set[tuple[int, int]],
                        borda: set[tuple[int, int]]) -> list[tuple[int, int]]:
    """Uma rodada do *boundary-fill*: esvazia a pilha corrente.

    A versão de livro é recursiva; aqui a recursão foi trocada por uma pilha
    explícita, que é o que qualquer implementação de verdade faz — a
    profundidade da recursão chegaria a milhares de níveis em uma imagem
    real.
    """
    novos = []
    proxima = []
    while pilha:
        i, j = pilha.pop()
        if not (0 <= i < COLUNAS and 0 <= j < LINHAS):
            continue
        if (i, j) in borda or (i, j) in pintados:
            continue
        pintados.add((i, j))
        novos.append((i, j))
        proxima.extend([(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)])
    pilha.extend(proxima)
    return novos


# ---------------------------------------------------------------------------

class RasterPoligonos(QOpenGLWidget):
    def __init__(self, parent=None):
        super().__init__(parent)
        self.modo = 1                 # 1 = scan-line, 2 = boundary-fill
        self.semente = SEMENTE
        self.mostrar_grade = True
        self.viewport = (0, 0, 1, 1)
        self.borda = rasterizar_contorno(POLIGONO)
        self.setFocusPolicy(Qt.FocusPolicy.StrongFocus)
        self._reiniciar()

    def _reiniciar(self) -> None:
        self.interior: set[tuple[int, int]] = set()
        self.linha_atual = 0
        self.pilha = [self.semente]
        self.concluido = False

    # -- ciclo de vida -----------------------------------------------------

    def initializeGL(self) -> None:
        glClearColor(0.10, 0.11, 0.13, 1.0)

    def resizeGL(self, w: int, h: int) -> None:
        w, h = max(1, w), max(1, h)
        largura = min(w, h * COLUNAS // LINHAS)
        altura = largura * LINHAS // COLUNAS
        self.viewport = ((w - largura) // 2, (h - altura) // 2, largura, altura)
        glViewport(*self.viewport)

        glMatrixMode(GL_PROJECTION)
        glLoadIdentity()
        gluOrtho2D(0.0, float(COLUNAS), 0.0, float(LINHAS))
        glMatrixMode(GL_MODELVIEW)
        glLoadIdentity()

    # -- passo a passo -----------------------------------------------------

    def _avancar(self) -> None:
        if self.modo == 1:
            if self.linha_atual >= LINHAS:
                self.concluido = True
                return
            self.interior.update(varrer_linha(POLIGONO, self.linha_atual))
            self.linha_atual += 1
        else:
            if not self.pilha:
                self.concluido = True
                return
            passo_boundary_fill(self.pilha, self.interior, self.borda)

    def _completar(self) -> None:
        limite = COLUNAS * LINHAS + LINHAS      # evita laço infinito
        while not self.concluido and limite > 0:
            self._avancar()
            limite -= 1

    # -- desenho -----------------------------------------------------------

    def paintGL(self) -> None:
        # glClear varre o framebuffer inteiro, não só o viewport corrente.
        glClear(GL_COLOR_BUFFER_BIT)

        if self.mostrar_grade:
            self._desenhar_grade()

        self._acender(self.interior, COR_INTERIOR)
        self._acender(self.borda, COR_BORDA)

        if self.modo == 1 and not self.concluido:
            self._desenhar_linha_varredura()
        elif self.modo == 2:
            self._marcar_semente()

        self._desenhar_contorno_ideal()

    def _tamanho_celula(self) -> float:
        return max(1.0, self.viewport[2] / COLUNAS)

    def _acender(self, pixels, cor) -> None:
        glColor3f(*cor)
        glPointSize(self._tamanho_celula())
        glBegin(GL_POINTS)
        for i, j in pixels:
            glVertex2f(i + 0.5, j + 0.5)
        glEnd()

    def _desenhar_grade(self) -> None:
        glColor3f(0.18, 0.20, 0.25)
        glLineWidth(1.0)
        glBegin(GL_LINES)
        for i in range(COLUNAS + 1):
            glVertex2f(float(i), 0.0)
            glVertex2f(float(i), float(LINHAS))
        for j in range(LINHAS + 1):
            glVertex2f(0.0, float(j))
            glVertex2f(float(COLUNAS), float(j))
        glEnd()

    def _desenhar_linha_varredura(self) -> None:
        y = self.linha_atual + 0.5
        glColor3f(*COR_VARREDURA)
        glLineWidth(2.0)
        glBegin(GL_LINES)
        glVertex2f(0.0, y)
        glVertex2f(float(COLUNAS), y)
        glEnd()

        # As interseções da linha corrente, na ordem em que serão pareadas.
        glPointSize(max(5.0, self._tamanho_celula() / 2.0))
        glBegin(GL_POINTS)
        for x in intersecoes_da_linha(POLIGONO, y):
            glVertex2f(x, y)
        glEnd()

    def _marcar_semente(self) -> None:
        glColor3f(*COR_VARREDURA)
        glPointSize(max(5.0, self._tamanho_celula() / 2.0))
        glBegin(GL_POINTS)
        glVertex2f(self.semente[0] + 0.5, self.semente[1] + 0.5)
        glEnd()

    @staticmethod
    def _desenhar_contorno_ideal() -> None:
        """A geometria contínua, por cima dos pixels.

        Mostra o quanto o contorno rasterizado se afasta do polígono real —
        é a mesma comparação da reta ideal em ``raster_linhas.py``.
        """
        glColor3f(0.55, 0.60, 0.70)
        glLineWidth(1.5)
        glBegin(GL_LINE_LOOP)
        for x, y in POLIGONO:
            glVertex2f(x, y)
        glEnd()

    # -- interação ---------------------------------------------------------

    def mousePressEvent(self, event) -> None:
        vx, vy, largura, altura = self.viewport
        x_gl = event.position().x() - vx
        y_gl = (self.height() - event.position().y()) - vy
        i = int(x_gl / (largura / COLUNAS))
        j = int(y_gl / (altura / LINHAS))
        if 0 <= i < COLUNAS and 0 <= j < LINHAS:
            self.semente = (i, j)
            self._reiniciar()
            self.update()

    def keyPressEvent(self, event) -> None:
        tecla = event.key()
        if tecla == Qt.Key.Key_Escape:
            self.close()
            return
        elif tecla in (Qt.Key.Key_1, Qt.Key.Key_2):
            self.modo = tecla - Qt.Key.Key_0
            self._reiniciar()
        elif tecla == Qt.Key.Key_Space:
            self._avancar()
        elif tecla == Qt.Key.Key_A:
            self._completar()
        elif tecla == Qt.Key.Key_R:
            self._reiniciar()
        elif tecla == Qt.Key.Key_G:
            self.mostrar_grade = not self.mostrar_grade
        else:
            return

        nomes = {1: "scan-line", 2: "boundary-fill"}
        self.setWindowTitle(
            f"Preenchimento de polígonos — {nomes[self.modo]} "
            f"({len(self.interior)} pixels)"
        )
        self.update()


def main() -> int:
    print(__doc__)

    fmt = QSurfaceFormat()
    fmt.setVersion(2, 1)
    fmt.setProfile(QSurfaceFormat.OpenGLContextProfile.NoProfile)
    fmt.setDepthBufferSize(0)
    QSurfaceFormat.setDefaultFormat(fmt)

    app = QApplication(sys.argv)
    janela = RasterPoligonos()
    janela.setWindowTitle("Preenchimento de polígonos — scan-line")
    janela.resize(820, 620)
    janela.show()
    return app.exec()


if __name__ == "__main__":
    raise SystemExit(main())