Geographic Shape Representations

The shape of Illinois Human beings possess the ability to deal with geographic detail at widely varying levels of detail. They can flexibly work with geographic facts at the global level and the local level. Most people, if pressed, can draw a rough map of the country in which they reside and show where it stands with relationship to other countries. Most people can draw a rough approximation of the other entities that they live in as well: states or provinces, counties, townships, parishes, cities, neighborhoods, and streets. Each individual knows the geographic details and relationships that are pertinent to them.

The long term goal of this research is to create artificial research agents that understand geographic relationships in a fashion similar to human beings. A key part of this research is investigating data structures for representing geographical shapes. The data structures must be compact, allow multiple levels of detail, and be flexible in adding or removing detail.



A quadtree shape A view of the quadtree Quadtrees are a well established technique in computer graphics and computer vision for representing 2D shape. A quadtree is a tree data structure with each tree node having up to 4 children. A quadtree node usually represents a square which can be subdivided into 4 other squares which cover the same area. Each leaf node is marked as being part of the object or not.

Advantages of quadtrees include

Quadtree disadvantages include

Chain codes

Chain codes represent the shape of a 2D object as a sequence of vectors taken from a small set of representative vectors. Advantages of chain codes include

Disadvantages of chain codes include


For geographic shapes, translation and rotation can be largely ignored. These operations occur mostly in the context of recognition problems. In geographic settings the main questions are those of relationship. Consequently, the research presented here is based on quadtrees with their strength of multi-resolutional representation.

Octahedral Quadtrees

When squares are used to represent the surface of the earth, distortion unavoidably occurs when approaching the poles. But squares are not the only shape that can be subdivided into similar forms. Triangles can also be subdivided into four smaller triangles, making triangular quadtrees possible. Coupled with one of the triangular platonic solids (tetrahedron, octahedron, or icosahedron) as an initial approximation and projected onto the surface of the earth, triangular quadtrees can be used to represent shapes on the earth's surface.

Octahedral mesh The octahedron is particularly well suited for geographic representations because the triangular subdivision scheme sets up edges that are roughly parallel to terrestrial latitude lines.


Mesh Creation

Software has been created to create octahedral quadtree meshes from collections of line segments describing geographical boundaries. Standard polygon scan conversion routines have been modified to output directly into a quadtree rather than into a bitmap which would be too large to fit into memory at the fine resolutions used.

Each node in the quadtree has one of four possible values. The area covered by each node can be either

  1. in the region
  2. out of the region
  3. partially in/out of the region
  4. not a leaf node, i.e., check with the children.

Work is currently underway to convert all of the geographic areas found in the Tiger/Line data set available from the U.S. Census Bureau. The scan conversion is being done to a resolution of approximately 10 meters.


The geographic regions are stored by following a level order traversal of the quadtree. The traversal does not need to store linkage information, so two bits per node is all that is needed to preserve the label.

The level order traversal also allows easy data simplification. The data stream can be truncated at any point and still remain a valid, lower resolution shape representation (after tweaking some former parent nodes to be leaf nodes with partial membership values).


Programs have been created for performing logical intersection, union, and negation on region.


Although visualization is not the goal of this research, an interactive region viewing program has been created to help evaluate correctness. The program allows interactive scrolling and scaling and owes its speed to the fact that it only needs a small portion of the quadtree to draw any given view.

This animation demonstrates a 1,000,000:1 zoom centered on an interesting point on the boundary of the state of Illinois. At the outermost level, the horizontal lines, from top to bottom, represent the north pole, equator, and south pole of the Earth. At the smallest level, the triangles shown are approximately 10m in size.

The animation shown is much slower than the real-time zoom rates experienced in the display software used. In this animation no more than 2929 nodes were used out of 1142920 at any given time.

In the animation, a slight popping can be seen when the data resolution used changes by a factor of 2. The data structure shown represents the entire state boundary of Illinois at 10m resolution and takes ~285kB of storage in its compressed form. In main memory, it takes ~35MB.

(Some people have asked if the expansion point in this animation has any particular significance. No, it was chosen arbitrarily as an area of nice fine-feature detail. In real life, it's a point in the middle of the Ohio River between Hardin County, Illinois and Crittenden County, Kentucky.)

Future Research

Future directions include

Last modified: Thu Jul 15 14:34:01 CDT 2004