Mathematics for a New Grid System

From Pyxis public wiki
Jump to: navigation, search


Cell-based vs Point-based Systems

Euclidian or point-based geometric systems are based on the idea of a point. A point is a mathematical construct that has no equivalent on the planet. For example, a point occupies no space, whereas all real objects do occupy space at some level.

[image for point-based system]

However, digital systems are based on the idea of a discrete cell containing a quantized value, usually an integer. A cell does occupy space. Moreover, because the cell has area and because it can be subdivided into smaller cells, it can absorb a range of errors around a point in a way that a point-based system cannot.

[image for cell-based system]

Because cells more fully represent geography, mass, and quantity, cell-based systems are more useful for geodata.

The process of transforming point-based data (or analog data) into mathematical cells (or digital data) is called gridding or sampling. It is similar to the way digital recordings (CDs) are created from old recordings: by sampling it at very fine resolutions, transforming it to numbers, and then performing analysis and error correction on the digitized data.

The Hexagon Cell System

Since ancient times, people have known that certain regular shapes can tile a plane: triangles, rectangles, squares, and hexagons. These shapes combine to form a Tessellation or grid.

Tessellation of Hexagons (source??)

The hexagon shape has an advantage over other shapes: it has Uniform Adjacency. That is, all the hexagons touch each other in the same way -- on the sides. Tessellations of squares do not have uniform adjacency because some squares touch each other on points and others on sides.

Uniform adjacency has another advantage: the distance from the midpoint of a cell to the midpoint of any of its neighbours is always the same.

Rosette Pseudo-Regular Tiling

Rosette Pseudo-Regular Tiling (source??)

A single hexagon and its six surrounding neighbours form a first-level aggregate shape called a 1-rosette. These 1-rosettes aggregate to form 2-rosettes, and the 2-rosettes aggregate to form 3-rosettes, etc., in a tesselation pattern known as rosette pseudo-regular tiling.

This kind of tiling can be described using a type of tesseral arithmetic known as Generalized Balanced Ternary. Note that the rosettes tile the plane in a regular manner; however, the rosettes are not hexagons, and the orientation shifts by about 19 degrees with each level of aggregation.

Thus, while useful, rosette tiling has some limitations.

Other Forms of Hexagonal Tiling

Alternate Rosette Pattern (source??)

Rosettes can also be tiled by alternating steps.

In the pattern shown here, we form a 1-rosette, then add six lone hexagons around the edge, then add a set of six 1-rosettes around the single hexagons.

The advantage of this tiling is its symmetry and recursive nature. In addition, the orientation changes with each aggregation by exactly 30 degrees.

However, this pattern has limitations, especially its complex, irregular shape. Moreover, developing a way to subdivide these hexagons into infinitely smaller hexagons for more precise calculations poses a problem.

Subdividing Hexagonal Tiles

Rosette containing a parent and child cell (source??)
Subdivided hexagons (source??

Hexagons can be subdivided into symmetrical smaller hexagons by using the vertexes of some hexagons as the centre-points of others.

For example, by linking the centre-points of the hexagons forming this 1-rosette, we create a new hexagon. The hexagon at the centre of the image is considered the Centroid Child of the parent cell (or Centroid Parent) that surrounds it.

With this new pattern, we can subdivide the hexagons into infinitely smaller hexagons. Note that because each smaller hexagon rotates 30 degrees, and because hexagons have 60-degree rotational symmetry, the inner hexagon lines up with the outer hexagon (the grandparent hexagon).

This type of subdivision is known as aperture 3 subdivision in tesseral arithmetic. Each hexagon can be uniquely identified by an index composed of digits. For each subdivision, another digit is added. Thus 0 represents the centroid child, and 1-6 represent the vertex children. The only drawback to this indexing method is that it only works reliably for a single-ancestor hexagon.

Here are some of the terms for the different properties of hexagons in a tesselation:

Centroid child: a smaller hexagon that shares its centre-point with a larger parent hexagon

Centroid parent: a larger hexagon that shares its centre-point with a smaller child hexagon

Vertex child: a smaller hexagon that takes its centre-point from the vertex of a larger parent hexagon

Vertex parent: a large hexagon whose vertices are the centre-points for vertex child hexagons

Major hexagon: a hexagon with six vertex child hexagons and a centroid child

Minor hexagon: a hexagon with only a centroid child

PYXIS Icosahedron

PYXIS Tesseral Arithmetic on a 3D Shape

Platonic solids (source??)
Icosahedron (source??)
To apply hexagonal tesselations to the Earth means devising a way to project the hexagon tile onto a largely spherical object.

Five different tilings of regular polygons yield complete shapes in three dimensions. These are known as the Platonic solids.

The icosahedron (20 triangles) is of special interest for discrete global grid systems because it allows the greatest approximation of the Earth's surface.

Geodesic DGGS and Icosahedron Models

Geodesic DGGS (discrete global grid systems) address some of the inadequacies of the latitude-longitude model. They use a polyhedron, much like those described above, to approximate the sphere, then perform subdivisions to create a multi-resolutional discrete grid.

One popular approach is the ISEA3H or Icosahedral Snyder Equal Area Aperture 3 hexagonal grid. First, the triangles of the icosahedron are projected onto the sphere. Then each triangular face is subdivided into hexagons. The vertices of the triangles are then truncated to form pentagons. This creates a shape composed of 20 hexagons and 12 pentagons. This "soccerball" shape is a very close surrogate for a sphere.

Icosahedron Projected onto Sphere (source?)
Triangles subdivided into hexagons
Soccerball Icosahedron

The PYXIS Approach

PYXIS uses the ISEA3H projection and the "soccerball" truncated icosahedron. To ensure that the tiling works on the polyhedron's surface, the pentagons are considered to be major hexagons (yielding major aggregates under subdivision), and the hexagons to be minor hexagons (yielding minor aggregates under subdivision).

For the pentagons to act as hexagons, we must treat the missing vertex as a one-sixth gap in a hexagon. Thus, when we unfold the PYXIS icosahedron, the major hexagons all have a one-sixth gap. In the northern hemisphere, these gaps all face north. In the southern hemisphere, these gaps all face south.

When folded back together, this tessellation completely tiles the sphere.

PYXIS Icosahedron Unfolded. Note the basic triangular shapes of the base icosahedron. Note also the one-sixth gaps in the major hexagons (pentagons).

The PYXIS global grid has several advantages over current analog grids:

1. It encodes spatial location and area of influence with a single unique index value.

2. Its explicit representation of precision gives better control over location error.

3. There is no "round-off" error on non-floating-point spatial indexes.

4. It unifies raster data and vector data. (It translates from a data format problem to the data structure problem of full and sparse matrices.)

5. Its calculations using PYXIS non-floating spatial indexes are significantly faster than those for analog grids.

6. It does not require data pre-processing (R-Trees) or data warehousing.

7. It provides consistent equal-area representation of location across the globe.

8. It is much more compact than floating-point geographic coordinates for efficient storage and transmission.


1. Introduction

2. Current Geodata Systems

3. Mathematics for a New Grid System

4. Cell Terminology


Back to WorldView Help Centre

Personal tools

Wiki Navigation