Skip to content

convert between Z-order, Cartesian, and quadtree/octree coordinates

License

Notifications You must be signed in to change notification settings

JaneliaSciComp/Morton.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

30 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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, [email protected]
Scientific Computing
Janelia Research Campus
Howard Hughes Medical Institute

About

convert between Z-order, Cartesian, and quadtree/octree coordinates

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages