基於Geohash演算法切分OID4點碼

語言: CN / TW / HK

導讀

OID編碼就是光學辨別編碼,利用光識別與點讀發音技術,達到快速點讀,識別記憶的效果;本文主要介紹:Geohash演算法在點陣編碼中的應用。

什麼是Geohash

GeoHash是一種地址編碼方法,他能夠把二維的空間經緯度資料編碼成一個字串。

GeoHash具有以下特點:

1、GeoHash用一個字串表示經度和緯度兩個座標。在資料庫中可以實現在一列上應用索引;

2、GeoHash表示的並不是一個點,而是一個區域;

3、GeoHash編碼的字首可以表示更大的區域。

我們知道,經度範圍是東經180到西經180,緯度範圍是南緯90到北緯90,我們設定西經為負,南緯為負,所以地球上的經度範圍就是[-180, 180],緯度範圍就是[-90,90]。如果以本初子午線、赤道為界,地球可以分成4個部分。

如果緯度範圍[-90°, 0°)用二進位制0代表,(0°, 90°]用二進位制1代表,經度範圍[-180°, 0°)用二進位制0代表,(0°, 180°]用二進位制1代表,那麼地球可以分成如下4個部分:

如果在小塊範圍內遞迴對半劃分呢?

可以看到,劃分的區域更多了,也更精確了。

geohash演算法就是基於這種思想,劃分的次數更多,區域更多,區域面積更小了。

Geohash演算法

Geohash演算法一共有三步

1、將經緯度變成二進位制

比如這樣一個點(39.923201, 116.390705)

通過將經緯度編碼,給地理位置分割槽,根據需要的精度,按照上面的方法,逐級換算,最終能得到經、緯度的二進位制字串。

緯度的二進位制為:

10111000110001111001

經度116.390705的二進位制為:

11010010110001000100

2、合併經緯度

合併方法是將經度、緯度二進位制按照奇偶位合併:

11100 11101 00100 01111 00000 01101 01011 

00001

3、按照Base32進行編碼:

Base32編碼表的其中一種如下

是用0-9、b-z(去掉a, i, l, o)這32個字母進行編碼。具體操作是先將上一步得到的合併後二進位制轉換為10進位制資料,然後對應生成Base32碼。需要注意的是,將5個二進位制位轉換成一個base32碼。

上例最終得到的值為:

wx4g0ec1

基於 Geohash演算法對OID4範圍碼點進行切分

主要改動點:

1、根據geohash原理,將經緯度的極限值改為,OID4的碼值範圍

2、考慮到儲存數字比儲存字串效能更優,所以在得到指定層級切分後的二進位制字串後,將其轉換為十進位制值數字,而不是base32

3、碼值範圍比經緯度大很多,所以直接採用整數部分,忽略小數

核心程式碼:

將座標,按指定層級、指定範圍轉換為二進位制

private static void transBanaryCode(long xy, long startRange, long endRange, int level, int count, BiConsumer<Integer, Character> consumer){     
long middle = (startRange + endRange) >> 1;
char code = ONE_CHAR;
if(xy < middle){
code = ZERO_CHAR;
endRange = middle;
} else {
startRange = middle;
}
consumer.accept(count, code);
count++;
if(count >= level){
return;
}
transBanaryCode(xy, startRange, endRange, level, count, consumer);
}

十進位制轉二進位制

public static char[] toBinary(int num, int accuracy) {     
char[] chars = new char[accuracy];
int count = accuracy - 1;
while (num != 0) {
chars[count--] = num % 2 == 0 ? ZERO_CHAR : ONE_CHAR;
num = num >> 1;
}
while (count >= 0){
chars[count--] = ZERO_CHAR;
}
return chars;
}

根據編碼獲取指定層級、指定範圍所屬慢點的座標範圍

private static long[] getRange(int count, int level, long startRange, long endRange, Function<Integer, Character> function){     
long middle = (startRange + endRange) >> 1;
if(ZERO_CHAR == function.apply(count)){
endRange = middle;
} else {
startRange = middle;
}
count++;
if(count >= level){
return new long[]{startRange, endRange};
}
return getRange(count, level, startRange, endRange, function);
}

至此就實現了,根據座標,定位其所屬點碼塊;根據點碼塊,獲取其點碼範圍。

掃描下方二維碼新增 「好未來技術」 微信官方賬號

進入好未來技術官方交流群與作者實時互動~

(若掃碼無效,可通過微訊號 TAL-111111 直接新增)

- 也許你還想看 -

給非前端夥伴的前端知識學習引導

關於冪等設計

Python併發程式設計入門

基於雙模檢測的通話錄音質檢解決方案

我知道你“在看”喲!~