MySQL8.0でGIS機能を試す No.5 - Ingressのリンク作成時のフィールド選定

本エントリの概要
大前提
検証したいこと「リンク生成時に生成されるフィールド選定」
- 生成されるフィールド選定条件
データ設計
データ準備
検証実施
参考

本エントリの概要

位置情報ゲームIngressの機能の一部をMySQL8.0のGIS機能を使って再現できるかを試してみた記録。
今回は「リンク生成時に生成されるフィールド選定」を試します。

大前提

本エントリはあくまで個人の興味から技術的な実装を「試してみた」だけの記録です。
実際のサービスが同等の技術で実装されているかは全く考慮していません。
- 特にパフォーマンスにおいては大きな差があるのは承知しています。
GIS以外の機能でできることは検証を省きます。
Ingressの基本ルール等については前のエントリを参照ください。
- MySQL8.0でGIS機能を試す No.1 - Ingressのリンク可能判定 - untitled .engineer

検証したいこと「リンク生成時に生成されるフィールド選定」

生成されるフィールド選定条件

リンク元ポータル、リンク先ポータルは固定
生成されたリンクと既存リンク2本が3角形を形成する場合にフィールドが生成される
既存のリンクによって四角形があり、生成されたリンクによってをそれを分断する場合、分断した両側にフィールドが生成される
同一方向に複数のフィールド候補がある場合、最大サイズのフィールドが選択される

今回すでに以下のようにリンクが作成されているものとします。
f:id:dupont_kedama:20180910215625p:plain

この状態から多摩市から国分寺市にリンクしたものとします。
生成されるフィールドは、上記ルールにより多摩市-国分寺市-福生市と多摩市-国分寺市-調布市の二つ。
f:id:dupont_kedama:20180910215650p:plain
今回は福生市と調布市を導き出すクエリを考えようと思います。

データ設計

今回のデータは地理座標系のSRID=4612を使います。
ポータルの情報として前のエントリで作ったportalsテーブルを利用します。
リンクの情報として前のエントリで作ったlinksテーブルを利用します。
- MySQL8.0でGIS機能を試す No.2 - Ingressのリンク可能なリンク先の選別 - untitled .engineer

データ準備

以下のSQLで既存リンクを生成しておきます。

INSERT INTO gis.links VALUES (null,13223,13214,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13223),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13214)),4326));
INSERT INTO gis.links VALUES (null,13214,13218,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13214),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13218)),4326));
INSERT INTO gis.links VALUES (null,13218,13224,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13218),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13224)),4326));
INSERT INTO gis.links VALUES (null,13224,13212,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13224),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13212)),4326));
INSERT INTO gis.links VALUES (null,13224,13202,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13224),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13202)),4326));
INSERT INTO gis.links VALUES (null,13202,13214,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13202),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13214)),4326));
INSERT INTO gis.links VALUES (null,13214,13208,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13214),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13208)),4326));
INSERT INTO gis.links VALUES (null,13214,13215,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13214),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13215)),4326));
INSERT INTO gis.links VALUES (null,13225,13224,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13225),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13224)),4326));
INSERT INTO gis.links VALUES (null,13224,13206,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13224),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13206)),4326));
INSERT INTO gis.links VALUES (null,13206,13214,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13206),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13214)),4326));
INSERT INTO gis.links VALUES (null,13218,13223,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13218),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13223)),4326));
INSERT INTO gis.links VALUES (null,13224,13208,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13224),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13208)),4326));
INSERT INTO gis.links VALUES (null,13218,13201,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13218),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13201)),4326));

リンクの内容は以下のSQLで確認できます。

SELECT
  L.id,
  F.name AS LinkFrom,
  T.name AS LinkTo,
  TRUNCATE(ST_Distance(F.geom, T.geom),0) AS DIST
FROM links L
LEFT JOIN portals F ON L.portal_from_id = F.id
LEFT JOIN portals T ON L.portal_to_id = T.id;

+-----+-----------------------+-----------------------+-------+
| id  | LinkFrom              | LinkTo                | DIST  |
+-----+-----------------------+-----------------------+-------+
| 121 | 立川市役所            | 国分寺市役所          |  4933 |
| 126 | 府中市役所            | 国分寺市役所          |  4863 |
| 122 | 国分寺市役所          | 調布市役所            |  9772 |
| 123 | 国分寺市役所          | 国立市役所            |  3539 |
| 117 | 国分寺市役所          | 福生市役所            | 12643 |
| 129 | 福生市役所            | 八王子市役所          |  8068 |
| 127 | 福生市役所            | 武蔵村山市役所        |  5776 |
| 118 | 福生市役所            | 多摩市役所            | 15638 |
| 116 | 武蔵村山市役所        | 国分寺市役所          |  8338 |
| 120 | 多摩市役所            | 立川市役所            |  9225 |
| 125 | 多摩市役所            | 府中市役所            |  4543 |
| 128 | 多摩市役所            | 調布市役所            |  8703 |
| 119 | 多摩市役所            | 日野市役所            |  6017 |
| 124 | 稲城市役所            | 多摩市役所            |  5281 |
+-----+-----------------------+-----------------------+-------+
14 rows in set (0.01 sec)

