Google S2地图脚本

抱歉猴子——地图笑话实在没什么意义……

Cindy Murphy最近对Pokemon Go的法证探索（这里和这里）激发了猴子对Google S2地图库的进一步研究。S2库也被Uber、Foursquare和Google（大概）用于映射位置数据。因此，在我们的法证旅程中，识别和/或翻译任何可能遇到的S2编码位置工件可能很有用，对吧？用低声重复旅程……

在简要介绍S2如何表示经纬度数据之后，我们将演示几个多平台（Windows/Linux）Python转换脚本，用于解码/编码S2位置（使用sidewalklabs的s2sphere库）。

S2映射（理论部分）

本节的主要资源是：

Christian S. Perone关于S2的博客文章。
Octavian Procopiuc的“球面几何：Google的S2库”Google文档。

TLDR——可以将球面上的纬度/经度转换为64位整数。所得的64位整数称为cellid。

但是我们如何计算这个64位cellid呢？这是通过将我们的球面点（纬度，经度）投影到包围立方体的6个面之一上，然后使用希尔伯特曲线函数为指定的单元格大小指定网格位置来实现的。希尔伯特曲线上值接近的点在空间上也彼此接近。Christian博客文章中的这个图表更好地说明了这一点：

希尔伯特曲线上彼此接近的点具有相似的值。来源：Christian Perone的博客

在上面的图表中，希尔伯特曲线（深灰色线）从左下角到右下角（或反之亦然）。每个网格框包含一个Y形图案。底部的比例尺表示如果曲线像一根绳子一样被拉直的情况。

如果你现在想象网格变得更细/更小，但每个框仍然需要一个Y形，你可以看到更小的单元格网格大小需要曲线上点的更精细分辨率。因此，单元格/网格大小越小，存储位置所需的位数就越高。例如，级别2的单元格大小只需要4位，而最大级别30需要60位。级别30的单元格大小大约为0.48-0.93平方厘米，具体取决于纬度/经度。

有趣的事实：Uber显然使用级别12的单元格大小（每个单元格大约3.3到6.4平方公里）。

第二个有趣的事实：公制已经存在了100多年，所以不要再抱怨所有的公制测量了严厉地看着美国、缅甸和利比里亚最后的帝国卫队。

嗯……所以这是一个级别30 cellid的样子：

级别30 cellid结构。来源：Octavian Procopiuc的Google文档

前3位表示使用包围立方体的哪个面，剩余的60位用于存储希尔伯特曲线上的位置。注意：最后一位设置为1以标记希尔伯特定位位的结束。

当cellid转换为十六进制并去除最低有效零（如果存在）时，它们处于缩短的"token"形式。

例如1：cellid = 10743750136202470315（十进制）有一个token id = 0x951977D377E723AB

例如2：cellid = 9801614157982728192（十进制）= 0x8806542540000000。然后，16个十六进制数字可以缩短为token值"880654254"。要转换回原始的十六进制数字，我们不断向"880654254"添加最低有效零，直到它长达16位（即64位）。

分析人员应预期看到cellid或token id。这些可能是纯文本（例如JSON）或可能在SQLite数据库中。

注意：Windows计算器在处理大的无符号64位数字时很糟糕。根据这个，它限制在-9,223,372,036,854,775,808和9,223,372,036,854,775,807之间。因此，像10,743,750,136,202,470,315这样的数字在转换后使其返回不正确的十六进制表示。

这只猴子旋转了他的爪子一段时间，试图弄清楚为什么token转换似乎没有意义。FFs解决方案——使用Ubuntu计算器进行64位整数的十六进制转换。

脚本

编写了两个Python 2.7+脚本来处理S2转换，可以从我的GitHub这里获取。它们已经在运行Python 2.7.12的Windows 7和运行Python 2.7.6的Ubuntu x64 14.04上进行了测试。

s2-latlong2cellid.py将纬度、经度和cellid级别转换为64位Google S2 cellid。

s2-cellid2latlong.py将64位Google S2 cellid转换为纬度、经度和S2 cellid级别。

重要：这些脚本依赖于第三方的s2sphere Python库。用户可以通过以下方式安装：

1

pip install s2sphere

（在Windows上）和：

1

sudo pip install s2sphere

（在Ubuntu上）

这是s2-latlong2cellid.py的帮助文本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


python s2-latlong2cellid.py -h
Running s2-latlong2cellid.py v2016-08-12
usage: s2-latlong2cellid.py [-h] llat llong level

Converts lat, long and cellid level to a 64 bit Google S2 cellid

positional arguments:
  llat        Latitude in decimal degrees
  llong       Latitude in decimal degrees
  level       S2 cell level

optional arguments:
  -h, --help  show this help message and exit

这是s2-cellid2latlong.py的帮助文本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


python s2-cellid2latlong.py -h
Running s2-cellid2latlong.py v2016-08-12
usage: s2-cellid2latlong.py [-h] cellid

Convert a 64 bit Google S2 cellid to a lat, long and S2 cellid level

positional arguments:
  cellid      Google S2 cellid

