谷歌的S2,上球体,细胞和希尔伯特曲线几何

更新 - 2017年12月5日:谷歌刚刚宣布它将着手开发一个新的发布版本的S2库,惊人的消息,可以找到资源库在这里

谷歌的S2图书馆是真正的宝贝,不仅是因为它的功能对空间索引,还因为它是在4年多前发布的,并没有得到应有的重视图书馆。在S2库是由谷歌本身的谷歌地图,MongoDB的发动机也被使用Foursquare的,但你不会找到除了通过四方,一纸库中的任何地方的任何文件或物品谷歌演示和源代码注释。您还将很难找到该库的绑定,官方存储库缺少Python库的Swig文件,感谢一些叉我们可以使用Python语言的部分绑定(我将在这篇文章中使用它)。我听说谷歌现在正积极致力于图书馆,我们可能很快就会得到更多的细节时,他们对这个发布这项工作,但我决定分享一些例子关于图书馆,我认为这个库的原因是太酷了。

去细胞的路

您将在S2代码中看到这种“单元格”概念。这些单元是球体(在我们的例子中是地球,但不限于它)的层次分解,将其压缩为区域或点的表示。区域也可以近似使用这些相同的细胞,有一些不错的特点:

  • 它们结构紧凑(由64位整数表示)
  • 他们对地理特征有判断力
  • 它们是分层的(它们有级别,相似的级别有相似的领域)
  • 对任意区域的遏制查询是非常快

在S2库通过球体的点/区域伸入立方体开始,并且该立方体的每个面具有四叉树,其中该球面点被投影到。在此之后,一些发生转换(关于为什么,看到更多的细节谷歌演示),空间离散,然后单元格在a上枚举希尔伯特曲线,这就是为什么这个库是太好,希尔伯特曲线是空间填充曲线转换多个维度成有一个特殊的空间特征一个维:它保留了局部性。

希尔伯特曲线

希尔伯特曲线

希尔伯特曲线是空间填充曲线,这意味着它的范围覆盖了整个n维空间。要理解它是如何工作的,你可以想象一根长弦以一种特殊的方式排列在空间上,这样弦穿过空间的每个正方形,从而填充整个空间。要将一个二维点转换成希尔伯特曲线,你只需要选择弦上这个点所在的点。理解它的一个简单方法是使用这个迭代例子在这里您可以点击曲线的任何一点,它会显示在字符串中的点位于反之亦然。

在下面的图像,在非常beggining希尔伯特曲线的(串)的点也位于沿曲线亚洲金博宝的最开始(曲线是通过在图像的底部的长字符串表示):

希尔伯特曲线
希尔伯特曲线

现在,下面我们有更多的积分图像中,很容易看到希尔伯特曲线是如何保留空间局部性。可以注意到,点彼此更接近的曲线(在图1D表示,在底部的线)也都在2D维空间(在x,y平面)更近。然而,需要注意的是相反的说法并不完全正确,因为你可以有不密切的希尔伯特曲线2D点是相互靠近在x,y平面。

希尔伯特曲线
希尔伯特曲线

由于S2使用希尔伯特曲线枚举细胞,这意味着单元值接近的值也是在空间上彼此接近。当这一想法与层次分解组合,你有一个非常快速的框架,用于索引和查询操作。亚洲金博宝在我们开始与实例之实践,让我们看到了细胞是如何在64位整数表示。

如果你有兴趣在希尔伯特曲线,我真的建议这篇文章,它非常直观,并亚洲金博宝展示了曲线的一些性质。

该单元表达

正如我已经提到的,细胞有不同的水平和覆盖的不同区域。在S2库中可以找到30个层次的分解。单元格级别和它们可以覆盖的区域范围显示在我下面复制的幻灯片中的Google演示文稿中:

细胞区
细胞区

如您所见,S2几何图形的一个非常酷的亚洲金博宝结果是,地球上的每一个cm的图形都可以使用64位整数表示。

将细胞使用下面的架构表示:

单元表达模式
单元格表示模式(来自原始谷歌表示的图像)

第一个是表示叶单元,与通常用来表示点的最小区域的小区。正如可以看到,3个初始比特被保留用于存储其中球体的点被投影的立方体的面,则随后在希尔伯特曲线总是跟随一个“1”位,该单元的位置是将识别单元的电平的标记。

