Encoding locations using Quadtree Notation
Accounting for positional data accuracy is a complex problem that is made more difficult by fixed precision of integer and floating point numbers, especially when accuracy varies within a dataset.
Descriptions of data quality are most often given as metadata and implemented as text files that accompany data files. This is not an elegant or scalable approach, as within-dataset variations are not easily described and the metadata is intended for human use rather than for computers.
One way to express spatial accuracy is to use a hierarchical tessellation such as a quadtree. This allows map space to be subdivided in a recursive fashion until cell size decreases to the limit of the data's positional accuracy.
Hierarchical locations may be denoted as series of digits identifying nested sequences of cells. The series terminates when cells are just large enough to contain a given location.
In a regular tessellation, cells may be ordered canonically. On the lower left diagram, the red dot occupies quadtree cell 3010; quadrant 0 is NorthWest, 1 is NorthEast, 2 is SouthWest and 3 is SouthEast from the parent's center.
Thus "3010" identifies this point and any other that happen to share its location. This number thus describes not only position but spatial resolution and thus accuracy as well.
A quadtree need not be rectangular. The one shown below has triangular quadrants made by connecting midpoints of edges, generating one central and three corner quadrants of equal size. The location of quadrant 3010 is indicated (using one of several ways of addressing quadrants).
