Bakalářská práce · MFF UK · 2020
Vezměte úsečku od nuly do jedničky. Ohýbejte ji tak dlouho, až projde každým bodem čtverce — a přitom se nikde nepřetrhne. David Hilbert ukázal v roce 1891, jak na to. Tady si to můžete osahat, bez jediného důkazu.
Proč to nikoho nenapadlo dřív
Úsečka je jednorozměrná, čtverec dvojrozměrný. Že by se jedno dalo napasovat na druhé, zní jako nesmysl. Devatenácté století zjistilo, že nesmysl to není — jen se musí dávat velký pozor na to, co přesně se po zobrazení chce.
Bodů na úsečce je přesně tolik co bodů ve čtverci. Dají se spárovat jeden k jednomu. Matematici tomu nechtěli věřit.
Ale žádné takové párování nemůže být spojité. Vždycky se někde roztrhne. Zdálo se, že je hotovo.
Když se vzdáme podmínky „jeden k jednomu" a spokojíme se s tím, že se trefíme do každého bodu, spojitě to jde.
Totéž, ale tak, že to jde nakreslit. Jeho recept je celý na téhle stránce — a je překvapivě jednoduchý.
Hlavní myšlenka
Rozdělte úsečku na čtyři stejné kusy a očíslujte je 0, 1, 2, 3. Rozdělte čtverec na čtyři stejné čtverečky a očíslujte je taky — ale v pořadí, v jakém jimi křivka projde: vlevo dole, vlevo nahoře, vpravo nahoře, vpravo dole. Teď první číslice vašeho čísla vybírá čtvereček. Druhá číslice vybírá čtvereček uvnitř něj. A tak pořád dál.
Adresa — klikáním přepínáte číslice
Funguje to i obráceně: klikněte kamkoli do čtverce a stránka dopočítá, které číslo z úsečky se tam trefí.
Co se stane s celou úsečkou najednou
Obarvěte úsečku plynulým přechodem. Rozstříhejte ji na 4n kousků a každý položte do jeho čtverečku. Kdyby zobrazení někde skákalo, barvy by se ve čtverci zamíchaly. Ony se nezamíchají.
Všimněte si, že sousední barvy zůstávají sousedy i ve čtverci. Křivka nikdy nepřeskočí přes celý obrázek — nejdál, kam se z jednoho čtverečku dostane, je čtvereček vedle.
A hlavně: kdykoli zvýšíte úroveň, obraz zůstane na místě. Nová číslice jen upřesní, kde ve svém čtverečku bod leží. Proto ta konstrukce v limitě vůbec dává smysl.
Test spojitosti, který si můžete udělat sami
Vezměte dvě čísla blízko sebe a podívejte se, kde skončí. Pak přepněte na běžné číslování „po řádcích", jak čte obrázek monitor, a sledujte, co se stane se zvýrazněným úsekem křivky. Tlačítko Skok uprostřed nastaví dvojici, na které je rozdíl vidět nejlíp.
Ta poslední řádka je záruka z práce: vzdálenost ve čtverci nikdy nepřeroste 2√5 · √|a − b|. Odmocnina je tam nutně — proto se křivka „natahuje", a proto je vůbec schopná vyplnit plochu. U číslování po řádcích žádná taková záruka neexistuje; dvě sousední čísla mohou skončit na opačných koncích.
Hrajte si
Rovná úsečka mezi středy čtverečků není povinná. Nahraďte ji lomenou čarou, obloukem nebo vlnkou — dokud náhrada zůstane ve svém čtverečku, limita je pořád křivka Peanova typu. Práce to zmiňuje jako poznámku; tady je to posuvník.
Rodina
Čím spojit sousední čtverečky
Barvy
Mimo učebnici
Hilbertův klíč umí to, co obyčejné číslování po řádcích neumí: převede polohu v ploše na jedno číslo tak, že blízké body dostanou blízká čísla. Za to ho má rádo dost oborů, které o Nettovi nikdy neslyšely.
Prostorové indexy ukládají souřadnice jako jediný Hilbertův klíč. Dotaz „co je poblíž" se pak zvládne přečtením několika souvislých úseků disku.
Textury a matice uložené v Hilbertově pořadí drží sousední data u sebe, takže procesorová cache trefuje častěji než při ukládání po řádcích.
Rozptylování chyby podél Hilbertovy křivky dává tiskovému rastru charakteristickou zrnitost bez pravidelných pruhů.
Známé plakáty s adresním prostorem IPv4 jsou Hilbertova křivka — proto na nich sousední bloky adres tvoří kompaktní obdélníky.