GPXなどのトラックログデータを簡略化するJava実装の例.AndroidアプリでMyTracksのルートデータを表示するために作成しました

トラックログの間引き

地図ロイドMyTracks のログデータを表示したいと考えたのですが, MyTracksのデータは普通にログを取るとかなり細かく, 例えば1時間だけの記録でも1000点程度になります.

うちの非力なHT-03Aでは,この全点を地図上にプロットすると重くて実用的ではありませんでした. それで,まともに動くようにするために,ログを間引いたものを表示することにしました.

この,間引き(簡略化,simplify)について調べたところ,間引く方法は主に

  • 単純に一定間隔で間引く
  • できるだけ誤差が少なくなるように点を選んで間引く

があるようですが,今回できるだけカーブなどの特徴を残したかったため,後者の方法をとりました.

カーブなどの特徴というのは,例えば以下の図(MyTracks)で,
mabiki1a.png

左上から道なりに歩いてきて右折して橋を渡って下に進んでいますが, この道なりに右折しているというルートを残したいという意図です.

あれこれアルゴリズムを試した結果,
mabiki1c.png

このようにそこそこ忠実に残るようになったので, 地図ロイドにGPXファイル取り込み機能として組み込んで,この記事に書いています.

間引きの方針

基本的な考え方は,以下のページを参考にしました.

点を削除したことによって生じる誤差ができるだけ小さくて済むように点を選んで,間引いてゆくわけです. ここで誤差をどう定義するかですが,今回はトラックログの各点を結ぶ距離の合計にしました.

ただし実際に使っているのは,距離ではありません.

(経度の差の2乗 + 緯度の差の2乗) の平方根 を小数以下切り捨てたもの
であり,距離に近い意味を持つ値でしかないのですが,Android実機での処理速度との兼ね合いでこうしています.

ただ副作用(?)として,同じ誤差を持つ点が複数出てきてしまい, そのうちどの点を削除するかが偏ると,間引き結果が不自然になるという問題が発生しました.

そのためできるだけ不自然にならないように均等に間引くために,乱数を使っています. なので同じデータを使っても,毎回間引き結果は変わってしまいます.

...泥臭いのであまり人にはお勧めできませんが,何かの参考になればという感じで公開します.

ソースコード

GpxUtil.java
package com.kamoland.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class GpxUtil {
	private static final int RANDOM_TABLE_SIZE = 10;

	private int[][] randTable;
	private Random rand = new Random();

	/**
	 * 間引きをおこなう
	 * @param plist 対象点のリスト
	 * @param remain 残したい点数の目安
	 * @return 間引き結果
	 */
	public List<TrkPoint> mabiki(TrkPoint[] plist, int remain) {
		int plen = plist.length;

		// 乱数表を初期化する
		initRandomTable(1, plen-2);

		// 合計距離
		// (正確には距離ではありませんが,
		// 距離に近い意味を持つ値として誤差の評価に使っています)
		int totalDist = 0;
		for (int i = 1; i < plen; i++) {
			int dx = plist[i].xe6 - plist[i-1].xe6;
			int dy = plist[i].ye6 - plist[i-1].ye6;
			int d = (int)Math.sqrt( dx * dx + dy * dy);
			totalDist += d;
		}

		final int ERR_MARK_TERMINAL = -1;
		final int ERR_MARK_DELETED = -2;

		// 各点の誤差を求めておく
		int[] err = new int[plen];
		err[0] = ERR_MARK_TERMINAL;
		for (int i = 1; i < plen-1; i++) {
			err[i] = calcErr(plist, i, totalDist);
		}
		err[plen-1] = ERR_MARK_TERMINAL;

		// 誤差の小さい点から消していく
		int delCnt = 0;
		while (plen - delCnt > remain) {
			int minErr = 0;
			int minIndex = -1;

			// 誤差が最小の点を検索する
			// ただし複数の点で誤差が一致した場合に生じる,消される点の偏りを防ぐために
			// 乱数表を使ってランダム順に検索している
			int[] indexList = selectRandomList();
			for (int p: indexList) {
				if (minIndex < 0 || err[p] < minErr) {
					if (err[p] >= 0) {
						minErr = err[p];
						minIndex = p;
					}
				}
			}
			if (minIndex < 0) {
				break;
			}

			// 消す
			delCnt++;
			err[minIndex] = ERR_MARK_DELETED;

			// 隣接点の誤差を再計算する
			if (minIndex > 1) {
				if (err[minIndex-1] > 0) {
					err[minIndex-1] = calcErr(plist, minIndex-1, totalDist);
				}
			}
			if (minIndex < plen-2) {
				if (err[minIndex+1] > 0) {
					err[minIndex+1] = calcErr(plist, minIndex+1, totalDist);
				}
			}
		}

		List<TrkPoint> result = new ArrayList<TrkPoint>();
		for (int i = 0; i < plen; i++) {
			if (err[i] != ERR_MARK_DELETED) {
				result.add(plist[i]);
			}
		}

		return result;
	}

	/**
	 * 指定した点を消した時の誤差を計算する.
	 * 誤差 = 消した時の合計距離と正しい合計距離の差
	 * @param plist
	 * @param target
	 * @param totalDist
	 * @return
	 */
	private static int calcErr(TrkPoint[] plist, int target, int totalDist) {
		int dt = 0;

		for (int i = 1; i < plist.length-1; i++) {
			int d;
			if (i == target) {
				d = 0;

			} else if (i == target + 1) {
				int dx = plist[i].xe6 - plist[i-2].xe6;
				int dy = plist[i].ye6 - plist[i-2].ye6;
				d = (int)Math.sqrt( dx * dx + dy * dy);

			} else {
				int dx = plist[i].xe6 - plist[i-1].xe6;
				int dy = plist[i].ye6 - plist[i-1].ye6;
				d = (int)Math.sqrt( dx * dx + dy * dy);
			}
			dt += d;
		}
		return Math.abs(totalDist - dt);
	}

	/**
	 * 乱数表を初期化する
	 * @param start
	 * @param end
	 * @return
	 */
	private void initRandomTable(int start, int end) {
		final int num = end - start + 1;

		randTable = new int[RANDOM_TABLE_SIZE][num];

		for (int n = 0; n < RANDOM_TABLE_SIZE; n++) {
			boolean[] picked = new boolean[num];

			int pickedCount = 0;
			while (pickedCount < num) {
				int i = rand.nextInt(num);
				if (! picked[i]) {
					randTable[n][pickedCount] = i + start;
					picked[i] = true;
					pickedCount++;
				}
			}
		}
	}

	private int[] selectRandomList() {
		return randTable[rand.nextInt(RANDOM_TABLE_SIZE)];
	}

	/**
	 * トラックログのポイント
	 */
	public static class TrkPoint {
		int xe6;
		int ye6;
		int ele;
		String time;
	}
}
実際の地図ロイドの実装では,さらに距離の計算結果をキャッシュして計算量を減らしたり,Mathの代わりにFloatMath を使ったりしていますが, 今回の主題ではないので省略しています.

HT-03Aがしょぼいというのもありますが,実機で実用的な速度を出すのは苦労したところではあります.

kamolandをフォローしましょう


© 2019 KMIソフトウェア