optional arguments:
  -h, --help  show this help message and exit

测试

我们通过转到GoogleMaps并记下拉斯维加斯一个十字路口的经纬度开始测试。

选择一个点！任何点！

然后我们将该经纬度作为输入指定到s2-latlong2cellid.py脚本（级别设置为24）：

1
2
3
4


python s2-latlong2cellid.py 36.114574 -115.180628 24
Running s2-latlong2cellid.py v2016-08-12

S2 cellid = 9279882692622716928

然后我们将该cellid放入s2map.com：

级别24测试cellid在s2map.com上绘制。

注意：红色箭头由猴子添加以更好地显示绘制的cellid（它很小）。所以我们可以看到我们的s2-latlong2cellid.py使我们非常接近我们最初在GoogleMaps上指定的位置。

如果我们保持相同的经纬度坐标，但将cellid的级别从24降低到12，会发生什么？

1
2
3
4


python s2-latlong2cellid.py 36.114574 -115.180628 12
Running s2-latlong2cellid.py v2016-08-12

S2 cellid = 9279882742634381312

显然这是一个不同的cellid，因为它设置在不同的级别，但绘制的级别12 cellid现在有多远？

级别12测试cellid在s2map.com上绘制。

哇！单元格精度刚刚下降了一大堆。这个cellid的中心似乎与我们最初在GoogleMaps中设置的位置完全不同。它现在以Bellagio为中心，而不是十字路口。这大概是因为单元格大小现在更大，并且单元格的中心点相应地移动了。

为了确认这些发现，我们使用我们的级别24 cellid 9279882692622716928与s2-cellid2latlong.py一起使用。

1
2
3
4
5


python s2-cellid2latlong.py 9279882692622716928
Running s2-cellid2latlong.py v2016-08-12

S2 Level = 24
36.114574473973924 , -115.18062802526205

然后我们将这些坐标绘制在GoogleMaps上……

级别24测试cellid 9279882692622716928通过s2-cellid2latlong.py在GoogleMaps上绘制

即我们的s2-cellid2latlong.py脚本对于级别24似乎工作正常。

当我们使用级别12 cellid 9279882742634381312时，它看起来像这样：

1
2
3
4
5


python s2-cellid2latlong.py 9279882742634381312
Running s2-cellid2latlong.py v2016-08-12

S2 Level = 12
36.11195989469266 , -115.17705862118852

级别12测试cellid 9279882742634381312通过s2-cellid2latlong.py在GoogleMaps上绘制

这似乎证实了来自s2map.com的结果。对于相同的经纬度，更改cellid级别可以显著影响返回的（中心）经纬度。

我们还用少量其他cellid和经纬度/级别测试了我们的脚本与s2map.com，它们似乎一致。显然，时间限制不允许我们测试每一个可能的点。

最终想法

使用s2sphere库，我们能够创建一个Python脚本将经纬度和级别转换为S2 cellid（s2-latlong2cellid.py）。我们还创建了另一个脚本将S2 cellid转换为经纬度和级别（s2-cellid2latlong.py）。

cellid级别越高，位置越准确。你可以通过使用s2-cellid2latlong.py脚本找到cellid级别。

使用s2map.com绘制cellid是在地图上可视化cellid边界的最简单方法。然而，更高级别（>24）实际上变得不可见。

为了定位潜在的S2 cellid，我们可以使用搜索词如"cellid"或变体如"cellid="。如果它以纯文本存储（例如JSON），这些搜索词应该找到它。如果它被加密或存储为二进制整数，就没有这样的运气了。

虽然有其他S2 Python库，但这只猴子决定使用sidewalklabs s2sphere库，基于其可用的文档和无痛的跨平台支持（支持pip安装）。

其他Google S2 Python库包括： https://github.com/micolous/s2-geometry-library （如Christian的博客中所演示，也用于Gillware Pokemon脚本。这似乎是仅限Linux）和 https://github.com/qedus/sphere （有评论：“需要适当打包以与PIP一起使用”）

其他一些有趣的背景资料…… David Blackman（Foursquare）的采访文章

Matt Ranney（Uber首席系统架构师）关于"扩展Uber的实时市场平台"的视频演示（见18:15标记的S2内容）

Uber使用司机的手机作为备份数据源（声称已加密）

最后，创建Python转换脚本出人意料地简单，只需要几行代码。

看看有多少应用程序留下Google S2 cellid工件（希望是那些具有高cellid级别的）将会很有趣。希望这些脚本在寻找位置工件时能证明有用。例如，当分析人员找到一个cellid/token并希望将其映射到经纬度时，或者当分析人员希望为特定的经纬度、级别计算cellid/token时。

深入解析Google S2地图库与Python数字取证脚本

本文详细介绍了Google S2地图库的技术原理，包括如何将经纬度坐标转换为64位单元格ID的算法过程，并提供了两个实用的Python脚本用于S2单元格ID与经纬度之间的相互转换，适用于数字取证中的地理位置数据分析。

Google S2地图脚本

S2映射（理论部分）

脚本

测试

最终想法