Menu

Thoughts on Topology, Planar Graphs and Maponics Boundaries

Looking for specific topics?

 

 

Try sorting by categories

Or, view our archive

Overview

At Maponics we take pride not just in the quality and coverage of our data, but also in making our data easy to use. We want our customers to be able to receive our data and be able to start using it immediately. To accomplish this, we build our boundary products according to specs that strike the perfect balance between efficient storage and ease of use. Personally, I love being able to tell people, “Our boundary products are delivered as polygons with a list of attributes.” It’s that simple, and our customers love it!

But modeling spatial data, particularly across dozens of feature layers that are being independently maintained, requires a specific skillset that is far more complex than simply delivering “polygons with a list of attributes”. Within our own specialized production environment we employ a number of proprietary tools and technologies to achieve that goal of easy to use products. 

Many customers working with Maponics data won’t have to worry about the specialized and complicated nature of cartographic database storage and maintenance. But for some, including those of us in the digital mapping field, these topics are always at the forefront of the mind. So let’s peel back the cover on that can of cartographic worms and talk about topology, planar graphs and how innovative hybrids of these technologies are used in our industry.

Topology

In the digital mapping industry, topology refers to the pre-calculated spatial relationships between the primitives used to model real-world features. The key phrase here is “pre-calculated” and this is the principal difference between an efficient database model and one that is little more than a vector drawing application. If topology is supported and you ask what neighborhood a school point is in, you will instantly get an answer because that relationship is already computed and maintained.   The answer will also let you know which lines are connected to one another so you can perform networking operations on the data in order to do things like build drive time isochrones. Other examples of stored topology included pre-calculated relationships such as “contains”, “adjacent”, or “shares a node” (the endpoint of a line segment).

To help understand the concept better, take a look at subway/tube map of London:

In the map, the tube lines are modeled as curved lines that terminate at tube stations. They form a topology because the lines share a common, pre-calculated endpoint. Thus, any basic routing algorithm can help get you from point A to point B. The tube stations are equivalent to nodes (the endpoints of lines) in a map database.

But, look closer at the map and you’ll see that several tube lines cross other tube lines at locations where there isn’t a station. At these locations the topology model does not contain a shared node. We can see an intersection here, but according to the database model, it simply doesn’t exist.

Planar Graphs

For decades, the largest and most complex cartographic databases have been built using a special form of topology called a planar graph. In a planar graph, no two features are allowed to touch except at the endpoints of lines. If we were to convert the above tube map into a planar graph, we’d have to split all lines where they intersect. Although the map doesn’t provide elevation details, most of the crossing tube lines are at different elevations. Perhaps one track is above ground, perhaps another is underground. They are, in a three-dimensional sense, in different planes! By splitting these lines at their intersections, you allow all lines to be modeled in a single two-dimensional plane. And since their edges touch, we can create a graph from them. Yes, a planar graph.

Planar graphs are a lot like jigsaw puzzles.  Both share two critical characteristics:

  1. Every single location on the final image is covered by a puzzle piece. There are no holes.
  2. No two puzzle pieces are allowed to overlap one another. Their edges match perfectly and there are no gaps.

To get an easy understanding, picture two circles, with a third of one overlapping a third of the other. We have the choice of modeling this as two overlapping circles or as three independent polygons (the overlapped area being the third polygon). With a planar graph, you would have three polygons.

There’s really no other way to put it:  Planar graphs are cool. If your core database is represented by a planar graph, then it’s trivial to store area features (boundaries) as simple collections of those primitive jigsaw puzzle pieces. (Tech note: In the industry we refer to these building blocks most commonly as “faces” or “two-cells.”) Your definition of any boundary, whether it is a neighborhood or a ZIP code, simply becomes, “A list of faces and a set of attributes.” And, the reverse is true; if you know which face you’re in, it’s a simple look-up to determine which boundary features you’re in. 

By calculating all of these relationships between the geometry and the features built from them, you enable your production environment to be extremely efficient. Quality checks such as looking for gaps, slivers, overlaps, and minimum and maximum feature sizes become simple relational queries. And, because all of the features are built from the same 2-D planar graph, you are ensured all features that should share common borders actually do. And, even more impressive, if you decide to move a node or reshape a line, all features associated with those geometries get updated in tandem. 

GIS Systems Hate Planar Graphs

Ok, I said it. Most GIS systems are simply not designed to work with planar graphs. And why should they? Planar graphs are great for building and maintaining spatial data, but they offer significant drawbacks when it comes to using the final products.

Most GIS systems don’t expect map data to be stored as a flattened planar graph. Instead, they view map data as layers. These layers usually have a single predefined primitive type (point, line or polygon) and you work with most GIS platforms by creating “projects,” which are quite pragmatically defined as a collection of these layers. This view of feature organization loses the relationships between those layered features, but the storage and display becomes much more optimized toward using the map data (as opposed to building or editing the map data.) Want to turn on postal boundaries? Just hit the check mark next to the appropriate layer. 

Maponics Boundaries – A Hybrid Approach

At Maponics we build our products using a hybrid approach that delivers products ready to use in common GIS data formats such as ESRI Shape, but with data quality that is consistent with databases built from a planar graph. Our neighborhoods, for example, are delivered as simple collections of polygons with attributes, yet they follow sophisticated overlapping rules. Neighborhoods of the same type share common edges without overlaps, but different types are allowed to overlap. This means a metro can contain multiple residential neighborhoods, etc. We deliver our data in this format because our customers love to use it this way!

It’s all a lot to keep in mind. But hopefully, this post has helped you to better understand how much thought goes into both building map data and providing quality products that are easy to use.