geohash.php 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319
  1. <?php
  2. /**
  3. * Geohash generation class for php
  4. *
  5. * This file copyright (C) 2013 Bruce Chen (http://weibo.com/smcz)
  6. *
  7. * Author: Bruce Chen (weibo: @一个开发者)
  8. *
  9. */
  10. /**
  11. *
  12. * Encode and decode geohashes
  13. *
  14. * Find neighbors
  15. *
  16. */
  17. class Geohash {
  18. private $bitss = array(16, 8, 4, 2, 1);
  19. private $neighbors = array();
  20. private $borders = array();
  21. private $coding = "0123456789bcdefghjkmnpqrstuvwxyz";
  22. private $codingMap = array();
  23. public function Geohash() {
  24. $this->neighbors['right']['even'] = 'bc01fg45238967deuvhjyznpkmstqrwx';
  25. $this->neighbors['left']['even'] = '238967debc01fg45kmstqrwxuvhjyznp';
  26. $this->neighbors['top']['even'] = 'p0r21436x8zb9dcf5h7kjnmqesgutwvy';
  27. $this->neighbors['bottom']['even'] = '14365h7k9dcfesgujnmqp0r2twvyx8zb';
  28. $this->borders['right']['even'] = 'bcfguvyz';
  29. $this->borders['left']['even'] = '0145hjnp';
  30. $this->borders['top']['even'] = 'prxz';
  31. $this->borders['bottom']['even'] = '028b';
  32. $this->neighbors['bottom']['odd'] = $this->neighbors['left']['even'];
  33. $this->neighbors['top']['odd'] = $this->neighbors['right']['even'];
  34. $this->neighbors['left']['odd'] = $this->neighbors['bottom']['even'];
  35. $this->neighbors['right']['odd'] = $this->neighbors['top']['even'];
  36. $this->borders['bottom']['odd'] = $this->borders['left']['even'];
  37. $this->borders['top']['odd'] = $this->borders['right']['even'];
  38. $this->borders['left']['odd'] = $this->borders['bottom']['even'];
  39. $this->borders['right']['odd'] = $this->borders['top']['even'];
  40. //build map from encoding char to 0 padded bitfield
  41. for($i=0; $i<32; $i++) {
  42. $this->codingMap[substr($this->coding, $i, 1)] = str_pad(decbin($i), 5, "0", STR_PAD_LEFT);
  43. }
  44. }
  45. /**
  46. * Decode a geohash and return an array with decimal lat,long in it
  47. * Author: Bruce Chen (weibo: @一个开发者)
  48. */
  49. public function decode($hash) {
  50. //decode hash into binary string
  51. $binary = "";
  52. $hl = strlen($hash);
  53. for ($i=0; $i<$hl; $i++) {
  54. $binary .= $this->codingMap[substr($hash, $i, 1)];
  55. }
  56. //split the binary into lat and log binary strings
  57. $bl = strlen($binary);
  58. $blat = "";
  59. $blong = "";
  60. for ($i=0; $i<$bl; $i++) {
  61. if ($i%2)
  62. $blat=$blat.substr($binary, $i, 1);
  63. else
  64. $blong=$blong.substr($binary, $i, 1);
  65. }
  66. //now concert to decimal
  67. $lat = $this->binDecode($blat, -90, 90);
  68. $long = $this->binDecode($blong, -180, 180);
  69. //figure out how precise the bit count makes this calculation
  70. $latErr = $this->calcError(strlen($blat), -90, 90);
  71. $longErr = $this->calcError(strlen($blong), -180, 180);
  72. //how many decimal places should we use? There's a little art to
  73. //this to ensure I get the same roundings as geohash.org
  74. $latPlaces = max(1, -round(log10($latErr))) - 1;
  75. $longPlaces = max(1, -round(log10($longErr))) - 1;
  76. //round it
  77. $lat = round($lat, $latPlaces);
  78. $long = round($long, $longPlaces);
  79. return array($lat, $long);
  80. }
  81. private function calculateAdjacent($srcHash, $dir) {
  82. $srcHash = strtolower($srcHash);
  83. $lastChr = $srcHash[strlen($srcHash) - 1];
  84. $type = (strlen($srcHash) % 2) ? 'odd' : 'even';
  85. $base = substr($srcHash, 0, strlen($srcHash) - 1);
  86. if (strpos($this->borders[$dir][$type], $lastChr) !== false) {
  87. $base = $this->calculateAdjacent($base, $dir);
  88. }
  89. return $base . $this->coding[strpos($this->neighbors[$dir][$type], $lastChr)];
  90. }
  91. public function neighbors_bak($srcHash) {
  92. $geohashPrefix = substr($srcHash, 0, strlen($srcHash) - 1);
  93. //$neighbors['top'] = $this->calculateAdjacent($srcHash, 'top');
  94. //$neighbors['bottom'] = $this->calculateAdjacent($srcHash, 'bottom');
  95. //$neighbors['right'] = $this->calculateAdjacent($srcHash, 'right');
  96. //$neighbors['left'] = $this->calculateAdjacent($srcHash, 'left');
  97. //$neighbors['topleft'] = $this->calculateAdjacent($neighbors['left'], 'top');
  98. //$neighbors['topright'] = $this->calculateAdjacent($neighbors['right'], 'top');
  99. //$neighbors['bottomright'] = $this->calculateAdjacent($neighbors['right'], 'bottom');
  100. //$neighbors['bottomleft'] = $this->calculateAdjacent($neighbors['left'], 'bottom');
  101. $res[] = $neighbors['top'] = $this->calculateAdjacent($srcHash, 'top');
  102. $res[] = $neighbors['bottom'] = $this->calculateAdjacent($srcHash, 'bottom');
  103. $res[] = $neighbors['right'] = $this->calculateAdjacent($srcHash, 'right');
  104. $res[] = $neighbors['left'] = $this->calculateAdjacent($srcHash, 'left');
  105. $res[] = $neighbors['topleft'] = $this->calculateAdjacent($neighbors['left'], 'top');
  106. $res[] = $neighbors['topright'] = $this->calculateAdjacent($neighbors['right'], 'top');
  107. $res[] = $neighbors['bottomright'] = $this->calculateAdjacent($neighbors['right'], 'bottom');
  108. $res[] = $neighbors['bottomleft'] = $this->calculateAdjacent($neighbors['left'], 'bottom');
  109. return $res;
  110. }
  111. public function neighbors($srcHash) {
  112. $geohashPrefix = substr($srcHash, 0, strlen($srcHash) - 1);
  113. for($i=0; $i<32; $i++) {
  114. $neighbors[] = $geohashPrefix.substr($this->coding,$i,1);
  115. }
  116. return $neighbors;
  117. }
  118. /**
  119. * Encode a hash from given lat and long
  120. * Author: Bruce Chen (weibo: @一个开发者)
  121. */
  122. public function encode($lat, $long) {
  123. //how many bits does latitude need?
  124. $plat = $this->precision($lat);
  125. $latbits = 1;
  126. $err = 45;
  127. while($err > $plat) {
  128. $latbits++;
  129. $err /= 2;
  130. }
  131. //how many bits does longitude need?
  132. $plong = $this->precision($long);
  133. $longbits = 1;
  134. $err = 90;
  135. while($err > $plong) {
  136. $longbits++;
  137. $err /= 2;
  138. }
  139. //bit counts need to be equal
  140. $bits = max($latbits, $longbits);
  141. //as the hash create bits in groups of 5, lets not
  142. //waste any bits - lets bulk it up to a multiple of 5
  143. //and favour the longitude for any odd bits
  144. $longbits = $bits;
  145. $latbits = $bits;
  146. $addlong = 1;
  147. while (($longbits + $latbits) % 5 != 0) {
  148. $longbits += $addlong;
  149. $latbits += !$addlong;
  150. $addlong = !$addlong;
  151. }
  152. //encode each as binary string
  153. $blat = $this->binEncode($lat, -90, 90, $latbits);
  154. $blong = $this->binEncode($long, -180, 180, $longbits);
  155. //merge lat and long together
  156. $binary = "";
  157. $uselong = 1;
  158. while (strlen($blat) + strlen($blong)) {
  159. if ($uselong) {
  160. $binary = $binary.substr($blong, 0, 1);
  161. $blong = substr($blong, 1);
  162. } else {
  163. $binary = $binary.substr($blat, 0, 1);
  164. $blat = substr($blat, 1);
  165. }
  166. $uselong = !$uselong;
  167. }
  168. //convert binary string to hash
  169. $hash = "";
  170. for ($i=0; $i<strlen($binary); $i+=5) {
  171. $n = bindec(substr($binary, $i, 5));
  172. $hash = $hash.$this->coding[$n];
  173. }
  174. return $hash;
  175. }
  176. /**
  177. * What's the maximum error for $bits bits covering a range $min to $max
  178. */
  179. private function calcError($bits, $min, $max) {
  180. $err = ($max - $min) / 2;
  181. while ($bits--)
  182. $err /= 2;
  183. return $err;
  184. }
  185. /*
  186. * returns precision of number
  187. * precision of 42 is 0.5
  188. * precision of 42.4 is 0.05
  189. * precision of 42.41 is 0.005 etc
  190. *
  191. * Author: Bruce Chen (weibo: @一个开发者)
  192. */
  193. private function precision($number) {
  194. $precision = 0;
  195. $pt = strpos($number,'.');
  196. if ($pt !== false) {
  197. $precision = -(strlen($number) - $pt - 1);
  198. }
  199. return pow(10, $precision) / 2;
  200. }
  201. /**
  202. * create binary encoding of number as detailed in http://en.wikipedia.org/wiki/Geohash#Example
  203. * removing the tail recursion is left an exercise for the reader
  204. *
  205. * Author: Bruce Chen (weibo: @一个开发者)
  206. */
  207. private function binEncode($number, $min, $max, $bitcount) {
  208. if ($bitcount == 0)
  209. return "";
  210. #echo "$bitcount: $min $max<br>";
  211. //this is our mid point - we will produce a bit to say
  212. //whether $number is above or below this mid point
  213. $mid = ($min + $max) / 2;
  214. if ($number > $mid)
  215. return "1" . $this->binEncode($number, $mid, $max, $bitcount - 1);
  216. else
  217. return "0" . $this->binEncode($number, $min, $mid, $bitcount - 1);
  218. }
  219. /**
  220. * decodes binary encoding of number as detailed in http://en.wikipedia.org/wiki/Geohash#Example
  221. * removing the tail recursion is left an exercise for the reader
  222. *
  223. * Author: Bruce Chen (weibo: @一个开发者)
  224. */
  225. private function binDecode($binary, $min, $max) {
  226. $mid = ($min + $max) / 2;
  227. if (strlen($binary) == 0)
  228. return $mid;
  229. $bit = substr($binary, 0, 1);
  230. $binary = substr($binary, 1);
  231. if ($bit == 1)
  232. return $this->binDecode($binary, $mid, $max);
  233. else
  234. return $this->binDecode($binary, $min, $mid);
  235. }
  236. }