геолокация — создание списка геохешей с длиной геохеша / точностью до 4 в переполнении стека

Я был бы признателен, если бы кто-то мог направить меня в правильном направлении к поиску решения проблемы, с которой я столкнулся в связи с проблемой.

Мне нужно сгенерировать все возможные гео-хэши земного шара с точностью до 4, чтобы я мог создать таблицу поиска, чтобы отсеивать данные базы данных местоположений.

Мы планируем разделить базу данных на основе первых 4 префиксов гео-хеша, в Redis будет хранилище ключей с префиксом гео-хеша и соответствующим IP-адресом шарда.

Есть библиотеки, которые генерируют хэши и находят соседей, но как мне сгенерировать список всех возможных хэшей определенной точности в PHP?

Есть ли способ повторения всех соседей с использованием гео-хеш-библиотеки и генерации списка? Я не могу понять логику для этого.

Заранее спасибо.

ОБНОВЛЕНИЕ 07-11-0215: Это то, что я до сих пор …

<?php
require 'geohash.php';

$hash_column = array();
$hash_list = array();
$center_hash = encode(0,0,3);
array_push($hash_column,$center_hash);
$start_hash = $center_hash;
//generate a list of hashes above '7zz' looping around when reaching top edge.
while(true)
{
if(!in_array(adjacent($start_hash,'n'),$hash_column))
{
$buffer = adjacent($start_hash,'n');
array_push($hash_column, $buffer);
}else
{
break;
}
$start_hash = $buffer;
}
//iterate through column and get list of hashes to the left of it looping around when reaching edge.
foreach($hash_column as $hash)
{
array_push($hash_list,$hash);
while(true)
{
if(!in_array(adjacent($hash,'w'),$hash_list))
{
$buffer = adjacent($hash,'w');
array_push($hash_list, $buffer);
}else
{
break;
}
$hash = $buffer;
}
}

echo count($hash_list);

geohash.php выглядит следующим образом: я портировал его на PHP из js-кода Криса Венесса.

<?php

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
/* Geohash encoding/decoding and associated functions        (c) Chris Veness 2014 / MIT Licence  */
/* @author Anand Davis                                                                            */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */

/* (Geohash-specific) Base32 map */
$base32Chars = array(
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g',
'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
);


/**
* Encodes latitude/longitude to geohash, either to specified precision or to automatically
* evaluated precision.
*
* @param   {number} lat - Latitude in degrees.
* @param   {number} lon - Longitude in degrees.
* @param   {number} [precision] - Number of characters in resulting geohash.
* @returns {string} Geohash of supplied latitude/longitude.
*
* @example
*     encode(52.205, 0.119, 7);
*/
function encode($lat, $lon, $precision = NULL) {
// infer precision?
if (empty($precision)) {
// refine geohash until it matches precision of supplied lat/lon
for ($p=1; $p<=12; $p++) {
$hash = encode($lat, $lon, $p);
$posn = decode($hash);
if ($posn[0]==$lat && $posn[1]==$lon) return $hash;
}
}

//$lat = (int)$lat;
//$lon = (int)$lon;
//$precision = (int)$precision;

if (!is_numeric($lat) || !is_numeric($lon) || !is_numeric($precision)) echo 'Invalid geohash';

$idx = 0; // index into base32 map
$bit = 0; // each char holds 5 bits
$evenBit = True;
$geohash = '';

$latMin =  -90;
$latMax =  90;
$lonMin = -180;
$lonMax = 180;

while (strlen($geohash) < $precision) {
if ($evenBit) {
// bisect E-W longitude
$lonMid = ($lonMin + $lonMax) / 2;
if ($lon > $lonMid) {
$idx = $idx*2 + 1;
$lonMin = $lonMid;
} else {
$idx = $idx*2;
$lonMax = $lonMid;
}
} else {
// bisect N-S latitude
$latMid = ($latMin + $latMax) / 2;
if ($lat > $latMid) {
$idx = $idx*2 + 1;
$latMin = $latMid;
} else {
$idx = $idx*2;
$latMax = $latMid;
}
}
if ($evenBit)
{
$evenBit = False;
}else
{
$evenBit = True;
}

if ($bit < 4) {
$bit++;
} else {
$geohash .= $GLOBALS['base32Chars'][$idx];
$bit = 0;
$idx = 0;
}

}

return $geohash;
}


/**
* Decode geohash to latitude/longitude (location is approximate centre of geohash cell,
*     to reasonable precision).
*
* @param   {string} geohash - Geohash string to be converted to latitude/longitude.
* @returns {{{number}lat, {number}lon}} (Center of) geohashed location.
*
* @example
*     decode('u120fxw');
*/
function decode($geohash) {

$bounds = bounds($geohash); // <-- the hard work
// now just determine the centre of the cell...

$latMin = $bounds[0][0]; //sw lat
$lonMin = $bounds[0][1]; //sw lon
$latMax = $bounds[1][0]; //ne lat
$lonMax = $bounds[1][1]; //ne lon

// cell centre
$lat = ($latMin + $latMax)/2;
$lon = ($lonMin + $lonMax)/2;

// round to close to centre without excessive precision: ⌊2-log10(Δ°)⌋ decimal places
$lat = round($lat,floor(2-log($latMax-$latMin)/log(10)));
$lon = round($lon,floor(2-log($lonMax-$lonMin)/log(10)));

return array( (float)$lat, (float)$lon);
}


