Vektory

Vektor se dá definovat všeljak, ale my si vystačíme s tím, že to je několik čísel zapsaných pohromadě. Dokonce nám ve větší části textu budou stačit dvourozměrné vektory. Z programátorského hlediska to může být třeba objekt v s vlastnostmi v.x a v.y, anebo prostě seznam se dvěma hodnotami.

Seznamy jsou elegantní způsob, jak vektory uložit – bohužel se ale vůbec nehodí na výpočty, protože sčítání ani násobení se nechová správně. Můžeme si ale napsat vlastní třídu, která od seznamu bude dědit a metody pro sčítání a násobení (__add__ a __mul__) vhodným způsobem předefinuje. Anebo prostě použít modul numpy a jeho typ numpy.array, který zvládne úplně všechno, o čem na téhle stránce bude řeč.

class Vector(list):
    def __add__(self, other):
        return Vector(a + b for a, b in zip(self, other))
    
    def __mul__(self, other):
        if hasattr(other, "__iter__"):
            # skalární součin dvou vektorů
            return sum(a * b for a, b in zip(self, other))
        else:
            # součin vektoru a čísla
            return Vector(a * other for a in self)
    __rmul__ = __mul__ # násobení zprava bude dělat totéž

Skalární součin

Skalární součin dvou vektorů (anglicky "dot product") se v klasické Euklidovské geometrii počítá jako u·v = u.x * v.x + u.y * v.y. Ve víc rozměrech bychom sečetli postupně všechno.

Velikost vektoru, čili jeho délka, se počítá Pythagorovou větou jako sqrt(u.x**2 + u.y**2). Všimněte si, že to je odmocnina ze skalárního součinu u·u. Vzdálenost dvou bodů A, B je velikost jejich rozdílu A-B a jako takovou ji můžeme spočítat.

Pohyb po úsečce

Když máme dané dva body A, B, můžeme si přát, aby například herní postavička přešla danou rychlostí z jednoho do druhého. Dejme tomu, že v čase tA = 0 má být panáček v bodě A a v čase tB = 1 má dojít do bodu B. Jeho poloha v jakémkoliv čase t mezi tím bude prostě vážený průměr obou bodů: pozice(t) = (1 - t) * A + t * B. (Nepoužívám Pythonský zápis funkce, musel bych přidat nějaké def a return.)

Vážený průměr se nechal napsat takhle snadno díky tomu, že hodnota t běžela jen od nuly do jedničky. Kdybychom to chtěli zobecnit na jakékoliv dva časy tA, tB, můžeme čas něčím vydělit a nějak ho posunout, aby vycházel v rozsahu od nuly do jedné, a to dosadit do původního vzorce. To vydělení a posunutí bude vypadat jako (t - tA) / (tB - tA) – ověřte si, že v krajních časech opravdu vychází hodnoty nula, jedna. Vzoreček, který hledáme, nám po dosazení a zjednodušení vyjde jako pozice(t) = (tB - t) * A / (tB - tA) + (t - tA) * B / (tB - tA). Hezké na něm je, že se dá takhle snadno napsat i pro složitější funkce a ve vícerozměrném prostoru, aniž bychom něco doopravdy počítali. Říká se mu Lagrangeův interpolační polynom.

Pohyb po mnohoúhelníku

Máme daný seznam bodů, kterými má panáček postupně projít, a stálou rychlost, jakou se má pohybovat. Začneme tedy tím, že si ze vzdáleností bodů napočítáme časy, kdy navštíví každý z nich, a někam si je zapíšeme do seznamu. Hodí se přitom vzdálenosti od začátku sčítat, aby nám vyšly opravdové časy od začátku cesty. Když pak počítáme pozici panáčka v daném čase, najdeme nejdřív, mezi kterými dvěma body zrovna je, a pak dopočítáme polohu na úsečce, jako jsme to vyřešili v předchozím odstavci.

Vektorový součin

Vektorový součin se zavádí pro třírozměrné vektory a vypočítá se jako u×v = [u.y*v.z - u.z*v.y, u.z*v.x - u.x*v.z, u.x*v.y - u.y*v.x]. Výsledkem je zase třírozměrný vektor. Vždycky bude kolmý na oba dva zadané a jeho velikost je úměrná sinu úhlu mezi u, v.

