アクトインディ開発者ブログ

子供とお出かけ情報「いこーよ」を運営する、アクトインディ株式会社の開発者ブログです

Geohash

こんにちは、chibaです。 昨晩は、弊社技師同僚間のTwitterで、Geohashの話題が盛り上っておりました。 話に混ざれずに疎外感を感じつつ就寝しようとしたのですが、ふと、会話中で示されていたGeohashの説明のページを眺めたところ、仕組みが分かるようで、分からないような、微妙にもどかしい感じだったので、だらだらと説明のとおりに上から順にコードを書いてみることにしました。

  • Geohash - Wikipedia, the free encyclopedia
  • そんな感じで、説明の順番のとおりに書いてできたコードが下記です。 なんとなく仕組みは分かったけど、そういえば、エンコード手順の説明は書いてないんだなあ…、と自分勝手なことを考えながら就寝しました。

    (defpackage :geohash
      (:use :cl)
      (:import-from :shibuya.lisp
                    :$ :$*))
    
    (in-package :geohash)
    
    (defun tr (from to string)
      (map 'string
           (lambda (c)
             (or (some (lambda (x y)
                         (and (char-equal x c) y))
                       from to)
                 (char-upcase c)))
           string))
    
    (defun 5bits (string)
      (map 'list
           ($ format nil "~5,'0,B"
              $ read-from-string
              $ format nil "#32R~A"
              $ tr "0123456789BCDEFGHJKMNPQRSTUVWXYZ"
                   "0123456789ABCDEFGHKJKLMNOPQRSTUV"
              $ string $)
           string))
    
    (defun longitude-latitude (strings)
      (let ((bit-c-list ($* concatenate 'list strings)))
        (loop :for c :in bit-c-list
              :for i :from (if (char= #\0 (car bit-c-list)) 0 1)
              :if (evenp i) :collect c :into even
              :else :collect c :into odd
              :finally (return
                         (list :longitude
                               (coerce even 'string)
                               :latitude
                               (coerce odd 'string))))))
    
    (defun bitlist (string)
      (map 'list ($ parse-integer $ string $)
           string))
    
    (defun decode (bits min mid max)
      (if (endp bits)
          mid
          ($* decode
              (cdr bits)
              (if (zerop (car bits))
                  (list min (/ (+ mid min) 2) mid)
                  (list mid (/ (+ mid max) 2) max)))))
    
    (defun decode-geohash (string)
      (let* ((u ($ longitude-latitude $ 5bits string))
             (lon (getf u :longitude))
             (lat (getf u :latitude)))
        (list
         :longitude
         ($ float $ decode (bitlist lon) -90 0 90)
         :latitude
         ($ float $ decode (bitlist lat) -180 0 180))))
    
    (decode-geohash "u4pruydqqvj")
    ;⇒ (:LONGITUDE 57.64911 :LATITUDE 10.407439)