Hilbert kurva

Hilbert-kurvan (även känd som den rymdfyllande Hilbert-kurvan ) är en kontinuerlig fraktal rymdfyllande kurva , som först beskrevs av den tyske matematikern David Hilbert 1891 [1] , som en variant av de rymdfyllande Peano-kurvorna som upptäcktes av Den italienske matematikern Giuseppe Peano 1890 [2] .

Eftersom kurvan fyller planet är dess Hausdorff-dimension ( exakt, dess bild är enhetskvadraten, vars dimension är 2 under valfri dimensionsdefinition, och dess graf är en kompakt uppsättning homeomorf till ett slutet enhetsintervall med Hausdorff-dimension 2).

är den :e approximationen till gränskurvan. Kurvans euklidiska längd är , det vill säga att den växer exponentiellt från , samtidigt som den alltid ligger inom en kvadrat med en ändlig area.

Ritningar

Applikationer och visningsalgoritmer

Både den sanna Hilbert-kurvan och dess diskreta approximation ger en kartläggning av endimensionella och tvådimensionella utrymmen som bevarar lokala egenskaper ganska väl [3] . Om vi ​​betecknar med ( x , y ) koordinaterna för en punkt i enhetskvadraten och med d avståndet längs kurvan vid vilken denna punkt nås, så kommer punkter som har värden nära d också att ha nära värden till ( x , y ). Det omvända är inte alltid sant - vissa punkter som har nära koordinater ( x , y ) har en ganska stor skillnad i avstånd d .

På grund av denna lokalitetsegenskap används Hilbert-kurvan flitigt i datorprogram. Till exempel kan ett intervall av IP-adresser som tilldelats datorer plottas med hjälp av en Hilbert-kurva. Ett program för att skapa en sådan representation för att bestämma färgen på prickarna kan konvertera bilden från tvådimensionell till endimensionell, och Hilbert-kurvan används ibland på grund av lokalitetsegenskapen för denna kurva, eftersom den låter dig hålla dig nära IP-adresser sluter i en endimensionell representation. Ett svartvitt fotografi kan vibreras genom att använda färre gråskalor genom att föra restljusstyrkan till nästa punkt längs Hilbert-kurvan. Hilbertkurvan används i det här fallet eftersom den inte skapar de synliga övergångarna i ljusstyrka som produceras av progressiv konvertering. Högdimensionella Hilbert-kurvor är generaliseringar av gråkoder och används ibland i liknande situationer för liknande ändamål. För flerdimensionella databaser föreslås att man använder Hilbert-ordningen istället för Z-ordningen , eftersom det ger bättre lokalitetsbevarande. Till exempel har Hilbert-kurvor använts för att komprimera och påskynda R- trädindex [4] . Hilbertkurvor har också använts för att komprimera informationsdatabaser [5] [6] .

Det är användbart att ha en algoritm som tillåter konvertering i båda riktningarna (både från ( x , y ) till d och från d till ( x , y )). I många programmeringsspråk föredras iteration framför rekursion. Följande C -program mappar i båda riktningarna med hjälp av iteration och bitoperationer snarare än rekursion. Programmet går ut på att dela upp kvadraten i n x n celler (rutor med sida 1), där n är en potens av två. Koordinater (0,0) tillhör det nedre vänstra hörnet och ( n -1, n -1) tillhör det övre högra hörnet. Avståndet d mäts från det nedre vänstra hörnet (avstånd 0) och växer till det nedre högra hörnet.

//Konvertera (x,y) till d int xy2d ( int n , int x , int y ) { int rx , ry , s , d = 0 ; för ( s = n / 2 ; s > 0 ; s /= 2 ) { rx = ( x & s ) > 0 ; ry = ( y & s ) > 0 ; d += s * s * (( 3 * rx ) ^ ry ); röta ( s , & x , & y , rx , ry ); } returnera d ; } //Konvertera d till (x,y) void d2xy ( int n , int d , int * x , int * y ) { int rx , ry , s , t = d ; * x = * y = 0 ; för ( s = 1 ; s < n ; s *= 2 ) { rx = 1 & ( t / 2 ); ry = 1 & ( t ^ rx ); ruttna ( s , x , y , rx , ry ); * x += s * rx ; * y += s * ry ; t /= 4 ; } } //rotera/reflektera kvadranten 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 och y int t = * x ; * x = * y ; * y = t ; } }

Programmet använder konventionerna för C- språket : &-tecknet betyder den bitvisa AND (AND) operationen, ^-tecknet betyder det bitvisa XOR (OR), +=-tecknet betyder variabeladditionsoperatorn och /=-tecknet betyder variabel divisionsdrift.

Funktionen xy2d arbetar från topp till botten, med start från de höga bitarna av x och y , och börjar bygga d från de höga bitarna. Funktionen d2xy fungerar i motsatt riktning, med start från de låga bitarna i d och bygger x och y från de låga bitarna. Båda funktionerna använder koordinatsystemets rotations- och reflektionsfunktion ( x , y ).

