Point of Beginning

Surveying GIS

August 1, 2004
In the realm of GIS, at the very core of it all, lies a single concept: topology. What is topology? Technically, and in GIS terms, topology defines the spatial relationships between features. It is the "glue" that holds everything together.

The history of the branch of mathematics called topology can be traced back to the works of 18th Century Swiss mathematician Leonhard Euler. Euler is regarded by many as the most prolific author of mathematics publications in history.

The locus of topology as it pertains to GIS (and surveying) has its origins in an Euler opus titled Solutio problematis ad geometriam situs pertinentis. For those whose Latin may be a bit rusty, in English that would be The Solution of the Geometry of Position Problem. The classic problem discussed in the composition involved the seven bridges in the town of Königsburg (now Kaliningrad, Russia). The challenge was to devise a route through the town of Königsburg where each of the seven bridges was crossed exactly once.

In his paper, Euler proved this was impossible, which begs the question, "What is so significant about proving that something is not possible?" The answer lies not in what Euler proved but how he proved it. Euler recognized that the problem had nothing to do with land or measurement and could be modeled by using arcs and vertices to create a graph.

With this formula he laid the foundation for the graphic solutions regularly employed in modern day mapmaking: A graph has a path traversing each edge exactly once if exactly two vertices have odd degree: v - e + f = 2.

How did we make that long journey from the Königsburg bridges to CAD and GIS? Well, in a lot of small but important steps mirroring the concept itself. Topology, in terms of GIS, not unlike surveying, is based on a set of rules. What Euler theorized was that (at least) one path on a graph exists that travels along each arc exactly once if the graph has no more than two odd numbered sets of arcs.

That "rule" is embedded in the code of all spatially intelligent software. And it is quite similar to the process a surveyor uses to locate a corner position. Most GIS software uses some combination of what is called "Arc-node topology." The vertices (x,y pairs) define the shape of the arc. The end point of each arc is called a node. Every arc has two nodes, a "from node" and a "to node." And arcs only join at nodes. Those are basic topology rules. (But I'll bet you already "node" that.)

Geodatabase topology.
The ability to store these topological relationships efficiently is one of the essential functions of a GIS product. Spatial relationships are depicted using the stored topological relationships. Although this is very similar to CAD products, there are subtle differences. Topology can be stored in a much more efficient manner. That is what allows faster processing of large data sets and provides a more robust environment for model analyses.

In the current generation of object-oriented GIS products, like ArcGIS, topology rules are integrated as a tool set with an associated set of behaviors. And as we can see from the graphic on page 48, the user is presented with a variety of choices and options to construct clean, consistent and solid topology from usable data.

There are three sets of topology rules in ArcGIS: point rules, line rules and polygon rules. The point rules are the simplest. They govern the relationships of points (vertices) to lines (arcs) and polygons. Users have the fewest options for points (four) and the most for lines (12).

It is important to understand how these rules work in building the toplogies because they have a direct effect on the results of subsequent actions that use them. To apply the various rules and edit geodatabase topologies, the full ArcInfo version of ArcGIS is required.

The geodatabase has been discussed before (Surveying GIS, "What's a geodatabase?," POB, April 2003), but it might be prudent to review a few things about it at this juncture. In ArcInfo, topology was stored in the coverage format. Arc features were edited in ArcEdit. Topology rules were invoked using either the "Build" or "Clean" commands. Both of these commands constructed polygons from vector data. "Dangles" and "Opens" (sometimes called "overshoots" and "undershoots") were resolved into completed polygon topology with "Build" or "Clean." "Build" or "Clean" have now evolved into topology rules.

ArcView 3.x introduced the shape file. Shape files were frequently created from coverages, and therefore, included the result of whatever topology was resident in the coverages. But ArcView 3.x could not construct topology per se. (This is also true in ArcView 8.x and 9.x.)

In the geodatabase, we use what is called an object-oriented vector data model. Within this model the feature objects have properties and behaviors. The object-oriented approach gives the user greater flexibility without sacrificing integrity.

In the end, good topology depends on good application of topology rules. In a large part, the quality of the GIS itself is as good as its use of topology rules. c

Note: The author chose to work with one product at a time for such a complex subject. Other products related to topology will be discussed in future issues.