Z-order curve

}}

}}

In [[mathematical analysis]] and [[computer science]], [[function (mathematics)|functions]] which are ”’Z-order”’, ”’Lebesgue curve”’, ”’Morton space filling curve”’,<ref>{{cite web| url=https://portal.opengeospatial.org/files/15-104r5#.pdf| title=Discrete Global Grid Systems Abstract Specification| publisher=[[Open Geospatial Consortium]]| date=2017}}</ref> ”’Morton order”’ or ”’Morton code”’ map [[Space-filling curve|multidimensional data to one dimension]] while preserving locality of the data points. It is named in France after [[Henri Lebesgue]] studied<ref>{{citation|langue=en|first=James|last=Dugundji|title=Topology|editor=Wm. C. Brown|publisher=Dubuque (Iowa)|year=1989|pages=447|page=105|isbn=0-697-06889-7}}</ref> in 1904, and named in US after [[Guy Macdonald Morton]], who first applied the order to file sequencing in 1966.<ref>{{citation|first=G. M.|last=Morton|title=A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing|series=Technical Report|publisher=IBM Ltd.|location=Ottawa, Canada|year=1966|url=https://domino.research.ibm.com/library/cyberdig.nsf/papers/0DABF9473B9C86D48525779800566A39/$File/Morton1966.pdf}}</ref> The z-value of a point in multidimensions is simply calculated by interleaving the [[Binary code|binary]] representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as [[binary search tree]]s, [[B-tree]]s, [[skip list]]s or (with low significant bits truncated) [[hash table]]s. The resulting ordering can equivalently be described as the order one would get from a [[Depth-first search|depth-first]] traversal of a [[quadtree]] or [[Oct-tree|octree]].

In [[mathematical analysis]] and [[computer science]], [[function (mathematics)|functions]] which are ”’Z-order”’, ”’Lebesgue curve”’, ”’Morton space filling curve”’,<ref>{{cite web| url=https://portal.opengeospatial.org/files/15-104r5#.pdf| title=Discrete Global Grid Systems Abstract Specification| publisher=[[Open Geospatial Consortium]]| date=2017}}</ref> ”’Morton order”’ or ”’Morton code”’ map [[Space-filling curve|multidimensional data to one dimension]] while preserving locality of the data points. It is named in France after [[Henri Lebesgue]] studied<ref>{{citation|language=en|first=James|last=Dugundji|title=Topology|editor=Wm. C. Brown|publisher=Dubuque (Iowa)|year=1989|<!– pages=447| –>page=105|isbn=0-697-06889-7}}</ref> in 1904, and named in US after [[Guy Macdonald Morton]], who first applied the order to file sequencing in 1966.<ref>{{citation|first=G. M.|last=Morton|title=A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing|series=Technical Report|publisher=IBM Ltd.|location=Ottawa, Canada|year=1966|url=https://domino.research.ibm.com/library/cyberdig.nsf/papers/0DABF9473B9C86D48525779800566A39/$File/Morton1966.pdf}}</ref> The z-value of a point in multidimensions is simply calculated by interleaving the [[Binary code|binary]] representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as [[binary search tree]]s, [[B-tree]]s, [[skip list]]s or (with low significant bits truncated) [[hash table]]s. The resulting ordering can equivalently be described as the order one would get from a [[Depth-first search|depth-first]] traversal of a [[quadtree]] or [[Oct-tree|octree]].

==Coordinate values==

==Coordinate values==

== See also ==

== See also ==

* [[Space-filling curve]]

* [[UB-tree]]

* [[Hilbert curve]]

* [[Hilbert R-tree]]

* [[Spatial index]]

* [[Geohash]]

* [[Geohash]]

* [[Locality of reference]]

* [[Hilbert R-tree]]

* [[Linear algebra]]

* [[Locality preserving hashing]]

* [[Locality preserving hashing]]

* [[Matrix representation]]

* [[Matrix representation]]

* [[Linear algebra]]

* [[Spatial index]]

==References==

==References==