Hilbertin käyrä

Hilbertin käyrä (tunnetaan myös nimellä tilan täyttävä Hilbertin käyrä ) on jatkuva fraktaalitilan täyttökäyrä , jonka saksalainen matemaatikko David Hilbert kuvasi ensimmäisen kerran vuonna 1891 [1] muunnelmana tilan täyttävistä Peano-käyristä , jotka on löydetty. Italialainen matemaatikko Giuseppe Peano vuonna 1890 [2] .

Koska käyrä täyttää tason, sen Hausdorff-mitta on (täsmälleen, sen kuva on yksikköneliö, jonka mitta on 2 missä tahansa mittamääritelmässä, ja sen kuvaaja on kompakti joukko, joka on homeomorfinen suljetun yksikkövälin kanssa Hausdorffin mittasuhteella 2).

on rajakäyrän th approksimaatio. Käyrän euklidinen pituus on , eli se kasvaa eksponentiaalisesti kohdasta , samalla kun se on aina rajallisen alueen sisällä.

Piirustukset

Sovellukset ja näyttöalgoritmit

Sekä todellinen Hilbertin käyrä että sen diskreetti approksimaatio antavat kartoituksen yksi- ja kaksiulotteisista avaruksista, jotka säilyttävät paikalliset ominaisuudet melko hyvin [3] . Jos merkitsemme ( x , y ) yksikköneliön pisteen koordinaatit ja d : llä etäisyyttä käyrällä, jolla tämä piste saavutetaan, niin pisteillä, joiden arvot ovat lähellä d :tä , on myös läheisiä arvoja . kohteeseen ( x , y ). Päinvastoin ei aina pidä paikkaansa - joillakin pisteillä, joilla on läheiset koordinaatit ( x , y ), on melko suuri ero etäisyydellä d .

Tämän paikkakunnan ominaisuuden vuoksi Hilbertin käyrä on laajalti käytössä tietokoneohjelmissa. Esimerkiksi tietokoneille osoitettujen IP-osoitteiden alue voidaan piirtää käyttämällä Hilbert-käyrää. Ohjelma tällaisen esityksen luomiseksi pisteiden värin määrittämiseksi voi muuntaa kuvan kaksiulotteisesta yksiulotteiseksi, ja Hilbertin käyrää käytetään joskus tämän käyrän paikallisuusominaisuuden vuoksi, koska sen avulla voit pysyä lähellä IP-osoitteet sulkeutuvat yksiulotteisessa esityksessä. Mustavalkoinen valokuva voidaan häivyttää käyttämällä vähemmän harmaasävyjä siirtämällä jäännöskirkkausarvo seuraavaan pisteeseen Hilbertin käyrällä. Hilbertin käyrää käytetään tässä tapauksessa, koska se ei luo näkyviä kirkkauden siirtymiä, jotka syntyvät progressiivisella muunnolla. Korkeampiulotteiset Hilbert-käyrät ovat Gray-koodien yleistyksiä, ja niitä käytetään joskus samanlaisissa tilanteissa samanlaisiin tarkoituksiin. Moniulotteisissa tietokannoissa on suositeltavaa käyttää Hilbertin järjestystä Z-järjestyksen sijaan , koska se antaa paremman paikkakunnan säilymisen. Esimerkiksi Hilbertin käyriä on käytetty R-puun indeksien pakkaamiseen ja nopeuttamiseen [4] . Hilbertin käyriä on käytetty myös tietokantojen pakkaamiseen [5] [6] .

On hyödyllistä käyttää algoritmia, joka mahdollistaa muuntamisen molempiin suuntiin (sekä ( x , y ) arvoon d että d :stä ( x , y )). Monissa ohjelmointikielissä iterointi on suositeltavampi kuin rekursio. Seuraava C -ohjelma kartoittaa molempiin suuntiin käyttämällä iteraatiota ja bittitoimintoja rekursion sijaan. Ohjelmassa neliö jaetaan n x n soluun (neliöt, joiden sivu on 1), missä n on kahden potenssi. Koordinaatit (0,0) kuuluvat vasempaan alakulmaan ja ( n -1, n -1) kuuluvat oikeaan yläkulmaan. Etäisyys d mitataan vasemmasta alakulmasta (etäisyys 0) ja kasvaa oikeaan alakulmaan.

//Muunna (x,y) muotoon 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 ); } paluu d ; } //Muunna d muotoon (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 ; } } // pyöritä /heijasta neljännestä void rot ( int n , int * x , int * y , int rx , intry ) { if ( ry == 0 ) { if ( rx == 1 ) { * x = n - 1 - * x ; * y = n - 1- * y ; } // Vaihda x ja y int t = * x ; * x = * y ; * y = t ; } }

Ohjelma käyttää C -kielen käytäntöjä: &-merkki tarkoittaa bittikohtaista AND-operaatiota (AND), ^-merkki bittikohtaista XOR-toimintoa (OR), +=-merkki tarkoittaa muuttujan summausoperaattoria ja /=-merkki tarkoittaa muuttuva jakotoiminto.

Xy2d-funktio toimii ylhäältä alas alkaen x :n ja y :n korkeista biteista ja alkaa rakentaa d :tä korkeista biteistä. Funktio d2xy toimii päinvastaiseen suuntaan, alkaen d :n alhaisista biteistä ja rakentaen x :n ja y :n alhaisista biteistä. Molemmat funktiot käyttävät koordinaattijärjestelmän ( x , y ) kierto- ja heijastusfunktiota.

