-
Notifications
You must be signed in to change notification settings - Fork 68
Tilemask
Tilemask encodes tile area converage information in a compact string. The tile coverage information is stored as a sparse quadtree in a bitstream that is encoded with modified URL-safe base64 encoding.
Tilemasks are generated from a tile set of up to a certain zoom level. In order for the generated tilemask to be compactly representable, zoom level should be constrained to 8-12, depending on the area and precision requirements. For offline packages, tilemasks are between 20 and 500 bytes.
Tiles of a tile set are stored in a quadtree, depth first. Each quadtree node information is stored in consecutive 2 bits called CHILDREN and INSIDE:
if CHILDREN is 0, then this is the leaf node, otherwise this is the inner node if INSIDE is 0, then this node is outside the tile set, otherwise the node belongs to the tile set
The first node always represents tile (z=0, x=0, y=0). Subtiles are encoded in the following order (z+1, 2x+0, 2y+0), (z+1, 2x+1, 2y+0), (z+1, 2x+0, 2y+1), (z+1, 2x+1, 2y+1).
Tileset (0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 0, 1), (1, 1, 1), (2, 0, 2), (2, 1, 2), (2, 1, 3) is encoded as follows:
1 1 # tile (0, 0, 0) is inside the tile set and contains children
0 1 # tile (1, 0, 0) is inside the tile set and is a leaf
0 1 # tile (1, 1, 0) is inside the tile set and is a leaf
1 1 # tile (1, 0, 1) is inside the tile set and contains children
0 1 # tile (2, 0, 2) is inside the tile set and is a leaf
0 1 # tile (2, 1, 2) is inside the tile set and is a leaf
0 0 # tile (2, 0, 3) is outside the tile set and is a leaf
0 1 # tile (2, 1, 3) is inside the tile set and is a leaf
0 1 # tile (1, 1, 1) is inside the tile set and is a leaf
Thus the bit encoding of 8 tiles takes 18 bits:
11 01 01 11 01 01 00 01 01
This is padded with zeros to be byte aligned, thus taking 24 bits = 3 bytes
11 01 01 11 01 01 00 01 01 00 00 00
When this byte stream is encoded using base64, the result is ’11FA’.
The effectiveness of tilemask comes from ability to encode large regions that are either outside or inside the tile set with only a few bits, if we make additional assumption and specify MAX_ZOOM.
We assume that CHILDREN=0, INSIDE=1 encoding implies that all subtiles up to a MAX_ZOOM level are part of the tile set. For example, if we have a tile set (0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 0, 1), (1, 1, 1), then this can be encoded as 11 01 01 01 01, or sparsely as 01. This also implies that when tile with CHILDREN=0, INSIDE=1 (as defined in bitstream encoding section) has to be encoded, then it must be encoded as 11 00 00 00 00 (as 01 encoding is reserved and has special meaning).
This scheme allows efficient construction of the tilemask quadtree and then pruning the quadtree.
Tilemasks are encoded using base64 encoding with a small modification: all ‘+’ symbols are replaced with ‘-‘ symbols and ‘/‘ symbols are replaced with ‘_’ symbols. This makes the encoded tilemasks more URL-friendly. Note that due to legacy reasons, some tilemasks may be encoded as unmodified base64.