Research in Geoprocessing and Cartography Problems of Interest Hierarchical Coordinate Systems Limitations of Coordinates A Multi-scale Perspective A Global Perspective Online Research Resources   Problems of Interest Although our prior R&D explorations have concerned a diversity of topics, a thread runs through all these efforts, one which we characterize as: Encoding geographic meaning in geodata and expressing it through visualization 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. Geodata are never created without significant errors or omissions, and are imprisoned by time, scale and their original purpose. Whenever geodatasets are released by their creators to users elsewhere, these limitations quickly become apparent, despite (if not because of) accompanying data dictionaries and metadata. When the focus of applications changes, one person's data may often becomes another person's trivia, and the aspects of reality encoded in existing datasets often prove to be inadequate to serve new purposes. Again and again, our research work has struggled with such questions, for example: How can inaccuracy and imprecision of measurements be documented in geodata? How can maps and other visualizations express uncertainty, error or doubt? How can knowledge about qualities of phenomena be encoded and symbolized? How can semantic relationships between spatial entities be represented and respected? Some progress has been made in pursuing these hard questions, both by ourselves and elsewhere. Since we began our studies in the 1970's, a substantial literature on such topics has arisen, and international conferences and symposia concerned with them are now common. New industry, national and international standards for geodata have been proposed and codified to make them more transparent and interoperable. These activites, along with numerous research projects, have brought together earth and computer scientists, cartographers and computer graphics experts, and database architects and philosophers in concerted efforts to encode, discover and express meaning in geodata. However, while such findings are rippling through geoprocessing communities, there has been so far little apparent impact from them on commercial geographic information system technology. We suspect that the main reason for this isn't because GIS vendors want to skirt these issues (which are, after all, central to developing viable standards), rather that the questions they raise are both deep and largely intractable under current paradigms. The importance and dogged persistence of such unsolved problems continues to drive our curiosity and commitment to the field. Global Hierarchical Coordinate System Research Most of our research work during the past ten years has been devoted to developing and proving the feasibility of hierarchical location coding that is not tied to a particular local coordinate reference system. The reasons for and results of doing this are detailed in the following section. Limitations of Coordinates. For about a decade, it has been apparent to us that progress in GIS database design and reusability has been impeded by unquestioning reliance on coordinate tuples to express geographic locations. This at first seems strange: why should relying on (lat,lon) or (x,y) descriptions of positions be problematic? Isn't all GIS, mapping and graphics sofware based on such notations, and do not they all profit by using them? Do not the simplicity and universality of such encodings make GIS data easier to share and use? We think not. A general unconcern for the inadequacy of coordinate data notation does not imply that its consequences should be ignored. Such consequences include: A plethora of coordinate systems and geodetic models that must be reconciled with one another, over and over Positional errors in projected coordinates serving to limit the extents over which they can be applied Differential accuracy from equator to pole in representing latitude-longitude coordinates Edge-of-the-world effects when global projections are relied upon Uniformity of precision for representing floating-point tuples No indication of accuracy of source data No sense of scale of source data To all of this, the GIS community has said "What, me worry?" and then gone on to expend thousands of hours in generating metadata and otherwise documenting the inherent limitations of coordinates in one geospatial data file after another, then countless additional hours attemting to cope with their implications to applications. Is this smart? Is it necessary? A Multi-scale Perspective. Ways to address spatial locations hierarchically have been developed and applied for many years.Quadtrees and their variants, such as octtrees, divide and refine linear dimensions by powers of two, thus quartering spatial domains in the process of homing in on particular places. While quadtrees have limitations -- such as rigid geometries and relatively coarse steps of resolution -- they have many advantages which have failed to be generally appreciated. Here is the general idea: This illustration is an excerpt from a sequence of drawings that describes one form of quadtree. We have also packaged it as an animation to allow it to take up less page space. That animation is in turn part of a dynamic series we call QTM Comix, which describes certain persistent problems in geographic data handling and how they are addressed by hierarchical spatial data modeling. The approach we have taken to representing locations hierarchically is neither "vector" nor "raster"; it can be -- and has been -- applied to both "space-primary" and "object-primary" data models. Our work on implementing these concepts, however, has been focused on manipulating vector data (points, lines, polygons), primarily to investigate map generalization techniques. A Global Perspective. In addition to being hierarchical, our approach models the Earth as a whole rather than limited portions of it, as zone- and map sheet-based coordinate systems do. Thus we do not have to contend with horizontal datums, projection distortions, map sheet boundaries. This is because we encode positions given in latitude and longitude directly, and decode back to geographic coordinates as desired. The decoded coordinates can then be projected as required by applications in conventional ways. Working directly on the globe, it is problematic to decompose space hierarchically into rectangular quadrants, so we build quadtrees out of triangles. While it would be possible to directly decompose the globe into four spherical triangles (thus modeling a tetrahedron), we have chosen to start with eight triangular quadtrees, each one developed from a face of an imaginary octahedron aligned to the poles and equator. This structure is more easily understood once visualized. Here it is shown developed to three levels of detail: By continuing to recursively subdivide the sphere in this manner, any geographic location can be encoded to a level of precision that expresses its known or presumed accuracy. The spatial resolution of the triangulat quadrants halves at each level, such that 10 levels yields 10 km resolution, 20 levels provide 10 m resolution and at 30 levels resolution is about 1 cm. As each parent triangle decomposes into four, we have named this structure quaternary triangular mesh, or QTM. Specifically, we are describing an octahedral quaternary triangular mesh. A somewhat longer summary of QTM (eight linked pages) is available that also illustrates its application to map generalization. You may also wish to visit QTM Comix, which explains the approach using animated panels. Several papers (in some cases not final versions) that have appeared in conference proceedings and journals are also available as PDF files. Online Research Resources QTM2: The QTM Quick Tour Magazine (8 pages) ... an overview of hierarchical coordinates and how QTM is structured, concluding with its use in map generalization QTM Comix ... An animated "comic strip" explaining why hierarchical coordinates are needed and how they work on the globe. Click on any panel to see a story. Visualizing Map Generalization Solutions on the World Wide Web ... A multi-part HTML document with figures and animations illustrating the application of QTM to line generalization. Geoffrey Dutton's Ph.D. Dissertation, A Hierarchical Coordinate System for Geoprocessing and Cartography, published by Springer-Verlag in 1998, and summarized here. The Spatial Effects HyperGlossary, which defines many geospatial terms used here and elsewhere. A selection of research papers with abstracts, as well as ascii files of coastline data used in doctoral research, that you may download. All papers are in Adobe PDF format. Home