1<?php
2
3namespace geoPHP\Adapter;
4
5use geoPHP\Geometry\Geometry;
6use geoPHP\Geometry\Point;
7use geoPHP\Geometry\LineString;
8use geoPHP\Geometry\Polygon;
9
10/**
11 * PHP Geometry GeoHash encoder/decoder.
12 *
13 * @author prinsmc
14 * @see http://en.wikipedia.org/wiki/Geohash
15 *
16 */
17class GeoHash implements GeoAdapter
18{
19    /**
20     * @var string
21     */
22
23    /** @noinspection SpellCheckingInspection */
24    public static $characterTable = "0123456789bcdefghjkmnpqrstuvwxyz";
25
26    /**
27     * array of neighbouring hash character maps.
28     */
29    private static $neighbours =  [
30        // north
31            'top' =>  [
32                    'even' => 'p0r21436x8zb9dcf5h7kjnmqesgutwvy',
33                    'odd' => 'bc01fg45238967deuvhjyznpkmstqrwx'
34            ],
35        // east
36            'right' =>  [
37                    'even' => 'bc01fg45238967deuvhjyznpkmstqrwx',
38                    'odd' => 'p0r21436x8zb9dcf5h7kjnmqesgutwvy'
39            ],
40        // west
41            'left' =>  [
42                    'even' => '238967debc01fg45kmstqrwxuvhjyznp',
43                    'odd' => '14365h7k9dcfesgujnmqp0r2twvyx8zb'
44            ],
45        // south
46            'bottom' =>  [
47                    'even' => '14365h7k9dcfesgujnmqp0r2twvyx8zb',
48                    'odd' => '238967debc01fg45kmstqrwxuvhjyznp'
49            ]
50    ];
51
52    /**
53     * array of bordering hash character maps.
54     */
55    private static $borders =  [
56        // north
57            'top' =>  [
58                    'even' => 'prxz',
59                    'odd' => 'bcfguvyz'
60            ],
61        // east
62            'right' =>  [
63                    'even' => 'bcfguvyz',
64                    'odd' => 'prxz'
65            ],
66        // west
67            'left' =>  [
68                    'even' => '0145hjnp',
69                    'odd' => '028b'
70            ],
71        // south
72            'bottom' =>  [
73                    'even' => '028b',
74                    'odd' => '0145hjnp'
75            ]
76    ];
77
78    /**
79     * Convert the geoHash to a Point. The point is 2-dimensional.
80     *
81     * @param string  $hash   a GeoHash
82     * @param boolean $asGrid Return the center point of hash grid or the grid cell as Polygon
83     *
84     * @return Point|Polygon the converted GeoHash
85     */
86    public function read($hash, $asGrid = false)
87    {
88        $decodedHash = $this->decode($hash);
89        if (!$asGrid) {
90            return new Point($decodedHash['centerLongitude'], $decodedHash['centerLatitude']);
91        } else {
92            return new Polygon(
93                [
94                    new LineString(
95                        [
96                            new Point($decodedHash['minLongitude'], $decodedHash['maxLatitude']),
97                            new Point($decodedHash['maxLongitude'], $decodedHash['maxLatitude']),
98                            new Point($decodedHash['maxLongitude'], $decodedHash['minLatitude']),
99                            new Point($decodedHash['minLongitude'], $decodedHash['minLatitude']),
100                            new Point($decodedHash['minLongitude'], $decodedHash['maxLatitude']),
101                        ]
102                    )
103                ]
104            );
105        }
106    }
107
108    /**
109     * Convert the geometry to geohash.
110     *
111     * @param Geometry $geometry
112     * @param float|null $precision
113     * @return string the GeoHash or null when the $geometry is not a Point
114     */
115    public function write(Geometry $geometry, $precision = null)
116    {
117        if ($geometry->isEmpty()) {
118            return '';
119        }
120
121        if ($geometry->geometryType() === Geometry::POINT) {
122            /** @var Point $geometry */
123            return $this->encodePoint($geometry, $precision);
124        } else {
125            // The GeoHash is the smallest hash grid ID that fits the envelope
126            $envelope = $geometry->envelope();
127            $geoHashes = [];
128            $geohash = '';
129            foreach ($envelope->getPoints() as $point) {
130                $geoHashes[] = $this->encodePoint($point, 0.0000001);
131            }
132            $i = 0;
133            while ($i < strlen($geoHashes[0])) {
134                $char = $geoHashes[0][$i];
135                foreach ($geoHashes as $hash) {
136                    if ($hash[$i] != $char) {
137                        return $geohash;
138                    }
139                }
140                $geohash .= $char;
141                $i++;
142            }
143            return $geohash;
144        }
145    }
146
147    /**
148     * @author algorithm based on code by Alexander Songe <a@songe.me>
149     * @see https://github.com/asonge/php-geohash/issues/1
150     *
151     * @param Point $point
152     * @param float|null $precision
153     * @return string The GeoHash
154     * @throws \Exception
155     */
156    private function encodePoint($point, $precision = null)
157    {
158        $minLatitude = -90.0000000000001;
159        $maxLatitude = 90.0000000000001;
160        $minLongitude = -180.0000000000001;
161        $maxLongitude = 180.0000000000001;
162        $latitudeError = 90;
163        $longitudeError = 180;
164        $i = 0;
165        $error = 180;
166        $hash = '';
167
168        if (!is_numeric($precision)) {
169            $lap = strlen($point->y()) - strpos($point->y(), ".");
170            $lop = strlen($point->x()) - strpos($point->x(), ".");
171            $precision = pow(10, -max($lap - 1, $lop - 1, 0)) / 2;
172        }
173
174        if (
175                $point->x() < $minLongitude || $point->y() < $minLatitude ||
176                $point->x() > $maxLongitude || $point->y() > $maxLatitude
177        ) {
178            throw new \Exception("Point coordinates ({$point->x()}, {$point->y()}) are out of lat/lon range");
179        }
180
181        while ($error >= $precision) {
182            $chr = 0;
183            for ($b = 4; $b >= 0; --$b) {
184                if ((1 & $b) == (1 & $i)) {
185                    // even char, even bit OR odd char, odd bit...a lon
186                    $next = ($minLongitude + $maxLongitude) / 2;
187                    if ($point->x() > $next) {
188                        $chr |= pow(2, $b);
189                        $minLongitude = $next;
190                    } else {
191                        $maxLongitude = $next;
192                    }
193                    $longitudeError /= 2;
194                } else {
195                    // odd char, even bit OR even char, odd bit...a lat
196                    $next = ($minLatitude + $maxLatitude) / 2;
197                    if ($point->y() > $next) {
198                        $chr |= pow(2, $b);
199                        $minLatitude = $next;
200                    } else {
201                        $maxLatitude = $next;
202                    }
203                    $latitudeError /= 2;
204                }
205            }
206            $hash .= self::$characterTable[$chr];
207            $i++;
208            $error = min($latitudeError, $longitudeError);
209        }
210        return $hash;
211    }
212
213    /**
214     * @author algorithm based on code by Alexander Songe <a@songe.me>
215     * @see https://github.com/asonge/php-geohash/issues/1
216     *
217     * @param string $hash a GeoHash
218     * @return array Associative array.
219     */
220    private function decode($hash)
221    {
222        $result = [];
223        $minLatitude = -90;
224        $maxLatitude = 90;
225        $minLongitude = -180;
226        $maxLongitude = 180;
227        $latitudeError = 90;
228        $longitudeError = 180;
229        for ($i = 0, $c = strlen($hash); $i < $c; $i++) {
230            $v = strpos(self::$characterTable, $hash[$i]);
231            if (1 & $i) {
232                if (16 & $v) {
233                    $minLatitude = ($minLatitude + $maxLatitude) / 2;
234                } else {
235                    $maxLatitude = ($minLatitude + $maxLatitude) / 2;
236                }
237                if (8 & $v) {
238                    $minLongitude = ($minLongitude + $maxLongitude) / 2;
239                } else {
240                    $maxLongitude = ($minLongitude + $maxLongitude) / 2;
241                }
242                if (4 & $v) {
243                    $minLatitude = ($minLatitude + $maxLatitude) / 2;
244                } else {
245                    $maxLatitude = ($minLatitude + $maxLatitude) / 2;
246                }
247                if (2 & $v) {
248                    $minLongitude = ($minLongitude + $maxLongitude) / 2;
249                } else {
250                    $maxLongitude = ($minLongitude + $maxLongitude) / 2;
251                }
252                if (1 & $v) {
253                    $minLatitude = ($minLatitude + $maxLatitude) / 2;
254                } else {
255                    $maxLatitude = ($minLatitude + $maxLatitude) / 2;
256                }
257                $latitudeError /= 8;
258                $longitudeError /= 4;
259            } else {
260                if (16 & $v) {
261                    $minLongitude = ($minLongitude + $maxLongitude) / 2;
262                } else {
263                    $maxLongitude = ($minLongitude + $maxLongitude) / 2;
264                }
265                if (8 & $v) {
266                    $minLatitude = ($minLatitude + $maxLatitude) / 2;
267                } else {
268                    $maxLatitude = ($minLatitude + $maxLatitude) / 2;
269                }
270                if (4 & $v) {
271                    $minLongitude = ($minLongitude + $maxLongitude) / 2;
272                } else {
273                    $maxLongitude = ($minLongitude + $maxLongitude) / 2;
274                }
275                if (2 & $v) {
276                    $minLatitude = ($minLatitude + $maxLatitude) / 2;
277                } else {
278                    $maxLatitude = ($minLatitude + $maxLatitude) / 2;
279                }
280                if (1 & $v) {
281                    $minLongitude = ($minLongitude + $maxLongitude) / 2;
282                } else {
283                    $maxLongitude = ($minLongitude + $maxLongitude) / 2;
284                }
285                $latitudeError /= 4;
286                $longitudeError /= 8;
287            }
288        }
289        $result['minLatitude'] = $minLatitude;
290        $result['minLongitude'] = $minLongitude;
291        $result['maxLatitude'] = $maxLatitude;
292        $result['maxLongitude'] = $maxLongitude;
293        $result['centerLatitude'] = round(($minLatitude + $maxLatitude) / 2, max(1, -round(log10($latitudeError))) - 1);
294        $result['centerLongitude'] = round(($minLongitude + $maxLongitude) / 2, max(1, -round(log10($longitudeError))) - 1);
295        return $result;
296    }
297
298    /**
299     * Calculates the adjacent geohash of the geohash in the specified direction.
300     * This algorithm is available in various ports that seem to point back to
301     * geohash-js by David Troy under MIT notice.
302     *
303     *
304     * @see https://github.com/davetroy/geohash-js
305     * @see https://github.com/lyokato/objc-geohash
306     * @see https://github.com/lyokato/libgeohash
307     * @see https://github.com/masuidrive/pr_geohash
308     * @see https://github.com/sunng87/node-geohash
309     * @see https://github.com/davidmoten/geo
310     *
311     * @param string $hash the geohash (lowercase)
312     * @param string $direction the direction of the neighbor (top, bottom, left or right)
313     * @return string the geohash of the adjacent cell
314     */
315    public static function adjacent($hash, $direction)
316    {
317        $last = substr($hash, -1);
318        $type = (strlen($hash) % 2) ? 'odd' : 'even';
319        $base = substr($hash, 0, strlen($hash) - 1);
320        if (strpos((self::$borders[$direction][$type]), $last) !== false) {
321            $base = self::adjacent($base, $direction);
322        }
323        return $base . self::$characterTable[strpos(self::$neighbours[$direction][$type], $last)];
324    }
325}
326