GeoDeltaというものを考えてみました
こんにちは。那由多屋の加藤です。
地球上の座標を示すためのコード「GeoDelta」というものを考えてみました。ちなみに考えてみただけです。実装求む！（笑）
特徴
GeoDeltaには下記のような特徴があります。たぶん。（なにぶん、まだ実装していないので本当かどうか・・・）
- メルカトル図法で描画された地図を正三角形で分割します。（Googleマップなど）
- 下位の領域（三角形）は上位の領域に包含されます。
- 比較的短いコードで領域（面積を持つ座標）を表現することができます。
- GeoDeltaコードの末尾を削ることで、1レベルまたは2レベル上位の領域を示すことができます。
- GeoDeltaコードは、口頭での伝達、手書きによる伝達で間違いが生じにくいように設計されています。
- 三角形を6つ組み合わせて六角形でビジュアライズするのが容易です。
- およそ北緯82.46度から南緯82.46度の領域を示すことができます。（南極観測隊のみなさん、ごめんなさい！）
開発者向けには以下のような特徴があります。
- たぶん、実装が容易です。
- 正しいGeoDeltaコードかどうか、1つの正規表現で判定できます。
- 単純な文字列処理で上位の領域が得られます。
仕様
以下、具体的な仕様です。まだあまり検証されていません。
領域
GeoDeltaでは、領域のことを「デルタ」と呼びます。地球を8個に分割したデルタを「ワールドデルタ」、入れ子になったデルタを「サブデルタ」と呼びます。
ワールドデルタには0から7までの番号が振られています。北半球から南半球、西から東の順番で番号が振られます。
上図における経度0度の北半球に位置するのがデルタ0（ヨーロッパを含む領域）、そこから東方向にデルタ1（主にアジアを含む領域）、デルタ2（日付変更線を含む領域）、デルタ3（北アメリカを含む領域）とします。
南半球も同様に、経度0度がデルタ4（南極だけを含む領域）、デルタ5（オーストラリアを含む領域）、デルタ6（日付変更線を含む領域）、デルタ7（南アメリカを含む領域）とします。
ワールドデルタは4つの領域に分割されます。分割されたデルタが「サブデルタ」です。サブデルタを分割したデルタもまた「サブデルタ」です。
サブデルタには0から3までの番号が振られています。中心を0とし、時計回りに1、2、3とします。上向きの三角形と下向きの三角形があることに気をつけて下さい。
レベル
領域の大きさは「レベル」と呼ばれる数値で示されます。ワールドデルタがレベル1、それを4分割したサブデルタのそれぞれがレベル2、そのサブデルタをさらに分割したものがレベル3です。
レベルが1つ大きくなるにつれて、地図上での面積が4分の1になります。実際に表現される領域の面積が4分の1になるわけではないことに気をつけて下さい。
コード体系
GeoDeltaコードは、下記のような書式で構成されます。
WSSSS....
「W」は符号化されたワールドデルタ、「S」は符号化されたサブデルタを示します。
より大きいレベル（狭い面積）を示すGeoDeltaコードほど長くなります。
符号化
GeoDeltaコードは、数字とアルファベットで構成されます。アルファベットは大文字小文字を区別しませんが、大文字で表記することが推奨されます。
GeoDeltaコードでは、数字の「0」「1」「9」、アルファベットの「I」「L」「O」「Q」「U」を除く28文字で表現されます。これらの文字が除かれている理由は、下記の通りです。
- 「0」: アルファベットの「O」と間違える可能性があるため。
- 「1」: アルファベットの「I」「L」と間違える可能性があるため。特に「L」が小文字の場合。
- 「9」: アルファベットの「Q」、数字の「6」と間違える可能性があるため。「Q」については日本語特有。
- 「I」: 数字の「1」、アルファベットの「L」と間違える可能性があるため。特に「L」が小文字の場合。
- 「L」: 数字の「1」、アルファベットの「I」と間違える可能性があるため。特に「L」が小文字の場合。
- 「O」: 数字の「0」と間違える可能性があるため。
- 「Q」: 数字の「9」と間違える可能性があるため。日本語特有。
- 「U」: アルファベットの「V」と間違える可能性があるため。特に手書きの場合。
ワールドデルタは1文字に符号化されます。対応表は下記の通りです。
| デルタ0 | Z |
| デルタ1 | Y |
| デルタ2 | X |
| デルタ3 | W |
| デルタ4 | V |
| デルタ5 | T |
| デルタ6 | S |
| デルタ7 | R |
ワールドデルタに続くサブデルタは、レベルによって文字数が異なります。サブデルタの符号化は、下記の順序で行います。
- 4進数（0から3）のシーケンス（例えば0、1、2）を2進数のシーケンス（例えば00、01、10）に変換します。
- 2進数のシーケンスをレベルの小さな領域から順番に結合します。
- 下記の対応表に従い、4ビット、または2ビットを文字に変換します。
4ビット以上残っている場合は、下記の表で変換します。
| 0000 | 2 |
| 0001 | 3 |
| 0010 | 4 |
| 0011 | 5 |
| 0100 | 6 |
| 0101 | 7 |
| 0110 | 8 |
| 0111 | A |
| 1000 | B |
| 1001 | C |
| 1010 | D |
| 1011 | E |
| 1100 | F |
| 1101 | G |
| 1110 | H |
| 1111 | J |
2ビット残った場合、下記の表で変換します。
| 00 | K |
| 01 | M |
| 10 | N |
| 11 | P |
符号化の例
GeoDeltaコードの符号化の例を下記に示します。
- アジア大陸を含むデルタ1→「Y」
- 日本を含む、デルタ1の右下のデルタ→「YP」（Y,11）
- 「YP」の上側のデルタ→「YG」（Y,11,01）
・・・これ以上は実際に実装しないと無理そうです。
実装のお願い
ここまで考えたのはいいのですが、実装する元気と時間がありません（笑）。実装を求む！
できることならば、OSI（Open Source Initiative）が認めるオープンソース・ライセンス下での提供を望みます。
一番最初にエンコーダ、デコーダを実装してくれた方にラーメンを奢ります！（ただし、関西圏、東京23区内に限る）
参考情報
実装者の参考になるであろう情報を並べておきます。
- 六角形によるジオコーディング: GeoHex
- 矩形によるジオコーディング: GeoHash
- メルカトル図法の概要について: メルカトル図法 - Wikipedia日本語版
- メルカトル図法の具体的な座標変換について: Mercator projection - Wikipedia英語版
- 三角格子座標系の効率的な表現について: いろいろな画素形状での離散ボロノイ図
ライセンス
この仕様書（笑）のライセンスは、CCライセンスのBY-SA（表示-継承）2.1とします。名前は「Yuya Kato (Nayutaya Inc.)」としてください。
