\title{Spatial Relationships in GIS -- Geospatial Topology Basics}
\author{Landon Blake}

\maketitle

\section{Introduction}

This article provides the reader with an introduction to geospatial
topology. It is a continuation of the article in the last issue of the
OSGeo Journal, which provided the reader with an introduction to
spatial relationships in GIS. This article is intended for a reader
with a basic knowledge of GIS, and does not cover advanced concepts. To
get the most benefit out of this article the reader should [1]
understand what a {\textquotedblleft}feature{\textquotedblright} is in
the context of a GIS, [2] understand how features are commonly
represented by vector geometry types like points, lines, and polygons,
and [3] have a basic knowledge of geometry and coordinate systems.

\section{What is topology?}

The word {\textquotedblleft}topology{\textquotedblright} has several
different definitions. The \textit{Random House
Webster{\textquotesingle}s College Dictionary} provides one definition
of topology as {\textquotedblleft}the mathematical study of those
properties of geometric forms that remain invariant under certain
transformations, as bending or stretching.{\textquotedblright} \ If you
wanted to translate this definition to a simpler, more common language
you might say that topology is {\textquotedblleft}the study of the
relationships between shapes or geometries that do not change when the
shapes or geometries are subjected to a common transformation or
manipulation.{\textquotedblright} In GIS, topology can be considered a
special type of spatial relationship. It is a spatial relationship that
does not depend on the coordinate geometry of the shapes or geometries
participating in the relationship.

A short example will help us to understand the definition of geospatial
topology. Consider two line segments that intersect one another. You
could apply several transformations to both lines, such as a
translation, rotation, scaling, or warping, and the lines will still
intersect. The fact that the two line segments intersect does not
change if the transformations are applied to both line segments in the
same manner. We also do not need to know anything about the coordinate
geometry of the two lines to understand this particular spatial
relationship. Therefore the intersection of the two lines is a
topological relationship.

This is different from the typical type of spatial relationship that we
discussed in the first article on this topic. As an example, the
interior angle formed by two line segments will change if the two line
segments are warped or stretched. This is an example of a spatial
relationship that is not topological.

\section{Article Scope}
In this article we will deal specifically with the topology that can
exist between features modeled with {\textquotedblleft}vector
geometries{\textquotedblright}. For the purposes of this discussion we
de[FB01?]ne {\textquotedblleft}vector \ geometries{\textquotedblright}
as shapes that can be expressed using distances, angles, or
coordinates. The shape and location of features in a GIS are commonly
described in two dimensions, but may be described in only one
dimension, or in three or more dimensions. In this article we will
concentrate on the topology that can exist between real world
objects represented in only two dimensions. We will only discuss two
types of geospatial topology in this article. The first type will be
containment and adjacency. The second type will be network topology.

\section{Containment \& Adjacency Topology}

The first basic type of geospatial topology that we will discuss is
containment and adjacency. This type of topology considers two similar
types of spatial relationships. The first is that one feature geometry
may contain, or be contained by another feature geometry. The second is
that one feature geometry my be next to, alongside, or adjacent to
another feature geometry.

An example will help us to understand containment and adjacency
topology. Diagram 001 shows a group of polygons that could be used to represent
parcels in a GIS. Consider the containment and adjacency topology
evident in this diagram.

\begin{itemize}
	\item {Parcel 1 is contained by Parcel 3.}
	\item {Parcel 3 contains Parcel 1.}
	\item {Parcel 3 is adjacent to Parcel 2.}
	\item {Parcel 2 is adjacent to Parcel 3.}
	\item {Parcel 4 is not contained by, does not contain, and is not adjacent to Parcel 1, Parcel 2, or Parcel 3.}
\end{itemize}

\begin{figure}[htbp]
	\centering
	\includegraphics[scale=0.2]{topical/blake/diagram_001.png}
	\label{fig:blake_001}
\end{figure}

From this example we can see that containment and adjacency
relationships can usually be expressed in a bi-directional manner.
Thus, if Parcel 1 is contained by Parcel 3, Parcel 3 must by necessity
contain Parcel 1.

\section{Network Topology}

The second basic type of geospatial topology that we will discuss is
known as network topology. Network topology represents the
relationships between segments in a linear network, or a collection of
line segments. (This could be straight line segments, curved lines
segments, or both.) There are 3 basic relationships between line
segments that are important in network topology.

\begin{enumerate}
	\item {The end point of one line segment can connect to the end point of another line segment. This connection is typically called a node.}
	\item {A line segment can intersect a node, but not connect to that node or the line segments joined by that node. (This often takes place when a line segment passes {\textquotedblleft}above{\textquotedblright} or {\textquotedblleft}below{\textquotedblright} a node.  For example, a railroad track might cross over the junction of two streams.)}
	\item {A line segment can intersect another line segment.}
	\item {A line segment can terminate at some point along another line segment.  Typically this termination point is also represented with a node.}
\end{enumerate}