検証実施

リンクでできるフィールド対象ポータル候補のリストアップ

まずはリンクでフィールドを形成する第3のポータルの候補をリストアップします。
リンク元かリンク先に接していて、共通の第3ポータルに接していてる2つのリンクがあればよいと考えます。
「共通の第3ポータルに接していてる」をST_Touches()で抽出します。

SET @pf = 13224;
SET @pt = 13214;
SELECT
  CASE WHEN FL.portal_to_id = @pf THEN FL.portal_from_id ELSE FL.portal_to_id END AS third_portal_id,
  CASE WHEN FL.portal_to_id = @pf THEN FP.name ELSE TP.name END AS third_portal_name,
  ST_Length(FL.geom) AS DIST
FROM links FL, links TL, portals FP, portals TP
WHERE
  FL.portal_from_id = FP.id
  AND
  FL.portal_to_id = TP.id
AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pf), FL.geom)
  AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pt), TL.geom)
AND
  ST_Touches(FL.geom, TL.geom)
ORDER BY ST_Length(FL.geom) DESC;

+-----------------+-------------------+--------------------+
| third_portal_id | third_portal_name | DIST               |
+-----------------+-------------------+--------------------+
|           13218 | 福生市役所        | 15638.296927686466 |
|           13202 | 立川市役所        |   9225.01516690306 |
|           13208 | 調布市役所        |   8703.61452844608 |
|           13206 | 府中市役所        |  4543.755252237839 |
+-----------------+-------------------+--------------------+
4 rows in set (0.02 sec)

色々思案したのですが、今回はSQLの可読性も考慮して、検索を2回に分割することにしました。

まずは最大サイズのフィールド

上の検索結果のうち、最大距離である福生市役所は問題なく一つ目の解です。
なのでこれを取り出すクエリを考えます。
自己結合でもいいのですが、MySQLらしくLIMIT句を使ってしまいます。

SET @pf = 13224;
SET @pt = 13214;
SET @first_id = (SELECT
  CASE WHEN FL.portal_to_id = @pf THEN FL.portal_from_id ELSE FL.portal_to_id END AS third_portal_id
FROM links FL, links TL, portals FP, portals TP
WHERE
  FL.portal_from_id = FP.id
  AND
  FL.portal_to_id = TP.id
AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pf), FL.geom)
  AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pt), TL.geom)
AND
  ST_Touches(FL.geom, TL.geom)
ORDER BY ST_Length(FL.geom) DESC
LIMIT 1);
SELECT @first_id;

+-----------+
| @first_id |
+-----------+
|     13218 |
+-----------+
1 row in set (0.00 sec)

次に反対側のフィールドを考える

正直これは（素人なので）悩みました。まさにパズルでした。

生成した線を延長して広域にわたって左右に分断し、反対側にあるポータルの最遠を探す？
延長ってどうやるの？
左右の判別ってどうやるの？

とまぁそういう方法も技術的にはできるのかもしれませんが、もっと楽な方法がありました。「候補のうち、最初に算出した第3ポータルとのフィールド（POLYGON）内に存在しない最遠のポータル」を探せばよいのです。
まずは候補をリストアップするクエリを考えます。

ユーザー定義変数は継続しているものとします。
「フィールド内に存在しない」はST_Disjoint()=1を使いました。
- ST_Contains()=0だと接しているものを省けないため、福生市も候補に出てきてしまうので今回は使いません。
ST_Disjoint()の第一引数には「最初の第三ポータルとのフィールド」をあてるのですが、これはST_GeomFromText('POLYGON()',4326)で作ることにします。
ST_Disjoint()の第二引数には次の第三ポータルのPOINTをあてるのですが、ここにリンクのLINESTRINGからST_StartPoint()もしくはST_EndPoint()で取り出したPOINTを使ってみました。

SELECT
  CASE WHEN FL.portal_to_id = @pf THEN FL.portal_from_id ELSE FL.portal_to_id END AS third_portal_id,
  CASE WHEN FL.portal_to_id = @pf THEN FP.name ELSE TP.name END AS third_portal_name,
  ST_Length(FL.geom) AS DIST
FROM links FL, links TL, portals FP, portals TP
WHERE
  FL.portal_from_id = FP.id
  AND
  FL.portal_to_id = TP.id
AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pf), FL.geom)
  AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pt), TL.geom)
AND
  ST_Touches(FL.geom, TL.geom)
AND
  ST_Disjoint(
    ST_GeomFromText(
      CONCAT(
        (SELECT CONCAT('POLYGON((',lat,' ',lon,',') FROM portals WHERE `id` = @pf),
        (SELECT CONCAT(lat,' ',lon,',') FROM portals WHERE `id` = @pt),
        (SELECT CONCAT(lat,' ',lon,',') FROM portals WHERE `id` = @first_id),
        (SELECT CONCAT(lat,' ',lon,'))') FROM portals WHERE `id` = @pf)
    )
    ,4326),
    CASE WHEN FL.portal_to_id = @pf THEN ST_StartPoint(FL.geom) ELSE ST_EndPoint(FL.geom) END
  ) = 1
ORDER BY ST_Length(FL.geom) DESC;

+-----------------+-------------------+-------------------+
| third_portal_id | third_portal_name | DIST              |
+-----------------+-------------------+-------------------+
|           13208 | 調布市役所        |  8703.61452844608 |
|           13206 | 府中市役所        | 4543.755252237839 |
+-----------------+-------------------+-------------------+
2 rows in set (0.03 sec)

うまくいったので、この最大を取り出して前のクエリとくっつけると以下のようになりました。

SET @pf = 13224;
SET @pt = 13214;

SET @first_id = (SELECT
  CASE WHEN FL.portal_to_id = @pf THEN FL.portal_from_id ELSE FL.portal_to_id END AS third_portal_id
FROM links FL, links TL, portals FP, portals TP
WHERE
  FL.portal_from_id = FP.id
  AND
  FL.portal_to_id = TP.id
AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pf), FL.geom)
  AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pt), TL.geom)
AND
  ST_Touches(FL.geom, TL.geom)
ORDER BY ST_Length(FL.geom) DESC
LIMIT 1);

SET @second_id = (SELECT
  CASE WHEN FL.portal_to_id = @pf THEN FL.portal_from_id ELSE FL.portal_to_id END AS third_portal_id
FROM links FL, links TL, portals FP, portals TP
WHERE
  FL.portal_from_id = FP.id
  AND
  FL.portal_to_id = TP.id
AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pf), FL.geom)
  AND
  ST_Touches((SELECT geom FROM portals WHERE id = @pt), TL.geom)
AND
  ST_Touches(FL.geom, TL.geom)
AND
  ST_Disjoint(
    ST_GeomFromText(
      CONCAT(
        (SELECT CONCAT('POLYGON((',lat,' ',lon,',') FROM portals WHERE `id` = @pf),
        (SELECT CONCAT(lat,' ',lon,',') FROM portals WHERE `id` = @pt),
        (SELECT CONCAT(lat,' ',lon,',') FROM portals WHERE `id` = @first_id),
        (SELECT CONCAT(lat,' ',lon,'))') FROM portals WHERE `id` = @pf)
    )
    ,4326),
    CASE WHEN FL.portal_to_id = @pf THEN ST_StartPoint(FL.geom) ELSE ST_EndPoint(FL.geom) END
  ) = 1
ORDER BY ST_Length(FL.geom) DESC
LIMIT 1);

SELECT @first_id, @second_id FROM DUAL;

+-----------+------------+
| @first_id | @second_id |
+-----------+------------+
|     13218 |      13208 |
+-----------+------------+

トータル 0.05secでした

フィールド1つの場合

参考までに、多摩市から八王子市にリンクすることを試してみます。
この場合、一つ目の福生市（13218）だけが返ることを期待します。

SET @pf = 13224;
SET @pt = 13201;
-- 以下同文

+-----------+------------+
| @first_id | @second_id |
+-----------+------------+
|     13218 |       NULL |
+-----------+------------+

想定通りです。

フィールドなしの場合

参考までに、多摩市から国立市にリンクすることを試してみます。
この場合、条件を満たさないためフィールドは生成されません。

SET @pf = 13224;
SET @pt = 13215;
-- 以下同文

+-----------+------------+
| @first_id | @second_id |
+-----------+------------+
|      NULL |       NULL |
+-----------+------------+

問題ありませんでした。
今回の検証はここまで。

次回の予定は・・・まだありません。残課題はあるし、他に元ネタもあるんですが、問題はそれに着手できるかどうか・・・

参考

MySQLマニュアル 12.15.1 Spatial Function Reference https://dev.mysql.com/doc/refman/8.0/en/spatial-function-reference.html
CraftMAP 白地図生成サービス http://www.craftmap.box-i.net/ken.php
- 地図画像を使わせてもらいました