Båda algoritmerna fungerar på liknande sätt. Hela torget betraktas som 4 2 x 2 områden. Varje område består av 4 mindre områden och så vidare upp till den slutliga nivån. På nivå s har varje region s x s celler. Det finns en enda FOR-slinga som löper genom nivåerna. Vid varje iteration läggs ett värde till d eller till x och y , som bestäms av området (av fyra) där vi befinner oss på denna nivå. Regioner ges av ett par ( rx , ry ), där rx och ry tar värdet 0 eller 1. Således definieras regionen av 2 ingångsbitar (antingen två bitar från d , eller en bit från x och y ), och de bildar två utgångsbitar. Rotationsfunktionen kallas också så att ( x , y ) kan användas på nästa nivå vid nästa iteration. För xy2d börjar den på den översta nivån av hela kvadraten och flyttar sig ner till den nedre nivån ner till de enskilda cellerna. För d2xy börjar processen från botten av cellerna och flyttas upp till en hel kvadrat.

Det är möjligt att effektivt implementera Hilbert-kurvor även om området inte bildar en kvadrat [7] . Dessutom finns det några generaliseringar av Hilbert-kurvor för högre dimensioner [8] [9] .

Representation i Lindenmayer-systemet

Skapandet av Hilbert-kurvan kan skrivas om för L-systemet .

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

Här betyder F "gå framåt", "−" betyder sväng vänster 90° , "+" betyder sväng höger 90° (se sköldpaddsgrafik ), och A och B ignoreras när man ritar.

Andra implementeringar

Arthur Butz [10] gav en algoritm för att beräkna Hilbert-kurvan i flerdimensionella rum.

Boken Graphics Gems II [11] diskuterar Hilbert-kurvan och ger en implementering.

Baserat på Hilbert-kurvan kan vibrator- eller tryckta antenndesigner implementeras [12] .

Se även

Anteckningar

  1. ↑ Hilbert, 1891 , sid. 459-460.
  2. ↑ Peano, 1890 , sid. 157-160.
  3. ↑ Moon, Jagadish, Faloutsos, Saltz, 2001 , sid. 124-141.
  4. ↑ Kamel, Faloutsos, 1994 , sid. 500-509.
  5. ↑ Eavis, Cueva, 2007 , sid. 1-12.
  6. ↑ Lemire, Kaser, 2011 .
  7. ↑ Hamilton, Rau-Chaplin, 2007 , sid. 155-163.
  8. ↑ Alber, Niedermeier, 2000 , sid. 295-312.
  9. ↑ Haverkort, van Walderveen, 2009 , sid. 63-73.
  10. ↑ Butz, 1971 , sid. 424-42.
  11. ↑ Voorhies, 1991 , sid. 26-30.
  12. ↑ Slyusar, V. Fractal Antennas. En i grunden ny typ av "trasiga" antenner. Del 2. . Elektronik: vetenskap, teknik, affärer. - 2007. - Nr 6. S. 82-89. (2007). Hämtad 22 april 2020. Arkiverad från originalet 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 plane.  // Mathematische Annalen . - 1890. - Utgåva. 36 .
  • D. Hilbert. Über die stetige Abbildung einer Line auf ein Flächenstück.  // Mathematische Annalen . - 1891. - Utgåva. 38 .
  • AR Butz. Alternativ algoritm för Hilberts rymdfyllningskurva. // IEEE Trans. På datorer. - 1971. - T. 20 . - doi : 10.1109/TC.1971.223258 .
  • B. Moon, HV Jagadish, C. Faloutsos, JH Saltz. Analys av klustringsegenskaperna för Hilberts rymdfyllande kurva // IEEE Transactions on Knowledge and Data Engineering. - 2001. - T. 13 , nr. 1 . - doi : 10.1109/69.908985 .
  • I. Kamel, C. Faloutsos. Proceedings of the 20th International Conference on Very Large Databases. - San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1994.
  • T. Eavis, D. Cueva. En Hilbert-rymdkomprimeringsarkitektur för datalagermiljöer // Lecture Notes in Computer Science. - 2007. - T. 4654 .
  • Daniel Lemire, Owen Kaser. Omordning av kolumner för mindre index // Informationsvetenskap. - 2011. - T. 181 , nummer. 12 . - arXiv : 0909.1346 .
  • CH Hamilton, A. Rau-Chaplin. Kompakta Hilbert-index: Utrymmesfyllande kurvor för domäner med ojämna sidolängder // Information Processing Letters. - 2007. - T. 105 , nr. 5 . - doi : 10.1016/j.ipl.2007.08.034 .
  • J. Alber, R. Niedermeier. På flerdimensionella kurvor med Hilbert-egenskap // Theory of Computing Systems. - 2000. - T. 33 , nr. 4 . - doi : 10.1007/s002240010003 .
  • HJ Haverkort, F. van Walderveen,. Proceedings of the Elfte Workshop on Algoritm Engineering and Experiment. — New York: Society for Industrial and Applied Mathematics (SIAM), 2009. — ISBN 9781615671489 .
  • Douglas Voorhies. Utrymmesfyllande kurvor och ett mått på koherens / Andrew S. Glassner. - Boston, San Diego, New York, London, Sydney, Tokyo, Toronto: AP Professional, 1991. - Vol. II. — (Graphics Gems). — ISBN 0-12-059756-X .

Länkar