区域内查找

﹏ヽ暗。殇╰゛Y 2023-02-14 10:17 5阅读 0赞

# [读书笔记-HBase in Action-第三部分应用-(2)GIS系统][-HBase in Action-_-_2_GIS] #

本章介绍用HBase存储、高效查询地理位置信息。

# Geohash空间索引 #

考虑LBS应用中常见的两个问题：1）查找离某地近期的k个地点。2）查找某区域内地点。

假设要用HBase实现高效查找，首先要考虑的是空间局部性（Spatial Locality），即位置上相近的点得物理存储在一起。

最简单的地理位置数据由两个维度组成：经度X和纬度Y。那么相相应最简单的Rowkey也能够由X和Y组成。Rowkey的有序性决定了数据首先依照经度X排序。再依照纬度Y排序，这样的方式最大的问题是经度值相等的A地点和B地点，可能纬度上相差十万八千里。

Geohash的解决思路是将经度和纬度以同样的权重构建空间索引。详细算法例如以下图：在经度范围\[-180。180\]，纬度范围\[-90,90\]内不断进行二分查找，假设值位于上半区则记标识位为1，位于下半区则记标识位为0。终于结果由经度纬度标识位交叉组成。

（注：在HBase中能够存储标识位的Base32编码串，每一个字符是5个bit位的编码结果）

![format_png][]

观察下面数据例子。可知geohash较好地反映了空间局部性：数据依照距离远近有序排列，距离相近的点geohash值有着很多其它的同样前缀。

![format_png 1][]

# 查找近期K个邻居 #

通过扫描geohash前缀能够高效解决这个问题1：查找离某地近期的k个地点。

当然，须要选择合适的位数来进行前缀匹配扫描。使用较少的位数能降低扫描次数，但可能会返回多余的数据，而使用较多的位数能可能每次扫描返回的结果优先，导致须要多次扫描。

然而，geohash值也存在一些问题，不能使用简单的前缀匹配扫描来查找邻居，例如以下图：有限长度的geohash值在地图上表示为一个矩形区域。位于中间的是dr5ruzb区域，它下方的邻居区域和它有着5位长度的同样前缀，而上方的三个区域尽管位置相邻，但仅仅有这2位长度的同样前缀。

![format_png 2][]

所以，假设要查找dr5ruzb的近期k个邻居，保险起见，能够一起查找它周围8个相邻区域的近期k个邻居。然后将全部查找到的点依照距离排序再得出终于结果。伪代码例如以下：takeN查找某个区域的近期n个点

![format_png 3][]

queryKNN则使用takeN查找四周8个相邻区域的近期n个点。终于再排序取值。

![format_png 4][]

来一个区域内查找的实例：在某某广场内有多少个wifi热点？解决思路分两步：

第一步。将区域内查找转化为对一系列geohash索引的扫描。

第二步。推断扫描到的坐标点是否包括在待查找区域多边形内。

工具方面。能够使用JTS Topology Suite([http://tsusiatsoftware.net/jts/main.html][http_tsusiatsoftware.net_jts_main.html]),JTS实现了常见几何对象、空间拓扑数据结构和操作算法。使用JTS查找待扫描的geohash坐标详细过程例如以下：

1.  依据待查找区域的各个顶点初始化多边形对象Geometry。并得出多边形对象的质心Centroid。
2.  对质心Centorid坐标进行geohash编码，精度取一定位数，假设geohash编码所代表的闭包已经覆盖了待查找多边形对象Geometry，那么直接返回质心作为待扫描的坐标。假设没有覆盖，继续步骤3。
3.  与前一节类似做法找到质心Centroid的四周8个相邻区域，闭包的范围扩大至包括这8个相邻区域顶点，再次推断闭包是否覆盖待查找区域。
    
     
    
    假设覆盖，那么这9个点一起作为待扫描的坐标返回；假设还是不能覆盖。返回到步骤2。使用更短的geohash编码长度来扩大位置范围，直到覆盖待查找区域为止。

得到待扫描geohash坐标后，使用前一节近期K个邻居查找算法在HBase表中扫描出一系列附近坐标点，最后过滤掉不在待查找区域范围内的坐标点。当中，过滤步骤能够通过Filter过滤器完毕。能利用上HBase的分布式并行处理能力，降低到client的传输数据量。

[-HBase in Action-_-_2_GIS]: https://www.cnblogs.com/clnchanpin/p/6860829.html
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTQwOTE5MjEyNTAwODc1?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTQwOTE5MjEyNzI4NjIx?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTQwOTE5MjEyODA2NDA1?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTQwOTE5MjEyNjM5Nzgx?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTQwOTE5MjEyOTA2NjA1?x-oss-process=image/format,png
[http_tsusiatsoftware.net_jts_main.html]: http://tsusiatsoftware.net/jts/main.html