Hilbertova křivka - Hilbert curve

Prvních šest iterací Hilbertovy křivky

Hilbertova křivka (také známý jako křivka vyplňující prostor Hilbertova ) je kontinuální fraktální křivka prostoru plnicí poprvé popsána v německé matematik David Hilbert v roce 1891, jako varianta prostorově plnicí Peano křivek zjištěných Giuseppe Peano v roce 1890.

Protože je to prostor vyplňující, jeho Hausdorffova dimenze je 2 (přesně, její obraz je jednotkový čtverec, jehož dimenze je 2 v jakékoli definici dimenze; jeho graf je kompaktní množina homeomorfní s uzavřeným jednotkovým intervalem, s Hausdorffovou dimenzí 2) .

Hilbertova křivka je konstruována jako limitace lineárních křivek po částech . Délka th křivky je , tj. Délka roste exponenciálně s , i když každá křivka je obsažena ve čtverci s plochou . ${\ displaystyle n}$ ${\ Displaystyle \ textstyle 2^{n}-{1 \ over 2^{n}}}$ ${\ displaystyle n}$ ${\ displaystyle 1}$

snímky

Hilbertova křivka, první řád
Hilbert křivky, první a druhý řád
Hilbert křivky, první až třetí objednávky
Pravidla výroby
Hilbertova křivka, konstrukce barevně odlišena
3-D Hilbertova křivka s barvou ukazující progresi
Varianta, první tři iterace

Algoritmy aplikací a mapování

Skutečná Hilbertova křivka i její diskrétní aproximace jsou užitečné, protože poskytují mapování mezi 1D a 2D prostorem, které poměrně dobře zachovává lokalitu. To znamená, že dva datové body, které jsou blízko sebe v jednorozměrném prostoru, jsou po skládání také blízko sebe. Konverzace nemůže být vždy pravdivá.

Kvůli této vlastnosti lokality je Hilbertova křivka široce používána v informatice. Například rozsah IP adres používaných počítači lze namapovat na obrázek pomocí Hilbertovy křivky. Kód pro generování obrázku by se mapoval z 2D na 1D, aby se zjistila barva každého pixelu, a někdy se používá Hilbertova křivka, protože udržuje blízké IP adresy blízko sebe na obrázku.

V algoritmu s názvem Riemersmamu rozklad, ve stupních šedi fotografii může být převeden na tónované černo-bílý obraz pomocí prahování, přičemž množství zbytků z každé přidané do dalšího pixelu podél křivky Hilbertova pixelu. Kód, který by to udělal, by mapoval od 1D do 2D a někdy se používá Hilbertova křivka, protože nevytváří rušivé vzory, které by byly viditelné okem, pokud by pořadí bylo jednoduše zleva doprava přes každou řadu pixelů. Hilbertovy křivky ve vyšších dimenzích jsou příkladem zobecnění Grayových kódů a někdy se používají pro podobné účely, z podobných důvodů. Pro vícerozměrné databáze bylo navrženo použití Hilbertova řádu místo pořadí Z, protože má lepší chování pro zachování lokality. Hilbertovy křivky byly například použity ke kompresi a zrychlení indexů R-stromu (viz Hilbertův R-strom ). Byly také použity ke komprimaci datových skladů.

Vzhledem k rozmanitosti aplikací je užitečné mít algoritmy pro mapování v obou směrech. V mnoha jazycích jsou lepší, když jsou implementovány spíše s iterací než s rekurzí. Následující kód C provádí mapování v obou směrech pomocí iterace a bitových operací, nikoli rekurze. Předpokládá čtverec rozdělený na n o n buněk, pro n mocninu 2, s celočíselnými souřadnicemi, s (0,0) v dolním levém rohu, ( n - 1, n - 1) v pravém horním rohu a vzdálenost d, která začíná na 0 v dolním levém rohu a pokračuje do v pravém dolním rohu. To se liší od výše uvedené animace, kde křivka začíná v levém horním rohu a končí v pravém horním rohu. ${\ Displaystyle n^{2} -1}$

//convert (x,y) to d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s=n/2; s>0; s/=2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(n, &x, &y, rx, ry);
    }
    return d;
}

