Proceedings, GIS/LIS'97, in press.

THE HISTORY OF GEOGRAPHIC INFORMATION SYSTEMS: INVENTION AND RE-INVENTION OF TRIANGULATED IRREGULAR NETWORKS (TINs)

David M. Mark
NCGIA, Department of Geography
University at Buffalo
Buffalo, NY 14261-0023
dmark@geog.buffalo.edu
http://www.geog.buffalo.edu/~dmark/

Abstract

The history of technical innovation in GIS appears to have many cases of real or apparent multiple discovery. This paper reports on the history of the invention and reinvention of Triangulated Irregular Networks (TINs) as structures for representing topographic surfaces. Data for the paper has been obtained from in-depth interviews with key innovators, as well as the literature. Triangles were used as a basis for drawing contours from irregularly distributed data points as early as 1964, but contouring solved as a two-dimensional geometric problem. Triangles were used for topography in geomorphometry in 1969, but triangles were analyzed individually. The first known TIN as a topologically-integrated triangulation, thought of as the upper surface of a three-dimensional solid, was described by Thomas K. Poiker (then spelled 'Peucker') in 1973. By 1975, the TIN model was well established and several articles had been published. However, triangulated structures were independently invented in 1973 by an environmental consulting firm for representing elevations and other attributes, and around 1975-76 by a geologist, for representing underground geological surfaces. TIN was a key element in the topological revolution in GIS.

1. Introduction

