技术白皮书

文档

参考文档

技术白皮书

引言

最初，tzf 是为需要将坐标转换为时区的后端服务设计的，主要用于地理和天气服务场景。

随着项目的发展，我们需要添加 Python 支持，因为当时 timezonefinder 在边界附近的查询速度无法满足我们的需求。

这便是 tzf (Go)、tzfpy (Python) 和 tzf-rs (Rust) 诞生的原因。

设计目标如下：

将坐标转换为时区名称。
性能优于完美精度。
至少支持 Go 和 Python。（Rust 是因 PyO3 生态而开发的。）
后端服务的最小化分发/二进制体积。

本白皮书涵盖 tzf 中使用的五项核心技术：

拓扑感知简化（数据管线第一阶段）
共享边去重（数据管线第二阶段）
Polyline 编码（数据管线第三阶段）
瓦片索引（FuzzyFinder 预索引）
YStripes 空间索引

数据管线概览

原始时区边界数据以 Protocol Buffers 二进制（Timezones 格式）存在，约 96 MB。两条并行的离线管线产生三个分发文件（文件名均带有 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 分发。

第一阶段——拓扑感知简化

背景：逐多边形方案及其局限

原始 GeoJSON 多边形数据首先被转换为使用 Protocol Buffers 的二进制编码。其 schema 如下：

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 算法从共享边界两侧移除不同的中间点，两个多边形最终得到略有不同的边形状——产生原始数据中不可见但在简化后出现的间隙和重叠。DefaultFinder 的 ±0.02° 空间容差回退是对此问题的临时变通方案，而非真正的修复。

拓扑感知方案

修复方法是将 RDP 简化集成到拓扑感知的管线中，该管线在所有相邻多边形上一致地处理共享边界。在任何简化进行之前，先对所有多边形环构建拓扑图：

标准化环绕方向（外环逆时针，孔顺时针），使相邻环以相反方向遍历共享边界——这是使反向边匹配可靠的关键。
移除零长度边（部分环中存在重复的相邻顶点会破坏共享边检测）。
对齐 T 形交汇顶点：如果拓扑节点落在相邻边的内部，在分析开始前将其作为新顶点插入。
通过规范键哈希检测共享边。将每个线段分类：
- 固定点：三个或更多环交汇处的顶点。这些锚点不能移动。
- 共享线段内部：可以简化，但只简化一次——所有伙伴环复用同一简化结果。
- 非共享：独立简化（海岸线、独立边界）。
飞地环（形状等同于内部时区外环的孔）特殊处理：两个伙伴环均旋转至字典序最小顶点（规范起点）并进入共享简化缓存，保证输出一致而无需任何固定顶点。
回退：对于简化后点数少于 3 个唯一点、产生零长度边或（对于小环 ≤ 100 点）自交的环，回退使用原始的未修改输入环。

此拓扑感知方案于 2026 年春季完成。其实现详见 internal/topology/README.md。

结果：减少 86% 的点数（8 M → 1.09 M 点），且共享边界拓扑一致—— 无间隙，无意外重叠。

第二阶段——共享边去重

简化后，较长的共享边界段仍在文件中出现两次—— 每个相邻时区环各一次。deduplicatetzpb 工具将 Timezones 二进制转换为 TopoTimezones 格式，每个共享段只存储一次：

一个全局 SharedEdge 库按 ID 索引每个长共享边界段。
每个环变为一系列 RingSegment 条目：要么是较短的内联点序列（≤ 10 点），要么是对某个 SharedEdge ID 的正向/反向引用。

环绕方向标准化必须在去重之前运行，原因与简化之前相同：只有当相邻环以相反方向遍历其共享边界时，去重才能将它们识别为同一条边（而不是归类为争议领土的同向重叠）。

结果（简化后数据）：额外约 20% 的体积缩减（12.5 MB → 10.0 MB）。TopoTimezones 格式还可以干净地往返转换回完整多边形，这使其成为下游工具的便利交换格式。

第三阶段——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 │
│           │           │           │
│           │           │           │
└───────────┴───────────┴───────────┘

这种类四叉树布局确保父瓦片恰好包含四个子瓦片，可以实现无间隙聚合：

每个时区独立处理。对于每个时区：

在索引缩放级别（缩放级别 13）生成触及该多边形的所有瓦片。
仅保留完全位于多边形内部的瓦片（EnsureInside）。
删除边界瓦片——即 8 个相邻瓦片中有任何一个不在瓦片集中的瓦片。此步骤执行两次（dropEdgeLayer = 2），从内部边界剥离两层，使靠近多边形边缘的瓦片被排除。
通过 MergeUp 将剩余瓦片向上合并到聚合缩放级别（缩放级别 3），然后对合并结果再次执行 EnsureInside。

由于每个时区是独立索引的，一个同时位于多个时区内部的瓦片会出现在所有相关时区的索引条目中。内存中的存储结构为 map[Tile][]string，因此一个瓦片可以返回多个时区名称。这处理了 Asia/Shanghai 和 Asia/Urumqi 等共享区域的情况，它们重叠的内部区域会在两个时区的预索引条目中生成匹配的瓦片。

查询时，从最粗的缩放级别（3）到最细的（13）依次查找，返回第一个匹配瓦片的所有时区名称：

如果找到匹配瓦片 → 返回其时区列表（无歧义的内部瓦片返回一个，共享区域瓦片返回多个）。
如果没有瓦片匹配（边界区域、海岸线、稀疏区域）→ 预索引返回空结果。

FuzzyFinder 仅使用此预索引。GetTimezoneNames 返回完整列表； GetTimezoneName 返回第一个条目。对于未覆盖区域，返回错误而非猜测——调用者负责处理空结果情况。

DefaultFinder 自动处理此问题：首先尝试瓦片预索引；如果无结果返回，则回退到通过 Finder 进行完整多边形查询。这使其对所有坐标正确，同时为大多数世界城市查询保持预索引的速度。

YStripes 索引

自 tzf v1.1.0 (Go) 和 tzf-rs v1.2.0 (Rust) 起，多边形级的点在多边形内测试使用 YStripes 空间索引，该索引移植自 Josh Baker 的 tidwall/tg 项目。

YStripes 通过预分区每个多边形的边为水平条带来改进朴素的射线投射。对于查询点，仅测试相关条带中的边，大幅减少每个多边形的工作量，且没有完整空间树的开销。

默认启用；禁用（例如在内存受限的环境中）可通过 Rust 的 FinderOptions 实现。使用 YStripes 后，配合 DefaultFinder 在现代硬件上单次随机城市查询持续低于 1 µs。

算法详情请参见作者在 POLYGON_INDEXING.md 中的解释。

最后更新于 May 2, 2026

生态系统