技術ホワイトペーパー

ドキュメント

リファレンス

技術ホワイトペーパー

はじめに

当初、tzf は座標をタイムゾーンに変換する必要があるバックエンドサービス向けに設計されました。主に地理・気象サービスが対象です。

プロジェクトの進化に伴い、Python サポートの追加が必要になりました。当時 timezonefinder の境界付近での速度が要件を満たせなかったためです。

それが tzf (Go)、tzfpy (Python)、tzf-rs (Rust) が作られた理由です。

設計目標は次の通りです：

座標をタイムゾーンに変換する。
完璧な精度よりもパフォーマンスを優先する。
最低でも Go と Python をサポートする。（Rust は PyO3 エコシステムのために開発されました。）
バックエンドサービス向けに最小限の配布/バイナリサイズ。

このホワイトペーパーでは、tzf で使用される 5 つのコア技術をカバーします：

トポロジー認識簡略化（データパイプラインステージ 1）
共有エッジ重複排除（データパイプラインステージ 2）
Polyline エンコーディング（データパイプラインステージ 3）
タイルベースインデックス（FuzzyFinder プレインデックス）
YStripes 空間インデックス

データパイプライン概要

生のタイムゾーン境界データは、Protocol Buffers バイナリ（Timezones 形式）として約 96 MB から始まります。 2 つの並行オフラインパイプラインが 3 つの配布ファイルを生成します（ファイル名には combined-with-oceans. プレフィックスが付きます）：

完全精度パイプライン——重複排除 + 圧縮のみ、簡略化なし：

生 .bin                     (96 MB,   Timezones)
  ↓ 共有エッジ重複排除
.topo.bin                   (54.6 MB, TopoTimezones,              −43%)
  ↓ Polyline デルタエンコーディング
.compress.topo.bin          (17 MB,   CompressedTopoTimezones,    −82%)  ← 埋め込み（完全版）

ライトパイプライン——トポロジー認識簡略化 + 重複排除 + 圧縮、プレインデックス分岐付き：

生 .bin                               (96 MB,   Timezones)
  ↓ トポロジー認識 D-P 簡略化
.topology.bin                          (12.5 MB, Timezones,              −87%)
  ├─→ preindextzpb → .topology.preindex.bin  (2.0 MB)  ← 埋め込み（プレインデックス）
  ↓ 共有エッジ重複排除
.topology.topo.bin                     (10.0 MB, TopoTimezones,          −90%)
  ↓ Polyline デルタエンコーディング
.topology.compress.topo.bin            ( 5.4 MB, CompressedTopoTimezones,−94%)  ← 埋め込み（ライト版）

最終的な配布ファイル：

ファイル	形式	サイズ
`combined-with-oceans.compress.topo.bin`	`CompressedTopoTimezones`	約 17 MB
`combined-with-oceans.topology.compress.topo.bin`	`CompressedTopoTimezones`	約 5.4 MB
`combined-with-oceans.topology.preindex.bin`	`PreindexTimezones`	約 2 MB

完全精度データセットは約 96 MB（生 protobuf）から約 17 MB に縮小——tzf-rs が手動ファイルダウンロードを必要とせず、オプションの Cargo feature として提供できるほど小さくなりました。

これらのファイルは ringsaturn/tzf-dist 経由で配布されます。

ステージ 1——トポロジー認識簡略化

背景：ポリゴンごとのアプローチとその限界

生の GeoJSON ポリゴンデータはまず Protocol Buffers を使用してバイナリエンコーディングに変換されます。スキーマはシンプルです：

message Point {
  float lng = 1;
  float lat = 2;
}

message Polygon {
  repeated Point points = 1;
  repeated Polygon holes = 2;
}

message Timezone {
  repeated Polygon polygons = 1;
  string name = 2;
}

message Timezones {
  repeated Timezone timezones = 1;
}

この変換後も、データをメモリに読み込むには約 900 MB 必要です。自然な次のステップは Ramer–Douglas–Peucker (RDP) アルゴリズムを適用して各ポリゴンのポイント数を削減することです：

