Hilbert-görbe

A Hilbert-görbe (más néven térkitöltő Hilbert-görbe ) egy folytonos fraktál térkitöltő görbe , amelyet először David Hilbert német matematikus írt le 1891-ben [1] , mint a térkitöltő Peano-görbék egyik változatát, amelyet a Giuseppe Peano olasz matematikus 1890-ben [2] .

Mivel a görbe kitölti a síkot, ennek Hausdorff-dimenziója ( pontosan a képe az egységnégyzet, amelynek mérete tetszőleges dimenziódefiníció esetén 2, a grafikonja pedig egy kompakt halmaz, amely egy zárt egységnyi intervallumra homeomorf 2-es Hausdorff-dimenzióval).

a határgörbe közelítése. A görbe euklideszi hossza , azaz exponenciálisan növekszik -tól , ugyanakkor mindig egy véges területű négyzeten belül van.

Rajzok

Alkalmazások és megjelenítési algoritmusok

Mind a valódi Hilbert-görbe, mind annak diszkrét közelítése olyan egydimenziós és kétdimenziós terek leképezését adja, amelyek elég jól megőrzik a lokális tulajdonságokat [3] . Ha az egységnégyzet egy pontjának koordinátáit ( x , y ) -vel jelöljük , és d -vel azt a távolságot a görbe mentén, amelynél ez a pont elérhető, akkor a d -hez közeli értékekkel rendelkező pontoknak is közeli értékei lesznek. -hoz ( x , y ). Ennek a fordítottja nem mindig igaz – néhány közeli ( x , y ) koordinátájú pont d távolsága meglehetősen nagy különbséggel rendelkezik .

Ezen lokalitási tulajdonság miatt a Hilbert-görbét széles körben használják számítógépes programokban. Például a számítógépekhez rendelt IP-címek egy tartománya ábrázolható Hilbert-görbe segítségével. A pontok színének meghatározására szolgáló ilyen ábrázolás létrehozására szolgáló program képes a képet kétdimenziósból egydimenzióssá alakítani, és ennek a görbének a lokalitási tulajdonsága miatt néha a Hilbert-görbét használják, mivel lehetővé teszi, hogy közel maradjon. Az IP-címek egydimenziós ábrázolásban záródnak. A fekete-fehér fénykép elszíneződhet kevesebb szürkeárnyalat használatával, ha a maradék fényerőt a Hilbert-görbe következő pontjára viszi. Ebben az esetben a Hilbert-görbét használjuk, mert nem hozza létre a látható fényerő-átmeneteket, amelyek progresszív konverzióval jönnek létre. A magasabb dimenziós Hilbert-görbék a Gray-kódok általánosításai, és néha hasonló helyzetekben, hasonló célokra használják. Többdimenziós adatbázisoknál a Z- rend helyett a Hilbert-rend használata javasolt , mivel ez jobb lokalitásmegőrzést biztosít. Például Hilbert-görbéket használnak az R-fa indexek tömörítésére és felgyorsítására [4] . Hilbert-görbéket is alkalmaztak információs adatbázisok tömörítésére [5] [6] .

Hasznos egy olyan algoritmus, amely lehetővé teszi az átalakítást mindkét irányban ( x , y ) -ből d -be és d -ből ( x , y )-be). Sok programozási nyelvben az iterációt részesítik előnyben a rekurzióval szemben. A következő C program mindkét irányban iterációt és bitműveleteket használ rekurzió helyett. A program magában foglalja a négyzet felosztását n x n cellára (1-es oldalú négyzetekre), ahol n kettő hatványa. A (0,0) koordináták a bal alsó sarokba, az ( n -1, n -1) pedig a jobb felső sarokba tartoznak. A d távolságot a bal alsó saroktól mérjük (0 távolság) és a jobb alsó sarokhoz növekszik.

//(x,y) konvertálása d- re 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 ); } vissza d ; } //D konvertálása (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 ); rothadás ( s , x , y , rx , ry ); * x += s * rx ; * y += s * ry ; t /= 4 ; } } //a kvadráns elforgatása/tükrözése 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 ; } // Csere x és y int t = * x ; * x = * y ; * y = t ; } }

A program a C nyelv konvencióit használja : a & jel a bitenkénti ÉS (ÉS) műveletet, a ^ jel a bitenkénti XOR-t (OR), a += jel a változó összeadás operátorát, a /= jel pedig a változó osztás művelet.

Az xy2d függvény fentről lefelé működik, az x és y magas bitjétől kezdve, és a d felépítését a magas bitekből kezdi . A d2xy függvény ellenkező irányban működik, a d alsó bitjéből indul ki, és az x és y -t az alacsony bitekből építi fel. Mindkét függvény az ( x , y ) koordinátarendszer forgatási és tükrözési függvényét használja .

