Curba Hilbert

Curba Hilbert (cunoscută și sub numele de curba Hilbert de umplere a spațiului ) este o curbă continuă de umplere a spațiului fractal , descrisă pentru prima dată de matematicianul german David Hilbert în 1891 [1] , ca o variantă a curbelor Peano de umplere a spațiului descoperite de către Matematicianul italian Giuseppe Peano în 1890 [2] .

Deoarece curba umple planul, dimensiunea sa Hausdorff este (exact, imaginea sa este pătratul unitar, a cărui dimensiune este 2 sub orice definiție de dimensiune, iar graficul său este un set compact homeomorf la un interval unitar închis cu dimensiunea Hausdorff 2).

este cea de- a aproximare a curbei limită. Lungimea euclidiană a curbei este , adică crește exponențial de la , în timp ce în același timp se află întotdeauna într-un pătrat cu o zonă finită.

Desene

Aplicații și algoritmi de afișare

Atât curba Hilbert adevărată, cât și aproximarea sa discretă oferă o mapare a spațiilor unidimensionale și bidimensionale care păstrează destul de bine proprietățile locale [3] . Dacă notăm cu ( x , y ) coordonatele unui punct din pătratul unității și cu d distanța de-a lungul curbei la care este atins acest punct, atunci punctele care au valori apropiate de d vor avea și valori apropiate la ( x , y ). Reversul nu este întotdeauna adevărat - unele puncte care au coordonate apropiate ( x , y ) au o diferență destul de mare în distanța d .

Datorită acestei proprietăți de localitate, curba Hilbert este utilizată pe scară largă în programele de calculator. De exemplu, o serie de adrese IP atribuite computerelor poate fi reprezentată folosind o curbă Hilbert. Un program pentru crearea unei astfel de reprezentări pentru determinarea culorii punctelor poate converti imaginea de la bidimensional la unidimensional, iar curba Hilbert este uneori utilizată datorită proprietății de localitate a acestei curbe, deoarece vă permite să păstrați aproape. Adresele IP se închid într-o reprezentare unidimensională. O fotografie alb-negru poate fi ditherată utilizând mai puține tonuri de gri, purtând valoarea luminozității reziduale la următorul punct de-a lungul curbei Hilbert. Curba Hilbert este folosită în acest caz deoarece nu creează tranzițiile vizibile în luminozitate care sunt produse prin conversie progresivă. Curbele Hilbert de dimensiuni superioare sunt generalizări ale codurilor Gray și sunt uneori folosite în situații similare în scopuri similare. Pentru bazele de date multidimensionale, se sugerează să se folosească ordinea Hilbert în loc de ordinea Z , deoarece oferă o mai bună conservare a localității. De exemplu, curbele Hilbert au fost folosite pentru comprimarea și accelerarea indicilor R-tree [4] . Curbele Hilbert au fost, de asemenea, folosite pentru comprimarea bazelor de date cu informații [5] [6] .

Este util să existe un algoritm care să permită conversia în ambele direcții (atât de la ( x , y ) la d , cât și de la d la ( x , y )). În multe limbaje de programare, iterația este preferată decât recursiunea. Următorul program C mapează în ambele direcții folosind operații de iterație și pe biți, mai degrabă decât recursiunea. Programul implică împărțirea pătratului în n x n celule (pătrate cu latura 1), unde n este o putere a două. Coordonatele (0,0) aparțin colțului din stânga jos, iar ( n -1, n -1) aparțin colțului din dreapta sus. Distanța d este măsurată din colțul din stânga jos (distanța 0) și crește până la colțul din dreapta jos.

//Conversia (x,y) în d int xy2d ( int n , int x , int y ) { int rx , ry , s , d = 0 ; pentru ( s = n / 2 ; s > 0 ; s /= 2 ) { rx = ( x & s ) > 0 ; ry = ( y & s ) > 0 ; d += s * s * (( 3 * rx ) ^ ry ); putregai ( s , & x , & y , rx , ry ); } întoarce d ; } //Conversia d în (x,y) void d2xy ( int n , int d , int * x , int * y ) { int rx , ry , s , t = d ; * x = * y = 0 ; pentru ( s = 1 ; s < n ; s *= 2 ) { rx = 1 & ( t / 2 ); ry = 1 & ( t ^ rx ); putregai ( s , x , y , rx , ry ); * x += s * rx ; * y += s * ry ; t /= 4 ; } } //rotiți/reflectați cadranul void put ( int n , int * x , int * y , int rx , int ry ) { dacă ( ry == 0 ) { dacă ( rx == 1 ) { * x = n -1 - * x ; * y = n -1 - * y ; } // Schimbați x și y int t = * x ; * x = * y ; * y = t ; } }

Programul folosește convențiile limbajului C : semnul & înseamnă operația AND (ȘI) pe biți, semnul ^ înseamnă XOR pe biți (SAU), semnul += înseamnă operatorul de adăugare a variabilei, iar semnul /= înseamnă operație de divizare variabilă.

Funcția xy2d funcționează de sus în jos, pornind de la biții înalți ai lui x și y și începe construirea d de la biții înalți. Funcția d2xy funcționează în direcția opusă, pornind de la biții inferiori ai lui d și construind x și y din biții inferiori. Ambele funcții folosesc funcția de rotație și reflexie a sistemului de coordonate ( x , y ).

