GeoHash索引

左手的ㄟ右手 2022-06-13 04:12 141阅读 0赞

# GeoHash简介 #

GeoHash索引是一种基于B树索引，又结合了格网索引的思想的使用广泛的空间索引算法。GeoHash将空间位置编码为一串字符，通过字符串的比较可以得到空间的大致范围。这种编码方法起初被用于以唯一的URL标识地图上的点实体，而点实体一般是以经纬度标识的，所以问题就转变为如何使用URL标识经纬度坐标。下面举例说明GeoHash编码的具体实现步骤。设定武汉大学的经纬度坐标是(114.360734E, 30.541093N)，首先，可以通过如下算法对纬度30.54进行逼近编码:  
（1）对维度区间\[-90,90\]进行二分为\[-90,0)和\[0,90\]，称为左右区间，可以确定30.541093属于右区间\[0,90\]，给标记为1；  
（2）接着将区间\[0,90\]进行二分为 \[0,45)和\[45,90\]，可以确定30.541093属于左区间 \[0,45)，给标记为0；  
（3）递归上述过程30.541093，如果给定的纬度属于左区间，则记录0，如果属于右区间则记录1，这样随着算法的进行会产生一个序列101010110110111，序列的长度跟给定的区间划分次数有关。  
（4）同样的方法，对经度区间\[-180, 180\]进行编码，可以得到一个二进制序列110100010101001。  
（5）合并经纬度编码，偶数位放经度编码（第一位从0开始），奇数位放纬度编码，把两串编码组合生成新串11100 11001 00011 10011 01100 10111。  
（6）对合成的新的二进制串，每五位转成十进制数得到28,25,3,19,12,23，然后再进行Base32编码得到该经纬度的GeoHash编码为wt3mdr。

![GeoHash][]

对于GeoHash索引，需要明确的是：（1）GeoHash编码值表示的并不是一个点，而是一个矩形区域。落在该矩形区域的所有点都可以用该编码表示。（2）字符串越长，表示的范围越精确。编码的前缀可以表示更大的区域。例如wt3mdrff，它的前缀wt3mdr表示包含编码wt3mdrff在内的更大范围。 利用该特性可以进行临近点的搜索。首先根据用户当前坐标计算GeoHash值，然后取其前缀进行查询。（3）GeoHash将区域划分为一个个规则矩形，位于矩形边界两侧的两点，虽然十分接近，但编码会完全不同，因为它的编码方式从左上到右下突变时存在不连续的“跳跃”。

# 一个例子 #

下面的例子用到了一个第三方GeoHash库，我使用maven构建项目，pom文件如下：

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
      <modelVersion>4.0.0</modelVersion>
    
      <groupId>cn.tzy</groupId>
      <artifactId>geohash</artifactId>
      <version>0.0.1-SNAPSHOT</version>
      <packaging>jar</packaging>
    
      <name>geohash</name>
      <url>http://maven.apache.org</url>
    
      <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
      </properties>
    
      <repositories>
        <repository>
            <id>repo1.maven.org</id>
            <name>Maven Official Repository</name>
            <url>http://repo1.maven.org/maven2/</url>
        </repository>
      </repositories>
    
      <dependencies>
        <dependency>
          <groupId>junit</groupId>
          <artifactId>junit</artifactId>
          <version>4.12</version>
          <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>ch.hsr</groupId>
            <artifactId>geohash</artifactId>
            <version>1.3.0</version>
        </dependency>
      </dependencies>
    </project>

Java代码入下：

package cn.tzy.geohash;
    
    import java.util.ArrayList;
    import java.util.List;
    
    import ch.hsr.geohash.GeoHash;
    
    public class GeoHashEx {
    
        public static void main(String[] args) {
            double lat = 30.541093;
            double lon = 114.360734;
    
            int precision = 6;
            GeoHash geoHash = GeoHash.withCharacterPrecision(lat, lon, precision);
            String hashCode = geoHash.toBase32();
            System.out.print("GeoHash编码为：");
            System.out.println(hashCode);
            String binaryCode = geoHash.toBinaryString();
            System.out.print("对应的二进制编码为：");
            System.out.println(binaryCode);
            int length = binaryCode.length();
    
            System.out.print("对应的十进制编码为：");
            for(int i = 0; i < length; i+=5) { 
                String code = binaryCode.substring(i, i + 5);
                int num = Integer.valueOf(code, 2);
                System.out.print(num);
                System.out.print(" ");
            }
            System.out.println();
    
            char[] binaryCodes = binaryCode.toCharArray();
            List<Character> latCodes = new ArrayList<Character>();
            List<Character> lonCodes = new ArrayList<Character>();
            for (int i = 0; i < binaryCodes.length; i++) { 
                if (i % 2 == 0) {
                    lonCodes.add(binaryCodes[i]);
                } else {
                    latCodes.add(binaryCodes[i]);
                }
            }
            StringBuilder latCode = new StringBuilder();
            StringBuilder lonCode = new StringBuilder();
            for (Character ch : latCodes) {
                latCode.append(ch);
            }
            for (Character ch : lonCodes) {
                lonCode.append(ch);
            }
    
            System.out.print("维度编码为：");
            System.out.println(latCode.toString());
            System.out.print("经度编码为：");
            System.out.println(lonCode.toString());
        }
    }

运行结果如下：

GeoHash编码为：wt3mdr
    对应的二进制编码为：111001100100011100110110010111
    对应的十进制编码为：28 25 3 19 12 23 
    维度编码为：101010110110111
    经度编码为：110100010101001

[GeoHash]: /images/20220613/8fae72e940fe4b9eb46deebf45aca643.png