Looking Back and Ahead: The Triangulated Irregular Network (TIN)
Current applications in GI have evolved from several efforts and research
around the world. Many date back in time, and today, they continue to affect many common GI applications. The triangulated irregular network (TIN) is one of those developments. GeoInformatics recently spoke to those involved with TIN 30 years ago, querying them about TIN. We also gathered their personal reflections on its importance now and into the future. Several researchers have previously documented the history of TIN. In this article we will look at TIN, how it came about and what the considerations
were, in the minds of those people involved - almost 30 years ago and how it relates to the present and future.
By Jeff Thurston, Editor
Who We Interviewed
Dr. Thomas Poiker (then Peucker) - leader of the first group known to describe TIN;
Professor, Simon Fraser University (SFU), Vancouver, Canada; now Director of the
UNIGIS program at SFU.
Dr. David Mark - then in undergraduate studies with Tom Poiker, finishing in 1970 and during 1974-1977 he was a PhD student back at Simon Fraser; now Professor and NCGIA Director at the University of Buffalo, New York.
Dr. Jim Little - then research associate in the TIN project moving from Harvard to SFU as research associate on TIN with Poiker; Professor, University of British Columbia, Vancouver, Canada.
Dr. Robert Fowler – then research associate in the TIN project moving from Harvard to SFU as research associate on TIN with Poiker; currently a researcher in high performance computing at Rice University.
Dr. Randolph Franklin - then a summer student involved in the TIN project during 1973 - creator of TIN 73, believed first computer coding for TIN; then an undergraduate at the U. of Ottawa working with David Douglas; now Professor at Rensselaer Polytechnic Institute, Troy, New York.
How TIN Originated
In the early 1960's, researchers had been working on various methods to describe and store topology for landscape surfaces - or digital elevation models (DEM). The triangulated irregular network is a method for describing surfaces and representing terrain at a lower need of storage space than the regular grid that was the only storage technique at the time (the early 70s). Most of those involved the use of grids, which are still used today and can be found in many GIS applications. Grids provide a method for use and storage whereby landscape surfaces are divided into uniform units of equal dimension.
As David Mark explains, at that time, "the idea was to 'capture' the nature of the terrain, the geometry of earth elevation surfaces, as efficiently as possible, i.e., with as few bits as possible. Because computers were so limited then and RAM ("core memory") and other storage was too limited and expensive, there was a big premium on efficiency, and regular grids seemed very inefficient."
The concept of grids as structures for terrain data was therefore in the minds of researchers at that time. Tom Poiker states, "I had developed (programmed) a view shed program for a student of ours and I showed some results to the Geography person at the Office of Naval Research in Washington, DC. She liked it and said that she wanted to support the research. So I said that I wouldn't just write another program, there had to be some "theory" and right there, I think, I got the idea of the triangles. I think I thought of the triangle because I wanted to get away from the regular grid and do something that could adopt to irregular terrain."
At that time, as compared to what we see in current day GIS, software in terms of topological structures did not exist. Scientists, then, were heading into a new field of discovery, that of topological structures for irregular terrain representation. Poiker indicates, "This was the time when topology was waiting at the door. Nick Chrisman [Editors Note: currently Professor, University of Washington and developer of POLYVRT structure for planar polygon maps] applied it to polygon structures and we hit it off when we met at Harvard University."
David Mark adds to this, "Tom Poiker invented the idea of TIN with explicit topology. Tom had some material from a person in Germany named Hormann who had measured terrain geometry using triangles and also some material from Germany on contouring using triangles. But these did not have the topology, the neighbor relations stored explicitly with pointers." Fowler points out, “The equivalent notions of Voronoi diagrams, Delaunay triangulations, and Thiessen polygons had been around since the early 1900's. The computer graphics community had been using sheets of triangles to model complex surfaces for several years.”
Franklin says, "We need ways to represent, compress, and operate on, surfaces. The TIN is one major method. Another is a simple matrix of elevations. The TIN can adapt to surface regions of varying complexity, and is not tied to a particular coordinate system. However it is more complex, which means that it is harder to implement. Also, for a given resolution, unless sophisticated data structures are used, it may take more space than a lossily compressed elevation matrix."
Today many GIS users are able to provide modeled terrains quickly and easily and these often take on photo-realistic appearances. A distinction is made between what TIN is and that should not be confused with visualization as Fowler says, “we embraced the strategy of starting with a set of necessary features (ridges, water courses, passes, other points/lines with "interesting" curvature, and point stations) and then adaptively augmenting the triangulation until the modeled surface was "good enough" according to some error criterion. In contrast, the main stream
computer graphics groups of the days were using many more triangles in a more brute force approach, for example, by creating fixed width slices of objects and triangulating the regions between the resulting contour lines.”
In science as in all endeavors where breakthroughs and unique achievements occur, both timing and place play an important role - just as in geography and GI itself. By now a group of interesting, knowledgeable and passionate scientists had converged and supported with funding from the U.S. Office of Naval Research. If there were ever a group of people that came together at a converging moment in GI time and history, to work together, it would include the TIN Group at Simon Fraser University during the 1970's.
Choosing the Name and Beginning
Along with Poiker, Mark, Little and Franklin was Rob Fowler and as Poiker reflects, "originally I wanted to call it "Independent Data of Irregularly Oriented Terrain" - IDIOT and asked Rob Fowler and Jim Little to join the group. Rob accepted the offer to work at Simon Fraser under the condition that I changed the project name. I made this the first order of business when he arrived, and that is how the triangulated irregular network (TIN) name came about (Fig. 1)."
During this time, Randolph Franklin, a computer scientist and mathematician, who later went on to be awarded the National Science Foundation Presidential Young Investigator Award, working with the group in Vancouver, set about to develop TIN 73. This was the computer code used to derive a TIN surface - one of the first such programs known along with those of German surveyors Dueppe and Gottschalk. Franklin detailed design, implementation, and performed testing.
At this point TIN was born in application, and as David Mark says, "being topological, with triangles as polygons, it led to the first integration of elevation data into ESRI's Arc/INFO, which before that was just 2-D polygonal maps. And ESRI hired Armando Guevara from Buffalo in 1983, and he was part of the team together with Swiss geographer Martin Heller tasked at ESRI with adding surfaces, and they chose TINs. Later, ESRI and other vendors integrated grids with polygons, and the problem became less important as TIN continued to be used.
Looking back at that time Franklin adds, "Higher degree triangular approximations were used by Paul de Casteljau at Citroen on or after 1959. However, his work was proprietary for years, so Bezier gets more credit for splines, although his are somewhat different." Thus it is apparent that the minds of scientists around the world were conceptualizing surfaces and how to represent them best. That is the nature of scientific research, where sometimes, several people may be working on similar work though largely unknown to each other.
New Frontiers
Discovery is interesting in that it leads to other discoveries that can often transcend original development purposes. In the case of TIN, other international research involves 'hierarchical TIN.' As Franklin explains, "TIN hierarchy is intended more for point location than for surface approximation. That is, suppose you want to know which triangle contains a test point, but there are a lot of triangles. You therefore compute a triangulation with fewer larger triangles. You also determine which small triangles overlap each big triangle. To locate the test point, you first find which big triangle contains it, then just test it against the overlapping small triangles - the application potentially being for varying resolutions, perhaps in flight simulators."
Importance of Science for the Future
Many scientists and non-scientists believe that GI has been largely focused upon technology - or become 'techno-centric' in nature. In part this has been due to the time period over which GI systems, particularly GIS, have grown and matured during their development. Consider TIN for example, developed almost 30 years ago - but not fully matured and deployed into GIS for mass applications until 1980's.
There are other GI technological developments that occurred some time ago such as the global positioning system (GPS) and remote sensing techniques and images, that have not been fully realized to mass production (and application) until very recently for mass use, although GPS and RS can be considered hardware oriented while TIN is software based.
The nature of scientific research as shown above, can be and often is, well ahead of its time. That value cannot be under estimated and clearly plays a significant role in the development, understanding and change within society. Today, GIS and imaging users around the world can acquire spatial information for oceans, cities, forests and the atmosphere - and numerous more. They are quickly able to develop continuous surfaces, using TIN algorithms in modern GI application software and share it with friends locally or via the Internet (Fig. 2).
I asked this group of individuals, "What are some of the prominent applications for TIN in the future do you think?" Their answers coincided and were enlightening. David Mark offered, "The main issues for GIS today I think are institutional issues, use and value, GI and society, and also the ontological issues about the nature of reality, and the cognitive issues of how people relate."
At the same time Tom Poiker states, "TIN should be applied to socio-economic data - as neighborhood relations." While Franklin offers the view, "They have the possibility of being generalized by using curved spline surfaces instead of planar triangles. So far as I know, that has not been investigated because the math is complicated. My personal research agenda includes finding more powerful surface representation techniques to match the physical properties of terrain. I've also studied lossy compression, visibility, etc, applied to elevation matrices.
Conclusion:
The representation of irregular terrain surfaces challenged scientists to develop new methods for their digital representation. One group, located at Simon Fraser University, Canada originated research leading to the discovery of TIN. Several unique individuals were involved in the project, each of who continue to challenge the boundaries of GI research internationally. Their discovery's some 30 year's ago continue to play a significant role in modern GIS software, applications and new theories about time and place, and how reality is represented.
Useful References
Original TIN 73 Source Code
Invention and re-invention of triangulated irregular networks(TINs)
The TIN Model
<Streamers>
In science as in all endeavors where breakthroughs and unique achievements occur, both timing and place play an important role - just as in geography and GI itself.
"The main issues for GIS today I think are institutional issues, use and value, GI and society, and also the ontological issues about the nature of reality, and the cognitive issues of how people relate."
<Figure 1 –tin1jpgf>
Figure 1 - Landscape elevation points.
<Figure 2 –tin2.jpg>