Ambii algoritmi funcționează în mod similar. Întregul pătrat este considerat ca fiind 4 zone 2 x 2. Fiecare zonă este formată din 4 zone mai mici și așa mai departe până la nivelul final. La nivelul s , fiecare regiune are s x s celule. Există o singură buclă FOR care trece prin niveluri. La fiecare iterație, se adaugă o valoare la d sau la x și y , care este determinată de aria (din patru) în care ne aflăm la acest nivel. Regiunile sunt date de o pereche ( rx , ry ), unde rx și ry iau valoarea 0 sau 1. Astfel, regiunea este definită de 2 biți de intrare (fie doi biți de la d , fie un bit de la x și y ) și formează doi biți de ieșire. Funcția de rotație este, de asemenea, numită astfel încât ( x , y ) să poată fi utilizat la nivelul următor la următoarea iterație. Pentru xy2d, începe la nivelul superior al întregului pătrat și se deplasează în jos la nivelul de jos până la celulele individuale. Pentru d2xy, procesul începe din partea de jos a celulelor și se deplasează până la un pătrat complet.

Este posibil să se implementeze eficient curbele Hilbert chiar dacă aria nu formează un pătrat [7] . Mai mult, există unele generalizări ale curbelor Hilbert pentru dimensiuni mai mari [8] [9] .

Reprezentarea în sistemul Lindenmayer

Crearea curbei Hilbert poate fi rescrisă pentru sistemul L.

Alfabetul  : A, B Constante  : F + − Axioma  : A Reguli : A→−BF+AFA+FB− B → + AF − BFB − FA +

Aici F înseamnă „merge înainte”, „−” înseamnă întoarce la stânga 90° , „+” înseamnă întoarce la dreapta 90° (vezi grafica broaștei testoase ), iar A și B sunt ignorate la desen.

Alte implementări

Arthur Butz [10] a dat un algoritm pentru calcularea curbei Hilbert în spații multidimensionale.

Cartea Graphics Gems II [11] discută curba Hilbert și oferă o implementare.

Pe baza curbei Hilbert, pot fi implementate modele de vibrator sau antene imprimate [12] .

Vezi și

Note

  1. ↑ Hilbert, 1891 , p. 459-460.
  2. ↑ Peano, 1890 , p. 157-160.
  3. ↑ Moon, Jagadish, Faloutsos, Saltz, 2001 , p. 124-141.
  4. ↑ Kamel, Faloutsos, 1994 , p. 500-509.
  5. ↑ Eavis, Cueva, 2007 , p. 1-12.
  6. ↑ Lemire, Kaser, 2011 .
  7. ↑ Hamilton, Rau-Chaplin, 2007 , p. 155-163.
  8. ↑ Alber, Niedermeier, 2000 , p. 295-312.
  9. ↑ Haverkort, van Walderveen, 2009 , p. 63-73.
  10. ↑ Butz, 1971 , p. 424-42.
  11. ↑ Voorhies, 1991 , p. 26-30.
  12. ↑ Slyusar, V. Fractal Antennas. Un tip fundamental nou de antene „rupte”. Partea 2. . Electronică: știință, tehnologie, afaceri. - 2007. - Nr 6. S. 82-89. (2007). Consultat la 22 aprilie 2020. Arhivat din original pe 3 aprilie 2018.

Literatură

  • I. Kamel, C. Faloutsos. Proceedings of the 20th International Conference on Very Large Data Bases / Jorge Bocca, Matthias Jarke, Carlo Zaniolo. - San Francisco, CA, SUA: Morgan Kaufmann Publishers Inc., 1994. - ISBN 1-55860-153-8 .
  • G. Peano. Sur une courbe, qui remplit toute une aire plane.  // Mathematische Annalen . - 1890. - Emisiune. 36 .
  • D. Hilbert. Über die stetige Abbildung einer Line auf ein Flächenstück.  // Mathematische Annalen . - 1891. - Emisiune. 38 .
  • AR Butz. Algoritm alternativ pentru curba de umplere a spațiului lui Hilbert. // IEEE Trans. Pe computere. - 1971. - T. 20 . - doi : 10.1109/TC.1971.223258 .
  • B. Moon, HV Jagadish, C. Faloutsos, JH Saltz. Analiza proprietăților de clustering ale curbei de umplere a spațiului Hilbert // ​​IEEE Transactions on Knowledge and Data Engineering. - 2001. - T. 13 , nr. 1 . - doi : 10.1109/69.908985 .
  • I. Kamel, C. Faloutsos. Proceedings of the 20 International Conference on Very Large Data Bases. - San Francisco, CA, SUA: Morgan Kaufmann Publishers Inc., 1994.
  • T. Eavis, D. Cueva. O arhitectură de compresie spațială Hilbert pentru medii de depozit de date // Note de curs în informatică. - 2007. - T. 4654 .
  • Daniel Lemire, Owen Kaser. Reordonarea coloanelor pentru indici mai mici // Științe informaționale. - 2011. - T. 181 , nr. 12 . - arXiv : 0909.1346 .
  • CH Hamilton, A. Rau-Chaplin. Indici Hilbert compacti: curbe de umplere a spațiului pentru domenii cu lungimi inegale ale laturii // Litere de procesare a informațiilor. - 2007. - T. 105 , nr. 5 . - doi : 10.1016/j.ipl.2007.08.034 .
  • J. Alber, R. Niedermeier. Pe curbe multidimensionale cu proprietatea Hilbert // Teoria sistemelor de calcul. - 2000. - T. 33 , nr. 4 . - doi : 10.1007/s002240010003 .
  • HJ Haverkort, F. van Walderveen,. Lucrările celui de-al unsprezecelea atelier de inginerie algoritmică și experimente. — New York: Society for Industrial and Applied Mathematics (SIAM), 2009. — ISBN 9781615671489 .
  • Douglas Voorhies. Curbe de umplere a spațiului și o măsură de coerență / Andrew S. Glassner. - Boston, San Diego, New York, Londra, Sydney, Tokyo, Toronto: AP Professional, 1991. - Vol. II. — (Gemuri grafice). — ISBN 0-12-059756-X .

Link -uri