各ポリゴンに RDP を独立して適用することで、データは約 11 MB に縮小されました。しかし、この単純なアプローチには根本的な正確性の問題がありました（tzf#183）：隣接するタイムゾーンポリゴンはエッジを共有していますが、各ポリゴンは独立して簡略化されます。D-P アルゴリズムが共有境界の両側から異なる中間ポイントを削除するため、2 つのポリゴンはわずかに異なるエッジ形状になり——生データでは見えないが簡略化後に現れるギャップと重複が生じます。 DefaultFinder の ±0.02° 空間許容フォールバックは、これに対する回避策であり、真の修正ではありませんでした。

トポロジー認識アプローチ

修正は、RDP 簡略化をトポロジー認識パイプラインに統合し、すべての隣接ポリゴンにわたって共有境界を一貫して処理することです。簡略化の前に、すべてのポリゴンリングに対してトポロジーグラフが構築されます：

巻き方向の正規化（外環は CCW、穴は CW）により、隣接するリングが反対方向で共有境界を走査するようにします——これが逆エッジマッチングを信頼できるものにします。
ゼロ長エッジの削除（一部のリングには共有エッジ検出を妨げる重複隣接頂点が含まれます）。
T 字路頂点のスナップ：トポロジーノードが隣接エッジの内部にある場合、分析の前に新しい頂点として挿入します。
正準キーハッシュによる共有エッジの検出。各セグメントを分類します：
- 固定：3 つ以上のリングが交わる頂点。これらのアンカーポイントは移動不可。
- 共有セグメント内部：簡略化可能だが、一度だけ——すべてのパートナーリングが同じ簡略化結果を再利用します。
- 非共有：独立して簡略化（海岸線、独立境界）。
飛地リング（内部タイムゾーンの外環と形状が等しい穴）は特別に処理：両方のパートナーリングが辞書順最小頂点（正準スタート）に回転し、共有簡略化キャッシュに入り、固定頂点なしで同一の出力を保証します。
フォールバック：簡略化後に一意のポイントが 3 未満になる、ゼロ長エッジが生じる、または（小リング ≤ 100 点で）自己交差するリングは、元の未修正の入力リングに戻します。

このトポロジー認識アプローチは 2026 年春に完了しました。その実装は internal/topology/README.md に文書化されています。

結果：86% のポイント削減（8 M → 1.09 M ポイント）、トポロジー的に一貫した共有境界—— ギャップなし、意図しない重複なし。

ステージ 2——共有エッジ重複排除

簡略化後も、長い共有境界セグメントはファイル内に 2 回現れます—— 隣接するタイムゾーンリングごとに 1 回ずつです。deduplicatetzpb ツールは Timezones バイナリを TopoTimezones 形式に変換し、各共有セグメントを一度だけ保存します：

グローバルな SharedEdge ライブラリが各長共有境界セグメントを ID でインデックスします。
各リングは RingSegment エントリのシーケンスになります：短いインラインポイントシーケンス（≤ 10 点）または SharedEdge ID への順方向/逆方向参照。

巻き方向の正規化は、簡略化前と同じ理由で重複排除の前にも実行する必要があります：隣接するリングが共有境界を反対方向に走査する場合にのみ、重複排除がそれらを同じエッジとして認識します（争議領域の同方向重複として分類するのではなく）。

結果（簡略化データ）：約 20% のさらなるサイズ削減（12.5 MB → 10.0 MB）。TopoTimezones 形式は完全なポリゴンにクリーンに往復変換できるため、下流ツールにとって有用な交換形式です。

ステージ 3——Polyline エンコーディング

最後のオフラインステージでは、Google Maps の Encoded Polyline アルゴリズムを適用して TopoTimezones に保存された座標シーケンスを圧縮します。地理的に連続するポイントは小さなデルタを持つため、デルタ + zig-zag エンコーディングが簡略化・重複排除済みデータに対して約 45% の追加圧縮を達成します。

共有エッジポイントシーケンスとインラインセグメントポイントはデルタエンコードされ、エッジ ID 参照（int32 順方向/逆方向参照）はそのまま通過します。

結果：10.0 MB → 5.4 MB（CompressedTopoTimezones）、生の 96 MB ソースから累計 94% の削減。

タイルベースインデックス

単純な Ray Casting アプローチは O(n²) 時間で動作し、高並行性バックエンドサービスには不適切です。空間 R-tree を検討しましたが、グローバルタイムゾーンの数が少なく、面積分布が不均一であるため、パフォーマンス向上はごくわずかでした。

