Curva de Hilbert

La curva de Hilbert (también conocida como la curva de llenado de espacio de Hilbert ) es una curva de llenado de espacio fractal continua descrita por primera vez por el matemático alemán David Hilbert en 1891, [1] como una variante de las curvas de Peano de llenado de espacio descubiertas por Giuseppe Peano en 1890. [2]

Primeras seis iteraciones de la curva de Hilbert

Debido a que ocupa espacio, su dimensión de Hausdorff es 2 (precisamente, su imagen es el cuadrado unitario, cuya dimensión es 2 en cualquier definición de dimensión; su gráfico es un conjunto compacto homeomorfo al intervalo unitario cerrado, con dimensión de Hausdorff 2) .

La curva de Hilbert se construye como un límite de curvas lineales por partes . La longitud della curva es , es decir, la longitud crece exponencialmente con , aunque cada curva está contenida en un cuadrado con área .

  • Curva de Hilbert, primer orden

  • Curvas de Hilbert, primer y segundo orden

  • Curvas de Hilbert, primer a tercer orden

  • Reglas de producción

  • Curva de Hilbert, construcción codificada por colores

  • Una curva de Hilbert 3-D con color que muestra la progresión

  • Variante, primeras tres iteraciones [3]

  • Foto de David Hilbert impuesta sobre una curva de Hilbert de séptimo orden

Tanto la curva de Hilbert verdadera como sus aproximaciones discretas son útiles porque dan un mapeo entre el espacio 1D y 2D que preserva bastante bien la localidad. [4] Esto significa que dos puntos de datos que están cerca uno del otro en un espacio unidimensional también están cerca uno del otro después del plegado. Lo contrario no siempre puede ser cierto.

Debido a esta propiedad de localidad, la curva de Hilbert se usa ampliamente en informática. Por ejemplo, el rango de direcciones IP que usan las computadoras se puede mapear en una imagen usando la curva de Hilbert. El código para generar la imagen se mapearía de 2D a 1D para encontrar el color de cada píxel, y la curva de Hilbert a veces se usa porque mantiene las direcciones IP cercanas entre sí en la imagen. [5]

En un algoritmo llamado Dithering de Riemersma, la fotografía en escala de grises se puede convertir en una imagen difuminada en blanco y negro utilizando el umbral, con la cantidad sobrante de cada píxel agregada al siguiente píxel a lo largo de la curva de Hilbert. El código para hacer esto se mapearía de 1D a 2D, y la curva de Hilbert a veces se usa porque no crea los patrones de distracción que serían visibles para el ojo si el orden fuera simplemente de izquierda a derecha en cada fila de píxeles. [6] Las curvas de Hilbert en dimensiones más altas son un ejemplo de una generalización de los códigos Gray y, a veces, se utilizan para propósitos similares, por razones similares. Para las bases de datos multidimensionales, se ha propuesto que se utilice el orden de Hilbert en lugar del orden Z porque tiene un mejor comportamiento de conservación de la localidad. Por ejemplo, las curvas de Hilbert se han utilizado para comprimir y acelerar los índices del árbol R [7] (ver Árbol R de Hilbert ). También se han utilizado para ayudar a comprimir los almacenes de datos. [8] [9]

Dada la variedad de aplicaciones, es útil tener algoritmos para mapear en ambas direcciones. En muchos lenguajes, estos son mejores si se implementan con iteración en lugar de recursividad. El siguiente código C realiza las asignaciones en ambas direcciones, utilizando iteración y operaciones de bits en lugar de recursividad. Supone un cuadrado dividido en n por n celdas, para n una potencia de 2, con coordenadas enteras, con (0,0) en la esquina inferior izquierda, ( n  - 1,  n  - 1) en la esquina superior derecha, y una distancia d que comienza en 0 en la esquina inferior izquierda y va aen la esquina inferior derecha. Esto es diferente de la animación que se muestra arriba, donde la curva comienza en la esquina superior izquierda y termina en la esquina superior derecha.

