Binary tiling scheme

Full title of this proposal: Identification of sub-units of a fixed grid with Ahnentafel numbering
Short name: bintiles

Overview

The goal of this proposal is to describe a binary tiling scheme, which is intentioned for a fixed grid where the horizontal and vertical sizes are not necessarily similar. It could be a solution for Computerteddy's problem that some 1x1 degree cells in Europe contain too much data, in order to generate Garmin images for.

The inspiration of this idea comes from the common pedigree (Ahnentafel) numbering scheme, which has been devised by Eytzinger, and subsequently popularized by Sosa and Kekulé von Stradonitz.

Note that in this proposal the terms tile and cell are used interchangeably.

Benefits

• Tile identification by a single integer value
  • "Genealogy" of a particular tile can be derived from the same value
• Not limited by scale
• Less redundant tiles are generated as compared to a quad tiling scheme

Disadvantages

• Interleaved bits; any quadtile scheme has the same problem
• The location of a tile is less obvious, because of the identification by a single integer value

Technical details

The parent cell has number n, and the two child cells have numbers 2*n and 2*n+1. The original 1x1 undivided cell has number n=1. This way all child cells can be identified uniquely by a positive integer. There will be no overlapping ranges of numbers.

Here is an overview of the tile ranges for a couple of 'generations' (level):

• 0: 1
• 1: 2-3
• 2: 4-7
• 3: 8-15
• 4: 16-31
• 5: 32-63
• 6: 64-127
• 7: 128-255

When dividing up a tile, the lower or leftmost tile will get the number 2*n, and the upper or rightmost tile will get the number 2*n+1. This allows for easier formulas when coordinates have to be converted to a tile.

The 'generation' (level) of a tile can be determined by counting the times an integer division by 2 needs to be applied, until the value 1 is reached.

A division is called odd when the number of subtiles at the resulting level will become 2^n, where n is an odd number: 2: 2^1; 8: 2^3; 32: 2^5, etc. Likewise, a division is called even when the number of subtiles at the resulting level will become 2^n, where n is an even number: 4: 2^2; 16: 2^4, 64: 2^6, etc.

Rationale

The reason that such a binary tiling is chosen is that often grid cells are not square, but rectangular. Nearly all lat/lon grid cells are rectangular as well, when accounted for the latitude. On the 45th latitude the aspect ratio (width:height) is approximately 0.7. At this zoom level all tiles will have about the same aspect ratio, although the width or the height will be larger than the other one interchangeably.

Another reason is that with this system there will be less "redundant" tiles than when a quadtile scheme is used for dividing up an area with varying data density. For example, when there is only a lot of data in one corner, you'll end up with three cells with this scheme, but already four with the quadtile schema. This way Computerteddy has to make less tiled available, and also for the CanVec import, where currently a quadtile scheme is used, there will be less files to import.

Examples

First few generations:


Suppose if subtile 23 contains a lot of data, the following tiles need to be generated: 3, 4, 10, 22, 23, which is a total of 5 tiles. When a quadtile scheme is used, the following tiles would be generated instead: 4, 6, 7, 20, 21, 22, 23, which is a total of 7 tiles. The reason is that the odd division steps are skipped.

Applications

Use in a grid referencing system

This scheme can also be used to identify cells in a grid referencing system (like MGRS, etc.). It can be used without a prefix, when the whole world would be used, and where tile n=1 would encompass (-180,-90)-(180,80). Of course it can also be used with a prefix. For example N52E005 identifies an area in the Netherlands, ranging from (5,52)-(6,53) (WGS84, lon;lat order). Tile n=2 is the area with the box (5,52)-(6,52.5), and tile n=27 is the area with the box (5.25,52.75)-(5.5,53). Both tiles could be designated with the identifiers "N52E005/2", and "N52E005/27" respectively.