Hilbert kurve

Hilbert-kurven (også kendt som den rumfyldende Hilbert-kurve ) er en kontinuert fraktal rumfyldende kurve , første gang beskrevet af den tyske matematiker David Hilbert i 1891 [1] , som en variant af de rumfyldende Peano-kurver opdaget af Den italienske matematiker Giuseppe Peano i 1890 [2] .

Da kurven udfylder planet, er dens Hausdorff -dimension (præcis, dens billede er enhedskvadraten, hvis dimension er 2 under enhver dimensionsdefinition, og dens graf er et kompakt sæt homeomorf til et lukket enhedsinterval med Hausdorff-dimension 2).

er den th tilnærmelse til grænsekurven. Kurvens euklidiske længde er , det vil sige, at den vokser eksponentielt fra , samtidig med at den altid er indenfor et kvadrat med et begrænset areal.

Tegninger

Applikationer og visningsalgoritmer

Både den sande Hilbert-kurve og dens diskrete tilnærmelse giver en kortlægning af en-dimensionelle og to-dimensionelle rum, der bevarer lokale egenskaber ganske godt [3] . Hvis vi angiver med ( x , y ) koordinaterne for et punkt i enhedskvadraten, og med d afstanden langs kurven, hvor dette punkt nås, så vil punkter, der har værdier tæt på d , også have tætte værdier til ( x , y ). Det omvendte er ikke altid sandt - nogle punkter, der har tætte koordinater ( x , y ) har en ret stor forskel i afstand d .

På grund af denne lokalitetsegenskab er Hilbert-kurven meget brugt i computerprogrammer. For eksempel kan en række IP-adresser , der er tildelt computere, plottes ved hjælp af en Hilbert-kurve. Et program til at skabe en sådan repræsentation til bestemmelse af farven på prikkerne kan konvertere billedet fra todimensionelt til endimensionelt, og Hilbert-kurven bruges nogle gange på grund af lokalitetsegenskaben for denne kurve, da den giver dig mulighed for at holde tæt på IP-adresser lukker i en endimensionel repræsentation. Et sort-hvidt fotografi kan rystes ved at bruge færre gråtoner ved at føre den resterende lysstyrkeværdi til det næste punkt langs Hilbert-kurven. Hilbert-kurven bruges i dette tilfælde, fordi den ikke skaber de synlige overgange i lysstyrke, som frembringes ved progressiv konvertering. Højere-dimensionelle Hilbert-kurver er generaliseringer af grå koder og bruges nogle gange i lignende situationer til lignende formål. For multidimensionelle databaser foreslås det at bruge Hilbert-rækkefølgen i stedet for Z-rækkefølgen , da det giver bedre lokalitetsbevarelse. For eksempel er Hilbert-kurver blevet brugt til at komprimere og fremskynde R- træindekser [4] . Hilbert-kurver er også blevet brugt til at komprimere informationsdatabaser [5] [6] .

Det er nyttigt at have en algoritme, der tillader konvertering i begge retninger (både fra ( x , y ) til d og fra d til ( x , y )). I mange programmeringssprog foretrækkes iteration frem for rekursion. Det følgende C -program kortlægger i begge retninger ved hjælp af iteration og bitoperationer i stedet for rekursion. Programmet går ud på at opdele kvadratet i n x n celler (kvadrater med side 1), hvor n er en potens af to. Koordinater (0,0) hører til det nederste venstre hjørne, og ( n -1, n -1) hører til det øverste højre hjørne. Afstanden d måles fra nederste venstre hjørne (afstand 0) og vokser til nederste højre hjørne.

//Konverter (x,y) til 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 ( s , & x , & y , rx , ry ); } returnere d ; } //Konverter d til (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 ); rådne ( s , x , y , rx , ry ); * x += s * rx ; * y += s * ry ; t /= 4 ; } } //rotate/reflect the quadrant 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 ; } // Byt x og y int t = * x ; * x = * y ; * y = t ; } }

Programmet bruger konventionerne for C -sproget : &-tegnet betyder den bitvise AND (AND) operation, ^-tegnet betyder den bitvise XOR (OR), +=-tegnet betyder den variable additionsoperator, og /=-tegnet betyder variabel divisionsoperation.

Funktionen xy2d arbejder fra top til bund, startende fra de høje bits af x og y , og begynder at bygge d fra de høje bits. Funktionen d2xy arbejder i den modsatte retning, startende fra de lave bits af d og bygger x og y fra de lave bits. Begge funktioner bruger koordinatsystemets rotations- og reflektionsfunktion ( x , y ).

Begge algoritmer fungerer på samme måde. Hele pladsen betragtes som 4 2 x 2 områder Hvert område består af 4 mindre områder og så videre op til det endelige niveau. På niveau s har hver region s x s celler. Der er en enkelt FOR-løkke, der løber gennem niveauerne. Ved hver iteration lægges en værdi til d eller til x og y , som bestemmes af det område (ud af fire), hvor vi er på dette niveau. Regioner er givet ved et par ( rx , ry ), hvor rx og ry tager værdien 0 eller 1. Området er således defineret af 2 inputbits (enten to bits fra d , eller en bit fra x og y ), og de danner to output bits. Rotationsfunktionen kaldes også, så ( x , y ) kan bruges på næste niveau ved næste iteration. For xy2d starter den på det øverste niveau af hele firkanten og bevæger sig ned til det nederste niveau ned til de enkelte celler. For d2xy starter processen fra bunden af ​​cellerne og bevæger sig op til en fuld firkant.