そこで、気象データサービスで使用される地図タイル形式に着想を得たタイルベースのインデックス方式を採用しました。各タイルは特定のズームレベルで四辺形領域を定義します：

┌───────────┬───────────┬───────────┐
│           │           │           │
│           │           │           │
│ x-1,y-1,z │ x+0,y-1,z │ x+1,y-1,z │
│           │           │           │
│           │           │           │
├───────────┼───────────┼───────────┤
│           │           │           │
│           │           │           │
│ x-1,y+0,z │ x+0,y+0,z │ x+1,y+0,z │
│           │           │           │
│           │           │           │
├───────────┼───────────┼───────────┤
│           │           │           │
│           │           │           │
│ x-1,y+1,z │ x+0,y+1,z │ x+1,y+1,z │
│           │           │           │
│           │           │           │
└───────────┴───────────┴───────────┘

この四分木ライクなレイアウトにより、親タイルが正確に 4 つの子タイルを含み、ギャップなしの集約が可能です：

タイルベースのタイムゾーンインデックスのデモ。ポリゴンとインデックスを含むライブデモは tzf-web で確認できます

各タイムゾーンは独立して処理されます。各タイムゾーンについて：

インデックスズームレベル（ズーム 13）でポリゴンに接触するすべてのタイルを生成します。
ポリゴン内に完全に収まるタイルのみを保持します（EnsureInside）。
エッジタイルを削除——8 つの隣接タイルのいずれかがタイルセットに存在しないタイル。このステップは 2 回適用され（dropEdgeLayer = 2）、内部境界から 2 層剥がして、ポリゴンエッジ付近のタイルを除外します。
MergeUp で残りのタイルを集約ズームレベル（ズーム 3）にマージし、マージ結果に再度 EnsureInside を適用します。

各タイムゾーンは独立してインデックスされるため、複数のタイムゾーン内に収まるタイルは、すべての関連タイムゾーンのインデックスエントリに現れます。メモリ内のマップは map[Tile][]string であり、1 つのタイルが複数のタイムゾーン名を返すことができます。これは Asia/Shanghai と Asia/Urumqi のような共有エリアを処理し、それらの重複する内部領域が両方のタイムゾーンのプレインデックスエントリに一致するタイルを生成します。

クエリ時には、最も粗いズーム（3）から最も細かい（13）まで走査し、最初に一致するタイルですべてのタイムゾーン名を返します：

一致するタイルが見つかった場合 → そのタイムゾーンリストを返します（曖昧でない内部タイルは 1 つ、共有エリアのタイルは複数）。
一致するタイルがない場合（境界領域、海岸線、疎なエリア） → プレインデックスは結果なしを返します。

FuzzyFinder はこのプレインデックスのみを使用します。GetTimezoneNames は完全なリストを返し、 GetTimezoneName は最初のエントリを返します。未カバーエリアでは推測せずにエラーを返します—— 呼び出し側が空のケースを処理する責任を負います。

DefaultFinder はこれを自動的に処理します：最初にタイルプレインデックスを試み、結果が返されない場合は Finder による完全なポリゴン検索にフォールバックします。これにより、すべての座標に対して正確でありながら、大部分の世界都市クエリでプレインデックスの速度を維持します。

YStripes インデックス

tzf v1.1.0 (Go) および tzf-rs v1.2.0 (Rust) 以降、ポリゴンレベルのポイントイン- ポリゴンテストは、Josh Baker の tidwall/tg プロジェクトから移植された YStripes 空間インデックスを使用します。

YStripes は、各ポリゴンのエッジを水平ストライプに事前分割することで、単純なレイキャスティングを改善します。クエリポイントに対して、該当するストライプ内のエッジのみがテストされ、完全な空間ツリーのオーバーヘッドなしでポリゴンごとの作業量を大幅に削減します。

これはデフォルトで有効です。無効にする（メモリ制約のある環境など）には、 Rust の FinderOptions を使用します。YStripes を使用すると、DefaultFinder で最新ハードウェア上で単一ランダム都市検索が一貫して 1 µs 未満で動作します。

アルゴリズムの詳細については、作者による説明 POLYGON_INDEXING.md を参照してください。

最終更新日 2026年5月2日

エコシステム