Universal Geospatial Data Exchange

2020-08-12 22:35

Universal Geospatial Data Exchange via Global Hierarchical Coordinates

Geoffrey Dutton
Spatial Effects
20 Payson Road
Belmont MA 02478 USA
t/f: 1-617-489-4524
e-m: dutton@spatial-effects.com
web: http://www.spatial-effects.com
Hierarchical coordinates can be considered as leaf node identifiers in area quadtrees
or nonary trees, numbered canonically. To achieve global coverage, the most
straightforward approach is to develop triangular tessellations of a platonic solid
fitted to the earth (or other spheroidal body), creating forests of quadtrees. In
practice, octahedra and icosahedra seem to be the best choices for a base solid, and
triangular quaternary breakdown of their faces also tends to be preferred. The hierarchical
coordinate system described is based on the octahedral quaternary triangular
mesh (O-QTM). Its form, topology, geometry, numbering system, nesting
and areal variations are summarized. Other hierarchical global grids can be designed
for geocoding and data exhange purposes, but will tend to have similar
properties, advantages and disadvantages as QTM. Geospatial data interchange is
then addressed. To overcome limitations and incompatibilities of local coordinate
systems and spatial identifiers, QTM's use is proposed for describing positional
data, using a binary notation called Loc8. Widespread adoption of this protocol
will yield a more efficient, elegant and reliable geospatial data infrastructure, avoid
common errors and uncertainties, and may save billions in geodata (re)processing
costs. The approach can be made completely transparent to many users, promote
distributed spatial data libraries and applications, and conserve network bandwidth
during data transmission.

This paper describes how a novel, scale-specific notation for geographic location can benefit
processing, management, communication and display of geographic information (“geodata”).
The approach uses a global multi-scale mesh that surmounts many basic difficulties
in handling geodata, including:
· Geometric distortions due to map projections
· Inadequate documentation of projections and datums
· Unspecified or variable accuracy of digitized coordinate data
· Limitations to dealing with geodata at different scales
· Indexing geodata for rapid query and retrieval
· Lack of documentation of roles and significance of features and points

Geoffrey Dutton International Conference on Discrete Global Grids, 3/2000
Many of these problems can be traced to unthinking reliance on coordinate notation — both
planar (“x, y”) and spherical (“latitude, longitude”). We model the globe as a polyhedron,
taking shape as a regular hierarchical triangulation of an octahedron embedded in a planet
(fig. 1). As it densifies, four child triangles develop within each existing one, and each has
a unique numeric address. Thirty levels of subdivision (which can be expressed in one 64-
bit word) yield child facets having areas of about 1 cm, but 20 levels (10m resolution) or
fewer usually suffice to fully encode medium-scale topographic map data. The paper discusses
various computational properties of the model, briefly describing how data encoding
is performed and applied to generalizing maps; resolution can be coarsened by supressing
less significant digits and via related techniques. We call this locational data encoding convention
Loc8 TM (a pun, not an acronym). Figure 1 illustrates the system, showing geographic
grid (yellow lines) spaced at 11.25°, which is the spacing of triangular grid points
at the third level of global subdivision (black lines).
Figure 1: Quaternary Triangular Mesh level 3 with 11.25 geographic grid,
showing encoded identifier containing Zürich, Switzerland
The U.S. public sector and geoprocessing industry lead the world in creating a national
geospatial data infrastructure — related archives of digital maps, aerial imagery and spatial

statistical data, much of it available via the internet and modestly priced if not free of
charge. These resources are increasingly relied upon for many civil, military and commercial
projects. Despite many deliberate, costly efforts to document geospatial data for consumers,
geodata are often difficult to use, and their fitness for specific uses is difficult to
evaluate in advance.

Other nations are also publishing geospatial data, leading to growing demands to integrate
datasets across national borders to enable broader, more powerful perspectives on our
planet. Despite ongoing attempts to create international geodata standards, many differences
in encoding, scale and accuracy persist, and consequently geodata consumers must spend
precious time and resources to understand the structure and limitations of other organizations’

