# Macierze jako przekształcenia i krzywe Béziera

## Wyświetlanie wektorów: `vector_shower.py`

Zanim zaczniemy przekształcać kształty, musimy umieć je wyświetlić.
Do tego posłuży nam biblioteka `vector_shower.py` (i towarzyszący jej program w C++).
Archiwum z biblioteką, potrzebnym do niej programem i jego kodem źródłowym możesz
    [pobrać stąd](https://quazyrog.pl/mdcs/2026/1/vector_shower.zip).

:::{important}
Rozpakuj pobranego zipa do tego samego folderu, w którym będziesz pisać programy na dzisiejszych
    zajęciach.
W folderze z programami z dzisiejszych zajęć będą potrzebne:
- folder `vector_shower` rospakowany z zipa,
- plik `matrices.py` z implementacją klasy macierzy.
:::

Biblioteka ta posiada dwie główne funkcje:
- `show_vector(vec, color)` — rysuje pojedynczy wektor (punkt) na ekranie.
- `show_vector_cloud(vectors, color)` — koloruje piksele tła zależnie od tego, jakie wektory
    znajdują się na obszarze ekranu pod tym pikselem.
    "Chmura" jest opisana za pomocą listy wektorów.
- Tych funkcji możesz używać zarówno ze skryptu, jak i z trybu interaktywnego.
- Kolejne wywołania będą rysować na tym samym obrazku; zamnkięcie okna spowoduje, że kolejne
    polecenia rysowania będą zaczynać od czystego obrazka.

![Przykład użycia `vector_shower`](static/vector_shower.png)

:::{note}
Biblioteka `vector_shower` odczytuje współrzędne z wektorów na dowolny z poniższych sposobów -
    wystarczy, żeby tylko jeden z nich był dostępny w klasie wektorów:
1. `x=v.x, y=v.y`
2. `x=v[0], y=v[1]` - dzięki temu można używać list jako wektorów.
3. `x=[0, 0], y=[1, 0]`
4. `x=v.get(0,0), y=v.get(1,0)` - z tego będziemy korzystać.
:::

Po uruchomieniu okna z wizualizacją możesz z nim wchodzić w interakcję:
- **Strzałki** — przesuwanie widoku.
- **Klawisze + / -** — przybliżanie i oddalanie (zoom); przybliżanie powoduje, że pojedynczy piksel
    tła pokrywa coraz mniejszy obszar na ekranie, dlatego "chmury" wektorów tworzące spójny kształt
    przy większym oddaleniu, po przybliżeniu zaczną mieć widoczne dziury.

W parametrze `color` możesz podawać nazwy kolorów (np. `"red"`, `"blue"`) lub ich kody HTML
    (np. `"#ff0000"` dla czerwonego, `"#123456"` dla ciemnego niebieskiego).

### Macierze jako wektory

Dzisiaj zamiast korzystać z klasy `Vector2D` tego, będziemy używać klasy do macierzy o wymiarach
    $2 \times 1$.
Dzięki temu będziemy mogli łatwo opisywać przekształcenia liniowe tych wektorów jako $v' = Mv$.

Pomocna będzie też funkcja tworzenia, dodawania i mnożenia macierzy-wektorów:

```python
def vec2d(x, y):
    v = Matrix(2, 1)
    v.set(0, 0, x)
    v.set(1, 0, y)
    return v

def vmul(a, v):
    return vec2d(a * v.get(0, 0), a * v.get(1, 0))

def vadd(v1, v2):
    return vec2d(v1.get(0, 0) + v2.get(0, 0), v1.get(1, 0) + v2.get(1, 0))
```

## Budowanie kształtów z wektorów

Poniższy przykładowy kod wyświetla kwadrat z narożnikami:

```py
from vector_shower import show_vector, show_vector_cloud
from matrices import Matrix

def vec2d(x, y):
    m = Matrix(2, 1)
    m.set(0, 0, x)
    m.set(1, 0, y)
    return m

def vmul(a, v):
    return vec2d(a * v.get(0, 0), a * v.get(1, 0))

def vadd(v1, v2):
    return vec2d(v1.get(0, 0) + v2.get(0, 0), v1.get(1, 0) + v2.get(1, 0))

unit_square = []
x = 0
while x <= 1:
    y = 0
    while y <= 1:
        unit_square.append(vec2d(x, y))
        y += 0.01
    x += 0.01
show_vector_cloud(unit_square, "#f00")
show_vector(vec2d(0,0))
show_vector(vec2d(1,0))
show_vector(vec2d(0,1))
show_vector(vec2d(1,1))

shift = vec2d(0.6, 0)
i = 0
while i < len(unit_square):
    unit_square[i] = vadd(shift, unit_square[i])
    i += 1
show_vector_cloud(unit_square, "#0f0")

shift = vec2d(-0.3, 0.6)
i = 0
while i < len(unit_square):
    unit_square[i] = vadd(shift, unit_square[i])
    i += 1
show_vector_cloud(unit_square, "#00f")
```

![Przykład użycia `vector_shower`](static/vector_shower-square.png)

:::{topic} Zadanie 1: Linia
Napisz funkcję `line(p0, p1)`, która dla podanych punktów zwróci listę (nie wszystkich!) punktów na
    odnicku `p1--p2`.
Punktów na liści powinno być na tyle dużo, żeby dało się ją narysować.
Wyświetl wynik jako "chmurę" punktów z końcami zaznaczonymi jako kropki:
![wynik zadania 1](static/vector_shower-line.png)
:::

:::{topic} Zadanie 3: Koło
Napisz funckję `circle(center, radius)`, która dla podanych współrzędnych środka (`center=[x,y]`)
    oraz promienia, zwróci "chmurę punktów" z tego koła.
Wyświetl koło o promieniu $1$ i środku w $(3, 3)$:
![wynik zadania 2](static/vector_shower-circle.png)
:::

:::{topic} Zadanie 2: Trójkąt
Napisz funkcję `triangle(A,B,C)`, która zwróci chmurę punktów wewnątrz trójkąta o podanych
    wierzchołkach.
Wierzchołki są podane jako listy dwóch współrzędnych.
Następnie wykorzystaj tę funkcję do narysowania trókjąta o wierzchołkach:

```py
A = [0,0]
B = [5, 1]
C = [3, 6]
```

![wynik zadania 3](static/vector_shower-triangle.png)
:::

## Mnożenie macierzy

Aby pomnożyć dwie macierze $A$ i $B$, element w $i$-tym wierszu i $j$-tej kolumnie macierzy wynikowej $C$ obliczamy jako sumę iloczynów elementów z $i$-tego wiersza macierzy $A$ i $j$-tej kolumny macierzy $B$:

$$c_{i\,j} = a_{i\,1} b_{1\,j} + a_{i\,1} b_{1\,j} + \dots + a_{i\,1} b_{1\,j}$$

**Przykład:**

$$\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \cdot \begin{pmatrix} 5 & 6 \\ 7 & 8 \end{pmatrix} = \begin{pmatrix} 1\cdot 5 + 2\cdot 7 & 1\cdot 6 + 2\cdot 8 \\ 3\cdot 5 + 4\cdot 7 & 3\cdot 6 + 4\cdot 8 \end{pmatrix} = \begin{pmatrix} 19 & 22 \\ 43 & 50 \end{pmatrix}$$

:::{topic} Zadanie 4: Implementacja mnożenia
Napisz funkcję `matmul(A, B)`, która zwróci nową macierz będącą wynikiem mnożenia $A \cdot B$.
Pamiętaj, że to mnożenie jest możliwe tylko wtedy, gdy liczba kolumn macierzy $A$ jest równa
    liczbie wierszy macierzy $B$ - zwróć `None` (lub zgłoś błąd) jeśli tak nie jest.
:::

### Przekształcanie wektorów

:::{topic} Zadanie 5: Przekształcenia
Napisz funkcję `transform(m, vs)`, która dla danej macierzy `m` i wektorów `vs` zwróci listę
    wektorów z `vs` przemnożonych przez macierz `m`.
:::

:::{topic} Zadanie 6: Symetria
Napisz funkcję `mirror_y()`, która zwróci macierz odbicia symetrycznego względem OX.
Następnie korzystając z dodatkowo funkcji `transform` i `triangle` z poprzednich zadań,
    narysuj odbicie symetryczne trójkąta o wierzchołkach $(0, 0.5)$, $(0, -0.5)$ i $(2, 0)$.
:::

Macierz obrotu o kąt $\alpha$ (w kierunku przeciwnym do ruchu wskazówek zegara) ma postać:

$$R = \begin{pmatrix} \cos\alpha & -\sin\alpha \\ \sin\alpha & \cos\alpha \end{pmatrix}$$

:::{topic} Zadanie 7: Obrót
Napisz funkcję `rotate(angle)`, która zwraca macierz obrotu o dany kąt w stopniach.
Pamiętaj o zamianie stopni na radiany!
Wyświetl kwadrat z Zadania 6 oraz jego wersję obróconą o 30 stopni.
:::

### Składanie przekształceń

:::{topic} Zadanie 8: Składanie przekształceń
Ponownie będziemy przekształcać trójkąt z zadania 6go, tym razem złożymy dwa przekształcenia
    - symetrię i obrót.
Niech $M_\text{s}$ to macierz symetrii, $M_\text{r}$ to macierz obrotu.
Wiemy już, że mnożenie macierzy odpowiada składaniu przekształceń.
Narysuj w sumie trzy trójkąty:
- ten oryginalny,
- przekształcony macierzą $M_\text{s} \cdot M_\text{r}$,
- przekształcony macierzą $M_\text{r} \cdot M_\text{s}$,
:::

To zadanie przypomina, że składanie przekształceń nie jest przemienne - ważna jest kolejność.

Tak życiowo możemy to zilustrować następująco - obracanie działa jak zegar (zawsze przeciwnie do
    ruchu jego wskazówek), ale kiedy patrzymy na zegar w lustrze (odbiciu), to wskazówki ruszają
    się w złą stronę.
Tak więc obrót następujący po odbiciu symetrycznym obraca w inną stronę, niż normalnie.

## Krzywe Béziera i algorytm De Casteljau

Algorytm De Casteljau pozwala wyznaczyć punkt na krzywej dla parametru $t \in [0, 1]$ poprzez wielokrotne wyznaczanie punktów pośrednich na odcinkach — podobnie do rysowania odcinka, ale obliczanie pojedynczego punktu jest bardziej skomplikowane: 

1. Masz listę punktów kontrolnych $[P_0, P_1, \dots, P_n]$.
2. Jeśli na liście jest tylko jeden punkt, to jest on wynikiem.
3. Jeśli jest więcej punktów, utwórz nową listę o jeden krótszą: $Q_i = (1-t)P_i + tP_{i+1}$.
4. Powtórz algorytm dla nowej listy punktów.

:::{topic} Zadanie 9: Krzywa Béziera trzeciego stopnia
W programach graficznych najczęściej używa się krzywych trzeciego stopnia (o czterech punktach kontrolnych).
Zaimplementuj funkcję `bezier_point_3(control_points, t)`, która dla podanej listy czterech punktów kontrolnych obliczy punkt na krzywej odpowiadający podanej wartości parametru `t`.
Następnie użyj jej do napisania funkcji `bezier_curve_3(control_points, step)`, która zwróci chmurę punktów na tej krzywej odpowiadających wartościom parametrów `[0, step, 2*step, 3*step, ..., 1]`.

```{hint}
:class: dropdown
Zgodnie z opisanym powyżej i na wykładzie algorytmem, wyliczenie punktu na krzywej dla podanej wartości parametru $t$ oraz punktów kontrolnych $P_0, P_1, P_2, P_3$ przebiega następująco:

$$\begin{align*}
Q_0 &= (1-t)P_0 + tP_1 \\
Q_1 &= (1-t)P_1 + tP_2 \\
Q_2 &= (1-t)P_2 + tP_2 \\
R_0 &= (1-t)Q_0 + tQ_1 \\
R_1 &= (1-t)Q_1 + tQ_2 \\
S &= (1-t)R_0 + tR_1 
\end{align*}$$

$S$ to wynikowy punkt.
```

:::

:::{topic} Zadanie 9.5: początek i koniec
Narysuj kilka różnych krzywych, za każdym razem zaznaczaj też punkty kontrolne. Co obserwujesz:
- Jak pierwszy i ostatni punkt kontrolny wpływają na kształt krzywej?
- Jak wpływają na niego dwa środkowe punkty?
:::

:::{topic} Zadanie 10: Przekształcanie krzywej
Wybierz 4 punkty kontrolne i macierz przekształcenia (np. obrót). Porównaj dwa podejścia:

1. Wygeneruj punkty krzywej Béziera, a następnie każdy z nich przekształć macierzą.
2. Przekształć najpierw punkty kontrolne, a następnie wygeneruj krzywą z nowych punktów.

Czy wyniki są identyczne?
:::

## Zadania domowe

### Chmury i przekształcenia

:::{topic} Zadanie `b.scale` **[1 punkt]**
Napisz funkcję `scale(k)`, która dla podanej skali zwróci macierz skalującą o ten współczynnik.
Narysuj dowolny z kształtów z poprzednich zadań wraz z jego przesunięciem.
:::

:::{topic} Zadanie `b.shift` **[1 punkt]**
Napisz funkcję `shift(v, vs)`, która (analogicznie do funkcji `transform`) przesunie wszystkie
    wetkroy z listy `vs` o wektor `v`.
Narysuj dowolny z kształtów z poprzednich zadań wraz z jego przesunięciem.
:::

:::{topic} Zadanie `b.ellipse` **[1 punkt]**
Elipsa to zbiór wszystkich punktów, których suma odległości od dwóch ustalonych punktów (nazywanych ogniskami) jest stała.
Elipsę symetryczną względem punktu $(0,0)$ opisuje równanie $\frac{x^2}{a^2}+\frac{y^2}{b^2} = 1$, gdzie $a, b$ to parametry decydujące o kształcie elipsy.
Napisz funkcję `ellipse(a, b)`, która zwróci chmurę punktów opisującą elipsę dla podanych wartości parametrów.
:::

:::{topic} Zadanie `b.poly` **[2 punkty]**
Napisz funkcję `convex_polygon(points)`, która dla podanej listy wierzchołków wielokąta wypukłego zwróci chmurę punktów z tego wielokąta.
Nie musisz sprawdzać, czy wielokąt faktycznie jest wypukły - załóż, że tak jest (w przeciwnym razie, twoja funkcja może zwrócić cokolwiek).

```{hint}
:class: dropdown
Kiedy wielokąt jest wypukły, łatwo podzielić go na trójkąty.
```

:::

:::{topic} Zadanie `b.solar` **[2 punkty]**
Księżyc (szare kółko, $r=0.25$) krąży wokół Ziemi (zielonego kółka, $r=0.5$), która krąży
    w okół Słońca (żółtego kółka, $r=2$):
- Słońce znajduje się w punkcie $(0, 0)$,
- Ziemia jest od Słońca oddalona o $8$ i obrócona $42^\circ$,
- Księżyc jest od Ziemi oddalony o  $2$ i obrócony o $126^\circ$.

Zilustruj tę sytuację korzystając z raz obliczonej chmury punktów kółka oraz składania
    przekształceń.
Innymi słowy w twoim programie może się znajdować tylko jedno przypisanie `ball = circle(...)`,
    a ponadto tylko dowolna liczba wywołań funkcji `transform`, `shift` (zad. `b.shift`),
    `rotate`, `scale` (zad `b.scale`) oraz `show_vector_cloud`.

```{tip}
:class: dropdown
Wynik jednej funkcji może być argumentem innej - podobnie jak na matematyce, gdzie piszemy np.
    $f(g(x))$.
Więc możesz napisać np:

`show_vector_cloud(transform(rotate(30), translate([8,0], transform(scale(2), vs) )))`

Żeby obrócić o trzydzieści stopni przesuniętom o $(0, 0)$ przeskalowaną dwukrotnie kulkę `vs`.
```

:::

### Krzywe

:::{topic} Zadanie `b.circle` **[1 punkt]**
Spróbuj opisać przy pomocy czterech krzywych Beziera kształt, który przypomina kółko.
:::

:::{topic} Zadanie `b.segments` **[2 punkty]**
Napisz funkcję `bezier_segments_3(control_points)`, która zwróci chmurę punktów obliczoną następująco: najpierw wyznaczy punkty na krzywej dla wartości $t = 0.0, 0.1, 0.2, \dots, 1.0$, a następnie obliczy chmury dla odcinków łączących kolejne punkty i zsumuje otrzymane chmury (listy).
:::

:::{topic} Zadanie `b.auto` **[3 punkty]**
Napisz funkcję `bezier_auto_curve(control_points)`, która zwróci obliczy chmurę punktów na krzywej Beziera, ale w taki sposób, żeby odległość między kolejnymi punktami na liście wynosiła nie więcej niż `0.05` niezależnie od podanych punktów kontrolnych.
To znaczy funkcja powinna w taki sposób dobierać wartości $t$ dla kolejnych punktów, żeby wypadały one blisko siebie; w szczególności $t$ nie muszą (i nie powinny) zmieniać się o ustaloną wartość.

```{tip}
:class: dropdown
Zacznij od ustalonej listy `ts` wartości $t$, na przykład.
Oblicz listę `ps` - punktów odpowiadających tym wartościom parametru.
Teraz przejdź w pętli po kolejnych punktach z `ps` - jeżel odległość między dwoma kolejnymi puktami jest mniejsza niż `0.05`, to wszystko jest w porządku, w przeciwnym razie potrzebujesz dostawić więcej wartości $t$ między tymi dwiema.
```

:::

:::{topic} Zadanie `b.degreen` **[3 punkty]**
Zaimplementuj funkcję `bezier_point_n(control_points, t)`, która zwraca punkt na krzywej o punktach kontrolnych `control_points` dla podanego parametru $t$.
Liczba punktów kontrolnych nie jest ustalona: $\texttt{len(control_points)} \ge 2$.
Następnie napisz funkcję `bezier_curve_n(control_points, step)`, która wygeneruje chmurę punktów na krzywej analogicznie do zadania 9.
:::