Navíc je pevně dané, na jakou bude směřovat stranu. Například když spočítáme vektorový součin dvou vektorů ve vodorovné rovině u.z = v.z = 0 a vektor v je proti směru hodinových ručiček od u, bude výsledek u×v směřovat nahoru; když je v po směru hodinových ručiček od u, bude směřovat dolů. V obou případech bude ten výsledek svislý. Když jsou dva vektory rovnoběžné, jejich vektorový součin je nulový.

V některých programech se proto zavádí vektorový součin i pro dvourozměrné vektory, který je daný předpisem u×v = u.x*v.y - u.y*v.x. Je to jen jedno číslo, jako bychom spočítali opravdový vektorový součin a nechali si z něj složku ve směru z (zbylé dvě by totiž stejnak byly nulové). Můžeme ho použít ke zjištění, který vektor je vlevo a který vpravo. Pro jednotkové vektory platí ještě přesnější vzoreček: u×v = sin(α). (Všimněte si, že počítáme vlastně skalární součin, když první z vektorů otočíme o devadesát stupňů doleva.)

Zavírání ovečky do ohrádky

Ohrádka je daná jako konvexní mnohoúhelník, tedy seznam bodů v pořadí proti směru hodinových ručiček. Ovečka je bod. Chceme zjistit, jestli je ovečka uvnitř, nebo venku.

Mnohoúhelník je spousta úseček. Díky tomu, že je konvexní, stačí ověřit, že je ovečka nalevo od každé z nich (když tedy jdeme dokola proti směru hodinových ručiček).

Budeme tedy řešit úlohu, jestli je ovečka vlevo od nějaké úsečky, a to zavání vektorovým součinem. Vektorový součin ale umíme počítat jenom pro body, ne pro úsečky – aby dával smysl, nejdřív všechno posuneme tak, aby úsečka začínala v bodě (0, 0). Pak už opravdu stačí jen se podívat na vektorový součin úsečky s ovečkou, a když je záporný, je něco špatně.

Konvexní obal

Zmíněný postup je ukázkou, že s mnohoúhelníky se zachází docela pěkně, dokud jsou konvexní. Hodilo by se tedy umět z nějakého mnohoúhelníka vyrobit konvexní, nebo – obecněji řečeno – vyrobit konvexní mnohoúhelník, do kterého uzavřeme celou zadanou množinu bodů.

Algoritmus se zakládá na následující myšlence: když máme nějaký konvexní mnohoúhelník a chceme k němu přidat jeden bod někde napravo od něj, jde to docela snadno. Najdeme na horní a spodní straně mnohoúhelníka dva body, které spojíme s tím novým, a uzavřenou oblast z mnohoúhelníka naopak vyhodíme. Zbývá dořešit, jak ty dva body najít, a na to se perfektně hodí vektorový součin.

Jinak se to dá říct takhle: vyhodíme z mnohoúhelníka všechny úsečky, od kterých je přidávaný bod napravo. Ty mají na svědomí, že je ten bod venku, když tam nebudou, bude uvnitř. Abychom vyhodili úsečku, stačí smazat vždycky jenom její pravý bod, rozmyslete nad obrázkem proč.

Pro stručnost si mnohoúhelník budeme rovnou pamatovat jako odděleně jeho horní a spodní část. Stačí opakovat cyklus, a dokud je přidávaný bod napravo od poslední úsečky, mazat poslední bod v seznamu. Potom nový bod přidáme na konec obou seznamů a můžeme pokračovat dál.

Aby byl přidávaný bod vždycky napravo od mnohoúhelníka, jaký zatím máme, musíme body seřadit zleva doprava. Když budou body seznamy nebo dvojice čísel, stačí k tomu použít zabudovanou funkci sorted(seznam).

def rozdil(seznam_a, seznam_b):
    return [a-b for a, b in zip(seznam_a, seznam_b)]

def cross(seznam_a, seznam_b):
    return seznam_a[0]*seznam_b[1] - seznam_a[1]*seznam_b[0]

def konvexni_obal(body):
    horni = list()
    spodni = list()
    for novy in sorted(body):
        while len(horni) >= 2 and (horni[-1] == novy or cross(rozdil(horni[-1], novy), rozdil(horni[-2], horni[-1])) <= 0):
            horni.pop()
        horni.append(novy)
        while len(spodni) >= 2 and (spodni[-1] == novy or cross(rozdil(spodni[-1], novy), rozdil(spodni[-1], spodni[-2])) <= 0):
            spodni.pop()
        spodni.append(novy)
    return spodni + horni[-2:0:-1]

