Geohash算法介绍
参考文章：https://blog.csdn.net/usher_ou/article/details/122716877
GeoHash是空间索引的一种方式，其基本原理是将地球理解为一个二维平面，通过把二维的空间经纬度数据编码为一个字符串，可以把平面递归分解成更小的子块，每个子块在一定经纬度范围内拥有相同的编码。
以GeoHash方式建立空间索引，可以提高对空间poi数据进行经纬度检索的效率。
编码规则为：先将纬度范围(-90, 90)平分成两个区间(-90, 0)和(0, 90)，如果目标维度位于前一个区间，则编码为0，否则编码为1，然后根据目标纬度所落的区间再平均分成两个区间进行编码，以此类推，直到精度满足要求，经度也用同样的算法，对(-180, 180)依次细分，然后合并经度和纬度的编码，奇数位放纬度，偶数位放经度，组成一串新的二进制编码，按照Base32进行编码。
算法库
参考文章：https://blog.csdn.net/qq_41737172/article/details/118539350
var BASE32_CODES = "0123456789bcdefghjkmnpqrstuvwxyz"
var BASE32_CODES_DICT = {}
for (var i = 0; i < BASE32_CODES.length; i++) {
BASE32_CODES_DICT[BASE32_CODES.charAt(i)] = i
}
var ENCODE_AUTO = "auto"
var MIN_LAT = -90
var MAX_LAT = 90
var MIN_LON = -180
var MAX_LON = 180
/**
* Significant Figure Hash Length
*
* This is a quick and dirty lookup to figure out how long our hash
* should be in order to guarantee a certain amount of trailing
* significant figures. This was calculated by determining the error:
* 45/2^(n-1) where n is the number of bits for a latitude or
* longitude. Key is # of desired sig figs, value is minimum length of
* the
* @type Array
*/
// Desired sig figs: 0 1 2 3 4 5 6 7 8 9 10
var SIGFIG_HASH_LENGTH = [0, 5, 7, 8, 11, 12, 13, 15, 16, 17, 18]
/**
* Encode
*
* Create a Geohash out of a latitude and longitude that is
* `numberOfChars` long.
*
* @param {Number|String} latitude
* @param {Number|String} longitude
* @param {Number} numberOfChars
* @returns {String}
*/
var encode = function (latitude, longitude, numberOfChars) {
if (numberOfChars === ENCODE_AUTO) {
if (typeof latitude === "number" || typeof longitude === "number") {
throw new Error("string notation required for auto precision.")
}
var decSigFigsLat = latitude.split(".")[1].length
var decSigFigsLong = longitude.split(".")[1].length
var numberOfSigFigs = Math.max(decSigFigsLat, decSigFigsLong)
numberOfChars = SIGFIG_HASH_LENGTH[numberOfSigFigs]
} else if (numberOfChars === undefined) {
numberOfChars = 9
}
var chars = [],
bits = 0,
bitsTotal = 0,
hash_value = 0,
maxLat = MAX_LAT,
minLat = MIN_LAT,
maxLon = MAX_LON,
minLon = MIN_LON,
mid
while (chars.length < numberOfChars) {
if (bitsTotal % 2 === 0) {
mid = (maxLon + minLon) / 2
if (longitude > mid) {
hash_value = (hash_value << 1) + 1
minLon = mid
} else {
hash_value = (hash_value << 1) + 0
maxLon = mid
}
} else {
mid = (maxLat + minLat) / 2
if (latitude > mid) {
hash_value = (hash_value << 1) + 1
minLat = mid
} else {
hash_value = (hash_value << 1) + 0
maxLat = mid
}
}
bits++
bitsTotal++
if (bits === 5) {
var code = BASE32_CODES[hash_value]
chars.push(code)
bits = 0
hash_value = 0
}
}
return chars.join("")
}
/**
* Encode Integer
*
* Create a Geohash out of a latitude and longitude that is of "bitDepth".
*
* @param {Number} latitude
* @param {Number} longitude
* @param {Number} bitDepth
* @returns {Number}
*/
var encode_int = function (latitude, longitude, bitDepth) {
bitDepth = bitDepth || 52
var bitsTotal = 0,
maxLat = MAX_LAT,
minLat = MIN_LAT,
maxLon = MAX_LON,
minLon = MIN_LON,
mid,
combinedBits = 0
while (bitsTotal < bitDepth) {
combinedBits *= 2
if (bitsTotal % 2 === 0) {
mid = (maxLon + minLon) / 2
if (longitude > mid) {
combinedBits += 1
minLon = mid
} else {
maxLon = mid
}
} else {
mid = (maxLat + minLat) / 2
if (latitude > mid) {
combinedBits += 1
minLat = mid
} else {
maxLat = mid
}
}
bitsTotal++
}
return combinedBits
}
/**
* Decode Bounding Box
*
* Decode hashString into a bound box matches it. Data returned in a four-element array: [minlat, minlon, maxlat, maxlon]
* @param {String} hash_string
* @returns {Array}
*/
var decode_bbox = function (hash_string) {
var isLon = true,
maxLat = MAX_LAT,
minLat = MIN_LAT,
maxLon = MAX_LON,
minLon = MIN_LON,
mid
var hashValue = 0
for (var i = 0, l = hash_string.length; i < l; i++) {
var code = hash_string[i].toLowerCase()
hashValue = BASE32_CODES_DICT[code]
for (var bits = 4; bits >= 0; bits--) {
var bit = (hashValue >> bits) & 1
if (isLon) {
mid = (maxLon + minLon) / 2
if (bit === 1) {
minLon = mid
} else {
maxLon = mid
}
} else {
mid = (maxLat + minLat) / 2
if (bit === 1) {
minLat = mid
} else {
maxLat = mid
}
}
isLon = !isLon
}
}
return [minLat, minLon, maxLat, maxLon]
}
/**
* Decode Bounding Box Integer
*
* Decode hash number into a bound box matches it. Data returned in a four-element array: [minlat, minlon, maxlat, maxlon]
* @param {Number} hashInt
* @param {Number} bitDepth
* @returns {Array}
*/
var decode_bbox_int = function (hashInt, bitDepth) {
bitDepth = bitDepth || 52
var maxLat = MAX_LAT,
minLat = MIN_LAT,
maxLon = MAX_LON,
minLon = MIN_LON
var latBit = 0, lonBit = 0
var step = bitDepth / 2
for (var i = 0; i < step; i++) {
lonBit = get_bit(hashInt, (step - i) * 2 - 1)
latBit = get_bit(hashInt, (step - i) * 2 - 2)
if (latBit === 0) {
maxLat = (maxLat + minLat) / 2
} else {
minLat = (maxLat + minLat) / 2
}
if (lonBit === 0) {
maxLon = (maxLon + minLon) / 2
} else {
minLon = (maxLon + minLon) / 2
}
}
return [minLat, minLon, maxLat, maxLon]
}
function get_bit(bits, position) {
return (bits / Math.pow(2, position)) & 0x01
}
/**
* Decode
*
* Decode a hash string into pair of latitude and longitude. A javascript object is returned with keys `latitude`,
* `longitude` and `error`.
* @param {String} hashString
* @returns {Object}
*/
var decode = function (hashString) {
var bbox = decode_bbox(hashString)
var lat = (bbox[0] + bbox[2]) / 2
var lon = (bbox[1] + bbox[3]) / 2
var latErr = bbox[2] - lat
var lonErr = bbox[3] - lon
return {
latitude: lat,
longitude: lon,
error: { latitude: latErr, longitude: lonErr },
}
}
/**
* Decode Integer
*
* Decode a hash number into pair of latitude and longitude. A javascript object is returned with keys `latitude`,
* `longitude` and `error`.
* @param {Number} hash_int
* @param {Number} bitDepth
* @returns {Object}
*/
var decode_int = function (hash_int, bitDepth) {
var bbox = decode_bbox_int(hash_int, bitDepth)
var lat = (bbox[0] + bbox[2]) / 2
var lon = (bbox[1] + bbox[3]) / 2
var latErr = bbox[2] - lat
var lonErr = bbox[3] - lon
return {
latitude: lat,
longitude: lon,
error: { latitude: latErr, longitude: lonErr }
}
}
/**
* Neighbor
*
* Find neighbor of a geohash string in certain direction. Direction is a two-element array, i.e. [1,0] means north, [-1,-1] means southwest.
* direction [lat, lon], i.e.
* [1,0] - north
* [1,1] - northeast
* ...
* @param {String} hashString
* @param {Array} Direction as a 2D normalized vector.
* @returns {String}
*/
var neighbor = function (hashString, direction) {
var lonLat = decode(hashString)
var neighborLat = lonLat.latitude + direction[0] * lonLat.error.latitude * 2
var neighborLon = lonLat.longitude + direction[1] * lonLat.error.longitude * 2
neighborLon = ensure_valid_lon(neighborLon)
neighborLat = ensure_valid_lat(neighborLat)
return encode(neighborLat, neighborLon, hashString.length)
}
/**
* Neighbor Integer
*
* Find neighbor of a geohash integer in certain direction. Direction is a two-element array, i.e. [1,0] means north, [-1,-1] means southwest.
* direction [lat, lon], i.e.
* [1,0] - north
* [1,1] - northeast
* ...
* @param {String} hash_string
* @returns {Array}
*/
var neighbor_int = function (hash_int, direction, bitDepth) {
bitDepth = bitDepth || 52
var lonlat = decode_int(hash_int, bitDepth)
var neighbor_lat = lonlat.latitude + direction[0] * lonlat.error.latitude * 2
var neighbor_lon = lonlat.longitude + direction[1] * lonlat.error.longitude * 2
neighbor_lon = ensure_valid_lon(neighbor_lon)
neighbor_lat = ensure_valid_lat(neighbor_lat)
return encode_int(neighbor_lat, neighbor_lon, bitDepth)
}
/**
* Neighbors
*
* Returns all neighbors" hashstrings clockwise from north around to northwest
* 7 0 1
* 6 x 2
* 5 4 3
* @param {String} hash_string
* @returns {encoded neighborHashList|Array}
*/
var neighbors = function (hash_string) {
var hashstringLength = hash_string.length
var lonlat = decode(hash_string)
var lat = lonlat.latitude
var lon = lonlat.longitude
var latErr = lonlat.error.latitude * 2
var lonErr = lonlat.error.longitude * 2
var neighbor_lat, neighbor_lon
var neighborHashList = [
encodeNeighbor(1, 0),
encodeNeighbor(1, 1),
encodeNeighbor(0, 1),
encodeNeighbor(-1, 1),
encodeNeighbor(-1, 0),
encodeNeighbor(-1, -1),
encodeNeighbor(0, -1),
encodeNeighbor(1, -1)
]
function encodeNeighbor(neighborLatDir, neighborLonDir) {
neighbor_lat = lat + neighborLatDir * latErr
neighbor_lon = lon + neighborLonDir * lonErr
neighbor_lon = ensure_valid_lon(neighbor_lon)
neighbor_lat = ensure_valid_lat(neighbor_lat)
return encode(neighbor_lat, neighbor_lon, hashstringLength)
}
return neighborHashList
}
/**
* Neighbors Integer
*
* Returns all neighbors" hash integers clockwise from north around to northwest
* 7 0 1
* 6 x 2
* 5 4 3
* @param {Number} hash_int
* @param {Number} bitDepth
* @returns {encode_int"d neighborHashIntList|Array}
*/
var neighbors_int = function (hash_int, bitDepth) {
bitDepth = bitDepth || 52
var lonlat = decode_int(hash_int, bitDepth)
var lat = lonlat.latitude
var lon = lonlat.longitude
var latErr = lonlat.error.latitude * 2
var lonErr = lonlat.error.longitude * 2
var neighbor_lat, neighbor_lon
var neighborHashIntList = [
encodeNeighbor_int(1, 0),
encodeNeighbor_int(1, 1),
encodeNeighbor_int(0, 1),
encodeNeighbor_int(-1, 1),
encodeNeighbor_int(-1, 0),
encodeNeighbor_int(-1, -1),
encodeNeighbor_int(0, -1),
encodeNeighbor_int(1, -1)
]
function encodeNeighbor_int(neighborLatDir, neighborLonDir) {
neighbor_lat = lat + neighborLatDir * latErr
neighbor_lon = lon + neighborLonDir * lonErr
neighbor_lon = ensure_valid_lon(neighbor_lon)
neighbor_lat = ensure_valid_lat(neighbor_lat)
return encode_int(neighbor_lat, neighbor_lon, bitDepth)
}
return neighborHashIntList
}
/**
* Bounding Boxes
*
* Return all the hashString between minLat, minLon, maxLat, maxLon in numberOfChars
* @param {Number} minLat
* @param {Number} minLon
* @param {Number} maxLat
* @param {Number} maxLon
* @param {Number} numberOfChars
* @returns {bboxes.hashList|Array}
*/
var bboxes = function (minLat, minLon, maxLat, maxLon, numberOfChars) {
if (numberOfChars <= 0) {
throw new Error("numberOfChars must be strictly positive")
}
numberOfChars = numberOfChars || 9
var hashSouthWest = encode(minLat, minLon, numberOfChars)
var hashNorthEast = encode(maxLat, maxLon, numberOfChars)
var latLon = decode(hashSouthWest)
var perLat = latLon.error.latitude * 2
var perLon = latLon.error.longitude * 2
var boxSouthWest = decode_bbox(hashSouthWest)
var boxNorthEast = decode_bbox(hashNorthEast)
var latStep = Math.round((boxNorthEast[0] - boxSouthWest[0]) / perLat)
var lonStep = Math.round((boxNorthEast[1] - boxSouthWest[1]) / perLon)
var hashList = []
for (var lat = 0; lat <= latStep; lat++) {
for (var lon = 0; lon <= lonStep; lon++) {
hashList.push(neighbor(hashSouthWest, [lat, lon]))
}
}
return hashList
}
/**
* Bounding Boxes Integer
*
* Return all the hash integers between minLat, minLon, maxLat, maxLon in bitDepth
* @param {Number} minLat
* @param {Number} minLon
* @param {Number} maxLat
* @param {Number} maxLon
* @param {Number} bitDepth
* @returns {bboxes_int.hashList|Array}
*/
var bboxes_int = function (minLat, minLon, maxLat, maxLon, bitDepth) {
bitDepth = bitDepth || 52
var hashSouthWest = encode_int(minLat, minLon, bitDepth)
var hashNorthEast = encode_int(maxLat, maxLon, bitDepth)
var latlon = decode_int(hashSouthWest, bitDepth)
var perLat = latlon.error.latitude * 2
var perLon = latlon.error.longitude * 2
var boxSouthWest = decode_bbox_int(hashSouthWest, bitDepth)
var boxNorthEast = decode_bbox_int(hashNorthEast, bitDepth)
var latStep = Math.round((boxNorthEast[0] - boxSouthWest[0]) / perLat)
var lonStep = Math.round((boxNorthEast[1] - boxSouthWest[1]) / perLon)
var hashList = []
for (var lat = 0; lat <= latStep; lat++) {
for (var lon = 0; lon <= lonStep; lon++) {
hashList.push(neighbor_int(hashSouthWest, [lat, lon], bitDepth))
}
}
return hashList
}
function ensure_valid_lon(lon) {
if (lon > MAX_LON) return MIN_LON + (lon % MAX_LON)
if (lon < MIN_LON) return MAX_LON + (lon % MAX_LON)
return lon
}
function ensure_valid_lat(lat) {
if (lat > MAX_LAT) return MAX_LAT
if (lat < MIN_LAT) return MIN_LAT
return lat
}
// 静态网格相关计算方法拓展--------------------------------------------------------------------------------------start
export const NUM_OF_CHARS = 7 // 静态网格计算所用 geohash 位数
export const ORIGIN_GEOHASH = "v9s1psg" // 中国范围内计算静态网格所用的参考点hash值，在中国范围的左上角
// 获取水平方向下一个静态网格的左上角geohash，
// 入参：当前静态网格左上角geohash，视图右侧最大经度值，静态网格尺寸（10、14、20）
// 出参：水平方向下一个静态网格的左上角geohash
function getHorizontalNextStaticGeohash(hashString, maxLon, stepCount) {
if (!hashString) return false
const rightNextGeohash = neighbor(hashString, [0, stepCount])
const bBox = decode_bbox(rightNextGeohash) //[minLat, minLon, maxLat, maxLon]
if (bBox[1] > maxLon) {
return false
} else {
return rightNextGeohash
}
}
// 获取垂直方向下一个静态网格的左上角geohash
// 入参：当前静态网格左上角geohash，视图下方最小纬度值，静态网格尺寸（10、14、20）
// 出参：垂直方向下一个静态网格的左上角geohash
function getVerticalNextStaticGeohash(hashString, minLat, stepCount) {
if (!hashString) return false
const bottomNextGeohash = neighbor(hashString, [-stepCount, 0])
const bBox = decode_bbox(bottomNextGeohash) //[minLat, minLon, maxLat, maxLon]
if (bBox[2] < minLat) {
return false
} else {
return bottomNextGeohash
}
}
// 根据静态网格左上角geohash和静态网格尺寸，计算出静态网格的paths点阵围栏
function getStaticPaths(hashString, stepCount) {
const leftTop = hashString
// const lb = neighbor(hashString, [0, 9]);
// const rt = neighbor(hashString, [0, 9]);
const rightBottom = neighbor(hashString, [-(stepCount - 1), stepCount - 1])
const bBox_lt = decode_bbox(leftTop) //[minLat, minLon, maxLat, maxLon]
const bBox_rb = decode_bbox(rightBottom) //[minLat, minLon, maxLat, maxLon]
const minLat = bBox_rb[0]
const minLon = bBox_lt[1]
const maxLat = bBox_lt[2]
const maxLon = bBox_rb[3]
const paths = [
[minLat, minLon],
[minLat, maxLon],
[maxLat, maxLon],
[maxLat, minLon]
]
const center = [(maxLat + minLat) / 2, (maxLon + minLon) / 2]
return { paths, center }
}
// 获取视图范围内所有静态网格数据：hash：左上角geohash，paths：静态网格点阵围栏
function getStaticList(firstGeohash, maxLon, minLat, stepCount) {
let staticList = [{ hash: firstGeohash, ...getStaticPaths(firstGeohash, stepCount) }]
let current_h = firstGeohash
do {
let current_v = current_h
do {
current_v = getVerticalNextStaticGeohash(current_v, minLat, stepCount)
current_v &&
staticList.push({
hash: current_v,
...getStaticPaths(current_v, stepCount)
})
} while (current_v)
current_h = getHorizontalNextStaticGeohash(current_h, maxLon, stepCount)
current_h &&
staticList.push({
hash: current_h,
...getStaticPaths(current_h, stepCount)
})
} while (current_h)
// console.log(staticList);
return staticList
}
// 通过 经纬度坐标点 获取该点所在静态网格的左上角geohash
// 入参：计算点、静态网格尺寸
function getLeftTopGeohashOfStaticByPoint(LatLngPoint, stepCount) {
const { lat, lng } = LatLngPoint
const leftTopGeohash = encode(lat, lng, NUM_OF_CHARS) // wx4kpt1
const direction = getDirection(leftTopGeohash, stepCount) // [15,-11]
const firstGeohash = neighbor(leftTopGeohash, direction)
return firstGeohash
}
// 静态网格尺寸（10、14、20），计算当前geohash所在静态网格的位置
// 返回 direction [lat, lon] ---- [15,-11]
function getDirection(hashString, stepCount) {
const currentPonit = decode(hashString) //originPonit.latitude, originPonit.longitude
let rightNext = ORIGIN_GEOHASH
let rightNextPonit = decode(rightNext) //originPonit.latitude, originPonit.longitude
let count_h = 0 // 水平方向计数，当前geohash与originGeohash间隔的hash个数
do {
rightNext = neighbor(rightNext, [0, 1])
rightNextPonit = decode(rightNext)
count_h++
} while (rightNextPonit.longitude < currentPonit.longitude)
// console.log(count_h, count_h % stepCount);
let bottomNext = ORIGIN_GEOHASH
let bottomNextPonit = decode(bottomNext) //originPonit.latitude, originPonit.longitude
let count_v = 0 // 垂直方向计数，当前geohash与originGeohash间隔的hash个数
do {
bottomNext = neighbor(bottomNext, [-1, 0])
bottomNextPonit = decode(bottomNext)
count_v++
} while (bottomNextPonit.latitude > currentPonit.latitude)
// console.log(count_v, count_v % stepCount);
return [count_v % stepCount, -(count_h % stepCount)]
}
// 计算某矩形范围的左上角geohash所在静态网格的位置，
// 计算出该静态网格左上角第一个geohash，
// 从某矩形范围的左上角第一个静态网格开始，计算出 该矩形范围内的所有 静态网格数据
// 出参：[{hash, paths, center},...]
function getStaticListByBounds(LatLngBounds, stepCount) {
const { _northEast, _southWest } = LatLngBounds
const minLat = _southWest.lat
const maxLon = _northEast.lng
// 矩形范围左上角经纬度坐标点
const point = { lat: _northEast.lat, lng: _southWest.lng }
// 矩形范围左上角经纬度坐标点----计算----所在静态网格的左上角的geohash
const firstGeohash = getLeftTopGeohashOfStaticByPoint(point, stepCount)
// 矩形范围内所有的静态网的
const staticList = getStaticList(firstGeohash, maxLon, minLat, stepCount)
return staticList
}
// 根据静态网格的尺寸和左上角的geohash，计算出该静态网格内的所有geohash-----自测用
function getAllHashInStatic(hashString, stepCount) {
const hashList = []
// 水平方向 horizontal
for (let h = 0; h < stepCount; h++) {
// 垂直方向 vertical
for (let v = 0; v < stepCount; v++) {
// hashString反解出所在区域的 最大、最小经度 和 最大、最小纬度 [minLat, minLon, maxLat, maxLon]
const bBox = decode_bbox(hashString)
hashList.push({
hash: neighbor(hashString, [-v, h]),
paths: [
[bBox[0], bBox[1]],
[bBox[0], bBox[3]],
[bBox[2], bBox[3]],
[bBox[2], bBox[1]]
]
})
}
}
return hashList
}
// 静态网格相关计算方法拓展-----------------------------------------------------------------------------------------end
var geohash = {
ENCODE_AUTO: ENCODE_AUTO,
encode: encode,
encode_uint64: encode_int, // keeping for backwards compatibility, will deprecate
encode_int: encode_int,
decode: decode,
decode_int: decode_int,
decode_uint64: decode_int, // keeping for backwards compatibility, will deprecate
decode_bbox: decode_bbox,
decode_bbox_uint64: decode_bbox_int, // keeping for backwards compatibility, will deprecate
decode_bbox_int: decode_bbox_int,
neighbor: neighbor,
neighbor_int: neighbor_int,
neighbors: neighbors,
neighbors_int: neighbors_int,
bboxes: bboxes,
bboxes_int: bboxes_int,
getHorizontalNextStaticGeohash: getHorizontalNextStaticGeohash,
getVerticalNextStaticGeohash: getVerticalNextStaticGeohash,
getStaticPaths: getStaticPaths,
getStaticList: getStaticList,
getStaticListByBounds: getStaticListByBounds,
getDirection: getDirection,
getAllHashInStatic: getAllHashInStatic
}
//module.exports = geohash;
export default geohash
网友评论