Many interoperability issues stem from using a “map sheet metaphor” to structure geodata;
naively mimicking paper maps in a digital environment fences our planet into countless
isolated flatlands that can be spatially related to one another only indirectly, using arcane
geodetic equations that may have undocumented components. We believe it possible to
completely circumvent these difficulties by providing software for encoding and decoding
coordinate data, enabling them to be readily shared, even between local spatial reference
systems. Furthermore, by explicitly documenting accuracy of every data point, Loc8 encoding
enables geodata to be relied upon at any appropriate scale, dramatically expanding
their applicability and discouraging their misuse. This is accomplished through adopting
hierarchical coordinates (HC) as an intermediary notation for positional data at a deep level.
Hierarchical Coordinates

Geodata encodes positional information in both raster and vector format. Throughout this
paper we will focus entirely on vector-based encodings. In GIS databases these are usually
implemented as themes, layers or feature classes, elements of which are described by geometric
point, line and area primitive shapes (“primitives”), with or without descriptions of
their topological relationships. Regardless of the many structural differences such datasets
may exhibit, they univerally describe feature locations and geometries using lists of coordinate
tuples; these are normally pairs of ordinates which either describe planar (x,y) positions
on map projections or geographic positions (longitude, latitide) on the globe using a
specific datum (sometimes an elevation is appended to each tuple). It is asserted here that
many difficulties in using and sharing geodata arise from using coordinate tuple notation,
which is insensitive to both scale and error, and that the source of these difficulties is rarely
examined. When attempts are made to document positional error, solutions tend to be ineffective,
mainly because it is not practical to describe variations in accuracy or scale in sufficient
detail without vastly enlarging and complicating geo-datasets. This is because external
metadata (of which positional data quality is an important subset) does not scale well as
complexity of geo-datasets increases.

To deal with this problem directly, we feel it is necessary to abandon coordinate tuple notation
and in its place substitute hierarchical coordinates. These are location identifiers that
zoom in on geographic locations by subdividing their spatial domain in a hierarchical, basically
recursive manner. One can visualize this as a process of cutting a map sheet into four
equal rectangles, numbering each one 0, 1, 2 or 3 in a specific order; a point location of
interest will be found on one of the four sections, and this section is cut into four similar
ones which are numbered like the four created in the prior step. At each stage uncut pieces
are discarded, and the procedure is repeated until the snippet of map remaining is small
enough to identify the location without ambiguity. Then the numbers written on the retained
pieces are written down, ordered left to right from largest to smallest, as a string of digits.
This quaternary number identifies the location of interest to a certain (presumably adequate)
level of precision, and constitutes an HC.

Notice that, as opposed to a coordinate pair (tuple), a hierarchical coordinate is a single
quantity, and thus can be stored in one memory location rather than having to occupy two.
This provides a more straightforward way of querying by location, as there is only one key
hence one sorting order for coordinates. Other important aspects of planar HCs include:
· The size and coordinate origin of the spatial domain to be subdivided
· The partitioning geometry (2x2, 3x3, ... MxN)
· The spatial ordering of numeric partition labels
The above example describes what is known as a quadtree, of which many variants exist
and which is not at all new to geoprocessing. Samet’s texts (Samet 1990a,b) provide the
classic overview of quadtrees and their applications. As the second bullet above implies,
dissections of space other than quaternary ones are possible (although rarely used). Less
well appreciated is the fact that quadtrees and their relatives need not tessellate space orthogonally

