はじめに

手書きの都道府県の輪郭を評価するアプリを作りました．こちらから．

キャンバスに都道府県の輪郭を書くと，その輪郭が各都道府県と類似しているかを採点します． 何を言っているのかよくわからないかもしれませんが，百聞は一見に如かず．こちらにアクセスしてキャンバスに何かを書こうとすると伝わるはず．

手書きの千葉県の輪郭（赤色）と本物の千葉県の輪郭（青色）．スコアは 85.87 点．

適当に一周書くと，それがどの県にどれだけ類似しているかというランキングが出ます．

中身について

データ

都道府県の形状データは国土交通省の国土数値情報ダウンロードサイトから．geojson という形式で形状データが得られます． しかし，かなりデータが細かくて大きいのと，離島や飛び地も含んでしまっています，これは今回やりたいことに合わない． そこで，いい感じに加工して一番面積が大きい成分を残しています，あとは点数削減のため，輪郭から等間隔で点をサンプリングし，500 点まで圧縮しています．

スコア計算

形状の類似度を算出する方法は複数考えられますが，今回は近傍の点までの距離を採用しました．

まずは，書いた輪郭（以下，ユーザー輪郭）と正しい輪郭（以下，マスター輪郭）の位置合わせをします．中心が原点，面積が 1 になるように並行移動と拡大縮小を行います． 重心，面積の計算には靴紐公式（英語版 Wikipedia）の Triangle formula を用いました．重心は面積を求めるついでにいい感じにやると計算できます． （この公式が何をしているかというと多角形を $3$ 角形に分割しています．具体的には，多角形が $N$ 角形だとすると，原点から $N$ 頂点に対して線を引いて，$N$ 個の $3$ 角形の集合としています．それぞれの $3$ 角形の重心と面積は外積を使うと求まるので，面積に応じた重み付けをすると重心も計算できます．方向によっては面積を負とみなす $3$ 角形も存在したりしますがあくまで計算上なので問題はありません．）

マスター輪郭側は事前にこの処理を行ったデータを持っておくので，この計算は本アプリ上ではユーザー輪郭側のみに対して行っています． 並行移動と拡大縮小に加えて，等間隔でサンプリングし，ユーザー輪郭も 500 点にしています．

次に，「ユーザー輪郭から見た時のマスター輪郭のスコア」 $s_\mathrm{user}$ と「マスター輪郭から見た時のユーザー輪郭のスコア」 $s_\mathrm{master}$ を計算して，調和平均をとります． これらの処理は同じなので，「ユーザー輪郭から見た時のマスター輪郭のスコア」の計算方法について説明します．

ユーザー輪郭の $i$ 点目の点の座標を $\mathbf{p}_i$，マスター輪郭の $j$ 点目の点の座標を $\mathbf{q}_j$ とします．また，ユーザー輪郭の点数を $N$ 点とします（$N=500$ です）．

スコアを求めるために，最近傍の点までの距離の平均値 $d_\mathrm{user}$ をまず求めます．

$d_\mathrm{user} = \frac{1}{N}\sum_{i=1}^N{\min_j{\left(\mathrm{dist}(\mathbf{p}_i,\mathbf{q}_j)\right)}}$

$d_\mathrm{user}$ は $0$ 以上の実数で，$0$ に近ければ近いほど良いです． これから，スコア $s_mathrm{user}$ を求めます．$k$ は正の実数です．いい感じのスコアになるように，適当に決めました．今回は $k = 3$ です．

$s_\mathrm{user} = 100e^{-kd_\mathrm{user}}$

最終的なスコア $s$ は，調和平均を取ることで求めます． これにより，ズルが困難になるはず．

$s = \frac{2s_\mathrm{user}s_\mathrm{master}}{s_\mathrm{user} + s_\mathrm{master}}$

高得点の出し方

概形を合わせる，これに限ります．先述したようなスコアの計算方法なので，複雑な海岸線を複雑に書いてもスコアの伸びは期待できません．

重心の位置がずれてしまうと，全体としてずれます．太いところは太く，細いところは細く．本物と合わせることが重要です． 加えて，東西南北がずれている際の補正はないので，方角をきっちり合わせるのも重要になります．

小さく書いても大きく書いても拡大縮小して補正するので，なるべく大きめに書くとやりやすいのではと思います．並行移動もするのでキャンバス真ん中に書かなくてもスコアに影響はありません．

おわりに

今回のスコア計算上，丸い都道府県（栃木，岡山など）は比較的簡単で，細長い県（石川など）は難しかったりします．千葉も結構難しめ． 形状の類似度の評価って難しいなと思いつつこの記事を締めます．今回の記事数式多めだなあ．

こちらから遊べます．