Working through the scales
A Global, Regular, Hierarchical Spatial Data Model
Download 2.64 Mb.
|
- Navigate this page:
- 2.2.1 Local and Global Properties
2.2 A Global, Regular, Hierarchical Spatial Data ModelIn place of latitudes, longitudes and metadata, we propose a notation for location that documents its own precision, one which can model spatial and scale relationships as well as denoting positions. Data in this form can be derived from coordinates plus scale or accuracy information, and is thus compatible with existing digital georeferenced data. Once so encoded, positions can be retrieved at a wide range of precision, i.e. at specific scales or resolutions. Locations neighboring a given one can be directly identified at any resolution. Every point on the planet has its own unique hierarchical geocode, accurate to the extent its location can or needs to be measured. Our notation uses integer identifiers rather than floating-point coordinates, and at first sight do not appear to be coordinates at all. But they directly denote position, and do so at multiple, nested resolutions. This is why we refer to it as a hierarchical coordinate system, the form and orientation of which is described by figures 2.2 and 2.3 
Figure 2.2: Quaternary Triangular Mesh to Three Levels of Detail These properties are achieved through the use of a geometric computational model that, starting with an octahedron we imagine to be embedded in the Earth, subdivides its eight faces into four each, proceeding to recursively subdivide each of the 32 resulting triangular facets (also called quadrants) into four children. The basic geometry and topology of this hierarchical model are illustrated in figure 2.3. While all facets can be subdivided in the same way, in practice this is not done everywhere, but only where one has point positions to encode. Each such location is identified by a sequence of quaternary digits (from 0 to 3), having as many places as the number of times facets were divided in representing that point. We call each of these places a level, as it is equivalent to a certain level of spatial resolution. Our implementation allows for 29 levels of detail (in a 64-bit word), corresponding to about 2 cm of ground resolution, or to maps at a scale of 1:50 or larger. This should suffice for nearly all cartographic and analytic purposes. 
Figure 2.3: Form and orientation of the Quaternary Triangular Mesh Detailed images of this structure are difficult to render properly, due to the great number of subdivisions that quickly accumulate. But many of its hierarchical properties are readily summarized numerically; table 2.1 presents the major ones. In that table, the third column refers to the number of subdivisions in an octant (an eighth of the earth); the Linear Divisions column likewise specifies how many times an octant’s edges are subdivided at each level. Dividing that number into one quarter of the earth’s circumference (10,000 km) yields the average length of a facet edge, labelled Linear Extent. Since these lengths do vary (by up to 35%, as section 3.1.1 shows) they are presented as round numbers and scaled to be easier to comprehend. The last two columns present a loose equivalence between spatial resolution and map scale. This correspondence is based on an (arguable) assumption that the positions of points on a printed map are accurate to within 0.4 mm (Tobler 1988). This exceeds U.S. national map accuracy standards (see section 1.3), but is still coarser than some line weights on topographic maps. The Scale Denominator is computed by dividing Linear Extent (in mm) by 0.4 mm. Simplifying further, this is rounded to a whole number in the Standard Scales column.
Table 2.1: Quaternary triangular mesh statistics for 30 levels of geometric detail As space is recursively subdivided into four nearly similar units, we have, computationally speaking, a quadtree, or quaternary division of space. More precisely, they form a forest of eight region quadtrees, one for each octahedral face, or octant. Region quadtrees are but one of numerous variants of hierarchical space partitioning systems, but are perhaps the most widely used of them. In our approach, however, as vertices (point locations) are encoded (as opposed to line elements or polygons), we could also call the data structure a point quadtree. In Samet’s semi-official terminology, we could call our storage mechanism a PR Quadtree (P for point, R for region), as each leaf node is a region that is occupied by one and only one vertex (Samet 1990: 92).6 Further-more, rather than a rectangular division of space (which quadtrees almost always employ), we use a three-axis system; it is triangles (starting with a set of eight) that subdivide into four each. The edges of these triangles are aligned in a finite three-way mesh that extends around the planet and densifies where precision goes up. Hence the model’s name, Quaternary Triangular Mesh, or QTM7 for short. 2.2.1 Local and Global PropertiesWe orient the octahedron to the Earth by aligning its vertices with cardinal points — to the poles and at longitudes 0, 90, 180 and -90 degrees along the equator — and number the octants from 1 to 8, as defined by table 2.2. The triangular subdivisions of octants are identified by adding a quaternary digit (0, 1, 2 or 3) to a series of them built up in the course of fixing a location. Upon reaching a point's limit of precision the process stops, and the sequence of digits becomes the QTM address (a quadtree leaf node which we denote as QTM ID) of that point. Address digits are assigned to quadrants according to a method that always numbers the central one 0, but permutes the other three identifiers at each level. This method results in grouping six 1's, 2's or 3's around every grid node, reflected in the last digit of facets’ QTM IDs.8 An octahedron has three axes that connect poles, and three orthogonal “equators.” Our way of coding its facets yields 429 (2.88230...E17) child facets. Every facet is defined by three mesh nodes at which (with six exceptions) six facets meet. When a node lies on the edge of an octant, three of its incident facets lie in one octant's quadtree; the other three are stored in an adjoining one. A similar relation holds true for any node, not just those along the edges of octants; facets incident at a node are cousins, not siblings, and relating objects that span them can be awkward in quadtrees. Because they relate quadrants in different trees and sub-trees, nodes play a critical role in the QTM framework, and are important enough to warrant the special name Attractor.9 For many purposes, attractors are as important for retrieving locational data as QTM addresses are for encoding them. Properties and uses of attractors will be examined in detail in following chapters. Octant Minimum Maximum Minimum Maximum ID Longitude Longitude Latitude Latitude 1 0 < 90 > 0 90 2 90 <180 > 0 90 3 180 <270 > 0 90 4 270 <360 > 0 90 5 0 < 90 -90 0 6 90 <180 -90 0 7 180 <270 -90 0 8 270 <360 -90 0 Table 2.2: Orientation of the QTM basis octahedron to the earth In describing QTM, we have so far stressed its global properties, as these are what qualify it as a (hierarchical) coordinate system suitable for encoding geographic data. Based on this overview, some readers might assume that QTM is only intended to handle geospatial data which spans the globe, such as world climatalogical, bioregional or demographic statistics. In the large, QTM can certainly support such world-wide applications, but only because it also works in the small, and throughout a range of scales. In this project we have deliberately focused on the small end of this continuum, but not simply to avoid grappling with global datasets, which would tax our processing platforms without adding much explanatory value; we have done this to explore essential details of hierarchical data handling that are critical to understand, regardless of the scope of one’s spatial data and their application. Directory: papers papers -> From Warfighters to Crimefighters: The Origins of Domestic Police Militarization papers -> The Tragedy of Overfishing and Possible Solutions Stephanie Bellotti papers -> Prospects for Basic Income in Developing Countries: a comparative Analysis of Welfare Regimes in the South papers -> Weather regime transitions and the interannual variability of the North Atlantic Oscillation. Part I: a likely connection papers -> Fast Truncated Multiplication for Cryptographic Applications papers -> Reflections on the Industrial Revolution in Britain: William Blake and J. M. W. Turner papers -> This is the first tpb on this product papers -> Basic aspects of hurricanes for technology faculty in the United States papers -> Title Software based Remote Attestation: measuring integrity of user applications and kernels Authors Download 2.64 Mb. Share with your friends:
|