GEO 580
Guest lecture on Alternative Data Structures

DISCRETE GLOBAL GRIDS - Dr. Jon Kimerling - 5/8/02

Equal Angle Grids - dividing the world into grid cells (into equal lat/long increments)

Problem here is that cells are NOT the same in terms of surface area, shape

ETOPO 5' data structure as an example of a compromise - stored and processed in computer as 4320 columns x 2160 rows
2 byte integer data
grid cells in computer are square but conceptually they are modeled as quadrilaterals

Are there alternatives to having just the square grid cells that still don't match the quadrilaterals of an ideal model? DISCRETE GLOBAL GRIDS

Goodchild Criteria - Top 5 Suggested Properties of an Ideal Discrete Global Grid System (for improved analysis):

1. areal cells constitute a complete tiling of the globe
2. cells must be equal in area (statisticians particularly like this for their sampling schemes)
3. cells must have the same shape
4. cells must have the same topology (adjacency, connectivity, relationships)
5. cells must be compact - should approximate a circle, the rounder the better

Persisent, age-old problem of trying to subdivide the Earth into the appropriate areal cells ("Next!" cartoon)

So... NEXT idea - "Constant" area grid instead of the equal angle - completely covers the Earth but cells are not quite perfect shape? triangles and squares
topology? problems with mismatches
compact? pretty much

NEXT idea - go for overall compactness - individual cells are polygons - use Thiessen polygons ("Voronoi tesselation") - start with sample points in whatever spatial arrangement - partition space into areas around those points based on minimum distance between the points (sides of polygons are perpendicular bissector to points) - Thiessen polygons completely tile the Earth
areas the same? no - will likely be higher density of points and smaller polygons over land versus oceans

NEXT idea - make Thiessen polygons as compact as possible
- honeycomb data structure - spherical beehive (soccer ball?)
- close in areas and very compact relative to other equal area
Hipparchus computer system developed by Canadian geographer - www.geodyssey.com

NEXT idea - subdividing the Earth could be akin to dimpling a golf ball! - many different designs for golf balls but they are all based on Platonic solids, then can subdivide further
Platonic solids - completely regular figures that can be projected onto a sphere or ellipsoid
See also www.georgehart.com/virtual-polyhedra/platonic-info.html no sliver problems! edges are true!

Tetrahedron 2 & 4 frequency subdivision or hexagonal subdivision
use that as basis for subdividing the Earth
problem is with great circle routes in subdividing faces
How about using small circles instead? Must be a small circle where if you duplicate 3 times you'll get equal area in all 4 cells
Lian Song M.S. thesis brilliant - she came up with small circle subdivision, icosahedron divided into triangles, exactly equal in area
- a way to group triangle into hexagons - no more quadrilaterals, but not as easy storage in computer
- closest tiling of surface, regular in shape, as compact as possible, equal area cells
See www.ncgia.ucsb.edu/globalgrids-book/song-kimmerling-sahr/

ANOTHER idea - treat it like a map projection problem
- like UTM is a kind of map projection solution to problem of areal cells
- distortions in area, shape or both can be quite extreme
- put grids on map projection surfaces - example of comedy and tragedy on various map projections which show different kinds of distortion
- e.g., Mercator will have bad distortion the farther you get from equator
- use cylindrical equal area projection instead but can still get severe distortion in cells
Better yet.... divide Earth into pieces (or lobes), and project each separately - Goode

Think of Earth as a soccer ball - soccer ball is geometric model of Earth - leads to truncated icosahedron model
EPA's Environmental Monitoring and Assessment Program (EMAP) sampling grid, developed by Dr. K in collaboration with Denis White and Scott Overton is based on this

See also www.epa.gov/region08/water/emap/emap.html
bufo.geo.orst.edu/tc/firma/gg/bibliography/bibterra.html

General Background on EMAP - www.epa.gov/emap/

EMAP sampling grid implemented in ArcInfo coverage - sunsite.utk.edu/samab/data/saa1/saa_pts/fhm/metadata/fhm_pts.txt

Equal area map projection
almost perfect hexagons, equal in area
going finer and finer in resolution

Divide Earth into basic geometric figure, projecting it w/equal area projection and then subdividing from there

BUT... not perfectly regular - works well w/50 states but not Canada

Sliver problem - slivers on edges of hexagons - these are areas not covered Snyder map projection solves this - projecting an icosahedron sphere onto a triangle - equal area projection with some distortion inside A big problem with the EMPA grid was the 12 huge pentagons that made it geometrically non-regular, along with the sliver problem.

Going backwards from map projection to data struture - compact, equal in area, but little variation in shape

ETOPO 5' Data in ISEA Grid, various resolutions
- fill hexagonal (not square!) cells with average elevation values

Implications for collecting data, storing data, analysis of data
One challenge is how to address the cells, which cell is next to which (similar to how quadtree cells are addressed for example?)

- people still trying to get used to it - hard to accept - e.g., NASA JPL insists on using equal area square grids even though there is so much distortion when you get into polar regions - but that is what they are used to

Beauty of Hexagons
- In theory there is no limit to resolution of hexagonal cells
- satellite sensors have a circular IFOV then try to scrunch the signal into a square grid cell - would be so much easier with a hexagonal grid cell - we need hexagonal sensing systems so that we can collect hexagonal pixels!

This data structure widely implemented in GIS? - not yet, still way in future. Dr. K. has chatted with ESRI owner Jack Dangermond about implementing a hexagonal grid structure. Potential for GIS analyses great - hexagons provide complete tiling, equal area cells, compactness, 6 adjacent neighbors instead of just 4

Current analyses benefitting from hexagonal grids?
Again, EPA EMAP - species counts, biodiversity mapping is prime example
See links on Geosciences Terra Cognita site - bufo.geo.orst.edu/tc/firma/gg/links.html

Return to GEO 580 Lectures