地球上の位置 (緯度・経度) を1個の文字列で表す方式「Geo3x3」

Geo3x3 は、地球上の位置 (緯度・経度のみで、標高には対応していない) を1個の文字列で表す方式である。
基本的には、長い文字列ほど狭い範囲を表す (すなわち、高い解像度で表す)。

表現方法

基本

まず、最初の文字を決める。
最初の文字は、表現する地点が西経であれば W、東経 (経度0度を含む) であれば E である。

2文字目以降は、その前の文字までで現した部分を縦・横それぞれ3等分した部分が、それぞれ左下 (南西) から右上 (北東) に向かってテンキーの数字のような配置で1～9の数字に対応する。
縦の境界線上は右 (東) 側の部分に、横の境界線上は上 (北) 側の部分に対応する。

E の次の文字は、以下のようになる。

E9 の次の文字は、以下のようになる。

このように文字を追加する(した)回数 (最初の W または E を含む) を「レベル」という。
「レベル」は非負整数である。
たとえば、E はレベル1、E91 はレベル3である。
レベルが大きいほど、緯度・経度の範囲を細かく (高い解像度で) 表すことができる。

北極点・東経180度線上における例外

Geo3x3のエンコードでは基本的には1回の操作で1個の文字しか追加しないが、北極点 (北緯90度) および東経180度線上の地点を表す際の2回目の操作 (W または E の次の文字の決定) では、1回の操作で2個の文字を追加することがある。
「縦の境界線上は右 (東) 側の部分に、横の境界線上は上 (北) 側の部分に対応する」というルールをこれらの部分にも適用するため、東経180度線上の地点は 4、7、10、13 のいずれかで表し、北極点 (北緯90度) は (実際は1点になるため意味はないかもしれないが、経度に応じて) 10、11、12、13 のいずれかで表す。

すなわち、1回目の操作で E を選択した後の2回目の操作では、表す場所に応じて以下の文字 (1文字または2文字) を追加する。

この例外の適用後の3回目以降の操作では、表す位置は2回目の操作で追加した (1個または2個の) 文字に対応する正方形の左端または下端になるため、この例外は関係なくなる。

南極点 (南緯90度) は、範囲の下端なので、東経180度の場合を除いてこの例外の対象外である。
西経180度線上も、(東経180度線上と同じ位置を表すが) 範囲の左端なので、北極点を除いてこの例外の対象外である。
経度0度は、(浮動小数点数 -0.0 で表す場合も) 1回目の操作で選択される文字は E であり、範囲の左端なので、北極点を除いてこの例外の対象外である。

1回の操作で2文字が追加される可能性があるため、エンコード結果の文字列の長さは指定したレベルを超える可能性がある。
特に、(C言語などで) 固定長の領域でエンコード結果の文字列を扱う場合は、バッファオーバーランを起こさないように注意するべきである。

この例外により、たとえば「南極大陸の東経20度～40度のあたり、レベル3」と「北極点の東経120度～180度のあたり、レベル2」が同じ文字列 E12 で表され、エンコード結果だけを見ても区別がつかなくなる。
デコード時は、このような曖昧なエンコード結果に注意し、曖昧かどうかの判定フラグなどを出力したほうがいい可能性がある。

この例外は解釈が一意に定まらない表現を生み、Geo3x3を不便にすると考えられる。しかし、この例外があることは (特に 12 および 13 の追加について) テストコードで明示されており、仕様であると考えられる。

パディング

前述のように表現した文字列の後ろに、パディングとして好きな個数 (0個以上) の 0 を追加することができる。
0 の追加は「レベル」にカウントしない。
たとえば、E913 と E913000 は同じレベル4で、同じ位置 (範囲) を表す。

アルゴリズム

エンコード (緯度・経度 → Geo3x3文字列)

入力

以下を入力として受け取る。

• 緯度 (-90 以上 90 以下の数値)
  • 南緯は負の値で、北緯は正の値で表す
• 経度 (-180 以上 180 以下の数値)
  • 西経は負の値で、東経は正の値で表す
• レベル (正の整数)
  • 表す範囲を細かくする操作の回数を表す

緯度・経度と入力の数値は、以下のような関係である。

初期化

入力の緯度に90を足し、南極点を0、北極点を180とする数値に変換する。この変換結果を $y$ とする。

入力の経度が負の場合は、エンコード結果 $r$ を文字列 "W" とし、入力の経度に180を足した値を $x$ とする。
入力の経度が0以上の場合は、エンコード結果 $r$ を文字列 "E" とし、入力の経度をそのまま $x$ とする。