// convertir (x, y) a d int  xy2d  ( int  n ,  int  x ,  int  y )  {  int  rx ,  ry ,  s ,  d = 0 ;  para  ( s = n / 2 ;  s > 0 ;  s / = 2 )  {  rx  =  ( x  &  s )  >  0 ;  ry  =  ( y  &  s )  >  0 ;  d  + =  s  *  s  *  (( 3  *  rx )  ^  ry );  rot ( n ,  & x ,  & y ,  rx ,  ry );  }  return  d ; }// convierte d en (x, y) void  d2xy ( int  n ,  int  d ,  int  * x ,  int  * y )  {  int  rx ,  ry ,  s ,  t = d ;  * x  =  * y  =  0 ;  para  ( s = 1 ;  s < n ;  s * = 2 )  {  rx  =  1  &  ( t / 2 );  ry  =  1  &  ( t  ^  rx );  pudrición ( s ,  x ,  y ,  rx ,  ry );  * x  + =  s  *  rx ;  * y  + =  s  *  ry ;  t  / =  4 ;  } }// rotar / voltear un cuadrante apropiadamente 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 ;  } // Intercambia xey  int  t  =  * x ;  * x  =  * y ;  * y  =  t ;  } }

Éstos utilizan las convenciones de C: el símbolo & es un AND bit a bit, el símbolo ^ es un XOR bit a bit, el operador + = agrega una variable y el operador / = divide una variable. El manejo de valores booleanos en C significa que en xy2d, la variable rx se establece en 0 o 1 para que coincida con los bits s de x , y de manera similar para ry .

La función xy2d funciona de arriba hacia abajo, empezando por los bits más significativos de X y Y , y la construcción de los bits más significativos de d en primer lugar. Las obras de función d2xy en el orden opuesto, a partir de los bits menos significativos de d , y la construcción de x y y de partida con los bits menos significativos. Ambas funciones usan la función de rotación para rotar y voltear el sistema de coordenadas ( x , y ) apropiadamente.

Los dos algoritmos de mapeo funcionan de manera similar. Se considera que el cuadrado completo está compuesto por 4 regiones, organizadas de 2 por 2. Cada región está compuesta por 4 regiones más pequeñas, y así sucesivamente, para varios niveles. A nivel s , cada región es s por s células. Hay un solo bucle FOR que recorre los niveles. En cada iteración, se agrega una cantidad ad o ax e y , determinada por en cuál de las 4 regiones se encuentra en el nivel actual. La región actual de los 4 es ( rx , ry ), donde rx y ry son cada uno 0 o 1. Por lo tanto, consume 2 bits de entrada (2 de d o 1 de x e y ) y genera dos bits de salida . También llama a la función de rotación para que ( x , y ) sea apropiado para el siguiente nivel, en la siguiente iteración. Para xy2d, comienza en el nivel superior de todo el cuadrado y desciende hasta el nivel más bajo de celdas individuales. Para d2xy, comienza en la parte inferior con celdas y trabaja hasta incluir todo el cuadrado.

Es posible implementar curvas de Hilbert de manera eficiente incluso cuando el espacio de datos no forma un cuadrado. [10] Además, hay varias generalizaciones posibles de las curvas de Hilbert a dimensiones superiores. [11] [12]

La curva de Hilbert se puede expresar mediante un sistema de reescritura ( sistema L ).

"> File:Hilbert Curve - 6.webmReproducir medios
Curva de Hilbert en su sexta iteración
Alfabeto  : A, B
Constantes  : F + -
Axioma  : A
Reglas de producción :
A → + BF − AFA − FB +
B → −AF + BFB + FA−

Aquí, "F" significa "avanzar", "+" significa "girar a la izquierda 90 °", "-" significa "girar a la derecha 90 °" (ver gráficos de tortugas ) y "A" y "B" se ignoran durante el dibujo. .