/**
* Returns SW/NE latitude/longitude bounds of specified geohash.
*
* @param   {string} geohash - Cell that bounds are required of.
* @returns {{sw: {lat: number, lon: number}, ne: {lat: number, lon: number}}}
*/
function bounds($geohash) {
if (strlen($geohash) == 0) echo 'Invalid geohash';

$geohash = strtolower($geohash);

$evenBit = True;
$latMin =  -90;
$latMax =  90;
$lonMin = -180;
$lonMax = 180;

for ($i=0; $i<strlen($geohash); $i++) {
$chr = $geohash[$i];
$idx = array_search($chr, $GLOBALS['base32Chars']);
if ($idx == -1) echo 'Invalid geohash';

for ($n=4; $n>=0; $n--) {
$bitN = $idx >> $n & 1;
if ($evenBit) {
// longitude
$lonMid = ($lonMin+$lonMax) / 2;
if ($bitN == 1) {
$lonMin = $lonMid;
} else {
$lonMax = $lonMid;
}
} else {
// latitude
$latMid = ($latMin+$latMax) / 2;
if ($bitN == 1) {
$latMin = $latMid;
} else {
$latMax = $latMid;
}
}

if ($evenBit)
{
$evenBit = False;
}else
{
$evenBit = True;
}
}
}

$bounds = array(
array($latMin, $lonMin),
array($latMax, $lonMax));

return $bounds;
}

/**
* Determines adjacent cell in given direction.
*
* @param   geohash - Cell to which adjacent cell is required.
* @param   dirn - Direction (N/S/E/W).
* @returns {string} Geocode of adjacent cell.
*/
function adjacent($geohash, $dirn) {
// based on github.com/davetroy/geohash-js

$geohash = strtolower($geohash);
$dirn = strtolower($dirn);

if (strlen($geohash) == 0) echo 'Invalid geohash';
//if (!('n' === $dirn)) echo 'Invalid direction';

$neighbour = array(
'n'=> array('even'=>'p0r21436x8zb9dcf5h7kjnmqesgutwvy', 'odd'=>'bc01fg45238967deuvhjyznpkmstqrwx' ),
's' => array( 'even'=>'14365h7k9dcfesgujnmqp0r2twvyx8zb', 'odd'=>'238967debc01fg45kmstqrwxuvhjyznp' ),
'e'=> array('even'=>'bc01fg45238967deuvhjyznpkmstqrwx', 'odd'=>'p0r21436x8zb9dcf5h7kjnmqesgutwvy' ),
'w'=> array('even'=> '238967debc01fg45kmstqrwxuvhjyznp', 'odd'=>'14365h7k9dcfesgujnmqp0r2twvyx8zb' )
);
$border = array(
'n'=> array( 'even'=>'prxz', 'odd'=>'bcfguvyz' ),
's'=> array('even'=> '028b',  'odd'=>'0145hjnp' ),
'e'=> array('even'=>'bcfguvyz', 'odd'=>'prxz'),
'w'=> array('even'=>'0145hjnp', 'odd'=>'028b')
);

$lastCh = substr($geohash, -1);    // last character of hash
$base = substr($geohash, 0, strlen($geohash) - 1);; // hash without last character
if(strlen($geohash) % 2 == 0)
{
$type = 'even';
}else
{
$type = 'odd';
}

// check for edge-cases which don't share common prefix
if (strpos($border[$dirn][$type],$lastCh) !== False && $base != '') {
$base = adjacent($base, $dirn);
}

// append letter for dirn to parent
return $base . $GLOBALS['base32Chars'][strpos($neighbour[$dirn][$type],$lastCh)];
}


/**
* Returns all 8 adjacent cells to specified geohash.
*
* @param   {string} geohash - Geohash neighbours are required of.
* @returns {{n,ne,e,se,s,sw,w,nw: string}}
*/
function neighbours($geohash) {
return array(
'n'=>  adjacent($geohash, 'n'),
'ne'=> adjacent(adjacent($geohash, 'n'), 'e'),
'e'=> adjacent($geohash, 'e'),
'se'=> adjacent(adjacent($geohash, 's'), 'e'),
's'=> adjacent($geohash, 's'),
'sw'=> adjacent(adjacent($geohash, 's'), 'w'),
'w'=>  adjacent($geohash, 'w'),
'nw'=> adjacent(adjacent($geohash, 'n'), 'w')
);
}

Проблема заключается в том, что он генерирует массив с 30504 элементами, но с точностью до геохеша 3 предполагается, что он имеет 256 (хеши по горизонтали) * 128 (хеши по вертикали) = 32768 хешей.

Я не знаю, где я иду не так?