1<?php
2/**
3 * PHP Geometry GeoHash encoder/decoder.
4 *
5 * @author prinsmc
6 * @see http://en.wikipedia.org/wiki/Geohash
7 *
8 */
9class GeoHash extends GeoAdapter{
10
11  /**
12   * base32 encoding character map.
13   */
14  private $table = "0123456789bcdefghjkmnpqrstuvwxyz";
15
16  /**
17   * array of neighbouring hash character maps.
18   */
19  private $neighbours = array (
20      // north
21      'top' => array (
22          'even' => 'p0r21436x8zb9dcf5h7kjnmqesgutwvy',
23          'odd' => 'bc01fg45238967deuvhjyznpkmstqrwx'
24      ),
25      // east
26      'right' => array (
27          'even' => 'bc01fg45238967deuvhjyznpkmstqrwx',
28          'odd' => 'p0r21436x8zb9dcf5h7kjnmqesgutwvy'
29      ),
30      // west
31      'left' => array (
32          'even' => '238967debc01fg45kmstqrwxuvhjyznp',
33          'odd' => '14365h7k9dcfesgujnmqp0r2twvyx8zb'
34      ),
35      // south
36      'bottom' => array (
37          'even' => '14365h7k9dcfesgujnmqp0r2twvyx8zb',
38          'odd' => '238967debc01fg45kmstqrwxuvhjyznp'
39      )
40  );
41
42  /**
43   * array of bordering hash character maps.
44   */
45  private $borders = array (
46      // north
47      'top' => array (
48          'even' => 'prxz',
49          'odd' => 'bcfguvyz'
50      ),
51      // east
52      'right' => array (
53          'even' => 'bcfguvyz',
54          'odd' => 'prxz'
55      ),
56      // west
57      'left' => array (
58          'even' => '0145hjnp',
59          'odd' => '028b'
60      ),
61      // south
62      'bottom' => array (
63          'even' => '028b',
64          'odd' => '0145hjnp'
65      )
66  );
67
68  /**
69   * Convert the geohash to a Point. The point is 2-dimensional.
70   * @return Point the converted geohash
71   * @param string $hash a geohash
72   * @see GeoAdapter::read()
73   */
74  public function read($hash, $as_grid = FALSE) {
75    $ll = $this->decode($hash);
76    if (!$as_grid) {
77      return new Point($ll['medlon'], $ll['medlat']);
78    }
79    else {
80      return new Polygon(array(
81        new LineString(array(
82          new Point($ll['minlon'], $ll['maxlat']),
83          new Point($ll['maxlon'], $ll['maxlat']),
84          new Point($ll['maxlon'], $ll['minlat']),
85          new Point($ll['minlon'], $ll['minlat']),
86          new Point($ll['minlon'], $ll['maxlat']),
87        ))
88      ));
89    }
90  }
91
92  /**
93   * Convert the geometry to geohash.
94   * @return string the geohash or null when the $geometry is not a Point
95   * @param Point $geometry
96   * @see GeoAdapter::write()
97   */
98  public function write(Geometry $geometry, $precision = NULL){
99    if ($geometry->isEmpty()) return '';
100
101    if($geometry->geometryType() === 'Point'){
102      return $this->encodePoint($geometry, $precision);
103    }
104    else {
105      // The geohash is the hash grid ID that fits the envelope
106      $envelope = $geometry->envelope();
107      $geohashes = array();
108      $geohash = '';
109      foreach ($envelope->getPoints() as $point) {
110        $geohashes[] = $this->encodePoint($point, 0.0000001);
111      }
112      $i = 0;
113      while ($i < strlen($geohashes[0])) {
114        $char = $geohashes[0][$i];
115        foreach ($geohashes as $hash) {
116          if ($hash[$i] != $char) {
117            return $geohash;
118          }
119        }
120        $geohash .= $char;
121        $i++;
122      }
123      return $geohash;
124    }
125  }
126
127  /**
128   * @return string geohash
129   * @param Point $point
130   * @author algorithm based on code by Alexander Songe <a@songe.me>
131   * @see https://github.com/asonge/php-geohash/issues/1
132   */
133  private function encodePoint($point, $precision = NULL){
134    if ($precision === NULL) {
135      $lap = strlen($point->y())-strpos($point->y(),".");
136      $lop = strlen($point->x())-strpos($point->x(),".");
137      $precision = pow(10,-max($lap-1,$lop-1,0))/2;
138    }
139
140    $minlat =  -90;
141    $maxlat =   90;
142    $minlon = -180;
143    $maxlon =  180;
144    $latE   =   90;
145    $lonE   =  180;
146    $i = 0;
147    $error = 180;
148    $hash='';
149    while($error>=$precision) {
150      $chr = 0;
151      for($b=4;$b>=0;--$b) {
152        if((1&$b) == (1&$i)) {
153          // even char, even bit OR odd char, odd bit...a lon
154          $next = ($minlon+$maxlon)/2;
155          if($point->x()>$next) {
156            $chr |= pow(2,$b);
157            $minlon = $next;
158          } else {
159            $maxlon = $next;
160          }
161          $lonE /= 2;
162        } else {
163          // odd char, even bit OR even char, odd bit...a lat
164          $next = ($minlat+$maxlat)/2;
165          if($point->y()>$next) {
166            $chr |= pow(2,$b);
167            $minlat = $next;
168          } else {
169            $maxlat = $next;
170          }
171          $latE /= 2;
172        }
173      }
174      $hash .= $this->table[$chr];
175      $i++;
176      $error = min($latE,$lonE);
177    }
178    return $hash;
179  }
180
181  /**
182   * @param string $hash a geohash
183   * @author algorithm based on code by Alexander Songe <a@songe.me>
184   * @see https://github.com/asonge/php-geohash/issues/1
185   */
186  private function decode($hash){
187    $ll = array();
188    $minlat =  -90;
189    $maxlat =   90;
190    $minlon = -180;
191    $maxlon =  180;
192    $latE   =   90;
193    $lonE   =  180;
194    for($i=0,$c=strlen($hash);$i<$c;$i++) {
195      $v = strpos($this->table,$hash[$i]);
196      if(1&$i) {
197        if(16&$v)$minlat = ($minlat+$maxlat)/2; else $maxlat = ($minlat+$maxlat)/2;
198        if(8&$v) $minlon = ($minlon+$maxlon)/2; else $maxlon = ($minlon+$maxlon)/2;
199        if(4&$v) $minlat = ($minlat+$maxlat)/2; else $maxlat = ($minlat+$maxlat)/2;
200        if(2&$v) $minlon = ($minlon+$maxlon)/2; else $maxlon = ($minlon+$maxlon)/2;
201        if(1&$v) $minlat = ($minlat+$maxlat)/2; else $maxlat = ($minlat+$maxlat)/2;
202        $latE /= 8;
203        $lonE /= 4;
204      } else {
205        if(16&$v)$minlon = ($minlon+$maxlon)/2; else $maxlon = ($minlon+$maxlon)/2;
206        if(8&$v) $minlat = ($minlat+$maxlat)/2; else $maxlat = ($minlat+$maxlat)/2;
207        if(4&$v) $minlon = ($minlon+$maxlon)/2; else $maxlon = ($minlon+$maxlon)/2;
208        if(2&$v) $minlat = ($minlat+$maxlat)/2; else $maxlat = ($minlat+$maxlat)/2;
209        if(1&$v) $minlon = ($minlon+$maxlon)/2; else $maxlon = ($minlon+$maxlon)/2;
210        $latE /= 4;
211        $lonE /= 8;
212      }
213    }
214    $ll['minlat'] = $minlat;
215    $ll['minlon'] = $minlon;
216    $ll['maxlat'] = $maxlat;
217    $ll['maxlon'] = $maxlon;
218    $ll['medlat'] = round(($minlat+$maxlat)/2, max(1, -round(log10($latE)))-1);
219    $ll['medlon'] = round(($minlon+$maxlon)/2, max(1, -round(log10($lonE)))-1);
220    return $ll;
221  }
222
223  /**
224   * Calculates the adjacent geohash of the geohash in the specified direction.
225   * This algorithm is available in various ports that seem to point back to
226   * geohash-js by David Troy under MIT notice.
227   *
228   *
229   * @see https://github.com/davetroy/geohash-js
230   * @see https://github.com/lyokato/objc-geohash
231   * @see https://github.com/lyokato/libgeohash
232   * @see https://github.com/masuidrive/pr_geohash
233   * @see https://github.com/sunng87/node-geohash
234   * @see https://github.com/davidmoten/geo
235   *
236   * @param string $hash the geohash (lowercase)
237   * @param string $direction the direction of the neighbor (top, bottom, left or right)
238   * @return string the geohash of the adjacent cell
239   */
240  public function adjacent($hash, $direction){
241    $last = substr($hash, -1);
242    $type = (strlen($hash) % 2)? 'odd': 'even';
243    $base = substr($hash, 0, strlen($hash) - 1);
244    if(strpos(($this->borders[$direction][$type]), $last) !== false){
245        $base = $this->adjacent($base, $direction);
246    }
247    return $base.$this->table[strpos($this->neighbours[$direction][$type], $last)];
248  }
249}
250