Graphics Gems II [13] analiza la coherencia de la curva de Hilbert y proporciona implementación.

La curva de Hilbert se usa comúnmente para renderizar imágenes o videos. Los programas comunes como Blender y Cinema 4D usan la curva de Hilbert para rastrear los objetos y renderizar la escena. [ cita requerida ]

  1. ^ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460.
  2. ^ G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.
  3. ^ Bourges, Pascale. " Chapitre 1: fractales ", Fractales et chaos . Consultado: 9 de febrero de 2019.
  4. ^ Luna, B .; Jagadish, HV; Faloutsos, C .; Saltz, JH (2001), "Análisis de las propiedades de agrupación de la curva de llenado de espacio de Hilbert", IEEE Transactions on Knowledge and Data Engineering , 13 (1): 124-141, CiteSeerX  10.1.1.552.6697 , doi : 10.1109 / 69.908985.
  5. ^ "Mapeo de todo Internet con curvas de Hilbert" . blog.benjojo.co.uk . Consultado el 2 de enero de 2021 .
  6. ^ Thiadmer Riemersma (1 de diciembre de 1998). "Una técnica de tramado equilibrado" . Diario del usuario de C / C ++ . Dr. Dobb's.
  7. ^ I.Kamel, C.Faloutsos, Hilbert R-tree: An mejorado R-tree using fractales, en: Actas de la 20a Conferencia Internacional sobre Bases de Datos Muy Grandes, Morgan Kaufmann Publishers Inc., San Francisco, CA, EE. UU., 1994 , págs. 500–509.
  8. ^ Eavis, T .; Cueva, D. (2007). Una arquitectura de compresión espacial de Hilbert para entornos de almacenamiento de datos . Apuntes de conferencias en Ciencias de la Computación . 4654 . págs. 1-12. doi : 10.1007 / 978-3-540-74553-2_1 . ISBN 978-3-540-74552-5.
  9. ^ Lemire, Daniel; Kaser, Owen (2011). "Reordenamiento de columnas para índices más pequeños". Ciencias de la información . 181 (12): 2550-2570. arXiv : 0909.1346 . doi : 10.1016 / j.ins.2011.02.002 . S2CID  15253857 .
  10. ^ Hamilton, CH; Rau-Chaplin, A. (2007). "Índices compactos de Hilbert: curvas de relleno de espacio para dominios con longitudes de lado desiguales". Cartas de procesamiento de información . 105 (5): 155-163. doi : 10.1016 / j.ipl.2007.08.034 .
  11. ^ Alber, J .; Niedermeier, R. (2000). "Sobre curvas multidimensionales con propiedad de Hilbert". Teoría de los sistemas informáticos . 33 (4): 295–312. CiteSeerX  10.1.1.7.2039 . doi : 10.1007 / s002240010003 . S2CID  788382 .
  12. ^ HJ Haverkort, F. van Walderveen, curvas de Hilbert de cuatro dimensiones para árboles R, en: Actas del undécimo taller sobre ingeniería de algoritmos y experimentos, 2009, págs. 63-73.
  13. ^ Voorhies, Douglas: curvas que llenan el espacio y una medida de coherencia, págs. 26-30, Graphics Gems II.

  • Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
  • McKenna, Douglas M. (2019). Curvas de Hilbert: de afuera hacia adentro y de adentro hacia afuera . Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1.

  • Curva dinámica de Hilbert con JSXGraph
  • Demostración de la curva de Hilbert 3D de Three.js WebGL
  • Caricatura de XKCD que usa las propiedades de localidad de la curva de Hilbert para crear un "mapa de Internet"
  • Generador de Gcode para la curva de Hilbert
  • Algoritmo iterativo para dibujar la curva de Hilbert en JavaScript
  • Algoritmo 781: generación de la curva de llenado de espacio de Hilbert por recursividad (Biblioteca digital ACM)