An example will help us understand network topology. Diagram 002 shows 
a group of line segments that could be used to
represent a road network in a GIS. The end point of each line segment
is represented by a node. Each node has been numbered in the diagram
for the purposes of our discussion. Let{\textquotesingle}s consider
some of the network topology that is evident in this diagram.

\begin{figure}[htbp]
	\centering
	\includegraphics[scale=0.2]{topical/blake/diagram_002.png}
	\label{fig:blake_002}
\end{figure}

\begin{enumerate}
	\item {Node \#2 and Node \#4 connect to line segments to one another. Node \#3 connects 3 line segments, while Node \#1, Node \#5, Node \#6, and Node \#9 are present at the end point of line segments, and represent the termination points of the network.}
	\item {The line segment between Node \#8 and Node \#9 crosses over, but does not connect to the line segment between Node \#1 and Node \#2.}
	\item {The line segment between Node \#10 and Node \#11 terminates at a point on the line segment between Node \#8 and Node \#9. This point is represented by Node \#11.}
\end{enumerate}

Relationships in network topology can be expressed in a bi-directional
manner, as the relationships in containment and adjacency topology can.
Thus, if the line segment between Node \#1 and Node \#2 connects to the
line segment between Node \#2 and Node \#3, then the line segment
between Node \#3 and Node \#3 must also connect to the line segment
between Node \#1 and Node \#2.

\section{Practical Application of Geospatial Topology}

What is the practical application of geospatial topology in a GIS? Like
the more basic type of spatial relationships, topology can be used to
aid in spatial analysis. For example, topology can be used to greatly increase
the speed and efficiency of the operations or tasks that must be performed
as part of spatial analysis. But in this article we will consider another practical
application of topology that allows it to be used in situations where
typical spatial relationships just won{\textquotesingle}t do what we
need them to.

Spatial relationships can also be used to a tool for data quality
assurance. This is done by placing g a constraint or a check one a
unique aspect of the spatial relationship between feature geometries.
Geospatial topology allows us to do this in some special ways. It can
be used to verify that the geometries of two or more features
participate in a topological relationship in a way that does not
violate the rules or restrictions set up for that particular
relationship.

Let{\textquotesingle}s consider a couple of examples.

Consider the containment and adjacency topology that was evident in
Diagram 001. In this diagram we see parcels of land or real property
represented by two-dimensional polygons. We discussed how these
polygons can contain other polygons, and how they can also be adjacent
or next to other polygons. When modeling parcels of land, or a
{\textquotedblleft}parcel fabric{\textquotedblright} as it is sometimes
called, it is helpful to set up some basic rules that govern how the
polygons used to represent the parcels can be related when it comes to
containment and adjacency. We typically do not want adjacent parcels to
overlap, nor do we want to have a gap between adjacent parcels. This is
a rule that we can set up and verify using geospatial topology. 

We might also set up a rule about the number of land parcels that can be
contained in any single assessment district. (In this case the tax
assessment district would also be represented by two-dimensional
polygons.) Because we are talking about containment, we can set up a
rule and verify it for this scenario using containment and adjacency
topology.

What about network topology? How can it be used to verify data quality
in a GIS? Consider for a moment a network of sanitary sewage pipes and
the manholes that connect them. What type of rules could we set up for
this type of utility system modeled by a series of straight line
segments and nodes? (A straight line segment would represent a sewer
pipe, while a node or a point would represent a manhole.) We could
define a direction of flow for each manhole and then require the
manhole at one end of a line segment to be represented by a node with
an elevation that is higher or greater than the elevation of the node
representing the manhole at the other end of the line segment. 

We might also have a rule that indicates only line segments belonging to a
sanitary sewer segment can connect to a sewer manhole, and that line
segments representing other types of pipes would not be allowed. We
might also dictate that a pipe leaving a manhole be at least the same
size or bigger than the pipe entering the manhole. All of these things
could be verified by setting up rules that take advantage of network
topology.

\section{Conclusion}

In this article we defined geospatial topology. We took a brief look at
the two main types of topology, containment and adjacency topology and
network topology. We also briefly examined a practical application of
geospatial topology, a tool to ensure data quality in a GIS. 

In a future issue of the OSGeo Journal we will examine how we can use the open
source Java Topology Suite to construct two-dimensional geometries used
to represent features, and then set up constraints on those geometries
to ensure data quality.

\section{References}
The following references were suggested for inclusion in this article:
\vspace{0.2cm}

\noindent "Towards Usable Topological Operators at GIS User Interfaces" Catharina Reidmann\footnote{Reidmann on topology: 
\url{http://www.agile-secretariat.org/Conference/greece2004/papers/8-1-3_Riedemann.pdf}}

\vspace{0.2cm}

\noindent "Simple Features For OLE/COM" Open Geospatial Consortium Inc.\footnote{OGC SF for OLE/COM: 
\url{http://portal.opengeospatial.org/files/?artifact_id=830}}

\vspace{0.2cm}

\noindent "Point-Set Topological Spatial Relations" M. Egenhofer and R. Franzosa
International Journal of Geographic Information Systems


\address{Landon Blake\\
\email{sunburned.surveyor AT gmail.com}
}