キョリ測新機能「なぞってキョリ測」、その裏側

こんにちは、中村です。

本日キョリ測に新しい機能をリリースしました。その名も「なぞってキョリ測」機能です（あれ!?実は社内でそう呼んでいるのは自分だけかも...）。Ctrl（Macの場合はCommand）キーを押しながら、地図上をドラッグすることで簡単にキョリ測出来るようになりました！

本エントリーではこの「なぞってキョリ測」機能の実装について紹介したいと思います。なおキョリ測はFlex(ActionScript3.0)で開発されているため、引用されるソースコードはActionScript3.0となります。

ドラッグによるルート描画の課題

これまでのキョリ測の仕様はクリックする毎にルート描画され、クリック地点に

このようなマーカーを描画していきます。これまでのクリックと同様にMOUSE_MOVEイベントでポイントを追加してしまうと、マウスが１ピクセル動く毎にポイント追加されてしまうため超大量のマーカーを描画してしまい、また実用的な処理スピードは実現できません。

map.addEventListener(MMapEvent.CLICK,function(event:MMapEvent):void{
    addPoint(event.mouseRP); // 緯度経度ポイントを追加してルート＆マーカー描画
});
map.addEventListener(MMapEvent.MOUSE_MOVE,function(event:MMapEvent):void{
    addPoint(event.mouseRP); // 超連続的に発生→クッソ重い。。。
});

あ、ここでのmapオブジェクトやMMapEventオブジェクトはFlashMapsAPIのものです。MA6にも絶賛提供中ですよ！（コマーシャルタイム）

解決策：ポイントの間引き

連続的に発生するポイントの集合において、直線とみなせる区間のポイント集合を除去することでこの問題を解決します。内々ではこれをポイントの間引き（以下、間引き）と呼んでます。ポイント集合を間引く関数normalizeを用意すればMOUSE_MOVEイベントはこう書き換えれますね。

var points:Array = [];
map.addEventListener(MMapEvent.MOUSE_MOVE,function(event:MMapEvent):void{
    points.push(event.mouseRP);
    if(points.length>100){ // 適当なタイミングで間引き発動
       var normalizedPoints:Array = normalize(points);
       while(normalizedPoints.length){
           addPoint(normalizedPoints.shift());
       }
       points = [];
    }
});

間引きロジック

以下のようなロジックで間引きを行ってみました。

1. 始点と終点を通過する直線Lから、すべてのポイントが距離d以内であれば間引き

2. 距離d以上のポイントがあれば分割し、それぞれに対して間引きロジックを再帰適用

3. 距離d以上のポイントが複数あれば、距離dが最大のもので分割し再帰適用

ヘルパークラス

直線とポイントとの距離dを求める直線Lを表すクラスがあると実装が楽になりそうですね。というわけで以下インターフェースを持つクラスを用意します。実装は割愛。

// 定義のみ、あくまで説明のためAS3の文法的には間違ってます
public class LinearFunction{
    public function LinearFunction(p1:Point,p2:Point);
    public function distance(p:Point):Number;
}

間引き実装

上記ロジックを実装に落とすとこうなります。

private function normalize(points:Array):Array
{
    // ポイント数が２つ以下はそのまま返す
    if(points.length<3)return points.concat();
    // 計算は緯度経度座標ではなく画面上の座標に変換した値を利用する
    var ppoints:Array = [];
    for(var i:uint=0,l:uint=points.length;i<l;i++){
        ppoints.push(map.latLngToGlobal(points[i] as Point));
    }
    // 始点終点の直線オブジェクトを生成
    var first:Point = ppoints[0] as Point;
    var last:Point = ppoints[ppoints.length-1] as Point;
    var linear:LinearFunction = new LinearFunction(first,last);
    // 最大の距離dを持つポイントを探索
    var max:Number = 0;
    var idx:int = -1;
    var THRESHOLD:Number = 5;
    for(i=1,l=ppoints.length-1;i<l;i++){
        var d:Number = linear.distance(ppoints[i] as Point);
        if(d>THRESHOLD&&d>max){
            max=d;
            idx=i;
        }
    }
    // 距離dを超えるポイントがあれば集合を分割して再帰適用
    if(idx>-1){
        var a1:Array = points.slice(0,idx+1);
        var a2:Array = points.slice(idx,points.length);
        var na1:Array = normalize(a1);
        na1.pop();
        var na2:Array = normalize(a2);
        return na1.concat(na2);
    }
    // すべてが距離d以内であれば始点と終点に間引いて返却
    return [points[0],points[points.length-1]];
}

完成！

というわけで、このロジックを既存プログラムに組み込むことで「なぞってキョリ測」機能が実現されました。実際にはもう少し処理を書いてはいますが、大雑把に説明するとこんなところです。

今回は新機能の実装部分を紹介してみましたが、如何でしたでしょうか？こんな感じでキョリ測に限らず、既存サービスをユーザーにとって使いやすいサービスとするため日々がんばっております。改善要望などあればブログのコメント欄に頂ければと思いますので、よろしくお願いします。