Mindkét algoritmus hasonló módon működik. A teljes négyzet 4 2 x 2 területnek minősül, minden terület 4 kisebb területből áll, és így tovább egészen a végső szintig. Az s szinten minden területen s x s cella van. Egyetlen FOR hurok fut végig a szinteken. Minden iterációnál hozzáadunk egy értéket d -hez vagy x -hez és y -hoz , amelyet az a terület határoz meg (a négyből), amelyen ezen a szinten vagyunk. A régiókat egy pár ( rx , ry ) adja meg, ahol rx és ry 0 vagy 1 értéket vesz fel. Így a régiót 2 bemeneti bit határozza meg (vagy két bit a d -ből , vagy egy bit az x -ből és y -ből ), és két kimeneti bitet alkotnak . A forgatás függvényt úgy is hívják, hogy ( x , y ) a következő iterációban a következő szinten használható legyen. Az xy2d esetében a teljes négyzet legfelső szintjétől kezdődik, és lefelé halad az alsó szintre az egyes cellákig. A d2xy esetében a folyamat a cellák aljáról indul, és felfelé halad egy teljes négyzetig.

A Hilbert-görbék hatékony megvalósítása akkor is lehetséges, ha a terület nem négyzetet alkot [7] . Ezenkívül a Hilbert-görbéknek van néhány általánosítása magasabb dimenziókra [8] [9] .

Képviselet a Lindenmayer rendszerben

A Hilbert-görbe létrehozása átírható az L-rendszerre .

ABC  : A, B Állandók  : F + − Axióma  : A Szabályok : A→−BF+AFA+FB− B → + AF − BFB − FA +

Itt F jelentése "menj előre", "-" azt jelenti , hogy 90°-kal balra fordulj , a "+" azt jelenti, hogy fordulj jobbra 90°-kal (lásd a teknős grafikát ), A és B pedig figyelmen kívül marad a rajzolás során.

Egyéb megvalósítások

Arthur Butz [10] algoritmust adott a Hilbert-görbe kiszámítására többdimenziós terekben.

A Graphics Gems II [11] című könyv a Hilbert-görbét tárgyalja és egy megvalósítást ad.

A Hilbert-görbe alapján vibrátoros vagy nyomtatott antennatervek valósíthatók meg [12] .

Lásd még

Jegyzetek

  1. ↑ Hilbert, 1891 , p. 459-460.
  2. ↑ Peano, 1890 , p. 157-160.
  3. ↑ Hold, 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. Fraktálantennák. Egy alapvetően új típusú "törött" antenna. 2. rész . Elektronika: tudomány, technológia, üzlet. - 2007. - No. 6. S. 82-89. (2007). Letöltve: 2020. április 22. Az eredetiből archiválva : 2018. április 3..

Irodalom

  • 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 repülőgép.  // Mathematische Annalen . - 1890. - Kiadás. 36 .
  • D. Hilbert. Über die stetige Abbildung einer Line auf ein Flächenstück.  // Mathematische Annalen . - 1891. - Kiadás. 38 .
  • AR Butz. Alternatív algoritmus a Hilbert-féle térkitöltési görbéhez. // IEEE Trans. Számítógépeken. - 1971. - T. 20 . - doi : 10.1109/TC.1971.223258 .
  • B. Moon, HV Jagadish, C. Faloutsos, JH Saltz. A Hilbert térkitöltési görbe klaszterezési tulajdonságainak elemzése // IEEE Transactions on Knowledge and Data Engineering. - 2001. - T. 13 , sz. 1 . - doi : 10.1109/69.908985 .
  • I. Kamel, C. Faloutsos. A 20th International Conference on Very Large Data Bases konferencia anyaga. - San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1994.
  • T. Eavis, D. Cueva. Hilbert tértömörítési architektúra adattárház-környezetekhez // Számítástechnikai előadásjegyzetek. - 2007. - T. 4654 .
  • Daniel Lemire, Owen Kaser. Oszlopok átrendezése kisebb indexekhez // Információtudomány. - 2011. - T. 181 , szám. 12 . - arXiv : 0909.1346 .
  • CH Hamilton, A. Rau-Chaplin. Kompakt Hilbert-indexek: Térkitöltő görbék egyenlőtlen oldalhosszúságú tartományokhoz // Information Processing Letters. - 2007. - T. 105 , sz. 5 . - doi : 10.1016/j.ipl.2007.08.034 .
  • J. Alber, R. Niedermeier. Többdimenziós görbékről Hilbert tulajdonsággal // Számítástechnikai rendszerek elmélete. - 2000. - T. 33 , sz. 4 . - doi : 10.1007/s002240010003 .
  • HJ Haverkort, F. van Walderveen,. A tizenegyedik algoritmustervezés és kísérletek műhelyének anyaga. — New York: Ipari és Alkalmazott Matematikai Társaság (SIAM), 2009. — ISBN 9781615671489 .
  • Douglas Voorhies. Térkitöltő görbék és a koherencia mértéke / Andrew S. Glassner. - Boston, San Diego, New York, London, Sydney, Tokió, Toronto: AP Professional, 1991. - II. kötet. — (Grafikai drágakövek). — ISBN 0-12-059756-X .

Linkek