Curva de Hilbert
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7c/Hilbert-curve_rounded-gradient-animated.gif/220px-Hilbert-curve_rounded-gradient-animated.gif)
A curva de Hilbert (também conhecida como a curva de preenchimento de espaço de Hilbert) é uma curva fractal contínua que preenche o espaço, descrita pela primeira vez pelo matemático alemão David Hilbert em 1891, como uma variante das curvas de Peano que preenchem o espaço, descobertas por Giuseppe Peano em 1890.
Por ser uma curva de preenchimento de espaço, sua dimensão de Hausdorff é 2 (precisamente, sua imagem é o quadrado unitário, cuja dimensão é 2 em qualquer definição de dimensão; seu gráfico é um conjunto compacto homeomórfico ao intervalo unitário fechado, com dimensão de Hausdorff 2).
A curva de Hilbert é construída como um limite de curvas linearmente segmentadas. O comprimento da -ésima curva é , i.e., o comprimento cresce exponencialmente com , mesmo que cada curva esteja contida num quadrado de área .
Imagens
- Curva de Hilbert, primeira ordem
- Curvas de Hilbert, primeira e segunda ordem
- Curvas de Hilbert, primeira a terceira ordem
- Regras de produção
- Curva de Hilbert, construção codificada em cor
- Uma curva de Hilbert 3-D com cores mostrando a progressão
- Variante, primeiras três iterações
Aplicações e algoritmos de mapeamento
Tanto a verdadeira curva de Hilbert quanto suas aproximações discretas são úteis porque fornecem um mapeamento entre o espaço 1D e 2D que preserva a localidade de forma bastante eficaz.[1] Isso significa que dois pontos de dados que estão próximos um do outro no espaço unidimensional também estão próximos um do outro após o dobramento. O inverso nem sempre pode ser verdadeiro.
Devido a essa propriedade de localidade, a curva de Hilbert é amplamente utilizada na ciência da computação. Por exemplo, o intervalo de endereços IP usado por computadores pode ser mapeado em uma imagem usando a curva de Hilbert. O código para gerar a imagem mapearia de 2D para 1D para encontrar a cor de cada pixel, e a curva de Hilbert é às vezes usada porque mantém endereços IP próximos uns dos outros na imagem.[2] A propriedade de localidade da curva de Hilbert também foi usada para projetar algoritmos para explorar regiões com robôs móveis.[3][4]
Em um algoritmo chamado dithering de Riemersma, fotografias em escala de cinza podem ser convertidas em uma imagem binária com dithering usando a limiarização, com a quantidade restante de cada pixel adicionada ao próximo pixel ao longo da curva de Hilbert. O código para fazer isso mapearia de 1D para 2D, e a curva de Hilbert é às vezes usada porque não cria os padrões que seriam visíveis ao olho se a ordem fosse simplesmente da esquerda para a direita em cada linha de pixels.[5] Curvas de Hilbert em dimensões superiores são uma instância de uma generalização de códigos Gray e são às vezes usadas para propósitos semelhantes, pelas mesmas razões. Para bancos de dados multidimensionais, a ordem de Hilbert foi proposta para ser usada em vez da ordem Z porque possui um comportamento de preservação de localidade melhor. Por exemplo, curvas de Hilbert foram usadas para comprimir e acelerar índices de árvores R[6] (veja a árvore R de Hilbert). Elas também foram usadas para ajudar a comprimir data warehouses.[7][8]
A distância linear de qualquer ponto ao longo da curva pode ser convertida em coordenadas em n dimensões para um dado n, e vice-versa, utilizando qualquer uma das várias técnicas matemáticas padrão, como o método de Skilling.
É possível implementar curvas de Hilbert de forma eficiente mesmo quando o espaço de dados não forma um quadrado.[9] Além disso, existem várias generalizações possíveis das curvas de Hilbert para dimensões superiores.[10][11]
Representação como um sistema de Lindenmayer
A Curva de Hilbert pode ser expressa por um sistema de reescrita (L-sistema).
- Alfabeto : A, B
- Constantes : F + −
- Axioma : A
- Regras de produção:
- A → +BF−AFA−FB+
- B → −AF+BFB+FA−
Aqui, "F" significa "avançar", "+" significa "virar à esquerda 90°", "-" significa "virar à direita 90°" (veja gráficos de tartaruga), e "A" e "B" são ignorados durante o desenho.
Outras implementações
"Graphics Gems II"[12] discute a coerência da curva de Hilbert e fornece implementação.
A Curva de Hilbert é comumente usada na renderização de imagens ou vídeos. Programas populares como Blender utilizam a Curva de Hilbert para traçar os objetos e renderizar a cena.[carece de fontes?]
Ver também
- Agendamento de curva de Hilbert
- Árvore R de Hilbert
- Localidade de referência
- Hashing sensível à localidade
- Curva de Moore
- Polígono de Murray
- Curva de Sierpiński
- Lista de fractais por dimensão de Hausdorff
Referências
- ↑ Moon, B.; Jagadish, H.V.; Faloutsos, C.; Saltz, J.H. (2001), «Analysis of the clustering properties of the Hilbert space-filling curve», IEEE Transactions on Knowledge and Data Engineering, 13 (1): 124–141, CiteSeerX 10.1.1.552.6697
, doi:10.1109/69.908985 .
- ↑ «Mapping the whole internet with Hilbert curves». blog.benjojo.co.uk. Consultado em 2 de janeiro de 2021
- ↑ Spires, Shannon V.; Goldsmith, Steven Y. (1998), Drogoul, Alexis; Tambe, Milind; Fukuda, Toshio, eds., «Exhaustive geographic search with mobile robots along space-filling curves», ISBN 978-3-540-64768-3, Berlin, Heidelberg: Springer Berlin Heidelberg, Collective Robotics, 1456, pp. 1–12, doi:10.1007/bfb0033369, consultado em 14 de agosto de 2023
- ↑ Sadat, Seyed Abbas; Wawerla, Jens; Vaughan, Richard (2015). Fractal trajectories for online non-uniform aerial coverage. 2015 IEEE International Conference on Robotics and Automation (ICRA). pp. 2971–2976
- ↑ Thiadmer Riemersma (1 de dezembro de 1998). «A Balanced Dithering Technique». Dr. Dobb's. C/C++ User's Journal
- ↑ Thiadmer Riemersma (1 de dezembro de 1998). «A Balanced Dithering Technique». Dr. Dobb's. C/C++ User's Journal
- ↑ Eavis, T.; Cueva, D. (2007). «A Hilbert Space Compression Architecture for Data Warehouse Environments». Data Warehousing and Knowledge Discovery. Col: Lecture Notes in Computer Science. 4654. [S.l.: s.n.] pp. 1–12. ISBN 978-3-540-74552-5. doi:10.1007/978-3-540-74553-2_1
- ↑ Lemire, Daniel; Kaser, Owen (2011). «Reordering Columns for Smaller Indexes». Information Sciences. 181 (12): 2550–2570. arXiv:0909.1346
. doi:10.1016/j.ins.2011.02.002
- ↑ Hamilton, C. H.; Rau-Chaplin, A. (2007). «Compact Hilbert indices: Space-filling curves for domains with unequal side lengths». Information Processing Letters. 105 (5): 155–163. doi:10.1016/j.ipl.2007.08.034
- ↑ Alber, J.; Niedermeier, R. (2000). «On multidimensional curves with Hilbert property». Theory of Computing Systems. 33 (4): 295–312. CiteSeerX 10.1.1.7.2039
. doi:10.1007/s002240010003
- ↑ H. J. Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.
- ↑ Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, pp. 26–30, Graphics Gems II.
Leituras adicionais
- Warren Jr., Henry S. (2013). Hacker's Delight 2 ed. [S.l.]: Addison Wesley – Pearson Education, Inc. ISBN 978-0-321-84268-8
- McKenna, Douglas M. (2019). Hilbert Curves: Outside-In and Inside-Gone. [S.l.]: Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1
Ligações externas
- Dynamic Hilbert curve with JSXGraph
- Three.js WebGL 3D Hilbert curve demo
- XKCD cartoon using the locality properties of the Hilbert curve to create a "map of the internet"
- Gcode generator for Hilbert curve
- Iterative algorithm for drawing Hilbert curve in JavaScript
- Algorithm 781: generating Hilbert's space-filling curve by recursion (ACM Digital Library)