List of topics: GIS, Lattice systems, GeoHash, Google S2, Uber H3, hexagon

Global discrete grid systems, it is to point to will the earth’s surface according to certain rules are divided into a grid area, usually for grid system, have a fixed grid and fixed grid points, a fixed grid, such as the Delaunay triangulation, tyson polygon, often is to pass the known point to build, a spot, the build of the grid are also different. Unfixed grid we will not discuss fixed grid systems today, which are more common in engineering.

First, we will discuss what is a fixed grid. A fixed grid, as its name implies, is a grid divided according to a fixed position. A point will correspond to only one grid, and each grid is as consistent as possible. In practice, such as spatial index of points, calculation of thermal diagram, region division and other scenarios will use the concept of lattice system. Today, I will discuss the advantages and disadvantages and application scenarios of three common open source grid systems, geoHash, Google S2 and Uber H3. From the grid system construction is roughly divided into three steps. The first step is to convert the sphere (earth surface) to a plane, the second step is to cover the plane polygon, and the third step is to encode the plane polygon. The principles of each step of these three fixed lattice systems will be roughly explained below. For the sake of simplicity, let’s think of the Earth as a sphere (which it is not).

1 The sphere transforms into a plane

Those who are familiar with gis related to plane projection may know common projection methods, such as Mercator projection and orthoaxial equiangular cylindrical projection, which is the process of sticking the cylindrical surface on the sphere, projecting the surface onto the cylindrical table name through the center of the sphere, and then expanding the cylindrical surface into a square.



This kind of projection is a representative kind of projection, and its advantages and disadvantages are equally obvious. The advantage is that the projection is very simple and easy to recognize and read. The disadvantage is also very obvious, and the deformation is very severe, especially in the north and south stages of the sphere, which are greatly enlarged after being unfolded. This is a serious drawback when building global-scale grid systems. The other is to surround a sphere with a regular polyhedron and then expand it into a plane. Google S2 and Uber H3 are both done this way.

Regular polyhedra are Platonic bodies. There are only five kinds in geometry, regular tetrahedra, cube, regular octahedron, regular dodecahedron and regular icosahedron. Since Google S2 has a square cell, it uses a regular octahedron, while Uber H3 uses a regular icosahedron.The deformation of a sphere fitted with a regular polyhedron is much smaller than that of a sphere fitted with a cylinder, and the more the number of faces of a regular polyhedron, the better the sphere fitted and the smaller the deformation, but the calculation will be more complicated. The advantage of this projection is that the deformation is small. The downside is that the calculations are relatively complex (the more they are, the more complex they are) and hard to read (can you see where Antarctica is in Google s2?).It is worth mentioning that Google S2 has also made some deformation optimization when doing projection.The three types of projection used in the lattice system:

  • Geohash: orthoaxial equiangular cylindrical projection
  • Google S2: regular hexahedron
  • Uber H3: regular icosahedron

Therefore, the advantages and disadvantages of the projection mode of the grid system are as follows: deformation degree: Uber H3 < Google S2 < GeoHash readable degree: GeoHash > Google S2 = Uber H3

2. Coverage of planar polygons

All use the same regular polygon to cover the entire plane, called a regular Mosaic. There are three types and only three types of tessellations. Only regular triangles, squares and hexagons can be inlaid in this wayThe choice of different shapes affects two properties of the lattice system. The coverage of multilevel grid, the influence of center grid on the weight of surrounding grid, and the number of grid levels. These features have different uses in different usage scenarios.

1 Multi-level coverage

Multi-level coverage feature has obvious advantages for building spatial indexes, which can be stored in a tree structure. Only triangles and squares can be covered at multiple levels, but hexagons do not. Of the three grid systems, GeoHash uses a rectangular + square grid (the middle level becomes rectangular due to base32 encoding), Google S2 uses a square grid, and Uber H3 uses a hexagonal grid. Similarly, Uber H3 has also made some optimization on multi-level coverage, and the grid of each layer is rotated 19.1° to cover the next level grid approximately. However, it can be seen that the next grid in Uber H3 still cannot completely cover the previous grid. Therefore, multi-stage coverage features:

geohash = google s2 > uber h3

2. Consistent weight characteristics of adjacent grids

The most typical application scenario of this feature is thermal diagram. For example, the imbalance between supply and demand in a certain grid will inevitably affect the supply and demand of the surrounding grid. For a hexagon, all the grids are edge adjacent, that is, the weight of the surrounding grid is consistent.For triangles and squares, besides edge adjacency, there are also points adjacency, so it is difficult to determine the weight values of edge adjacency and point adjacency.Therefore, hexagons are usually a better choice than squares in the selection of thermal maps. So the weight of adjacent lattice is consistentuber h3 > geohash = google s2

3 number of cell levels

The number of levels of the grid from the largest level, to the smallest level of the total number of levels statistics. The greater the number of cell levels, the smoother the transition from large to small cells, and the richer the choice of levels. Geohash typically provides a grid of 12 levels, ranging from about 5000km to about 3cm.

Geohash length Cell width * Cell height
1 5000 km by 5000 km or less
2 1250 km by 625 km or less
3 156 km by 156 km or less
4 39.1 km by 19.5 km or less
5 4.89 km by 4.89 km or less
6 1.22 km by 0.61 km or less
7 153 m by 153 m or less
8 38.2 m * 19.1 m or less
9 4.77 m * 4.77 m or less
10 1.19 m * 0.596 m or less
11 149 mm * 149 mm or less
12 37.2 mm x 18.6 mm or less
Google S2 offers 30 levels of cells, ranging from about 8000km to about 1cm
Uber H3 offers 15 levels of grid, ranging from about 1107km to about 0.5m
From the number of levels
google s2 > uber h3 > geohash
Google S2 is smoother, making it a better choice when data levels are spread over large scales.