Corba d'ompliment

Autor: Dr. Joan Nunes. Universitat Autònoma de Barcelona
Promotor: Institut Cartogràfic de Catalunya, 2013

 

Una corba d'ompliment (space-filling curve) és una corba fractal (Mandelbrot, 1982) contínua que té la capacitat de passar per tots els infinits punts d'un espai fins a omplir-lo enterament. Intuïtivament, una corba d'ompliment es pot entendre com un traç continu que és capaç de recórrer tots els punts d'un espai sense interrupció i sense encreuar-se (però podent fer contacte) amb ella mateixa.

Exemple de corba d'ompliment: la corba de Moore, una variant de la corba de Hilbert, en 2 i 3 dimensions, en la tercera etapa d'iteració.

Les corbes d'ompliment s'utilitzen, entre d'altres aplicacions, per a crear índexs espacials en els sistemes d’informació geogràfica (Laurini and Thompson, 1992) i, en general, en informàtica gràfica i processament d'imatges. Les corbes d'ompliment més emprades per a aquesta finalitat són la corba de Peano, la corba de Hilbert i la corba de Lebesgue,.

El matemàtic italià Giuseppe Peano va ser el primer a formular una corba d'aquest tipus. Per aquest motiu, sovint s'anomena corba de Peano qualsevol corba d'ompliment definida en el pla, encara que la corba de Peano només és un dels casos de corba d'ompliment en el pla. 

Sumari:

 

Origen

L'origen de les corbes d'ompliment és l'article publicat a finals del segle XIX pel matemàtic italià Giuseppe Peano (1890), en el qual exposà el descobriment d'una corba autointersecant que passa per tots i cada un dels punts del quadrat unitat. Amb aquest treball Peano donà solució al problema de trobar una aplicació contínua no injectiva entre l'interval unitat i el quadrat unitat, que fos consistent amb el resultat contraintuïtiu a què havia arribat anteriorment Cantor, segons el qual l'infinit nombre de punts de l'interval unitat té la mateixa cardinalitat que l'inifinit nombre de punts de qualsevol varietat d'un nombre de dimensions finit, com és ara el quadrat unitat. El resultat de Peano no fou demostrar si existeix tal funció sinó trobar una de les possibles funcions i provar que tal funció és contínua; és a dir, una funció o corba que omple l'espai. La corba de Peano fou la primera de les corbes d'ompliment que han estat formulades.

L'any següent el matemàtic alemany David Hilbert (1891) publica la definició d'una altra corba d'ompliment, la corba de Hilbert, amb una formulació analítica més complexa que la de la corba de Peano. Hilbert va ser el primer, però, a incloure un gràfic per ajudar a visualitzar la tècnica de construcció d'aquest tipus de corbes.

Definició

Formalment, una corba d'ompliment és una corba fractal el rang de la qual conté per complet l'interval unitat [0,1] en una dimensió, el quadrat unitat en dues dimensions o, en general, l'hipercub unitat en n dimensions. És a dir, una funció que té per imatge o rang de la funció tots els punts de l'espai en el qual és definida i que per tant omple aquest espai. Idealment, les corbes d'ompliment es poden definir en un espai de qualsevol dimensió, però els casos més habituals de corbes d'ompliment que han estat estudiats i que tenen aplicacions pràctiques són els de corbes definides en el pla bidimensional (corbes planars) o en l'espai tridimensional (corbes 3D).

La majoria de les corbes d'ompliment es construeixen iterativament com el límit d'una seqüència de funcions lineals parcials contínues (segments rectes) que segueixen un ordre o patró determinat, en forma de N, de Z, de P o d'altres, i recorren el pla dividit en quadrants (o l'espai dividit en cubs, o un hiperespai dividit en hipercubs) successivament més petits, de manera que el nombre de punts tendeix a infinit a mesura que la mida dels quadrats tendeix a zero i en el límit la corba acaba passant per tots els possibles punts i omple el pla o l'espai (Sagan, 1994). Per aquest motiu, sovint aquestes corbes s'identifiquen més per la imatge de la funció (el conjunt de tots els possibles valors de la funció) que no pas per la funció en si mateixa.