Molemmat algoritmit toimivat samalla tavalla. Koko neliö katsotaan alueeksi 4 2 x 2. Jokainen alue koostuu 4 pienemmästä alueesta ja niin edelleen viimeiseen tasoon asti. Tasolla s jokaisella alueella on s x s solua. Tasojen läpi kulkee yksi FOR-silmukka. Jokaisessa iteraatiossa d :hen tai x :ään ja y : ään lisätään arvo , jonka määrää alue (neljästä), jolla olemme tällä tasolla. Alueet annetaan parilla ( rx , ry ), jossa rx ja ry saavat arvon 0 tai 1. Siten alue määritellään 2 tulobitillä (joko kaksi bittiä d :stä tai bitti x :stä ja y :stä ) ja ne muodostavat kaksi lähtöbittiä. Kiertofunktiota kutsutaan myös, jotta ( x , y ) voidaan käyttää seuraavalla tasolla seuraavassa iteraatiossa. Kun kyseessä on xy2d, se alkaa koko neliön ylätasolta ja siirtyy alaspäin yksittäisiin soluihin asti. Kun kyseessä on d2xy, prosessi alkaa solujen alaosasta ja etenee täysneliöön.

Hilbertin käyrät voidaan toteuttaa tehokkaasti, vaikka alue ei muodosta neliötä [7] . Lisäksi Hilbertin käyristä on olemassa joitain yleistyksiä suurempia ulottuvuuksia varten [8] [9] .

Edustus Lindenmayer-järjestelmässä

Hilbert-käyrän luominen voidaan kirjoittaa uudelleen L-järjestelmää varten .

Aakkoset  : A, B Vakiot  : F + − Aksiooma  : A Säännöt : A→−BF+AFA+FB− B → + AF − BFB − FA +

Tässä F tarkoittaa "mennä eteenpäin", "−" tarkoittaa käännöstä vasemmalle 90° , "+" tarkoittaa käännöstä oikealle 90° (katso kilpikonnagrafiikka ), ja A ja B ohitetaan piirrettäessä.

Muut toteutukset

Arthur Butz [10] antoi algoritmin Hilbertin käyrän laskemiseen moniulotteisissa tiloissa.

Kirja Graphics Gems II [11] käsittelee Hilbertin käyrää ja tarjoaa toteutuksen.

Hilbertin käyrän perusteella voidaan toteuttaa vibraattori- tai painettuja antennimalleja [12] .

Katso myös

Muistiinpanot

  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. Fraktaaliantennit. Pohjimmiltaan uudenlainen "rikkinäinen" antenni. Osa 2 . Elektroniikka: tiede, teknologia, liiketoiminta. - 2007. - Nro 6. S. 82-89. (2007). Haettu 22. huhtikuuta 2020. Arkistoitu alkuperäisestä 3. huhtikuuta 2018.

Kirjallisuus

  • 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 lentokone.  // Mathematische Annalen . - 1890. - Numero. 36 .
  • D. Hilbert. Über die stetige Abbildung einer Line auf ein Flächenstück.  // Mathematische Annalen . - 1891. - Numero. 38 .
  • AR Butz. Vaihtoehtoinen algoritmi Hilbertin avaruuden täyttökäyrälle. // IEEE Trans. Tietokoneissa. - 1971. - T. 20 . - doi : 10.1109/TC.1971.223258 .
  • B. Moon, HV Jagadish, C. Faloutsos, JH Saltz. Analyysi Hilbert-tilan täyttökäyrän klusterointiominaisuuksista // IEEE Transactions on Knowledge and Data Engineering. - 2001. - T. 13 , no. 1 . - doi : 10.1109/69.908985 .
  • I. Kamel, C. Faloutsos. 20. kansainvälisen Very Large Data Bases -konferenssin julkaisut. - San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1994.
  • T. Eavis, D. Cueva. Hilbert-avaruuden pakkausarkkitehtuuri tietovarastoympäristöihin // Tietojenkäsittelytieteen luentomuistiinpanot. - 2007. - T. 4654 .
  • Daniel Lemire, Owen Kaser. Sarakkeiden uudelleenjärjestäminen pienempiä indeksejä varten // Informaatiotieteet. - 2011. - T. 181 , numero. 12 . - arXiv : 0909.1346 .
  • CH Hamilton, A. Rau-Chaplin. Kompaktit Hilbert-indeksit: Tilan täyttökäyrät verkkotunnuksille, joiden sivupituudet ovat epäyhtenäiset // Tietojenkäsittelykirjaimet. - 2007. - T. 105 , no. 5 . - doi : 10.1016/j.ipl.2007.08.034 .
  • J. Alber, R. Niedermeier. Moniulotteisilla käyrillä Hilbertin ominaisuudella // Laskentajärjestelmien teoria. - 2000. - T. 33 , no. 4 . - doi : 10.1007/s002240010003 .
  • HJ Haverkort, F. van Walderveen,. Yhdennentoista algoritmisuunnittelua ja -kokeita käsittelevän työpajan julkaisut. — New York: Society for Industrial and Applied Mathematics (SIAM), 2009. — ISBN 9781615671489 .
  • Douglas Voorhies. Avaruuden täyttökäyrät ja koherenssin mitta / Andrew S. Glassner. - Boston, San Diego, New York, Lontoo, Sydney, Tokio, Toronto: AP Professional, 1991. - Vol. II. - (Grafiikan helmiä). — ISBN 0-12-059756-X .

Linkit