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

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

Objective-C的???Geohash

こんにちは!
はまっている時間はたいていRSpecに起因するものなのではないかと以前から感じているmasudaです。
なんとか約束の火曜日に間に合ったでしょうか???

先日chibaさんがGeohashをdecodeするものをCLで書いていらしたので、それを微妙に参考にしながらCocoaのCoreLocationのCLLocationにgeohashをencode/decodeするメソッド追加してみました。

本当はビット演算がしたいのですが、文字列処理の方が自分には単純で簡単だったため、とりあえず今回は文字列処理にしてみました。

我ながらひどいコードだと思いますので、これからリファクタリングをしていきたいところです。

[CLLocation+Geohash.h]

#import <CoreLocation/CoreLocation.h>
#import <Foundation/Foundation.h>


@interface CLLocation(Geohash)

@property (nonatomic, readonly)   NSString    *geohash;

+ (CLLocation *)locationFromGeohash:(NSString *)aGeohash;

@end

[CLLocation+Geohash.m]

#import "CLLocation+Geohash.h"

#include <math.h>

NSString *int_to_binary(NSUInteger input)
{
    if (input == 1 || input == 0)
    {
        return [NSString stringWithFormat:@"%d", input];
    }

    return [NSString stringWithFormat:@"%@%d", int_to_binary(input / 2), input % 2];
}


double parse_binary(NSString *binary, double max, double min)
{
    double mid = 0.0;

    for (NSUInteger i = 0; i < [binary length]; ++i)
    {
        if ([binary characterAtIndex:i] == '1')
        {
            min = mid;
        }
        else
        {
            max = mid;
        }

        mid = (max + min) / 2;
    }

    return mid;
}


NSUInteger binary_to_int(NSString *input)
{
    NSUInteger result, length;

    result = 0;
    length = [input length];

    for (NSUInteger i = 0; i < length; ++i)
    {
        if ([input characterAtIndex:i] == '1')
        {
            result += pow(2, length - i - 1);
        }
    }

    return result;
}


NSString * generate_binary(double input, double max, double min, int cutoff)
{
    NSMutableString     *result;
    double              mid;

    result = [NSMutableString string];
    for (int i = 0; i < cutoff; ++i)
    {
        mid = (max + min) / 2;

        if (input > mid)
        {
            [result appendString:@"1"];
            min = mid;
        }
        else
        {
            [result appendString:@"0"];
            max = mid;
        }
    }

    return [NSString stringWithString:result];
}


@implementation CLLocation(Geohash)

- (NSString *)geohash
{
    int cutoff = 15;
    NSString *base32_characters  = @"0123456789bcdefghjkmnpqrstuvwxyz";

    NSString            *bin_lat, *bin_lng;
    NSMutableString     *bin_packed, *result;

    bin_lat = generate_binary([self coordinate].latitude, 90.0, -90.0, cutoff);
    bin_lng = generate_binary([self coordinate].longitude, 180.0, -180.0, cutoff);

    bin_packed = [NSMutableString string];

    for (int i = 0; i < [bin_lat length]; ++i)
    {
        [bin_packed appendFormat:@"%c%c", [bin_lng characterAtIndex:i], [bin_lat characterAtIndex:i]];
    }

    result = [NSMutableString string];

    // extract by 5-bit.
    for (int i = 0; i < [bin_packed length] / 5; ++i)
    {
        NSUInteger index;
        index = binary_to_int([bin_packed substringWithRange:NSMakeRange(i * 5, 5)]);
        [result appendFormat:@"%c", [base32_characters characterAtIndex:index]];
    }

    return result;
}


+ (CLLocation *)locationFromGeohash:(NSString *)aGeohash
{
    NSString *base32_characters  = @"0123456789bcdefghjkmnpqrstuvwxyz";

    NSMutableString *bin_packed, *bin_lat, *bin_lng;

    bin_packed = [NSMutableString string];

    for (NSUInteger i = 0; i < [aGeohash length]; ++i)
    {
        NSString *character;
        character = NSMutableString stringWithFormat:@"%c", [aGeohash characterAtIndex:i lowercaseString];

        for (NSUInteger j = 0; j < [base32_characters length]; ++j)
        {
            if ([character isEqualToString:[NSString stringWithFormat:@"%c", [base32_characters characterAtIndex:j]]])
            {
                NSMutableString *binary;
                binary = [NSMutableString stringWithFormat:@"%@", int_to_binary(j)];

                NSUInteger length = [binary length];
                for (NSUInteger k = 0; k < 5 - length; ++k)
                {
                    [binary insertString:@"0" atIndex:0];
                }

                [bin_packed appendString:binary];
                break;
            }
        }
    }

    bin_lat = [NSMutableString string];
    bin_lng = [NSMutableString string];

    for (NSUInteger i = 0; i < [bin_packed length]; ++i)
    {
        if (i % 2)
        {
            // a latitude is composed of odd bits.
            [bin_lat appendFormat:@"%c", [bin_packed characterAtIndex:i]];
        }
        else
        {
            // a longitude is composed of even bits.
            [bin_lng appendFormat:@"%c", [bin_packed characterAtIndex:i]];
        }
    }

    return [[CLLocation alloc] initWithLatitude:parse_binary(bin_lat, 90.0, -90.0)
                                      longitude:parse_binary(bin_lng, 180.0, -180.0)];
}


@end

NSStringでかなり遅いcharacterAtIndexを使いまくっている。

参考

Geohash - Wikipedia, the free encyclopedia
GeoHashのdecodeのアルゴリズムの解説します & ScalaのGeoHashライブラリを作ってみました(仮) - ゆろよろ日記