java - 检查一个 geohash 是否与另一个 geohash 相交

Question

我有一个问题，我需要检查一个 geohash 是否落入具有动态半径/框的其他点的列表中。我目前正在做的是获取包含纬度/经度的 ortb 出价请求消息，并使用 redis 检查哪些 Activity 将与 ortb 的设备纬度/经度相匹配。如果我用固定半径查询，这很好用。问题是我想存储具有取决于人口密度的动态半径的 Activity 。

当前实现

在 redis 的 3.2 版本中，您可以使用内置命令将 geohashes 存储在 zset 中。这会将纬度/经度转换为 52 位 geohash。

使用 redis zset 功能，我可以查询也以半径传递的 Activity 列表。这将返回落入当前半径的 (0,n) 个 Activity 。

当前的实现缺陷

我遇到的问题是 Activity 具有动态半径。因此，例如 1 个 Activity 的半径可能为 3 英里，而另一个 Activity 的半径可能为 20 英里。因为我需要在一个半径内通过，所以我只通过了 5 英里，但这将排除来自 20 英里半径的请求。

可能改进的实现

我正在考虑这个问题，但不确定如何将其组合在一起。我认为更好的解决方案是在具有不同精度的排序集中拥有一个 geohashes 列表，本质上是为每个条目创建一个 geo hash 框。现在的问题是，我不能 100% 确定如何将它们组合在一起，或者它是否会按我想要的那样工作。我真的在寻找指导，如果这行得通，如果有人把这样的东西放在一起。我想我可以使用一个简单的排序集来完成此操作，然后将这些位屏蔽到排序集中条目的精度之下。但是，在处理大量 Activity 时，我可以看到这是一个问题。不确定它是否适用于多个不同精度的整数，或者 O 符号如何在这个整数上工作。由于我每天要处理大约 4+0 亿个请求，因此我需要它尽可能快。

注意事项

我希望我已经很好地解决了这个问题，因为它是一个描述起来相当复杂的问题。我也看过不少图书馆，但我认为它们不会为我解决问题。我已经开始编写自己的实现，但复杂性很快让我头疼。

我调查的原始库。允许单框查询。

https://github.com/kungfoo/geohash-java

这个看起来更有前途，但我不确定它是否真的能提供搜索多个框的能力。

https://github.com/davidmoten/geo

这是对地理定位的出色概述。不知道为什么它位于一个 IP，但我很高兴我找到了它。

http://23.239.12.206:8000/posts/2014-04-05-geohash-proximity-pt2.html

Answer 1

您可以尝试加权 voronoi 图和多边形测试中的点。一个简单快速的解决方案可以是位图，其中加权 voronoi 图的每个单元格都有一种颜色。然后简单地检查点的颜色。