因此,要检查单元格的级别,所需要做的就是检查最后一个“1”位在单元格表示中的位置。检查包含性,检查一个单元格是否包含在另一个单元格中,您只需做一个前缀比较。这些操作是非常快的,他们是可能的只有希尔伯特曲线枚举和层次分解方法使用。

覆盖区域

所以,如果你想生成细胞覆盖的区域,可以使用该库的方法,其中指定的细胞的最大数量,要使用的最大细胞水平和最小细胞水平,那么算法将接近这个使用指定的参数的区域。在下面的例子中,我使用的S2库提取一些机器学习二进制特征使用水平15细胞:

15级单元-机器学习的二进制特征
细胞以15级 - 二元特征的机器学习

细胞区域,上面用透明的多边形超过我的城市感兴趣的整个区域的图像在这里表示。因为我既用于最低和最高级别的15级,细胞都覆盖区域类似的区域。如果更改的最低水平到8(因此允许使用较大的细胞的可能性),则算法将在某种程度上接近的区域,这将提供细胞的较小的数量,并且还试图保持近似精确像在下面的例子:

使用从8到15(水平)范围覆盖
使用从8到15(水平)范围覆盖

如你所见,我们现在有一个覆盖在中心使用较大的细胞和处理边界,我们有一个近似使用较小的细胞(还要注意四叉树)。

例子

*在本教程中我使用了Python从2.7绑定以下资料库。编译和安装的说明出现在存储库的readme中,所以我不在这里重复。

将纬度/经度点转换为单元格表示的第一步如下所示:

>>>进口s2 >>> latlng = s2.S2LatLng.FromDegrees(-30.043800, -51.140220) >>> cell = s2.S2CellId.FromLatLng > >0 >1 cell.level() 30 >3 >4 cell.id() 10743750136202470315 >5 >6 >7 cell. totoken () 951977d377e723ab

如您所见,我们首先创建类的一个对象S2LatLng公司代表纬度/经度点,然后我们将其送到S2CellId类构建单元表达。在此之后,我们可以得到类的水平和id。还有一种方法叫托肯将整数表示形式转换为压缩的字母数字表示形式,以后可以使用FromToken方法。

您还可以得到该单元格(它的上一级)的母细胞,并检查使用方法围堵如果一个细胞被另一个细胞包含:

>>>父= cell.parent()>>>打印parent.level()29 >>> parent.id()10743750136202470316 >>> parent.ToToken()951977d377e723ac >>> cell.contains(父)假>>> parent.contains(细胞)真

正如你所看到的,家长的水平是一个孩子的细胞上面(在我们的情况下,叶细胞)。该ID还除了电池和安全壳检查级别非亚洲金博宝常相似的是非常快(它只是检查母细胞的子单元的范围)。

这些单元格可以存储在数据库中,它们将在BTree索引上执行得非常好。要创建覆盖区域的单元格集合,可以使用S2RegionCoverer类等在下面的例子:

>>> region_rect = S2LatLngRect(S2LatLng.FromDegrees(-51.264871,-30.241701),S2LatLng.FromDegrees(-51.04618,-30.000003))>>>防尘罩= S2RegionCoverer()>>> coverer.set_min_level(8)>>>防尘罩.set_max_level(15)>>> coverer.set_max_cells(500)>>>覆盖= coverer.GetCovering(region_rect)

首先,我们定义了一个S2LatLngRect这是界定我们想要覆盖该区域的矩形。还有一些其他类,您可以使用(构建多边形为例)时,S2RegionCoverer与使用类作品S2Region类作为基类。定义的矩形后,我们实例S2RegionCoverer然后设置上述的最小/最大水平和我们想要产生近似的细胞的最大数量。

如果你想绘制覆盖,你可以使用Cartopy,身材匀称和matplotlib,就像下面的例子:

进口matplotlib.pyplot从S2进口* PLT从shapely.geometry进口多边形进口cartopy.crs作为CCRS导入cartopy.io.img_tiles作为cimgt PROJ = cimgt.MapQuestOSM()plt.figure(figsize =(20,20),DPI= 200)AX = plt.axes(投影= proj.crs)ax.add_image(PROJ,12)ax.set_extent([ -  51.411886,-50.922470,-30.301314,-29.94364])region_rect = S2LatLngRect(S2LatLng.FromDegrees( -51.264871,-30.241701),S2LatLng.FromDegrees(-51.04618,-30.000003))防尘罩= S2RegionCoverer()coverer.set_min_level(8)coverer.set_max_level(15)coverer.set_max_cells(500)覆盖= coverer.GetCovering(region_rect)geoms =[用于在覆盖CELLID:new_cell = S2Cell(CELLID)顶点= []为i的x范围(0,4):顶点= new_cell.GetVertex(ⅰ)经纬度= S2LatLng(顶点)vertices.append((latlng.lat().degrees(),latlng.lng()度()))=地理多边形(的顶点)geoms.append(GEO)打印 “总几何:{}”。格式(LEN(geoms))ax.add_geometries(geoms,ccrs.PlateCarree(),facecolor = '珊瑚',edgecolor = '黑',人PHA = 0.4)plt.show()

其结果将是下一个:

覆盖细胞。
覆盖细胞。

在S2 API中有很多东西,我真的建议您去探索和阅读源代码,这真的很有帮助。S2单元可用于索引和键值数据库,它可用于效率非常高的B树,甚至用于机器学习(这是我的情况),无论如何,它是一个非常有用的工具,您应该保存在工具箱中。我希望你喜欢这个小教程!亚洲金博宝

- Christian S. Perone

引用本文为:基督教S. Perone,“谷歌的S2,上球体,细胞和希尔伯特曲线的几何形状,”在亚洲金博宝未发现的地域,14/08/2015,//www.cpetem.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/

68个想法,“谷歌的S2,上球体,细胞和希尔伯特曲线几何”

  1. 这是投射到单位球面上的四叉树,加上利用希尔伯特曲线整数索引和小区之间的快速映射。

  2. 感谢这篇文章。帮了我很多。你把这个链接贴在我的问题堆栈交换。

    我已经运行在Java中获得cellIDs的同样的例子。它工作得很好。不过,我有一些问题,你可能能够回答或给方向是相同的:

    1) 单元格ID与geo hash有何不同?还是一样?

    2)可以路由与S2做什么?

    3) 当我试图用我的车辆/自行车数据做ETA(到达时间)分析时,我遇到了S2图书馆。我读到谷歌,foursquare,Uber使用这个库。我也提出了同样的问题:地理信息系统。堆垛机。用于gpx分析的com/questions/152719/postgis。几天前。你能想出解决同样问题的办法吗?

    1. 您好,我要说的是,S2是一类具有不同性质的地理散列的。Routing cannot be done with S2, S2 isn’t a algorithm for routing but for geometry on sphere, it can be used to generate a covering for a route but not for routing itself, for that I suggest you to look at the traditional routing algorithms like A-star, etc.
      你的问题是一个全开放的问题,您可以使用机器学习方法来近似它会使用历史记录去在一天的某个时间某个目的地的时候,有很多的可以使用的方法,但我不’t really know any benchmark (of results performance) between different models for that, try searching for papers about that, you should certainly find something related with your problem.

      1. 你说的很好——“它可以用来生成路由的覆盖物,但不能用于路由本身,”
        这意味着,如果我有一组点的沿着路线,我可以创建S2细胞覆盖。
        我必须从历史数据中预先计算单元格在一天的特定时间移动所需的时间。我可以把它们加起来得到。

        但是,什么是这里希尔伯特曲线的最好用?我仍然困惑w.r.t相同的usecases。可以S2细胞更多的信息在我的情况下,随着时间的推移得到充实,什么样的?和希尔伯特曲线可能给这个信息我更快的查找?

        1. 不知道,如果问题仍然在你的心中,但如果他们是:
          GeoHash和S2Cells的目的相同,它们将球形地理空间平面划分为分区/单元,同时保留局部性(这意味着2个地理空间相邻单元应具有“相似”的哈希代码/单元id)

          GeoHash将球体分为两部分,一部分编码为1,另一部分编码为0 (lvl1),获取其中一部分并继续执行相同的过程将产生一个具有更细粒度和更长的GeoHash代码的新lvl。
          此方法作为你看到的是线性在嵌入(LON,经纬度 - >地理散列码),这使得它超快速但缺乏准确性(主要是近赤道线),因此对细胞大方差尺寸(2个相邻的细胞可以在细胞区变化很大)

          S2Cell嵌入是更复杂的,边界与立方体的球体,将每个立方体表面4份用四叉树(以及每个部分到较小的部分,由此来S2细胞水平,这在树水平的概念)和最后枚举树树叶s2cell使用希尔伯特空间填充曲线编号(长码)。
          嵌入因此二次(利用),这是有点慢geohash但考虑从一个球体投影到一个立方体的交易和减少方差对于细胞面积(相邻细胞的大小相近的,聚合时得到更少的错误出现在每一个细胞,比较他们,这是一个“热点”吗?)亚洲金博宝

          希望这可以帮助!
          S2细胞是真棒,这是一个很大的一块!
          (这里提供的所有数据是“公开”,意思是,你可以从上面的介绍了一些巨大的努力演绎它的源代码:))

          还有一个资源,可以帮助是这样介绍:
          http://www.slideshare.net/danielmarcus/geo-data-analytics

          当做,
          丹尼尔·Marcous。

  3. “但是,请注意,相反的情况并不完全正确,因为在x,y平面上可以有彼此接近的二维点,而在希尔伯特曲线上则不太接近。”

    我注意到了这一点,想知道这意味着什么。这似乎会使一些行动“不对称”。这在实践中是个问题吗?

  4. “你不会找到除了通过四方,谷歌的演示和源代码注释的纸库中的任何地方的任何文件或物品。”

    嗨!我在哪里可以找到来自四方的文件?我心中已经在类S2CellId在Java版本了迷惑,怎么剂量它生成一个查找表递归,这太过分了位操作使代码难以阅读。

  5. 您好克里斯蒂安 - 我觉得从micolous库库是贴图坐标到错误的立体面,从而导致更多的钻石般的细胞形状。我没有用在华盛顿的一些坐标的封面。该micolous图书馆把他们的脸101,而s2map把它们放在100我贴的比较滑的位置:http://imgur.com/ymvw3o2

  6. 基督教,这是一个伟大的文章。我有一个question-是否在理想范围的S2细胞谎言呢,还是反映实际表面的轮廓?此外,由于它假定一个球体,有一个问题,因为地球的实际形状是扁平椭圆?

  7. 这太棒了。感谢克里斯蒂安,我很抱歉找不到一个词,除了神奇,真的可以恭维你这一点。

  8. S2可以用来做地理径向查询?例如,比方说,我有一组纬度/长,我想找出在那些与从给定位置给定距离。GeoAdd和GeoRadis Redis的命令的基本组合。

  9. 伟大的职位。

    如果你有在数据库中的纬度/经度数据的负载 - 你将如何去创造S2功能去从纬度/长到单元ID在给定的水平。

    我在google bigquery中有lat/long数据,我想知道是否可以使用UDF在BQ中获得s2功能,以避免将数据发送回python或其他地方进行处理。

    干杯
    安迪

  10. 很棒的帖子,Python 3.5和s2sphere(Python)的更新

    进口s2sphere为S2

    进口matplotlib.pyplot如PLT
    从shapely.geometry进口多边形
    进口cartopy.crs为加拿大遥感中心
    进口cartopy.io.img_tiles为cimgt

    项目= cimgt.OSM ()
    plt.figure(figsize =(20,20),DPI = 200)
    AX = plt.axes(投影= proj.crs)
    ax.add_image(PROJ,12)

    ax.set_extent ([-51.411886, -50.922470,
    -30.301314,-29.94364)

    region_rect = s2.LatLngRect(
    s2.LatLng.from_degrees (-51.264871, -30.241701),
    s2.LatLng.from_degrees(-51.04618,-30.000003))
    防尘罩= s2.RegionCoverer()
    coverer.min_level = 8
    coverer.max_level = 15
    coverer.max_cells = 500
    覆盖=掩护者,掩护者(区域)
    几何学= []

    用于盖盖cellid:
    new_cell = s2.Cell(CELLID)
    顶点= []
    对于范围(0,4)内的i:
    顶点= new_cell.get_vertex(我)
    经纬度= s2.LatLng.from_point(顶点)
    vertices.append (latlng.lat () .degrees latlng.lng () .degrees))
    地理=多边形(的顶点)
    geoms.append(GEO)
    打印( “总的几何结构:{}”。格式(LEN(geoms)))

    斧子。add_geometries(geoms, css . platecarree (), facecolor='coral', edgecolor='black', alpha=0.4)
    plt.show ()

  11. 嗨,基督徒,

    非常感谢这个博客帖子!

    由于没有S2Polygon对象的文档,我想知道需要为它提供什么参数。
    你能给我一个指示吗?
    谢谢你!

  12. 一亚洲金博宝切都贴发了一堆的感觉。然而,考虑这一点,假设你写一个真棒标题?
    我不是说你的信息不好,但是如果你加了一个吸引人们注意的标题呢?我是说谷歌
    s S2,球面上的几何,细胞和希尔伯特曲线|未知的地形是有点香草味的。亚洲金博宝

    你可以看一下雅虎的主页,并注意它们是如何制造新闻
    头条新闻让人们点击。您可以添加一个视频或相关的图片或
    二是让人们对你要说的话感兴趣。

    只是我的观点,它会给你的网站带来一点活力。

  13. 克里斯…我不知道为什么我花了这么长时间才找到这个好职位,但这对我是一个巨大的好处!!!

    非常感谢你!亚洲金博宝

  14. 由于基督教S. Perone的这篇文章。它帮助推行使用谷歌S2图书馆做我们的地理空间查询的,因为我们正在开发一个车队跟踪系统。那些有兴趣谁在一个非常酷的node.js执行请看看安德烈的打亚洲金博宝字稿实现谷歌S2的这很好地起到节点在github上(nodes2ts)。金宝博游戏网址https://金宝博游戏网址github.com/vekexasia/nodes2-ts

  15. 谢谢你的吉祥书面记录。它事实上曾经是一个享受的帐户了。

    一览复杂更提供从您愉快!由
    这样,我们如何能够接触?

  16. 非常感谢这个惊人的教程基督徒!

    但我有很多疑问。如果你能帮忙就太好了。

    在本例中,您从两点创建了一个矩形区域。这是怎么回事?
    我想从一千个点创建一个区域(latlong)。然后在细胞中分裂它。我该怎么做呢?

    我可以看到有一个方法addPoint在C ++库的rect,但没有在Python。
    你能帮我吗?非常感谢!

  17. 嗨,基督徒,
    非常感谢您的文章,真的很全面!我唯一的问题是如何确定合适的面(立方体的6个面)投射一个给定的(lat,lng)区域。
    最好,
    - ZP

    1. 编辑:
      我原来的印象是,每个区域(或点可能直线上的多个立方体的表面投射(那些地方是”看得见的),但似乎每个区域(或点)具有独特的投影立方体,as the projection of the line segment starting from the Earth center, passing through the region (or point) and ending at a point in one of the six cube faces (as shown in Google’s presentation:https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view#幻灯片=编号i15)。

  18. 与课本相比亚洲金博宝,在网上查找任何东西都要费很大的力气,因为我是在这个网页上找到这篇文章的。

  19. 嗨,基督徒,
    非常感谢这个很棒的博客。真是太棒了。

    我在那里我有用户的地理位置在城市的一个点一个用例,我需要找到是点的5公里半径内谁的用户。我可以代表用户的位置,并与S2小区ID的地步。不过,我将如何查询呢?
    我是否需要加载所有用户inmemory我的应用程序数据,然后使用图书馆找到我的目标用户。或者,我可以存储使用希尔伯特曲线,所以我们知道谁拥有更接近S2小区ID在距离更近彼此是地理点在S2的小区ID S2小区ID数据库,进行查询所有用户的数据。
    或者是有哪些我缺少任何其他方法
    我在这里先向您的帮助表示感谢

  20. 嗨,基督徒,
    非常感谢这个很棒的博客。真是太棒了。

    我在那里我有用户的地理位置在城市的一个点一个用例,我需要找到是点的5公里半径内谁的用户。我可以代表用户的位置,并与S2小区ID的地步。不过,我将如何查询呢?
    我是否需要加载所有用户inmemory我的应用程序数据,然后使用图书馆找到我的目标用户。或者,我可以存储使用希尔伯特曲线,所以我们知道谁拥有更接近S2小区ID在距离更近彼此是地理点在S2的小区ID S2小区ID数据库,进行查询所有用户的数据。
    或者是有哪些我缺少任何其他方法
    我在这里先向您的帮助表示感谢

    1. 嗨,
      看到这个博客很晚。亚洲金博宝我还等着回复您发布的问题。以任何机会做你解决问题。

  21. 你好,Christian,谢谢你的文章。我只是想提一下,我不得不使用' OSM '而不是' MapQuestOSM ',并在附加' geoms '时切换lat和lng的顺序

    而不是:
    “‘
    vertices.append((latlng.lat()。度(),
    latlng.lng()。度()))
    “‘
    我做了:
    “‘
    vertices.append((latlng.lng()。度(),
    latlng.lat()。度()))
    “‘

  22. 一亚洲金博宝切由沃斯非常合乎逻辑的。然而,这个是什么?
    如果你加了一点信息?我是不是暗示你的信息是不好的,但
    假设你添加一个帖子的标题,抓住民间的关注?
    我的意思是谷歌的S2,球体上的几何,细胞,希尔伯特·库尔维|未知领域有点简单。亚洲金博宝你可以浏览一下雅虎的首页
    看看他们是如何创造新闻头条的
    有人问津。您mignt添加视频ORR相关
    图片或两个对它感兴趣约你有什么读者
    说。在我看来,这会让你的博客更有趣一点。

  23. 你好。我看到你不经常更新你的网站。我知道写文章既费时又无聊。
    但是你知道,有一个工具,它允许您创建
    新文章使用现有的内容(从文章目录或从你的利基其他网站)?
    它做得很好。亚洲金博宝新文章是惟一的,并且通过了copyscape测试。
    你应该尝试miftolo的工具

  24. 对一些人来说,垃圾食品似乎是不可避免的,即使他们知道快餐不可避免的风险
    饮食疗法可能会引发。

  25. 任何人都得到一个JavaScript版本?我只是具有reg地图一个reg家伙,我想实现这。

  26. 宏伟的货物从你的男人。我明白你的东西以前到
    而你只是太大。其实我喜欢你这里获得什么,真的很喜欢你
    在说明和您说的方式。你让它娱乐,你还是照顾,以保持它明智。
    我迫不及待地想从你读得多。这个
    是一个非常棒的网站。

  27. 我一直在探索的一个位在这种房子的任何高品质的文章或博客帖子。
    在雅虎的探索中,我最终偶然发现了这个网站。
    读到这些信息,我很高兴告诉大家,我有一种非常棒的不可思议的感觉,我碰到了什么亚洲金博宝
    我需要。我最无可争议地将一定的不?吨省略此网站,请
    它看起来很有规律。

  28. 有用的信息。幸运的是我偶然发现了你的网站,我很惊讶为什么这次事故没有发生
    早点来!我给它加了书签。

  29. 基督徒,

    谢谢你把这些整理在一起,非常有用

    注意,您需要注意为每个包提供lats/lons的顺序,即,
    - s2取(lat, lon)顺序
    –shapely接受(x,y)或(lon,lat)顺序
    - cartopy的set_extent接受(x0, x1, y0, y1)或(lon0, lon1, lat0, lat1)顺序

    你的示例代码似乎遵循这一点,但在线条35-36你给S2(纬度,经度)以指定每个几何顶点匀称多边形,这应该是在(LON,LAT)为了代替。

    另外,我希望将整个s2geometry API公开给Python,而不是局限于google/s2geometry SWIG Python绑定提供的受限API覆盖范围。

    通过你的博客的启发,我开始是在旅程https://金宝博游戏网址github.com/bjlittle/docker-s2geometry

留下一个回复

您的电子邮件地址不会被公开。

本网站使用的Akismet,以减少垃圾邮件。了解如何处理评论数据