The history of scientific and technical innovation includes many cases of real or apparent multiple discovery or invention (Lamb and Easton, 1984). GIS is no exception, and documentation of the thought processes and experiences leading up to innovations in as much detail as possible will help to identify common sparks or inspirations, or to confirm truly independent discoveries. This paper reports on the history of the invention and reinvention of Triangulated Irregular Networks (TINs) as structures for representing topographic surfaces. Data for the paper were obtained from in-depth interviews with key innovators, as well as the literature. This research is part of The GIS History Project, which is attempting to trace and document the history of this technology, and to conduct a critical examination of developments in their social, institutional, and technological context (http://www.geog.buffalo.edu/ ncgia/gishist). This paper provides an early summary of innovation in the TIN case study, and documents some aspects of the technical and institutional environments surrounding these developments.

2. TIN-0: Precursors

Digital elevation models are important to a number of military and engineering applications, and thus were one of the earliest areas of digital geographic information to receive research attention and funding. In the 1960s, regular grids were the conventional method for storing topography in computers. The main alternative available at that time was digitized contours, but it was becoming clear that contours, the most effective method to store and retrieve precise elevation data on paper maps, were not an effective base for storing and analyzing topography on computers. The main reason is that the topological relations or nesting of the contours is visually obvious on graphic diagrams, but difficult to store and manipulate on computers (see Mark, 1978a, 1979). A paper by Boehm (1967) was seminal work comparing different methods for terrain storage, concentrating on grids and digitized contours.

As early as 1964, triangles were used as a basis for drawing contours or other isolines through irregularly distributed data points in two-dimensional spaces (Bengtsson and Nordbeck, 1964). According to Davis (1975) IBM was using a triangle-based approach to contouring in 1965, which Davis said could "simulate the process of manual contouring" (IBM, 1965). Davis (1975) further commented that triangulation is "the most obvious computer contouring approach." Similarly, Gold (personal communication) reported that, as of 1970, there was at least one other commercial contouring system using triangles, developed for the oil industry (SCA, 1970). Such triangle-based contouring itself seems to have been multiply 'invented,' but appears to have been solved as a purely two-dimensional geometric problem--apparently, the triangles were not thought of as representing a 3-dimensional, or 2.5 dimensional, surface. The first known use of triangles to explicitly represent such a surface was in 1969, when German geomorphologist K. Hormann proposed a system of triangles could be used to represent topographic surfaces for geomorphological analysis (Hormann, 1969, 1971); however, Hormann's triangles were not connected topologically, but were analyzed separately and the results summed.

3. TIN-1: Poiker's ONR Project

The first known published description of a TIN as a topologically-integrated triangulation thought of as the upper surface of a three-dimensional solid was described by Thomas K. Poiker (formerly 'Peucker') in 1973, in the first-year report of a project funded by the US Office of Naval Research. Poiker's development of this structure had many earlier antecedents. An important step in his thinking is shown in his essay, "Some thoughts on optimal mapping and coding of surfaces," in which he proposed to represent terrain by an irregularly distributed set of "surface-specific" points such as peaks and saddle points, that would have higher information content per point and thus might require less total data storage space and processing time (Peucker, 1969). However, the story of the actual invention of TIN appears to have begun early in 1971, when Poiker wrote an intervisibility program for William Wolferstan, a graduate student at Simon Fraser University, to use in his research on coastal tourism (Poiker, personal electronic communication, October 1996). Poiker used regular grids of elevations as the data structure in that program, although he was apparently aware of Bengtsson and Nordbeck's (1964) contouring by triangulation approach, since Poiker cited their work in his 1972 AAG monograph, "Computer Cartography" (Peucker, 1972).

Early in 1972, Poiker was visiting the University of Maryland, and a government employee named Bob Mercready, whom Poiker had met earlier at the Harvard Laboratory for Computer Graphics and Spatial Analysis, arranged for Poiker to have lunch with Evelyn Pruitt, geography program officer at the US Office of Naval Research (Poiker interview, March 18, 1997). Poiker showed her his visibility maps, and Pruitt apparently expressed interest in funding further research on the topic. Poiker was unhappy with grid DEMs, having read Boehm's (1967) paper, and felt there must be a way to combine the advantages of regular grids and contours. He also reported that he did not want to get a grant simply to re-do something he had already done, but would prefer to use a grant as an opportunity to do something innovative. In a March 1997 interview, Poiker reported that the idea to use triangles actually occurred to him during that lunch with Evelyn Pruitt:

"I wanted to do this differently, and that's when the triangle came up, right at that lunch. So, it [the TIN idea] must have been there, it must have been just waiting" (Poiker, interview, March 1997).

Poiker wrote a proposal and received ONR funding later that year (1972) to develop TIN. The TIN idea was well developed in the first year report of that grant, submitted to ONR in December 1973 (Peucker et al., 1973). By 1975, the TIN model was well established and several articles had been published (Mark, 1975; Peucker and Chrisman, 1975). Complete summaries of this TIN project also were published (Peucker et al., 1978, 1979). A paper by Peucker and Chrisman (1975) was a landmark in the maturation of topological data structures for GIS, since that paper outlined both the TIN structure and the POLYVRT structure for planar polygon maps. Being academics, Poiker and his colleagues published early and often, and thus their version of TIN became the best known in academic circles. The fact that it indeed seems to have been the earliest incarnation of a topological TIN structure is almost a coincidence, since if the following, slightly later TIN projects had happened a year or two earlier than they did, they probably would not have been know to academics until long after Poiker's version of TIN had been established.

4. TIN-2: ADAPT

A second invention of TIN as a topological data structure for topography happened in a private sector environment. On May 3, 1973, programmers at Engineering-Science, a consulting firm based in northern Virginia, came up with the idea of representing topography by using triangles in an application involving planning of sewer lines (Grayman, 1997). This key idea became ADAPT (Areal Design and Planning Tool), a triangle-based GIS that used triangle vertices for elevations and triangle faces to carry other attributes (Grayman et al., 1975; Males, 1978). According to Grayman, the key innovation was suggested in an evening session of an all day 'brain-storming' meeting led by William E. Gates, looking for alternatives to regular grid-based digital elevation models. "Several of the participants had experience in the surveying field and someone suggested that since three points define a plane, that a triangular based system was obviously the best way to store topographical information" (Grayman, 1997). In December 1973, W. E. Gates left Engineering-Science to form his own firm, and Grayman, Males, and the ADAPT system moved with him to the new company. Males (email, 2 June 1997) states that none of the development team knew about other TIN projects at the time that ADAPT was being developed; they only learned about Poiker's TIN project during visits to the Harvard Lab later in the 1970s.

5. TIN-3: Gold's TINs

A triangulated structure was independently invented by geologist Christopher Gold around 1975-76 for representing underground geological surfaces. In email to David Mark on October 25, 1996, Gold told his recollections of how he came up with the TIN idea. His dissertation involved attempting to "reconstruct the subsurface glacial stratigraphy of the Cold Lake area, from bore-hole data." The distribution of his data points was very uneven, yet he needed and interpolation of surface reconstruction method that would exactly 'honor' all the data points. In the early 1970s, he was not able to locate a ready-made program capable of doing a good job with data and objects of the type that he had. He stated:

"I can still remember working at home with this one evening, and remarking to [my wife] that what was needed was a structure that was adaptive to the data distribution. Such as a set of triangles. Little did I know!" (Gold, email, October 5, 1996).

Gold began implementing a triangle-based approach, and struggled with various aspects of it. He eventually came up with a solution quite different from those of Poiker's group or ADAPT: he (re)-invented methods for producing a smooth surface across triangle boundaries, whereas both of the other groups used linear interpolation within triangles, leaving breaks of slope along most triangle edges.

Gold was not able to recall exactly when he came up with the triangle idea, but the innovation presumably happened in the period 1972-1975. Gold first presented the methods publicly in May 1976, first at a University of Alberta symposium and later that month at to a Geological Association of Canada conference. The next year, he had a paper on his method accepted for the 1977 SIGGRAPH meeting (Gold et al., 1977), and through submission of that paper, began correspondence with Thomas Poiker and his TIN group. That connection led Gold to present a paper in the fall of 1977 to the First International Advanced Study Symposium on Topological Data Structures for Geographic Information Systems organized by Harvard in October 1977 (Gold, 1978). That was a pivotal meeting for the maturation of TIN and the conceptual integration of the three main projects, as Richard Males also gave a paper there on TINs (Males, 1978), as did several members of Poiker's ONR-funded research group (Little, 1978; Mark, 1978b; Peucker, 1978).

6. Discussion

6.1 Multiple Invention?

TIN appears to be a case of genuine multiple invention. It seems clear that none of the three groups discussed in this paper was aware of any of the others when coming up with the idea of using triangles to represent topographic surfaces. There are no particular common key papers or talks that provided inspiration. However, both Poiker and Gold were aware of triangle-based contouring programs, and both Poiker and the ADAPT group make reference to triangles as being the way surveyors conceptualize terrain. All also were influenced to varying degrees by the unfavorable trade-off between resolution and data volume inherent in regular grids, and were looking for more efficient ways to attain needed accuracy and resolution in critical areas.

Two themes have recurred in accounts of the invention of TINs. One involves early triangle-based contouring programs, and another is based on the idea that triangles are the 'natural' way for a surveyor to think of topography. Each of these will be discussed briefly in the following sections.

6.2 Triangles in the Plane vs. A Triangulated Surface

In his monograph comparing TINs and gridded DEMs, Kumler begins his discussion of the origins of TIN with a reference to Bengtsson and Nordbeck's 1964 paper on contouring using triangles (Kumler, 1994). But, how important were these contouring programs? A key question is whether a triangle-based program to draw isolines actually involves a 3-dimensional, or 2.5 dimensional representation or data model. Did the programmers think of the data as a surface? We will have to ask, if we can find them. However, the author's intuition says that drawing contours or isolines through and around a set of irregularly distributed points in the plane is not a 3-dimensional problem, but is commonly approached as a strictly 2-dimensional problem. When doing this by hand and eye, one identifies pairs of nearby points that straddle the isoline one is drawing, and then use linear interpolation along the imaginary line joining those points, to position the isoline. The mental process is very similar to drawing bisectors, or constructing Thiessen polygons. No sloping surfaces or hills or valleys are visualized.

Results of an informal survey posted to some relevant electronic news groups appear to confirm the author's suspicions. Correspondents described in considerable detail the process of interpolating along straight lines between neighboring points, and did not mention 3-D visualization. If the triangle-based contouring programs of the 1960s were developed and used along similar lines, then the leap to topological triangles forming surfaces to bound a solid may have been a greater innovation that it is given credit for today.

6.3 Surveyors Use Triangles

There is a belief among some GISers that surveyors think of topography as a set of triangular planar facets. This belief was widely held in Poiker's ONR project at Simon Fraser University, as reflected in Poiker's recent interview comments:

"you've got to realize that the triangle is something that's... there are a lot of people outside who would immediately think of triangles, because that's they way surveyors measure terrain, and a lot of people think in these terms. I think what we did was we added topology to it." (Poiker, interview, March 1997)

This author contributed to the dissemination of that idea. In a paper on conceptual views of topography and their reflection in data models for elevation data, I stated:

The surveyor's approach involves a polyhedral solid which approximates the terrain, and adapts in density to the complexity of the topography. This view can be accommodated by the 'triangulated irregular network' (TIN) approach" (Mark, 1978a, p. 28)

Surveyors certainly triangulate. But do they really think of triangular facets approximating the terrain surface? Twenty years later, my intuition on this had changed, and so I asked some surveying engineering professors, and again posted a query on Usenet. The academics were unanimous in saying that surveyors use triangulation only to fix locations in the two-dimensional plane. Elevations are determined independently of the triangulation. Furthermore, since triangle edges traditionally have been sight lines for instruments, they must lie entirely above the surface, rather than approximating it! And furthermore, the triangles need not even form a tessellation--they can overlap or have gaps, as long as each surveyed point is tied to control points by a set of triangles. An analogy is to a stick figure, all of whose points sit on the terrain, but whose sticks must stay above the terrain.

"Stick figures only, from my experience. The line-of-sight notion in these triangles is so strong, that I have never thought myself about the plane, although we always point out how closely related the concept is to DTMs" (Email from a survey science academic, May 30 1997)

Surprisingly, the word from practicing land surveyors was quite different. Practice in the late 1990s seems to be to survey terrain by selecting points in the field based on the field worker's knowledge of the software that will be used to interpolate, model, and contour later! If the above views from surveyors trained at a much earlier time are true, the existence of the TIN model seems to have changed field practice in topographic surveying! And the effect of the change is to bring field survey practice and the data model much closer together than we suspect they were in the early 1970s. Apparently, in this case, life imitates art, or at least, life imitates software. This makes the idea that surveying practice inspired TINs in the early 1970s even more interesting, and worthy of further study.

6.4 Conclusions and Future Work

The TIN data model as a basis for computerized storage, retrieval, and analysis of topography, appears to have been independently invented in North America at least three times in the early 1970s. The environments for the TIN innovation were very different. One was in an academic geography department by a cartographer with a geography background; one was by engineers working on environmental consulting in the private sector; and one was by a geologist working in academia on data that did not readily fit existing programs. There were few common factors, except a dissatisfaction with existing data models and software, especially regular square gridded digital elevation models. Use of triangles in surveying (two cases) or finite elements calculations (one case) may have been factors contributing to the innovation, as may have been programs to draw isolines in the plane based on a triangulation of control points. Academic conferences eventually provided a forum for exchange of ideas among the three groups and others, and by the end of the 1970s, a single unified TIN model was a standard way to represent topography in GIS and other software.

This paper has dealt very little with institutional and societal factors in these three projects. Poiker's project was funded by the Office of Naval Research, a part of US Department of Defense, at a Canadian University, beginning in 1972, a time of campus unrest and anti-War and anti-US sentiment among many Canadian university students. The political context of the funding source, and any influence that DoD funding may have had on the project, must be investigated further. The other two projects appear to have been carried out in less politicized contexts, related to non-military applications. The entire social and political context of the invention of TIN will require critical examination as part of placing GIS technology in general in its societal and historical context.

The fact that, within a few years in the early 1970s, at least 3 groups came up with the same solution probably means that triangles were an obvious, natural, and practical way to represent topography. This must emerge from some combination of the characteristics of topography, of early 1970s computing, and of human cognition and society. Why then was TIN not invented about a decade earlier? Perhaps computing environments were unfavorable, or perhaps alternative approaches such as grids had to be developed for some minimum period of time that would allow the need for something different to become evident. Future work will attempt to address this question, as well as the others raised above, both for TIN and for other elements of GIS

7. Acknowledgments

I am especially grateful to Thomas Poiker, Richard Males, Christopher Gold, and Walter Grayman for consenting to be interviewed by electronic mail and (in Poiker's case) in person, and providing with with their memories and insights regarding the early days of their TIN projects. Discussions with other members of the GIS History Project have influenced my approach to this research, and also are acknowledged. This paper is part of The GIS History Project (http://www.geog.buffalo.edu/ ncgia/gishist), which in turn is part of Initiative 19, The Social Implications of How People, Space, and Environment are Represented in GIS, of the National Center for Geographic Information and Analysis (NCGIA). Initial stages of the project have been funded by the NCGIA's NSF grant, SBR-8810917; support from NCGIA and NSF is gratefully acknowledged.

8. Literature Cited

Bengtsson, B.-E., and Nordbeck, S., 1964, Construction of isarithmic maps by computers. B. I. T. v. 4, no. 2, pp. 87-105

Boehm, B. W., 1967, Tabular representation of multivariate functions with application to topographic modeling. Proceedings, 22nd National Conference, Association for Computing Machinery, pp. 403-415.

Davis, J., 1975, Contouring Algorithms. Proceedings, Auto Carto II, pp. 352-359.

Gold, C. M., 1978, The practical generation and use of geographic triangular element data structures. Harvard Papers on Geographic Information Systems, v. 5.

Gold, C. M., Charters, T., and Ramsden, J., 1977, Automated contour mapping using triangular element data structures and an interpolant over each triangular domain. Proceedings, SIGGRAPH '77, San Jose, California.

Grayman, W. M., 1997. A Brief History of ADAPT. Unpublished electronic manuscript sent by email to David Mark, 2 June 1997.

Grayman, W. M., Males, R. M., Gates, W. E., and Hadder, A. W., 1975. Land-based modeling system for water quality management studies. Journal of the Hydraulics Division, ASCE, v. 101, pp. 567-580.

Hormann, K., 1969, Geomorphologische Kartenanalyse mit Hilfe elektronischer Rechenanlagen. Zeitschrift fur Geomorphologie, 13, 75-98.

Hormann, K., 1971, Morphometrie der Erdoberflache. Kiel. 179 pp.

IBM, 1965, Numerical surface techniques and contour map plotting. IBM Data Processing Applications, White Plains, NY, 36 pp

Kumler, M. P., 1994. An intensive comparison of triangulated irregular networks (TINs) and digital elevation models (DEMs). Monograph 45, Cartographica, V. 31 (2), pp. 1-99

Lamb, D., and Easton, S. M., 1984. Multiple Discovery: The Pattern of Scientific Progress. Avebury, England: Avebury Publishing Company.

Little, J. J., 1978, Strategies for interfacing geographic information systems. Harvard Papers on Geographic Information Systems, v. 5.

Males, R. M., 1978, ADAPT-- A spatial data structure for use with planning and design models. Harvard Papers on Geographic Information Systems, v. 3.

Mark, D. M., 1975, Computer analysis of topography: a comparison of terrain storage methods. Geografiska Annaler, 57A, 179-88.

Mark, D. M., 1978a. Concepts of "data structure" for digital elevation models. Proceedings, American Society of Photogrammetry, Digital Terrain Models Symposium, St. Louis, Missouri, May 9-11, 1978, pp. 24-31.

Mark, D. M., 1978b. Topological properties of geographic surfaces: applications in computer cartography. Harvard Papers on Geographic Information Systems, v. 5.

Mark, D. M., 1979. Phenomenon-based data-structuring and digital terrain modelling. Geo-processing, 1, 27-36.

Peucker, T. K., 1969, Some thoughts on optimal mapping and coding of surfaces. Geography and the Properties of Surfaces. Harvard Papers in Theoretical Geography. Number 34, pp. 1-11.

Peucker, T. K., 1972, Computer Cartography. AAG Resource Paper.

Peucker, T. K., 1978, Data structures for digital terrain models: Discussion and comparison. Harvard Papers on Geographic Information Systems, v. 5.

Peucker, T. K., and Chrisman, N., 1975, Cartographic data structures. American Cartographer, v. 2, pp. 55-69.

Peucker, T. K., Fowler, R. J., Little, J. J., and Mark, D. M., 1978, The triangulated irregular network. Proceedings, American Society of Photogrammetry, Digital Terrain Models Symposium, St. Louis, Missouri, May 9-11, 1978, pp. 516-40.

Peucker, T. K., Fowler, R. J., Little, J. J., and Mark, D. M., 1979, The triangulated irregular network. Proceedings, International Symposium on Cartography and Computing: Applications in Health and Environment (Auto Carto 4), Reston, Virginia, November 4-8, 1979, pp. 96- 103.

Peucker, T. K., Mark, D. M., and Pfaltz, J. L., 1973 , Geographic data structures: report after year one. Tech. Rept. #1, ONR Contract N00014-73-C-0109, Department of Geography, Simon Fraser University, Burnaby, Canada, 113 pp.

SCA, 1970, [A commercial contouring system for the oil industry that used triangles.]. Source: C. Gold, personal communication.