Overview‎ > ‎

Topological Models of GIS

Several different topological models of GIS exist, all using topological concepts to define and distinguish relationships between pairs of geographic areas. We will use a model originally created by Egenhofer and Franzosa in [3] and again described in Section 2.4 of [1]. For a sampling of other, more advanced GIS models, see [4], where the authors analyze the effectiveness of GIS after the usual initial assumption of operation in Euclidean space is dropped, and [5], where the author discusses non-topological models of GIS and the usefulness of adding measures of proximity and direction to a topological model.
 
When using a GIS, the user may want to know when one area is contained within another, when two areas intersect, or perhaps simply when two spaces are adjacent to one another. Topology gives us the tools necessary to answer these types of questions and thus plays a central role in the formation of GIS.
 
Models of GIS are still being perfected, particularly the language used in user interface as GIS builders learn more about how users relate objects and how best to relay that to the computer. As such, the model we present is simply the start of a GIS system.



Definitions


First we look at some definitions necessary to understand the model. All definitions are taken directly from [1] with a few editorial changes. If you need a refresher on any other terms used below, such as an open set or connectedness, grab your old Topology textbook. If you do not have a background in Topology, consider enrolling in the course or getting a book, for, as you will see below, it is an interesting and often useful topic. 

Definition 1

Let A be a subset of a topological space X. The interior of A, denoted Int(A), is the union of all open sets contained in A. The closure of A, denoted Cl(A), is the intersection of all closed sets containing A

Definition 2

Let A be a subset of a topological space X. The boundary of A, denoted 

A, is the set = Cl(A) - Int(A).

Definition 3

For a set Y, define CY = 0 if Y is empty and C­Y = 1 if Y is not empty. Given closed sets A and B, in X, define IA,B, the intersection value for A and B in X, by

            IA,B = (CA∩∂B , CInt(A)Int(B) , C∂A∩Int(B) , CInt(A)∩∂B ).

Since each entry within the intersection value has two possible values, there are 16 total possibilities, that is, there are 16 unique ways in which two closed sets can intersect. A good exercise is to draw an example for each possible intersection value, a few are given below to get you started. In the first example, the boundaries of A and B intersect, the interior of each set intersects the other, and the boundary of each set intersects the other's interior. In the second, the boundary of A does not intersect the interior of B, while in the third the boundaries also do not intersect one another. Finally in the last example the interiors do not intersect one another but the whisker on each set causes the boundaries to intersect the respective interiors.


While each intersection value is possible, some of them require extreme sets such as A and B in the right-most example above. Most geographic areas used in a GIS are more regularly shaped, and thus we are able to restrict our analysis to the types of spaces defined below.

Definition 4

A set A for which A = Cl(Int(A)) is called regularly closed.

Regularly closed sets include the annulus and square, while the circle, sets of individual points, and any set with a 'whisker' are not regularly closed, as depicted below. 


In our final definition we further specify the spaces which will be permitted in this model.

Definition 5

A planar spatial region is a nonempty proper subset C of the Cartesian plane satisfying the following conditions:
        1) It is regularly closed.
        2) The interior of C is connected.

The two diamonds below are each separately a planar spatial region. But their intersection is only one point, which is in the boundary of each set, so while regularly closed, their union is not a planar spatial region since its interior is disconnected.


Clearly this GIS model would not be suited well for an analysis of the number of fire stations whose area of coverage intersects gerrymandered congressional districts within a state as these oft-derided and sometimes comically drawn districts could probably be defined as "not regularly closed spaces whose interior is the union of nonempty open sets".



Using the Model

 
In this model, we only consider spaces which satisfy definition 5 of a planar spatial region. This narrows down the list of possible intersection values to 9 from the original 16. We do this because these 9 intersection values tell us exactly how the two spaces are related to one another.

Requiring that the spaces be regularly closed eliminates 6 ambiguous intersection values, including (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (1, 0, 0, 1), (1, 0, 1, 0), and (1, 0, 1, 1), by the following theorem from [1].

Theorem 1

Let A and B be regularly closed in a topological space X. If A  Int(B) is not empty, then Int(A Int(B) is not empty.

Proof: We first need show that A is contained in Cl(Int(A)). Since A is closed, it follows that A is contained in A. Furthermore, A = Cl(Int(A)) since A is regularly closed. Thus A is contained in Cl(Int(A)).

Now assume  Int(B) is not empty, and let x be an element of this intersection. Since x is in A, which is contained in Cl(Int(A)), it follows that every open set containing x intersects Int(A). But, Int(B) is an open set containing x, therefore Int(A) intersects Int(B), as desired.

Requiring that spaces be planar spatial regions further eliminates the intersection value (0, 1, 0, 0) as it is not possible for two planar spatial regions, which must be proper subsets of the Cartesian plane, to intersect on their interiors without at least one of their boundaries intersecting the other space [3]. This leaves us with the 9 intersection values in the following table, which each indicate a specific relation between the the two closed sets A and B.

Language

Intersection Value

Relationship

A is disjoint from B

(0, 0, 0, 0)

A B

A touches B

(1, 0, 0, 0)

A B = A B

A equals B

(1, 1, 0, 0)

A = B

A is within B

(1, 1, 1, 0) or (0, 1, 1, 0)

A contained in B

A contains B

(1, 1, 0, 1) or (0, 1, 0, 1)

A contains B

A overlaps B

(1, 1, 1, 1) or (0, 1, 1, 1)

Int(A) Int(B)

A not in B, and B not in A


Now that we have well defined intersection values between any two planar spatial regions, we can query the GIS database for areas with specific types of intersections to answer the research question we are examining or perform the analysis we desire. The example below demonstrates a simple use of GIS while the following pages give some more advanced uses.



Example


For a simple example, consider Allegheny College's goal of campus-wide wireless network coverage. With the knowledge of the approximate range of each wireless router in use, a GSI user could overlay a map of campus buildings with a map of available wireless coverage. In the map below of what is certainly the most important part of campus (at least to a math/econ double major who lived in Baldwin, Caflisch, and North Village), I have estimated the approximate wireless coverage for each building based on my personal experience.

The buildings are represented by the gray boxes and wireless coverage areas by the ellipses. While in the Definitions section above I listed circles as not regularly closed sets, these wireless coverage areas are actually closed discs, unfortunately my limited artistic ability requires that they be represented by circles.

Using the official language from the above section, we have both academic buildings within wireless coverage. North Village II is also within wireless coverage, note that being within the union of several routers makes no difference to our analysis. Baldwin overlaps wireless coverage, with neither space completely containing the other, while Caflisch contains wireless coverage (my old room in Caflisch would be said to touch the wireless coverage area, with the boundaries intersecting but no coverage on the interior the room).

An interested student could query this GIS for all residence halls with complete wireless coverage by searching for all buildings within a network, allowing them to make a well informed decision of where to live the next year. A school administrator or computer services employee could search for buildings disjoint from, touching, containing, or overlapping wireless coverage areas to see where improvements need to be made on campus and which buildings should be upgraded first.

This GIS model is clearly a useful tool and can be extended to analyze almost any geographic question asked about Allegheny's campus. It certainly gives a better picture of the state of wireless coverage than the list seen here http://computing.allegheny.edu/tutorials/wireless/wirelessaccess.php. An even more advanced model could incorporate a third dimension, the height of the buildings, and show wireless availability on each floor of a building.

Comments