Morton.jl

Convert between Z-order, Cartesian, and quadtree/octree coordinates
Author JaneliaSciComp
Popularity
7 Stars
Updated Last
1 Year Ago
Started In
April 2018

Morton

Build Status codecov.io

This package provides functions to convert between Morton number (a.k.a. Z-order), Cartesian coordinates, and quadtree and octree coordinates.

Say for example you have a 4x4 matrix. The sixteen cells could be addressed in each of the following three ways.

Morton order:

1 2 5 6
3 4 7 8
9 10 13 14
11 12 15 16

Cartesian coordinates:

1,1 2,1 3,1 4,1
1,2 2,2 3,2 4,2
1,3 2,3 3,3 4,3
1,4 2,4 3,4 4,4

Quadtree coordinates:

1,1 1,2 2,1 2,2
1,3 1,4 2,3 2,4
3,1 3,2 4,1 4,2
3,3 3,4 4,3 4,4

To convert from Morton to Cartesian, use the morton2cartesian function:

julia> Pkg.add("Morton")
julia> using Morton

julia> morton2cartesian(13)
2-element Array{Int64,1}:
3
3

Similarly, one can convert from Morton to quadtree, or Cartesian to quadtree:

julia> morton2tree(13)
2-element Array{Int64,1}:
4
1

julia> cartesian2tree([3,3])
2-element Array{Int64,1}:
4
1

Of course each of the functions can be reversed:

julia> cartesian2morton([3,3])
13

julia> tree2morton([4,1])
13

julia> tree2cartesian([4,1])
2-element Array{Int64,1}:
3
3

Corresponding functions also exist for three dimensional matrices (i.e. octrees). Simply replace the 2 with a 3: morton3cartesian, morton3tree, etc.

There are also un-exported N-dimensional functions to convert between tree and Morton, and tree and Cartesian (e.g. Morton._treeNmorton). Please let me know if you have a clever way to convert directly between Morton and Cartesian in arbitrary dimensions!

Related packages

RegionTrees

Author

Ben Arthur, arthurb@hhmi.org
Scientific Computing
Janelia Research Campus
Howard Hughes Medical Institute