La dimensió fractal d'una corba d'ompliment és igual al nombre de dimensions de l'espai en què és definida, ja que l'omple, mentre que la dimensió topològica de la corba és una menys que la dimensió fractal. Així, una corba d'ompliment definida en el pla és un element lineal (de dimensió topològica 1) amb una dimensió fractal igual a 2.

Les corbes d'ompliment tenen la propietat de ser autointersecants en qualsevol punt però sense encreuar-se, la qual cosa significa que poden fer contacte amb si mateixes en tots els punts, que és la condició per "omplir" l'espai.

Corbes d'ompliment emprades per a indexació espacial

Les corbes d'ompliment tenen la propietat fonamental de transformar dades multidimensionals en unidimensionals, la qual cosa és de gran aplicació pràctica en el cas de la informació geogràfica, i de la informació espacial en general, per a crear índexs espacials ja que redueixen les posicions espacials en 2 o 3 dimensions a un ordre seqüencial unidimensional que pot ser organitzat segons estructures d'indexació de dades no espacials de tipus arbre binari o similars, que redueixen els temps de cerca a logaritmes. Les corbes d'ompliment més emprades per a índexs espacials són la corba de Peano, la corba de Hilbert i la corba de Lebesgue.

Corba de Peano

La corba de Peano és una corba d'ompliment definida en el pla, que omple el quadrat unitat mitjançant una seqüència de segments rectes que passa pels vèrtexs, pels punts mitjans dels costats i pel centre del quadrat. És la corba d'ompliment més antiga que es coneix.

Corba de Peano.

La corba de Peano que s'utilitza per a derivar l'ordre de Peano és una versió modificada de la corba de Peano original, que passa només pels centres dels quadrants en què es divideix el quadrat unitat i pren la forma de N. L'ordre de Peano és un mètode per a construir índexs espacials que, mitjançant una corba de Peano modificada en forma de N, redueix la posició de quadrants en l'espai de dues dimensions a una seqüència unidimensional, que posteriorment s'indexa mitjançant qualsevol de les estructures de dades emprades per a indexar dades no espacials, com és ara un arbre binari.

Corba de Peano modificada, o corba N, emprada per a definir l'ordre de Peano d'indexació de dades espacials. 

Corba de Hilbert

La corba de Hilbert és una corba d'ompliment definida en el pla, que omple el quadrat unitat mitjançant una seqüència de segments rectes en forma de lletra P que passa pels centres dels quadrants en què es divideix el quadrat unitat. La corba de Hilbert és la base per a derivar l'ordre de Peano-Hilbert. que serveixper a construir índexs espacials que, mitjançant una corba de Hilbert, redueixen la posició de quadrants en l'espai de dues dimensions a una seqüència unidimensional.

Corba de Hilbert.

La corba de Hilbert té la propietat de conservar força bé la proximitat en els dos espais entre els quals s'estableix correspondència: l'espai multidimensional de coordenades (habitualment el pla bidimensional en el cas de la informació geoespacial) i l'espai unidimensional de la corba. Això vol dir que els punts propers sobre la corba són punts propers en l'espai de coordenades i, en la major part dels casos, també a l'inrevés, malgrat que no es pot garantir que tots els punts propers en l'espai de coordenades siguin punts propers sobre la corba, ja que la transformació de posicions multidimensionals a una seqüència unidimensional inevitablement comporta una trajectòria sobre l'espai de coordenades que no sempre passa pels punts més propers, sino sobre els punts que toca segons el patró de definició de la corba d'ompliment.

Amb tot, la corba de Hilbert és de les que millor conserva la proximitat. Per aquest motiu, l'ordre de Peano-Hilbert sembla preferible a l'ordre Z o de Morton per a la indexació de bases de dades espacials. En particular, l'ordre de Peano-Hilbert s'ha utilitzat per a accelerar índexs espacials de tipus arbre R, en el que es coneix com a arbre R de Hilbert (Kamel and Faloutsos, 1994). D'altra banda, la corba de Hilbert es pot implementar de manera eficient també fins i tot quan l'espai de coordenades no té forma quadrada (Hamilton and Rau-Chaplin, 2007).

Per últim, hi ha diverses generalitzacions possibles de la corba de Hilbert per a espais de més de dues dimensions. En particular, per a espais de tres o de quatre dimensions (Haverkort and van Walderveen, 2009), que són els d'especial interès per a la informació geoespacial en 3D i en aplicacions espaciotemporals.

