Technical Specification

This document defines the BGrid protocol for geospatial indexing. It is intended for developers who wish to implement BGrid in any programming language.

1. Overview

BGrid is a hierarchical spatial index that maps latitude/longitude coordinates to a sequence of 11-bit integers (1-2048). These integers are typically represented by words from the BIP39 wordlist.

• Input: WGS84 Coordinates (Latitude, Longitude)
• Output: Array of indices $[i_1, i_2, ..., i_n]$ where $1 \le i_k \le 2048$.

2. Coordinate System

• Latitude range: $[-90, 90]$ representing South to North.
• Longitude range: $[-180, 180]$ representing West to East.
• Datum: WGS84 is assumed.

3. Grid Structure

The grid is defined recursively. At each level, the parent cell is subdivided into a fixed number of child cells.

Subdivision Strategy

To minimize distortion (keeping cells roughly square), the subdivision factors alternate between levels:

Level	Columns ($div_{lon}$)	Rows ($div_{lat}$)	Total Cells	Aspect Ratio Correction
Odd (1, 3, …)	64	32	2048	Wide (2:1)
Even (2, 4, …)	32	64	2048	Tall (1:2)

Since the Earth’s latitudinal span (180°) is half its longitudinal span (360°), the initial 64x32 grid produces cells with a generic 1:1 aspect ratio at the equator. Alternating maintains this relative balance.

4. Encoding Algorithm

To convert a coordinate $(\phi, \lambda)$ (Lat, Lon) to a BGrid path of depth $L$:

Initialization

Normalize the coordinates to the unit interval $[0, 1]$:

$$x_0 = \frac{\lambda + 180}{360}$$ $$y_0 = \frac{90 - \phi}{180}$$

Iteration

For each level $k$ from 1 to $L$:

1. Determine Divisors:

   • If $k$ is odd: $W_k = 64, H_k = 32$
   • If $k$ is even: $W_k = 32, H_k = 64$

2. Calculate Cell Indices:

   $$col_k = \lfloor x_{k-1} \times W_k \rfloor$$ $$row_k = \lfloor y_{k-1} \times H_k \rfloor$$

3. Clamp Indices (Handle edge cases like +180 lon):

   $$col_k = \min(\max(col_k, 0), W_k - 1)$$ $$row_k = \min(\max(row_k, 0), H_k - 1)$$

4. Compute 1-based Index:

   $$Index_k = (row_k \times W_k) + col_k + 1$$

5. Update Normalized Coordinates (Zoom in for next iteration):

   $$x_k = (x_{k-1} \times W_k) - col_k$$ $$y_k = (y_{k-1} \times H_k) - row_k$$

6. Append $Index_k$ to result.

5. Decoding Algorithm

To convert a BGrid path $[i_1, i_2, ..., i_L]$ back to a coordinate and bounds:

Initialization

Start with global bounds:

• $MinLon_0 = -180, MaxLon_0 = 180$
• $MinLat_0 = -90, MaxLat_0 = 90$

Iteration

For each level $k$ corresponding to index $i_k$:

1. Adjust to 0-based index:

   $$idx = i_k - 1$$

2. Determine Divisors:

   • If $k$ is odd: $W_k = 64, H_k = 32$
   • If $k$ is even: $W_k = 32, H_k = 64$

3. Decode Row/Col:

   $$col = idx \pmod{W_k}$$ $$row = \lfloor idx / W_k \rfloor$$

4. Calculate Cell Dimensions:

   $$\Delta_{lon} = \frac{MaxLon_{k-1} - MinLon_{k-1}}{W_k}$$ $$\Delta_{lat} = \frac{MaxLat_{k-1} - MinLat_{k-1}}{H_k}$$

5. Update Bounds:

   $$MinLon_k = MinLon_{k-1} + (col \times \Delta_{lon})$$ $$MaxLon_k = MinLon_k + \Delta_{lon}$$

   Note: BGrid iterates Latitude from North (90) to South (-90) (top-down in grid terms).

   $$MaxLat_k = MaxLat_{k-1} - (row \times \Delta_{lat})$$ $$MinLat_k = MaxLat_k - \Delta_{lat}$$

Final Result

The resulting bounds $[[MinLat_L, MinLon_L], [MaxLat_L, MaxLon_L]]$ define the area covered by the BGrid address. The point coordinate is typically the center of these bounds.

6. String Representation

The numeric indices naturally map to the BIP39 wordlist, which contains 2048 words.

• Index 1 $\rightarrow$ Word 1 (abandon)
• Index 2048 $\rightarrow$ Word 2048 (zoo)

This allows BGrid addresses to be localized into any language supported by BIP39.

Format

Standard text representation uses a designated separator (usually space or hyphen).

• Raw: [4, 1827, 201]
• Text (English): ability-smoke-board