Všimněte si, jak na konci sloučíme horní a spodní seznam do jednoho: horní seznam musíme otočit pozpátku a vyhodit z něj oba konce, aby se ve výsledku neopakovaly. Snažte se pochopit podmínky v obou cyklech, ale mějte přitom na paměti, že totéž by šlo zapsat spoustou dalších způsobů (vektory můžeme otočit nebo prohodit ve vektorovém součinu a v souladu s tím změnit znaménko nerovnosti).

Funkce sorted(sekvence) navrací seznam utříděných hodnot a když jí dáme dvojice, seřadí je podle první souřadnice. Funkce list.pop() vyhodí (a navrátí, ale to je tady fuk) poslední položku ze seznamu – v tomto kódu si dáváme pozor, aby to byl vždycky bod na pravé špičce mnohoúhelníka.

Odbočka: kouzla se sekvencemi

class Vector(list):
    def __add__(self, other):
        return [a + b for a, b in zip(self, other)]
    
    def __mul__(self, other):
        if hasattr(other, "__iter__"):
            # skalární součin dvou vektorů
            return sum(a * b for a, b in zip(self, other))
        else:
            # součin vektoru a čísla
            return [a * other for a in self]
    __rmul__ = __mul__ # násobení zprava bude dělat totéž

V zápisu třídy Vector výše jsem použil několik triků, díky kterým je náramně stručná, ale které jsme ještě neprobírali. Využívá toho, že dědí od třídy list (to přečtete hned na prvním řádku), takže i třídu Vector je možné procházet cyklem (například).

Generátory

Python umožňuje velmi stručně vyrobit seznam z cyklu. Místo toho, abyste vyrobili prázdný seznam a napsali cyklus, který do něj jednu po druhé vloží nějaké hodnoty – například druhé mocniny čísel do stovky:

seznam = list()
for i in range(100):
    seznam.append(i**2)

...můžete ten cyklus rovnou napsat do hranatých závorek a Python potřebný seznam tiše vyrobí. Předchozí kód tedy jde napsat stručně takhle:

seznam = [i**2 for i in range(100)]

Všimněte si zápisu podrobně: tady i**2 je hodnota, kterou vkládáme do seznamu, ale proměnnou i napíšeme až o dvě slova později. Na konec napíšeme sekvenci, kterou proměnná i bude procházet.

Ve třídě Vector je ještě vtipnější zápis s kulatými závorkami, kdy se vůbec ani seznam nevyrobí – můžeme takhle stručně vyrobit cyklus a pak ho předhodit nějaké funkci. Šetří to paměť, protože se výsledek nikam neukládá, ale chová se to skoro jako seznam. Nějak podobně se chová taky funkce range, na kterou už jsme zvyklí.

Příklad. Vyrobte seznam zbytků po dělení třemi pro čísla od 0 do 99. (Začínat tedy bude [0, 1, 2, 0, ...]).

Funkce sum

Tahle funkce prostě sečte sekvenci, kterou ji dáte.

Příklad. Sečtěte všechna prvočísla menší než 100.

Funkce zip

Tahle funkce taky dělá se sekvencemi to, co slibuje její název. Když jí jako parametry dáte dvě sekvence, vrátí jednu sekvenci dvojic. Podobně to funguje i s trojicemi atd. Výsledek bude mít tolik prvků, kolik měl nejkratší parametr – funkce se jakoby zastaví, hned jak některou sekvenci projde celou.

Ve třídě Vector to používáme k tomu, abychom dostali vždycky pozici x z obou vektorů, potom pozici y z obou a nakonec z Pak je můžeme takhle rovnou sečíst a vyrobit z výsledků seznam (součet vektorů) nebo je znásobit a sečíst všechny výsledky (skalární součin).

Příklad. Napište něco podobného hře Logik: vstupem jsou dva seznamy barev (dejme tomu, že každá barva je řetězec – to je fuk), první je hráčův tip, druhý je správné řešení. Výstupem má být seznam pravdivostních hodnot (True, False), které barvy jsou na správném místě.

>>> logik(["červená", "modrá", "žlutá"], ["žlutá, "modrá", "modrá"])
[False, True, False]