Det er muligt at implementere Hilbert-kurver effektivt, selvom området ikke danner en firkant [7] . Desuden er der nogle generaliseringer af Hilbert-kurver for højere dimensioner [8] [9] .

Repræsentation i Lindenmayer-systemet

Oprettelsen af ​​Hilbert-kurven kan omskrives til L-systemet .

Alfabet  : A, B Konstanter  : F + − Aksiom  : A Regler : A→−BF+AFA+FB− B → + AF − BFB − FA+

Her betyder F "gå fremad", "−" betyder drej 90° til venstre , "+" betyder drej 90° til højre (se skildpaddegrafik ), og A og B ignoreres ved tegning.

Andre implementeringer

Arthur Butz [10] gav en algoritme til beregning af Hilbert-kurven i flerdimensionelle rum.

Bogen Graphics Gems II [11] diskuterer Hilbert-kurven og giver en implementering.

Baseret på Hilbert-kurven kan vibrator- eller trykte antennedesign implementeres [12] .

Se også

Noter

  1. ↑ Hilbert, 1891 , s. 459-460.
  2. ↑ Peano, 1890 , s. 157-160.
  3. ↑ Moon, Jagadish, Faloutsos, Saltz, 2001 , s. 124-141.
  4. ↑ Kamel, Faloutsos, 1994 , s. 500-509.
  5. ↑ Eavis, Cueva, 2007 , s. 1-12.
  6. ↑ Lemire, Kaser, 2011 .
  7. ↑ Hamilton, Rau-Chaplin, 2007 , s. 155-163.
  8. ↑ Alber, Niedermeier, 2000 , s. 295-312.
  9. ↑ Haverkort, van Walderveen, 2009 , s. 63-73.
  10. ↑ Butz, 1971 , s. 424-42.
  11. ↑ Voorhies, 1991 , s. 26-30.
  12. ↑ Slyusar, V. Fractal Antennas. En fundamentalt ny type "knækkede" antenner. Del 2. . Elektronik: videnskab, teknologi, forretning. - 2007. - Nr. 6. S. 82-89. (2007). Hentet 22. april 2020. Arkiveret fra originalen 3. april 2018.

Litteratur

  • I. Kamel, C. Faloutsos. Proceedings of the 20th International Conference on Very Large Data Bases / Jorge Bocca, Matthias Jarke, Carlo Zaniolo. - San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1994. - ISBN 1-55860-153-8 .
  • G. Peano. Sur une courbe, qui remplit toute une aire fly.  // Mathematische Annalen . - 1890. - Udgave. 36 .
  • D. Hilbert. Über die stetige Abbildung einer Line auf ein Flächenstück.  // Mathematische Annalen . - 1891. - Udgave. 38 .
  • AR Butz. Alternativ algoritme til Hilberts rumudfyldningskurve. // IEEE Trans. På computere. - 1971. - T. 20 . - doi : 10.1109/TC.1971.223258 .
  • B. Moon, HV Jagadish, C. Faloutsos, JH Saltz. Analyse af klyngeegenskaberne for Hilbert rumfyldningskurven // IEEE Transactions on Knowledge and Data Engineering. - 2001. - T. 13 , no. 1 . - doi : 10.1109/69.908985 .
  • I. Kamel, C. Faloutsos. Proceedings of the 20th International Conference on Very Large Data Bases. - San Francisco, Californien, USA: Morgan Kaufmann Publishers Inc., 1994.
  • T. Eavis, D. Cueva. En Hilbert-rumkompressionsarkitektur til datavarehusmiljøer // Lecture Notes in Computer Science. - 2007. - T. 4654 .
  • Daniel Lemire, Owen Kaser. Omarrangering af kolonner til mindre indekser // Informationsvidenskab. - 2011. - T. 181 , udg. 12 . - arXiv : 0909.1346 .
  • CH Hamilton, A. Rau-Chaplin. Kompakte Hilbert-indekser: Rumudfyldende kurver for domæner med ulige sidelængder // Information Processing Letters. - 2007. - T. 105 , no. 5 . - doi : 10.1016/j.ipl.2007.08.034 .
  • J. Alber, R. Niedermeier. På multidimensionelle kurver med Hilbert-egenskab // Theory of Computing Systems. - 2000. - T. 33 , no. 4 . - doi : 10.1007/s002240010003 .
  • HJ Haverkort, F. van Walderveen,. Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments. — New York: Society for Industrial and Applied Mathematics (SIAM), 2009. — ISBN 9781615671489 .
  • Douglas Voorhies. Rumfyldende kurver og et mål for sammenhæng / Andrew S. Glassner. - Boston, San Diego, New York, London, Sydney, Tokyo, Toronto: AP Professional, 1991. - Vol. II. — (Grafik Gems). — ISBN 0-12-059756-X .

Links