H3:用六边形铺满地球

H3: Tiling the Earth with Hexagons

频道:Uber Engineering · 时长:25:39 · 发布:2018-01-22 · 播放:53741

在 YouTube 观看

简介

Uber 工程团队的 Joseph Gilley 解释了为什么 Uber 使用六边形进行地理空间索引,并介绍了 H3,其开源分层网格系统。他涵盖了用例以及如何处理失真。

HN 为什么推荐

在关于 H3 的讨论中,HN 指出它详细解释了为什么六边形适合地图网格。

他们在同一个视频的后面深入探讨了很多细节。 — HN, 2019

数据库与存储 · 数据可视化与信息设计 · 算法与数据结构

中文字幕节选

接下来我们邀请市场团队的工程师Joseph Kaylee来谈谈 关于六边形的话题,谢谢,非常感谢,那么 大家好,我叫Joseph,我将要讨论的是 用六边形铺满地球。我先简要 介绍一下动态定价的历史背景,让大家了解我为什么谈论 六边形,在位置服务的聚会上谈论这个有点奇怪,但我们 相信它能解决非常重要的位置问题。所以在我铺垫之后 我会谈谈为什么我们选择六边形作为我们基础的地理空间 单元,然后希望你们能相信我们做出了正确的选择, 接着我会介绍我们构建的六边形地理空间索引库 叫做h3,我们会讲到这个。好的 我先简要介绍搜索的历史。最初我们的使命 在动态定价方面是确保车辆不短缺,这在 初期是个大问题,在高需求事件期间,比如节假日或 音乐会或体育赛事等活动,需求飙升,当需求 飙升时,乘客请求大量车辆,当我们调度这些车辆时 车辆供应,即可用于调度的空闲车辆急剧下降,如果降得太 低,我们就没有车了,正如Brent所说,这违背了我们的使命,我们的 目标是像自来水一样可靠,如果没有车可调度,我们 就失败了。所以我们的目标是不要缺车。我们引入了动态定价, 这是首次引入,在新年前夜效果很好,当时我们 有城市规模,大家都在外面聚会,每个人都需要乘车, 所以动态定价需求启动,激励司机上路 并使自己可用于调度,这样我们 就能满足这种需求高峰,这有效,但 它并没有完全解决问题,它解决了城市规模的问题,所以 之后我们真正需要的是在社区内不缺车,这些社区有 高度本地化的需求,比如体育赛事或音乐会或任何 特定于地点或区域的事情,甚至像高峰时段这样简单的事情,那里有 市中心和郊区,我们需要能够处理 这些需求高峰,确保我们在这些区域不缺车,所以我们 引入了社区动态定价或地理围栏,我们绘制了这些形状, 在社区的一般区域绘制地理围栏,我们认为那里会有 本地化需求,然后监控空闲车辆的供应和 这些区域乘客请求乘车的需求,我们能够识别出 需要供应空闲车辆的社区,这样我们就可以对 城市中的特定区域实施动态定价。通过这样做,我们可以告知 司机,这就是我在这里展示的,这是2014年的司机应用,我们 从上一张幻灯片改进了设计,我们需要展示 司机哪里有需求,这样搜索,你知道,告知他们 动态定价以及在这些热图中的位置,将允许他们定位自己 以获得这些调度,从而倍增他们的收入, 这有效,这非常有效地针对这些区域提供空闲车辆,我 构建了一个模拟来证明我们有四辆车在动态定价场景中, 激励他们上线,接下来会发生什么,他们朝着 动态定价区域移动,我真的喜欢那个模拟,这是你知道的基本证明,这 有效,无需提问或其他什么,所以但 它实际上并没有解决整个问题,它肯定有帮助,但我们 开始看到这个解决方案出现其他模式,比如 我的司机今天早上取消了我的行程,但取消是正常的,它 在每个城市都会发生,事情会发生,司机被允许这样做,那不是 问题,但我们看到的是个人重复取消,那不正常,

HN 上的讨论

他们在这次演讲中详细讨论了一些细节 [VIDEO]。我从他们的解释中了解到,六边形是地图网格的更好形状,因为它们是可以镶嵌的最复杂的形状(另外两种是三角形和正方形)。由于它们更接近圆形,单元格内的距离更稳定,而且计算从单元格中心到邻居的距离在六边形中也是稳定的。我认为六边形不那么常见的原因是与三角形或正方形相比,细分很难创建。Uber 通过将其细分为 7 个更小的六边形并倾斜,使它们以一些小的重叠覆盖更大的形状来解决这个问题。另一个大问题是失真,我从未想过这会是一个如此大的问题,但这确实有道理。他们在同一个视频的后面详细讨论了很多细节。 — mtrovo, 2019-07
在 h3 中选择六边形的关键原因——当你尝试对球形进行镶嵌时,六边形比正方形具有更低的失真。你只需要 12 个五边形就能完成这种镶嵌。——所有六个相邻单元格到单元格中心的距离都相等。Uber 试图解决的一个用例是在 Uber 应用上为司机显示哪些区域有高峰定价。使用 h3 和六边形,你可以说它看起来稍微好一点,渐变更平滑 [LINK]。我不确定 Uber 是否将 h3 用于其他用例,比如——查找位置最近的司机。请参阅 Uber 关于此的演示:[VIDEO] — poeticLLama, 2025-03
为什么是六边形?* 邻居遍历简单:三角形有 3 类邻居,正方形有 2 类邻居,六边形只有一类邻居!* 细分:正方形显然在这方面做得很好,但通过交替顺时针和逆时针旋转,并允许不完全完美的覆盖,它们可以用不同的分辨率/六边形大小进行分片。* 失真:“最重要的”基本上,这里的用例是保持基本单元外观的可视化。他们甚至选择将顶点位置放在水面上,以最小化陆地失真。来源:[VIDEO] 附言:正如 `contravariant` 所说,你无法用六边形来镶嵌球体,所以他们将其投影到一个二十面体上,在十二个顶点处使用五边形(位置在水面上)[VIDEO] — notroot, 2018-06

相关视频