MySQL 8.0.23で、Spatial(GIS)関連機能として、フレシェ距離を求める関数 ST_GrechetDistance() と、ハウスドルフ距離を求める関数 ST_HausdorffDistance() が追加されました。どちらも、２つのジオメトリどうしの類似度を求める関数のようですが、今ひとつよく分からないので、今日は主にフレシェ距離を中心に色々と動作を試してみて、「こういうことかな？」の理解を試みました。
想像して、試して、結果に納得する、という作業ですので、正しくない理解を書いているかもしれません。お気づきの方は、やさしくお教えいただければ幸いです。
フレシェ距離とは
ざっくり言うと、２つのジオメトリ（MySQL 8.0.23 ではLineStringのみ対応）がどれくらい似ているかを示す数値。２つの線があった時、片方の線上の任意の点から相手方の線の最も近いところまで、最悪でもどれくらいの距離を行けば良いかを示す数字、というざっくりとした理解をしています（この理解は、正確ではないことは実験していて分かりましたが）。
なお、線上の任意の点と書きましたが、MySQLに実装されているのは「離散」のフレシェ距離、つまり、LineString を構成するために明示された各点のみを対象とするものです。
はじめてのFrechetDistance
とりあえず、２つのLineStringを作って、ST_FrechetDistance()を試してみます。シンプルにこんな２つの平行線( ポイント数3）で。
SET @g1=ST_GeomFromText('LINESTRING(1 1, 2 1, 4 1)'); SET @g2=ST_GeomFromText('LINESTRING(1 2, 2 2, 4 2)');
mysql> SELECT ST_FrechetDistance(@g1, @g2) d; +------+ | d | +------+ | 1 | +------+
どの点から見ても、相手方の一番近い点は距離1のところにあるので、その中で一番大きなもの(遠いもの)も 1 となります。予想と結果は一致。
点をひとつ遠くにしてみる
青いほうの点（@g2）の真ん中の点を少しだけ遠ざけて見ます。赤い線(@g1)はそのままで。
mysql> SET @g2_1=ST_GeomFromText('LINESTRING(1 2, 2 2.1, 4 2)'); mysql> SELECT ST_FrechetDistance(@g1, @g2_1) d; +------+ | d | +------+ | 1.1 | +------+
@g1 と @g2_1 それぞれの点を比べて、真ん中の点の距離どうしが少し遠くなって 1.1 になったので、そのような結果が返ってきます。予想通り。
試しに横方向にも動かしてみる
先ほどは真ん中の点をy軸方向にずらしてみましたが、今度は横方向に動かしてみます。
mysql> SET @g2_2=ST_GeomFromText('LINESTRING(1 2, 2.1 2, 4 2)'); mysql> SELECT ST_FrechetDistance(@g1, @g2_2) d; +-------------------+ | d | +-------------------+ | 1.004987562112089 | +-------------------+ 1 row in set (0.00 sec)
真ん中の点どうしの距離が、1よりも少し遠くなったのだということは分かりますが、この数字が合っているかどうか、もう少し確認してみないと。この数字は、直角を挟んだ辺の長さがそれぞれ 1 と 0.1 の直角三角形の斜辺の長さですから、これもMySQLを使って計算してみます。
mysql> SELECT SQRT(1*1 + 0.1*0.1); +---------------------+ | SQRT(1*1 + 0.1*0.1) | +---------------------+ | 1.004987562112089 | +---------------------+
一致しました。想定通りのフレシェ距離が得られたことが確認できました。
少し刻んでみると・・・・
赤いほうの線(@g1)は固定のままで、青いほうの線を少し刻んでみましょう。(3,2)と(4,2)の間に (3,2) という点を追加してみます。言うまでもなく刻もうが刻むまいが線としては同じ線をあらわしているはずですが・・・・
mysql> SET @g3=ST_GeomFromText('LINESTRING(1 2, 2 2, 3 2, 4 2)'); mysql> SELECT ST_FrechetDistance(@g1, @g3) d; +--------------------+ | d | +--------------------+ | 1.4142135623730951 | +--------------------+
おや。この数字はルート２。追加した点から相手方の一番近い点を探した結果、x方向に1、y方向に-1行ったところにある点が一番近いと見つけたということですね、これは。
つまり、MySQLの（離散）フレシェ距離では、結果として同じ線をあらわしているようなLineStringどうしでも、粒度（刻み方）が異なると数字が大きくなってしまうと考えてよさそうです。
フレシェ距離は順序が大切
ここで改めて一番最初の事例に戻ってみます。
ただしここでは、赤いほうの線を右から左へ向かって定義してみます。
SET @g2r=ST_GeomFromText('LINESTRING(4 2, 2 2, 1 2)');
２つの線を構成するPOINT自体に何ら変更はないので、同じ結果となることを予想していたのですが・・・・
mysql> SELECT ST_FrechetDistance(@g1, @g2r) d; +--------------------+ | d | +--------------------+ | 3.1622776601683795 | +--------------------+
これはどうも、例えば左上の点と右下の点の距離がフレシェ距離として表示されていますね。x方向に3、y方向に1だけ隔たっていますから、
mysql> SELECT SQRT(3*3 + 1*1); +--------------------+ | SQRT(3*3 + 1*1) | +--------------------+ | 3.1622776601683795 | +--------------------+
うん。その点どうしの距離です。
つまり、フレシェ距離は、２つのLineStringを構成する点の集合どうしを比べるものではなく、LineString を構成する点を順に比較していくものと考えられます。いや、ほんとはよくわからないので、ご存じの方、教えてください。
一方、ハウスドルフ距離は
ハウスドルフ距離のほうは、LineString内の順序ではなく、構成する点の集合のみに着目しているように見えます。
先ほどの2本の平行線を逆順にしたもの（@g1 と @g2r）で試すと、距離１のままとなります。
mysql> SELECT ST_HausdorffDistance(@g1, @g2r) d; +------+ | d | +------+ | 1 | +------+
また、ST_HausdorffDistance()は引数の順序が大切（どちらのジオメトリを基準に相手方との最小距離を求めるのか）であるようです。先ほどの「刻んだ」線である @g3を例に。
mysql> SELECT ST_HausdorffDistance(@g1, @g3) d; +------+ | d | +------+ | 1 | +------+
相手方(@g3)が幾ら刻もうが、@g1側から見て一番近い点は 距離1のところにあるので、その値が結果として返ってきます。
一方で、@g3側から見ると、刻んだ点(3,2)から見た相手方の一番近い点、というのが最長の最短距離になるので、ルート2の値が返ってくることになります。
mysql> SELECT ST_HausdorffDistance(@g3, @g1) d; +--------------------+ | d | +--------------------+ | 1.4142135623730951 | +--------------------+