以下のような関係になる。

ここまでの変換で、入力された場所は縦と横の長さがともに 180 の正方形内のどこかに対応するといえる。
この、入力された場所がある正方形の一辺の長さを $u$ で表す。$u = 180$ に初期化する。

メイン処理

「レベル － 1」回、以下を繰り返す。(レベルが1のときは0回繰り返す、すなわち以下は行わない)

ここでは、以下の変数を用いている。(おさらい)

変数	意味
$x$	正方形の左下を原点とする、表す場所の横座標
$y$	正方形の左下を原点とする、表す場所の縦座標
$u$	正方形の一辺の長さ
$r$	エンコード結果の文字列

$u' = u / 3$ とする。

$dx = \lfloor x / u'\rfloor, dy = \lfloor y / u'\rfloor$ を求める。($x$、$y$ を $u'$ で割り、小数点以下を切り捨てた値をそれぞれ $dx$、$dy$ とする)

ここでは非負の値しか扱わないため、「切り捨て」と「その値以下の最大の整数を求める」は同じ結果になる。

$3 \times dy + dx + 1$ の値を十進数の整数で表した文字列を $c$ とする。

$3 \times dy + dx + 1$ の値は最大で 13 になり、$c$ は1桁または2桁である。
前述の北極点・東経180度線上における例外があるため、$dx$ や $dy$ が 3 のときもそのまま (2にクリップせずに) 処理を行ってよい。

変数を以下のように更新する。

変数	新しい値
$x$	$x - u' \times dx$
$y$	$y - u' \times dy$
$u$	$u'$ (すなわち $u / 3$)
$r$	$r$ の後ろに $c$ を結合した文字列

結果の出力

メイン処理における繰り返しが完了した後、最終的に得られた文字列 $r$ をエンコード結果として出力する。

デコード (Geo3x3文字列 → 緯度・経度)

入力

Geo3x3 形式の文字列 (E913 など) を入力として受け取る。

簡単のため、今回は不正な (Geo3x3 形式に沿っていない) 文字列は入力として与えられないと仮定する。
また、例外が適用された (すなわち、北極点または東経180度線上の点をエンコードした) 文字列も入力として与えられないと仮定する。

初期化

以下の数値型変数を初期化する。
ここで、「デコード結果」とは、入力の文字列をデコードした結果得られる緯度・経度の範囲を表す正方形のことを表す。

変数	意味	初期値
$x$	デコード結果の左下の頂点の横座標	0
$y$	デコード結果の左下の頂点の縦座標	0
$u$	デコード結果の1辺の長さ	180
$r$	デコードした文字列のレベル	1

メイン処理

入力の文字列の2番目の文字 (最初の文字の次の文字) から最後の文字の順に1文字ずつみていき、それぞれの文字について以下の処理を行う。
入力が1文字のときは、以下の処理は行わない。

Geo3x3 形式の文字列は1文字以上なので、入力が0文字の場合は考えなくてよい。

処理対象の文字が表す数値から1を引いた値を $c$ とする。
$c$ が -1 のとき (すなわち、処理対象の文字が 0 のとき) は、何もしない。(後述の変数の更新も行わない)

例外が適用されていなければ、0 が現れた場合はその後の文字もすべて 0 (パディング) のはずなので、最初の0 が現れた時点で処理を打ち切ってよい。

例外が適用された文字列の入力も受け付ける場合は、途中に 10 が現れる可能性があるため、0 がパディングを表すとは限らない。

$c$ が非負のときは、$c$ を 3 で割り (整数の除算)、商を $dy$、余りを $dx$ とする。

$u' = u / 3$ とする。

変数を以下のように更新する。

変数	新しい値
$x$	$x + u' \times dx$
$y$	$y + u' \times dy$
$u$	$u'$ (すなわち $u / 3$)
$r$	$r + 1$

出力

メイン処理における繰り返しが完了した後、以下の処理を行う。

入力の文字列の1文字目が W である場合は、$x$ の値を $x - 180$ に更新する。
そうでない場合は、$x$ の値はここでは更新しない。

以下の情報を出力する。

情報	値
デコード結果の中心の緯度	$y + u / 2$
デコード結果の中心の経度	$x + u / 2$
デコード結果の範囲を表す正方形の1辺の長さ	$u$
デコードした文字列のレベル	$r$

資料

この記事で紹介した表現方法およびアルゴリズムは、JavaScript版の実装を参考にした。
解説で用いた地図は、CraftMAP で出力したものを加工したものである。