into rectangles, but may also use triangular quadrants. This alternative geometry
offers useful possibilities, some of which the remainder of the paper will discuss.
The specific hierarchical coordinate system described here is called quaternary triangular
mesh (QTM).1 This model has evolved from one designed for digital elevation modeling
(Dutton 1984), subsequently recast into its current form to facilitate global spatial indexing
(Dutton 1989; Goodchild, Yang and Dutton 1991; Goodchild and Yang 1992; Otoo and
Zhu 1993), positional data quality management (Dutton 1990, 1992, 1996), terrain modeling
(Lugo and Clarke 1995) and map generalization (Dutton and Buttenfield 1993; Dutton
1999). A Ph.D. dissertation (Dutton (1998) provides an overview of QTM's development,
properties and its application to map generalization. To create a QTM, an octahedron is
aligned to the earth with its six vertices at cardinal points, fitted to an ellipsoid describing a
global datum such as WGS 84. The process of hierarchically identifying locations begins
by dividing any of its eight faces at edge midpoints to define four child triangular facets, as
figures 1 and 2 illustrate.

1 For further information about QTM, please see h ttp://www.spatial-effects.com/SE-research1.htm l

Figure 2: Quaternary Triangular mesh form, orientation and level 1 quadrant numbering
Generating hierarchical subdivisions simply requires computing arithmentic averages of the
latitudes and longitudes of vertices. Note that all such first-level (and higher level) facets --
although identical on the octahedron -- vary slightly in size and shape when the new vertices
are projected to the spheroidal surface (local relief, were it to be encoded on top of this,
would further distort facets). Subdivision may be recursively repeated as many times as are
needed to locate positions on the ground: 10 levels of subdivision produce facets about 10
km wide, 20 levels have 10 m resolution, 25 levels have 1 m resolution and 30 levels yield
1 cm facets. By consistently numbering the original eight faces and their children, every
facet – no matter how small – will have a unique integer identifier (a base8 digit followed
by some number of base4 digits). Longer QTM identifiers (QTMIDs) are more precise than
shorter ones, as resolution improves by powers of two. A set of QTMIDs thus is equivalent
to a linear quadtree (Gargantini 1982), a set of leaf node identifiers that specify the
tree's branching structure by implication only. Interior nodes are not needed, as the only
information needed to decode any given QTMID into coordinates that define that facet (or
define a representative point for it) are:
· The orientation of the octahedron within the planet;
· The ordering of the octahedron's eight faces;
· The algorithm used to assign child facet numbers (quadrant IDs);
· The number of significant digits the decoding should use, and
· A reference ellipsoid for the region, if required.

Given these parameters and an algorithm, precise geographic coordinates of its defining
triangle can be recovered from any QTMID. If the geocode represents a very small feature,
it may also alias other small ones nearby if the depth of encoding is not sufficient to distinguish
their locations. This could be problematic if data density varies considerably, especially
when a fixed level of QTM resolution is used to geocode a large population of
features. Of the above five elements, the third one is potentially most confusing. Several
schemes have been proposed for numbering QTM facets, each of which produces different
geocodes for a given location (Fekete 1990; Otoo and Zhu 1993; Lugo and Clarke 1995;
Lee and Samet 1998). However, all but one of these encoding implementations traverse
identical sets of triangular facets, because all align the octahedron in the same fashion (note
that while Fekete's numbering system is congruent with the author's, his trees are rooted in
an icosahedron, as are Lee and Samet’s). Therefore, even if different algorithms are used to
encode a given feature, a direct 1:1 mapping between the resulting geocodes exists (Fekete's
and Lee and Samet’s models excepted, again because of the different base solid).
Structure and Encoding of Loc8 Metadata

Enriching existing geodata to use Loc8 hierarchical coordinates involves several steps.
Given a geo-dataset (e.g., feature class or layer) described using vector coordinate tuples...
1. Terrestrial positional error (variable or constant) is estimated for every spatial entity
2. Coordinates are deprojected to latitude and longitude on a geocentric ellipsoidal datum
(when necessary)
3. Metadata describing types and roles of features and/or specific points are compiled
4. For each entity, geo-coordinates are converted to QTM addresses of specified precision
5. A core Loc8 identifer is constructed for each point containing its QTM address
6. Qualitative metadata applicable to the point is encoded and attached to the Loc8 ID
7. The Loc8 identifier is binary-encoded as a 64-bit word (or successive 32-bit words)
8. The dataset is updated one feature at a time, replacing coordinate tuples with Loc8 IDs
This procedure results in modifying the database to replace all coordinates with binary Loc8
identifiers that capture positional accuracy and selected qualitative attributes. The result is to
consolidate positional accuracy and related qualitative metadata parameters into one place,
rather than having them specified at each layer, feature class or feature (current GIS data
models make feature-level specification quite cumbersome, hence it is rarely attempted).
The differece between current practice (in which metadata occupies specially-designated
database fields or external files) and how Loc8 can encode positional accuracy or certainty
is diagrammed in figure 3.

Figure 3: Use of Loc8 Identifiers to encapsulate positional accuracy information
As each Loc8 ID occupies 64 bits, the amount of qualitative metadata that can be included is
inversely proportional to the precision of QTM encoding. The exact amount is given by the
MB = 58 - 2L,
where MB is the number of metadata bits available and L is the number of QTM hierarchical
levels of encoding a given point requires. Thus a 20-level encoding (c. 10 m resolution)
leaves 18 bits available for each points’s metadata, and a 24-level encoding (c. 0.5 m) allows
for 10 bits of metadata. Note that the level of QTM resolution is implicit, requiring no
bits of storage. As QTM resolution doubles at each level, it is simple to substitute resolution
for L in the above equation, given the rule of thumb
L = ceil(log2(5.0e6 / Rm)),
where 5.0e6 is one-eighth of the earth’s circumference in meters (i.e., octant edge length),
and Rm is the resolution desired, also in meters. Thus given a spatial resolution in meters,
the number of metadata bits available to further qualify such points is by substitution:
Coordinates Metadata
Geodata with Explicit
Positional Metadata
Geodata with Implicit
Positional Metadata
Storing coordinate data as Loc8
identifiers sorts this all out and
builds in positional metadata

MB = 58 - 2 ceil(log2(5.0e6 / Rm))
Ten to 20 bits may not seem like very much space in which to encode attributes or metadata,
but quite a lot of information can be built into such qualifiers. Dutton (1996, 1999)
provides examples of information that can be organized into such qualifier fields, aimed at
augmenting QTM IDs to aid map generalization operations. The qualifiers described are
each coded as 2-bit quantities which are restricted to have only three values (01, 10, 11);
the pattern 00 is excluded because it is used as a sentinel to terminate qualifier sets. This
means that any number of ternary qualifiers, up to MB/2 or less, can be encoded in a Loc8
ID, or no qualifiers may be stored. Parsing the qualifiers is simple if they are known to use
2-bit ternary encoding; starting at the highest-order bit, successive pairs of bits are examined.
Nonzero pairs are qualifiers, and their values and positions are noted. The first zerovalue
bit pair encountered indicates that all qualifiers have been parsed, and the next
nonzero bit-pair encountered is interpreted as the first half on a QTM octant ID (the octant
ID occupies 4 bits, and when it is parsed 4 is subtracted from the value stored; the left shift
is introduced in order to avoid placing 00 in the two high-order octant ID bits). The remaining
low-order bits in the Loc8 ID are all significant 2-bit QTM quadrant IDs. A parsing
algorithm is described in (Dutton 1996). An example of the bit-level encoding that results is
illustrated in figure 4.

Figure 4: 64-bit word layout of a Loc8 Identifier having seven ternary qualifiers
14 bits 6 bits 4 bits 40 bits
zero zero zero or non-zero
Some possible locational Qualifiers and encoding conventions
1 Vertex Type Node Point Mixed Topological role
2 Vertex Origin Defined Imputed Mixed Locational importance
3 Vertex Angle Sharp Smooth Mixed Local angularity
4 Feature Genus Point Line Area Topological dimension
5 Feature Origin Cultural Natural Mixed Source of entity
6 Feature Width Fixed Variable Mixed Uniformity of extent
7 Feature Priority High Low Medium General malleability

While the above describes qualifiers as two-bit ternary fields, they can have any even number
of bits; using two bits seems to offer the most flexibility, especially when QTM resolutions
are allowed to vary. The Loc8 format enables the lengths of qualifier fields, the
number of fields and the number of quaternary digits to vary point by point. As the number
of qualifiers in a given Loc8 ID may not be known in advance, and may change from one
feature or even one point to the next, their field ordering is significant and rules are needed
to interpret them correctly. The rules can be rigid or flexible, as the following illustrate:
· Rigid: Each qualifier is two bits, and contains 01, 10 or 11; interpretation depends
only on absolute position (i.e., bits 1-2 are qualifier A, bits 3-4 are qualifier B ...);
where space restricts their number, “least significant” qualifiers are omitted.
· Flexible: Some qualifiers imply that others follow directly, and certain ones might be
larger than two bits (i.e., ordering/size is partly contextual).

Whatever scheme is adopted, it needs to be documented in some fashion so that recipients
of Loc8 data can parse and interpret qualifier fields (in the absence of such directives the
QTMID portion of Loc8 words can still be retrieved, however). Just as QTMID lengths can
vary between and even within features or not, the meanings of qualifiers may change, or
may remain fixed across an entire dataset. In all cases, some sort of higher-level metadata
(akin to a feature attribute table or feature coding guide) needs to be provided at the appropriate
level of detail within datasets. This paper will not pursue such concerns beyond
pointing out that such higher-level metadata must indicate:
· Names and descriptions of each qualifier
· Sizes of specific qualifiers (number of bit-pairs)
· Descriptions of what specific qualifier values mean
· Ordering or priorities assumed for qualifiers
· Dependencies between qualifiers, if any

At least two types of dependencies may occur. Type I dependency enables qualifier i, by its
value, to indicate what the identity of qualifier i+1 is; type II dependency enables qualifier i,
by its value, to modify the interpretation of the values of qualifier i+1 (the identity of which
would be given by its position in the set). Such metadata must be provided in both machine-
and human-interpretable form.

Including qualifiers in Loc8 words is not mandatory of course, and their presence can always
be ignored. While handling qualifiers adds to the complexity of creating and using
Loc8 data, making such internal metadata available provides a distinct opportunity to geoprocessing
communities to add real value and remove sources of potential error from geodata.
Furthermore, the content and application of Loc8 qualifiers can vary across datasets,
applications and knowledge domains. Qualifiers can be encoded as simple attributes, or
indicate specific operations or behaviors. One can think of a Loc8 word as an object that
describes its behavior or how it should be used, i.e., as containing an operator and an operand.
Methods invoked on a Loc8 object’s data can be specified by the operator portion,
or may be defined for the class to which a Loc8 object belongs. This provides a high deUniversal
gree of flexibility in applying Loc8 to encode and use semantic knowledge at very detailed
degrees of specificity.
General Benefits of Loc8

Were Loc8 encoding to be adopted for data transmission and database storage, it could
simplify a host of applications and enable them to become more transparent, capable and
reliable. This will occur beneath users’ notice, although many will appreciate enhancements
it will bring to data access and productivity. How this can happen is described below. What
it would specifically mean for users is difficult to enumerate, but involves at least these
three “U”s:
· U s abilit y : encoding a geographic position into Loc8 requires its accuracy to be explicitly
stated; this critical metadata is built into all Loc8 data and is available to inform applications
of limitations to analysis or dislay.
· U n iversalit y : Loc8 handles all locations equally well, regardless of where they lie or
what national, state or local coordinate reference systems may exist there; to the extent
they are mapped, other planetary bodies can be treated exactly the same way.
· U n iquenes s : Although a Loc8 identifier is shared by all locations within a specific triangular
patch of ground or water, if that triangle excludes all competing entities, such
an address can fully identify a specific feature, and can be enhanced to specify characteristics
of it besides location. Thus Loc8 enables construction of globally unique geocodes
(similar to postcodes).

Loc8 by itself will not provide complete interoperability, as it constitutes only part of a
protocol or standard for handling geodata; other necessary elements include geometries,
images, topologies, attributes, relationships, labels, semantics and metadata. While many
geodata exchange standards have been proposed and adopted, few standards exist for internal
database architectures or interfaces between applications and databases. Much of the
progress in this area is being made and reported by the Open GIS Consortium (OGC,
Wayland MA, http://www.ogc.org/), which coordinates its activities with industry and
standards bodies such as NIST and ISO. By injecting Loc8 into OGC’s process — aiming
at having it supported as an alternative encoding method — geoprocessing standards can
both anticipate and promote Loc8’s diffusion into practice as OGC’s work starts to impact
geoprocessing during the next five years or so.
Unresolved Issues
Several prototypes of Loc8-based software have been built. The author’s testbed encodes
coordinates of map features, analyzes the encodings and regenerates the features at specified
scales using special techniques. This software (written in C) is not fit for general use,
but has proven the validity of the concept. An earlier C-language prototype developed by
academic colleagues (Goodchild and Yang 1992) successfully demonstrated applicability of

a Loc8 variant to common operations on spatial data, but was abandoned when funding
expired. Some issues these projects did not address that still need to be explored are:
Bit-level R e presentation o f L oc8 g eocode s . To date, software prototypes have represented
Loc8 identifiers as strings of characters, as this made handling and debugging them simpler.
But binary encoding such as is described above is needed to make Loc8-based software
more efficient and capable. As Loc8 geocodes need to carry 64 bits of precision, their
binary representation is problematic; until recently computer hardware, programming languages
and operating systems only supported such quantities in restricted and clumsy
ways. These limitations are receding, and settling on an internal format for binary Loc8
codes is thus a high priority. Doing this is not technically difficult, but the protocol must be
robust, extensible to include additional identifying information and acceptable to the potential
user community. Hence careful multi-sector requirements analyses are needed.
Extended O bject S p atial I n dexin g . Fulfilling Loc8’s promise as a spatial indexing mechanism
entails developing methods and structures to efficiently represent the locations, sizes
and shapes of geographic entities, which range from fenceposts to continents, and may be
neither compact nor regular. Several approaches to this involving collections of Loc8 facets
have been conceptualized, and need to be implemented and tested. Whether Loc8 is widely
accepted may depend strongly on how efficiently software can insert and retrieve many varieties
of spatial entities in a “Loc8-native” database.

Native S p atial A nalysis M ethod s . Existing methods to determine spatial properties of
Loc8-encoded data need to be augmented, as few such algorithms exist for data in a triangulated
polyhedral domain. Examples of spatial property measures include: computing facet
areas, finding distances between facets, determining what facets lies within a region and
what facets lie between two points. We can perform such operations in Cartesian and
spherical domains, but doing so requires converting Loc8 geocodes to coordinates, which
is inefficient. Fast, appropriate native methods need to be developed. The most general
technical challenge faced is to integrate two very different computational domains, v ecto r
(geometry-oriented) and r a ste r (pixel-oriented). Existing GIS packages combine them in
certain ways, but in databases the two types of representation are always maintained separately
(hence the wisecrack, “raster is faster but vector is correcter”). Our experience encourages
us that Loc8 can bring these domains closer together at rather low levels, and this
will greatly facilitate fusion of disparate types of geodata (such as digital maps and satellite
images), a common yet complex geoprocessing requirement.

[b]Implementing Loc8 in GIS Environments[/b]

The era of proprietary database formats for geographical and other information is coming to
a close. With few exceptions, major database vendors now provide API protocols for remote
access by foreign applications. Besides being voluminous, geographical data can be
highly complex and structured idiosyncratically; thus interoperability has improved in rather
small steps, but progress is accelerating thanks to continuing industry and governmental
efforts to codify geoprocessing standards.
It is this context that Loc8-enabled software can address, providing solutions to nagging
problems that are well-known but have yet to be appropriately addressed. One design for
implementing Loc8 as middleware is shown in figure 5. The diagram depicts how Loc8
data is encoded, transmitted between applications and decoded for use in a transparent
fashion (users may need to indicate or supply relevant metadata, and should be sophisticated
enough to exploit the stored metadata in analysis and interpretation). The data interface
link at the bottom of figure 5 shows how Loc8 databases or extracts of them can be
shared, but a given GIS would normally possess both encoding and decoding capabilities.
Figure 5: A possible Loc8 geodata conversion architecture
Such a strategy makes sense because (1) translating coordinates to and from Loc8 identifiers
should not affect users’ views of geodata, (2) GIS software and other applications need
not know how to interpret and manipulate Loc8 encodings, and (3) database mechanisms
and schemata should be modified as little as possible to handle Loc8 data. The middleware
layer will be imposed in between the database and the application; it will encode coordinates
as Loc8 IDs based on metadata suppled by the user via a manual interface, file and/or external
database. The encoded coordinates will occupy the fields in the database previously
allocated to feature coordinates; these fields may need to be redefined in the schema if they
data access
interface DBMS
Loc8 Parameters specify positional
accuracy and semantic qualifiers for entities
Loc8 Conversion involves encoding/decoding
base4 identifiers for each geo-coordinate
were initially described as containing floating-point tuples. The sizes of existing coordinate
data fields may change when Loc8 encoding is implemented, but should never grow larger
(e.g, two 32-bit fields become one 64-bit field, or two 64-bit fields become one 64-bit
field, in which case the unused space can be reclaimed). The Loc8 software layer will receive
and emit coordinate and metadata data via an application programming interface
(API). In turn, it will communicate to geospatial databases via APIs appropriate to the specific
store involved. Flags can be set for features, classes or layers to indicate that Loc8 encoding
is present, and schemata inserted to identify whether and how metadata are
described within Loc8 fields.

[b]Concluding Observations[/b]

The overarching impediment to the adoption of Loc8 is a general complacency and lack of
awareness about the inherent limitations of coordinate notation. For years, GIS communities
have avoided confronting those problems, apparently preferring to expend millions of
hours generating metadata, doctoring deficiencies in one geographic dataset after another,
and then waste more time trying to cope with consequences of uncertain data quality to
spatial analysis and display. Is this smart? Is it necessary? We think not.
Achieving acceptance for Loc8 is an uphill struggle, because nothing like it has ever been in
general use and no rival schemes exist that might supply similar benefits. Some technical
objections to this approach may be argued by individuals with expertise in geodesy and
surveying. Such feedback is welcomed, and may be useful as we refine our approach. The
principal challenge faced, however, is not simply technical; we must convince geoprocessing
constituencies of the need for and value of Loc8. This is presently difficult because
very few developers and users in geodata communities recognize the impediments erected
by reliance on coordiinate tuple notation.

One further limitation to the general use of Loc8 is the prevalence of geodata with projected
(planar) rather than geographic (spherical) coordinates. As Loc8 encoding can only be performed
from spherical notation, only planar geodata for which inverse projection equations
to latitude and longitude are available can be handled. Many spatial datasets — particularly
local working data files for applications — do not describe their projection types and parameters.
If applications are not sophisticated in their handling of coordinate data, they are
not likely to be able to use Loc8 directly. We will initially deal with this by concentrating on
inserting Loc8 earlier in the “geodata food chain,” and by encouraging development of data
translation utilities to nourish less capable applications.

No map or geographic database can be truly faithful the richness of the world, to its majesty
and diversity in space, time and human understanding. GIS professionals confront
these limits constantly in designing databases and maps, manipulating and analyzing geodata,
and attempting to adapt it to changing needs. Using digital lenses to view the world
distorts it in subtle ways that practitioners don't always understand. The technology is thus
far from neutral in its consequences, and our growing dependence upon it creates new
Universal Geospatial Data Exchange via Global Hierarchical Coordinates Page 14 / 15
Geoffrey Dutton International Conference on Discrete Global Grids, 3/2000
kinds of spatial effects -- good, bad and often unknown -- not just in models and on monitors,
but in the real world itself. We worry about this, have dedicated years to improving
the handling and communication of geodata, and are committed to bringing higher standards
to geographic information and its application. Creating a global multi-scale geodata
infrastructure will be a huge step toward this goal.

Dutton, G., 1984, Geodesic modelling of planetary relief. Cartographica. 21(2&3), 188-
Dutton, G., 1989, Modelling locational uncertainty via hierarchical tessellation. In M.
Goodchild & S. Gopal (eds.), Accuracy of Spatial Databases,. (London: Taylor &
Francis), 125-140.
Dutton, G., 1990, Locational properties of quaternary triangular meshes. Proc. Spatial
Data Handling Symp. 4. Dept. of Geography, U. of Zurich (July 1990), 901-10.
Dutton, G., 1992, Handling positional uncertainty in spatial databases. Proc. Spatial Data
Handling Symp. 5. Charleston, SC, August 1992, 2, 460-469.
Dutton, G. and Buttenfield, B.P., 1993, Scale change via hierarchical coarsening:
Cartographic properties of Quaternary Triangular Meshes. Proc. 16th Int.
Cartographic Conference. K?ln, Germany, May 1993, 847-862.
Dutton, G., 1996, Improving locational specificity of map data: A multi-resolution,
metadata-driven approach and notation. Int. J. of GIS. London: Taylor & Francis,
10(3), 253-268.
Dutton, G., 1998, A hierarchical coordinate system for geoprocessing and cartography.
Lecture Notes in Earth Science 79. Berlin: Springer-Verlag. XIX + 231 pp. 97
figs., 12 plates, 16 tabs. ISSN 0930-0317; ISBN 3-540-64980-8.
Dutton, G., 1999, Scale, sinuosity and point selection in digital line generalization.
Cartography and Geographic Information Science 26(1), 33-53.
Fekete, G., 1990, Rendering and managing spherical data with sphere quadtrees.
Proc.Visualization '90 (First IEEE Conference on Visualization, San Francisco, CA,
October 23-26, 1990). Los Alamitos CA: IEEE Computer Society Press.
Gargantini, I., 1982, An effective way to represent quadtrees. Comm. of the ACM,
25(12), 905-910.
Goodchild, M.F. and Yang Shiren, 1992, A hierarchical data structure for global
geographic information systems. Computer Graphics, Vision and Image Processing,
54(1), 31-44.
Goodchild, M., Yang Shiren and Dutton, G., 1991, Spatial Data Representation and
Basic Operations for a Triangular Hierarchical Data Structure. Santa Barbara, CA:
NCGIA Technical Paper 91-8.
Lee, M. and Samet, H., 1998, Traversing the triangle elements of an icosohedral spherical
representation in constant-time. Proc. Spatial Data Handling Symposium '98.
Vancouver Canada, July 1998, 22-33.
Lugo, J.A. and Clarke, K.C., 1995, Implementation of triangulated quadtree sequencing
for a global relief data structure. Proc. Auto Carto 12. ACSM/ASPRS, 147-156.
Otoo, E.J. and Zhu, H., 1993, Indexing on spherical Surfaces using semi-quadcodes.
Advances in Spatial Databases. Proc. 3rd Int. Symp. SSD'93, Singapore, 510-529.
Samet, H., 1990a, The Design and Analysis of Spatial Data Structures. Reading MA:
Samet, H., 1990b, Applications of Spatial Data Structures: Computer Graphics, Image
Processing and GIS. Reading MA: Addison-Wesley.