//convert d to (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s=1; s<n; s*=2) {
        rx = 1 & (t/2);
        ry = 1 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4;
    }
}

//rotate/flip a quadrant appropriately
void rot(int n, int *x, int *y, int rx, int ry) {
    if (ry == 0) {
        if (rx == 1) {
            *x = n-1 - *x;
            *y = n-1 - *y;
        }

        //Swap x and y
        int t  = *x;
        *x = *y;
        *y = t;
    }
}

Používají konvence C: symbol & je bitový AND, symbol ^ je bitový XOR, operátor += přidává k proměnné a operátor /= dělí proměnnou. Manipulace s booleans v C znamená, že v xy2d proměnná rx je nastavena na 0 nebo 1 tak, aby odpovídala bit s o x , a podobně pro ry .

Funkce xy2d funguje shora dolů, počínaje nejvýznamnějšími bity x a y a nejdřív tvoří nejvýznamnější bity d . Funkce d2xy pracuje v pořadí opačném, počínaje nejméně významných bitů d , a budování x a y počínaje nejméně významných bitů. Obě funkce používají funkci rotace k odpovídajícímu otočení a překlopení souřadného systému ( x , y ).

Oba mapovací algoritmy fungují podobným způsobem. Celé náměstí je považováno za složené ze 4 oblastí uspořádaných 2 po 2. Každá oblast se skládá ze 4 menších oblastí atd. Pro řadu úrovní. Na úrovni s , každá oblast je s od y buňkami. Existuje jedna smyčka FOR, která iteruje úrovněmi. Při každé iteraci se přidá částka k d nebo k x a y , podle toho, ve které ze 4 oblastí se na aktuální úrovni nachází. Aktuální oblast ze 4 je ( rx , ry ), kde rx a ry jsou každý 0 nebo 1. Spotřebovává tedy 2 vstupní bity (buď 2 z d nebo 1 z x a y ), a generuje dva výstupní bity . Také volá funkci otáčení, takže ( x , y ) bude vhodné pro další úroveň, při další iteraci. U xy2d začíná na nejvyšší úrovni celého čtverce a postupuje až na nejnižší úroveň jednotlivých buněk. U d2xy začíná ve spodní části buňkami a funguje tak, že zahrnuje celý čtverec.

Hilbertovy křivky je možné efektivně implementovat i v případě, že datový prostor netvoří čtverec. Kromě toho existuje několik možných zobecnění Hilbertových křivek na vyšší dimenze.

Zastoupení jako systém Lindenmayer

Hilbertovu křivku lze vyjádřit přepisovacím systémem ( L-systém ).

Přehrávejte média

Hilbertova křivka v šesté iteraci

Abeceda : A, B

Konstanty : F + -

Axiom : A.

Pravidla produkce :

A → +BF − AFA − FB +

B → −AF+BFB+FA−

Zde „F“ znamená „natáhnout dopředu“, „+“ znamená „otočit doleva o 90 °“, „-“ znamená „otočit doprava o 90 °“ (viz grafika želvy ) a „A“ a „B“ jsou během kreslení ignorovány .

Další implementace

Graphics Gems II pojednává o koherenci Hilbertovy křivky a poskytuje implementaci.

Hilbertova křivka se běžně používá při vykreslování obrázků nebo videí. Běžné programy jako Blender a Cinema 4D používají Hilbertovu křivku ke sledování objektů a vykreslení scény.

Viz také

Poznámky

^ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460.
^ G. Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.
^ Bourges, Pascale. „ Chapitre 1: fractales “, Fractales a chaos . Přístup: 9. února 2019.
^ Měsíc, B .; Jagadish, HV; Faloutsos, C .; Saltz, JH (2001), „Analýza klastrových vlastností Hilbertovy křivky vyplňování prostoru“, IEEE Transactions on Knowledge and Data Engineering , 13 (1): 124–141, CiteSeerX 10.1.1.552.6697 , doi : 10.1109/ 69,908985.
^ „Mapování celého internetu pomocí Hilbertových křivek“ . blog.benjojo.co.uk . Citováno 2021-01-02 .
^ Thiadmer Riemersma (1998-12-01). „Vyvážená technika rozkladu“ . Uživatelský deník C/C ++ . Dr. Dobba.
^ I. Kamel, C. Faloutsos, Hilbert R-strom: Vylepšený strom R pomocí fraktálů, in: Proceedings of the 20. International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994 , s. 500–509.
^ Eavis, T .; Cueva, D. (2007). Architektura komprese prostoru Hilbert pro prostředí datového skladu . Přednášky z informatiky . 4654 . s. 1–12. doi : 10,1007/978-3-540-74553-2_1 . ISBN 978-3-540-74552-5.
^ Lemire, Daniel; Kaser, Owen (2011). „Změna pořadí sloupců pro menší indexy“. Informační vědy . 181 (12): 2550–2570. arXiv : 0909.1346 . doi : 10,1016/j.ins.2011.02.002 . S2CID 15253857 .
^ Hamilton, CH; Rau-Chaplin, A. (2007). „Kompaktní Hilbertovy indexy: Křivky vyplňující prostor pro domény s nestejnými délkami stran“. Informační dopisy . 105 (5): 155–163. doi : 10.1016/j.ipl.2007.08.034 .
^ Alber, J .; Niedermeier, R. (2000). „Na vícerozměrných křivkách s Hilbertovou vlastností“. Teorie výpočetních systémů . 33 (4): 295–312. CiteSeerX 10.1.1.7.2039 . doi : 10,1007/s002240010003 . S2CID 788382 .
^ HJ Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.
^ Voorhies, Douglas: Křivky vyplňující prostor a měřítko soudržnosti, s. 26–30, Grafické drahokamy II.

Další čtení

Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
McKenna, Douglas M. (2019). Hilbert Curves: Outside-In a Inside-Gone . Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1.

externí odkazy

[1] D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460.

[2] G. Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.

[3] Bourges, Pascale. „ Chapitre 1: fractales “, Fractales a chaos . Přístup: 9. února 2019.

[4] Měsíc, B .; Jagadish, HV; Faloutsos, C .; Saltz, JH (2001), „Analýza klastrových vlastností Hilbertovy křivky vyplňování prostoru“, IEEE Transactions on Knowledge and Data Engineering , 13 (1): 124–141, CiteSeerX 10.1.1.552.6697 , doi : 10.1109/ 69,908985.

[5] „Mapování celého internetu pomocí Hilbertových křivek“ . blog.benjojo.co.uk . Citováno 2021-01-02 .

[6] Thiadmer Riemersma (1998-12-01). „Vyvážená technika rozkladu“ . Uživatelský deník C/C ++ . Dr. Dobba.

[7] I. Kamel, C. Faloutsos, Hilbert R-strom: Vylepšený strom R pomocí fraktálů, in: Proceedings of the 20. International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994 , s. 500–509.

[8] Eavis, T .; Cueva, D. (2007). Architektura komprese prostoru Hilbert pro prostředí datového skladu . Přednášky z informatiky . 4654 . s. 1–12. doi : 10,1007/978-3-540-74553-2_1 . ISBN 978-3-540-74552-5.

[9] Lemire, Daniel; Kaser, Owen (2011). „Změna pořadí sloupců pro menší indexy“. Informační vědy . 181 (12): 2550–2570. arXiv : 0909.1346 . doi : 10,1016/j.ins.2011.02.002 . S2CID 15253857 .

[10] Hamilton, CH; Rau-Chaplin, A. (2007). „Kompaktní Hilbertovy indexy: Křivky vyplňující prostor pro domény s nestejnými délkami stran“. Informační dopisy . 105 (5): 155–163. doi : 10.1016/j.ipl.2007.08.034 .

[11] Alber, J .; Niedermeier, R. (2000). „Na vícerozměrných křivkách s Hilbertovou vlastností“. Teorie výpočetních systémů . 33 (4): 295–312. CiteSeerX 10.1.1.7.2039 . doi : 10,1007/s002240010003 . S2CID 788382 .

[12] HJ Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.

[13] Voorhies, Douglas: Křivky vyplňující prostor a měřítko soudržnosti, s. 26–30, Grafické drahokamy II.

Languages

In other projects