Corba de Lebesgue / Ordre de Morton

La corba de Lebesgue és una corba d'ompliment definida en el pla, que omple el quadrat unitat mitjançant una seqüència de segments rectes en forma de Z que passa pels centres dels quadrants en què es divideix el quadrat unitat. La corba de Lebesgue és la base per a derivar l'ordre de Morton.

L'ordre de Morton és una funció que fa correspondre posicions bidimensionals en el cas de les dades cartogràfiques de posició, o en general posicions multidimensionals, a posicions unidimensionals tot preservant la localització de les posicions originals. Va ser ideat per l'enginyer Morton (1966) per a indexar espacialment dades geoespacials, dins del projecte del primer sistemes d’informació geogràfica conegut, el Canadian Geographic Information System (Tomlinson, 1967), i és el primer índex espacial en el camp de la informació geoespacial.

Corba de Lebesgue i ordre de Morton.

El codi de l'ordre de Morton, que indica la posició dins la corba de Lebesgue, d'un punt bidimensional de coordenades x i y, o en general d'un punt multidimensional de n coordenades, es calcula simplement intercalant de forma alternada els dígits de la representació binària dels valors de les coordenades originals.

Obtenció de l'ordre de Morton intercalant els dígits de la representació binària de les coordenades espacials en dues dimensions.

 

Un cop ordenades les posicions espacials segons el codi de l'ordre de Morton, qualsevol estructura de dades unidimensional (és a dir, per a dades no espacials), com és ara un arbre binari o una taula resum (hash table), es pot fer servir per a indexar les posicions espacials, convertides a codis de Morton, com si fossin dades alfanumèriques.

D'altra banda, l'ordenació resultant de l'ordre de Morton és equivalent a l'ordenació que resulta de travessar un arbre quaternari (quadtree) fent una cerca en profunditat (depth-first), ja que l'ordre de les posicions sobre la corba Z emprada en l'ordre de Morton és el mateix que el dels quadrants en l'arbre quaternari i es construeix molt ràpidament intercalant la codificació binària de les coordenades. Per aquest motiu l'ordre de Morton es pot utilitzar per a construir arbres quaternaris de manera eficient (Gargantini, 1982) i, en general, altres estructures de dades de major nombre de dimensions, com per exemple els arbres octals per a dades de posicions en tres dimensions.

Malgrat que la corba de Lebesgue no és de les que millor conserven la proximitat dels punts en l'espai de coordenades, la simplicitat per a generar l'ordre de Morton i la correspondència directa amb l'estructura de dades d'arbre quaternari en fan una de les opcions d'indexació espacial més interessants.

Temes relacionats

• Fractal
• Sistemes d’informació geogràfica

Referències

Gargantini, I. (1982) "An effective way to represent quadtrees", Communications of the ACM, 25, 12, 905–910 .

Hamilton, C.H. and Rau-Chaplin, A. (2007) "Compact Hilbert indices: Space-filling curves for domains with unequal side lengths", Information Processing Letters, 105, 5, 155–163.

Hilbert, D. (1891) "Ueber die stetige Abbildung einer Line auf ein Flächenstück", Mathematische Annalen, 38, 459–460.

Kamel, I. and Faloutsos, C. (1994) "Hilbert R-tree: An improved R-tree using fractals" in Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco, California: Morgan Kaufmann Publishers Inc.

Laurini, R. and Thompson, D. (1992) Fundamentals of Spatial Information Systems, Oxford, Academic Press Ltd.

Mandelbrot, B.B. (1982) The Fractal Geometry of Nature, W. H. Freeman.

Morton, G. M. (1966) A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, Technical Report, Ottawa, Canada: IBM Ltd.

Peano, G. (1890) "Sur une courbe, qui remplit toute une aire plane", Mathematische Annalen, 36, 1, 157–160.

Sagan, H. (1994) Space-Filling Curves. Berlin: Springer-Verlag.

Tomlinson, R.F. (1967) An Introduction to the Geographic Information System of the Canada Land Inventory. Ottawa: Department of Forestry and Rural Development.

Haverkort, H. J. and van Walderveen, F. (2009) "Four-dimensional Hilbert curves for R- trees"  in Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments.

Lectures recomanades

Laurini, R. and Thompson, D. (1992) Fundamentals of Spatial Information Systems, Oxford, Academic Press Ltd.