MySQL8.0でGIS機能を試す No.2 - Ingressのリンク可能なリンク先の選別

本エントリの概要
大前提
検証したいこと「リンク先ポータルの選別」
- 検証対象のリンク先ポータルの選別条件
データ設計
検証実施
検索1 「10km以内のポータルに絞り込む」
検索2 「既存のリンクと交差しない」
検索3 「既存のリンクと一致しない」
距離を延ばすとどうなるでしょう
参考

本エントリの概要

位置情報ゲームIngressの機能の一部をMySQL8.0のGIS機能を使って再現できるかを試してみた記録。
今回はその2として「リンク可能なリンク先の選別」を試します。

大前提

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

検証したいこと「リンク先ポータルの選別」

検証対象のリンク先ポータルの選別条件

リンク元ポータルは固定
リンク同士が交差するリンクは作れない
リンク元とリンク先の間にすでにリンクがある場合は作れない
リンク先が一定距離以内のものだけ選別する

ルール上は他にも条件があります。今回以下のリンク条件の設計は省きます。

リンク先のポータルキーを保持していること
リンク先が自陣に占有されていること
リンク先に自陣のレゾネーターが8本残っていること

ただ、「世界中どこにでも自由にリンクできる」訳ではことを知らない方のために念のため説明しておきます。

リンク先のポータルのカギ"ポータルキー"を持っていないとリンクを作れない
ポータルキーはそのポータルの近くまで行って「ハック」というアクションをしないと手に入らない
- ハックには冷却期間があり、連続してハックできない
ポータルキーはリンクを作ると消費する
ユーザー同士の（ポータルキーを含む）アイテム交換は実際に同じ場所にいる必要がある

データ設計

ポータルの位置情報として前回のエントリで作ったportalsテーブルを利用します。
- MySQL8.0でGIS機能を試すためのデータ準備 - untitled .engineer
実際のポータルはもっと多い（非公式の参考情報では港区だけで2500ポータル以上）のですが、実際に保持するポータルキー最大2000の中から選別することになります。
これを実装するため（ほかの検証項目も考慮）のデータ設計として、portalsテーブルのほかに作成済のリンク情報を格納するlinksテーブルを作ります。

CREATE TABLE links (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `portal_from_id` int(11) NOT NULL,
    `portal_to_id` int(11) NOT NULL,
    `geom` GEOMETRY NOT NULL,
    PRIMARY KEY (`id`)
    ,UNIQUE(`portal_from_id`,`portal_to_id`)
    ,CONSTRAINT duplicate_check CHECK(`portal_from_id` != `portal_to_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

NULL/NOT NULLの区別に深い意味はありません。
遊びでcheck制約をつけています。構文は通りますが、MySQLの暗黒面に吸い込まれてなかったことにされます。

検証実施

検証内容

以下を結ぶリンクが存在するとする(「役所」を省略します)
- 新宿区-港区
- 港区-台東区
- 台東区-練馬区
- 練馬区-世田谷区
- 世田谷区-渋谷区
新宿区役所から張れるリンク先を検索する
まずは10km以内を検索する

確認内容

リンクがクロスする杉並区、豊島区など外側にはリンクを張れない
リンクの頂点である台東区、練馬区などはリンクがクロスしないので張れる
すでにリンクされている港区へは張れない
開放されている品川区など南東側へはリンクを張れる

f:id:dupont_kedama:20180905194621p:plain （大田区に丸が付いてますが、10km以内の条件の場合は対象外です）

データ投入

linksテーブルにリンク情報をGEOMETRY型で投入します。
POINT間を結ぶ線なのでLINESTRING型を使います。
今回はportalsテーブルから緯度経度を取り出してLINESTRING()のWKT経由でLINESTRING型を作ります。
- POINT型から緯度経度を取り出す方法やWKTを経由しない方法もあるようなのですが、記録は別の機会にします。

INSERT INTO links VALUES (
  null,
  13112,
  13113,
  ST_GeomFromText(
    CONCAT(
      (SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13112),
      (SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13113)
    )
  ,4612)
);

これを繰り返して上記の5本のリンクを登録します。

INSERT INTO gis.links VALUES (null,13104,13103,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13104),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13103)),4612));
INSERT INTO gis.links VALUES (null,13103,13106,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13103),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13106)),4612));
INSERT INTO gis.links VALUES (null,13106,13120,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13106),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13120)),4612));
INSERT INTO gis.links VALUES (null,13112,13120,ST_GeomFromText(CONCAT((SELECT CONCAT('LINESTRING(',lat,' ',lon,',') FROM portals WHERE `id` = 13112),(SELECT CONCAT(lat,' ',lon,')') FROM portals WHERE `id` = 13120)),4612));

検索1 「10km以内のポータルに絞り込む」

リンク元からの距離が10km以内のポータルにST_Distance()を使って絞り込みます。
ST_Distance()の戻り値の単位はメートルです。

SELECT
  PT.name,
  ST_Distance(PF.geom, PT.geom) AS DIST
FROM portals PT, portals PF
WHERE PF.id = 13104
AND PT.id != 13104
AND ST_Distance(PF.geom, PT.geom) < 10000
ORDER BY ST_Distance(PF.geom, PT.geom);

+--------------------+--------------------+
| name               | DIST               |
+--------------------+--------------------+
| 東京都庁           | 1175.4095006244806 |
| 渋谷区役所         | 3549.5686834591866 |
| 豊島区役所         | 3757.4751184419847 |
| 中野区役所         | 3882.5356232040904 |
| 千代田区役所       |  4535.764268316921 |
| 文京区役所         |  4676.014716130442 |
| 目黒区役所         |  5852.924396190413 |
| 港区役所           |  5897.349461409455 |
| 杉並区役所         |  6097.523104640373 |
| 板橋区役所         |  6345.303138702013 |
| 練馬区役所         |  6549.366224942158 |
| 中央区役所         |  6723.568951496037 |
| 世田谷区役所       |  6991.478924121638 |
| 北区役所           |  7071.888306636993 |
| 台東区役所         |  7225.022753473394 |
| 荒川区役所         |   8605.61770356254 |
| 墨田区役所         |  9074.479658534936 |
| 品川区役所         |  9737.160881870968 |
+--------------------+--------------------+
18 rows in set (0.13 sec)

【2018/09/06追記】 
SRID=4326からSRID=4612に変更したことでここの小数点以下が変わりました。
以下はSRID=4326のときの結果抜粋です。
| 品川区役所   |  9737.160882015474 |
（差は0.000000144506m）

検索2 「既存のリンクと交差しない」

これから作ろうとするリンクが既存のリンクと交差しないものに絞り込みます。
ST_Crosses()=1が使えそうです。
「これから作ろうとするリンク」は ST_GeomFromText('LINESTRING(xx yy, xx yy)',4612) で作り出します。
距離の小数点以下を省いて見やすくします。

SELECT
  PT.name,
  TRUNCATE(ST_Distance(PF.geom, PT.geom),0) AS DIST
FROM portals PT, portals PF
WHERE PF.id = 13104
AND PT.id != 13104
AND ST_Distance(PF.geom, PT.geom) < 10000
AND NOT EXISTS(
  SELECT `id`
  FROM links L
  WHERE 
    ST_Crosses(
      ST_GeomFromText(
        CONCAT(
          'LINESTRING(',PF.lat,' ',PF.lon,',',PT.lat,' ',PT.lon,')'
        )
      ,4612),
      L.geom
    ) = 1)
ORDER BY ST_Distance(PF.geom, PT.geom);

+--------------------+------+
| name               | DIST |
+--------------------+------+
| 東京都庁           | 1175 |
| 渋谷区役所         | 3549 |
| 中野区役所         | 3882 |
| 千代田区役所       | 4535 |
| 文京区役所         | 4676 |
| 港区役所           | 5897 |
| 練馬区役所         | 6549 |
| 世田谷区役所       | 6991 |
| 台東区役所         | 7225 |
| 品川区役所         | 9737 |
+--------------------+------+
10 rows in set (0.15 sec)

既存リンクの外側がフィルタされたことが確認できます。

検索3 「既存のリンクと一致しない」

「これから作ろうとするリンク」が既存のリンクと一致しないものに絞り込みます。
ST_Equals()=1が使えそうです。

SELECT
  PT.name,
  TRUNCATE(ST_Distance(PF.geom, PT.geom),0) AS DIST
FROM portals PT, portals PF
WHERE PF.id = 13104
AND PT.id != 13104
AND ST_Distance(PF.geom, PT.geom) < 10000
AND NOT EXISTS(
  SELECT `id`
  FROM links L
  WHERE 
    ST_Crosses(
      ST_GeomFromText(
        CONCAT(
          'LINESTRING(',PF.lat,' ',PF.lon,',',PT.lat,' ',PT.lon,')'
        )
      ,4612),
      L.geom
    ) = 1)
AND NOT EXISTS(
  SELECT `id`
  FROM links L
  WHERE
    ST_Equals(
      ST_GeomFromText(
        CONCAT(
          'LINESTRING(',PF.lat,' ',PF.lon,',',PT.lat,' ',PT.lon,')'
        )
      ,4612),
      L.geom
    ) = 1)
ORDER BY ST_Distance(PF.geom, PT.geom);

+--------------------+------+
| name               | DIST |
+--------------------+------+
| 東京都庁           | 1175 |
| 渋谷区役所         | 3549 |
| 中野区役所         | 3882 |
| 千代田区役所       | 4535 |
| 文京区役所         | 4676 |
| 練馬区役所         | 6549 |
| 世田谷区役所       | 6991 |
| 台東区役所         | 7225 |
| 品川区役所         | 9737 |
+--------------------+------+
9 rows in set (0.22 sec)

ちゃんと港区へのリンクがフィルタされました。
なんか思った通りのことができましたので検証成功とします。

距離を延ばすとどうなるでしょう

上では「10km以内」としましたが、Ingressのゲーム内では判別するのは200km以内らしいです。すごいですね。
参考までに AND ST_Distance(PF.geom, PT.geom) < 10000 の部分の数値を大きく10倍(100km)にするとどうなるでしょう。

+--------------------+-------+
| name               | DIST  |
+--------------------+-------+
| 東京都庁           |  1175 |
  (中略)
| 品川区役所         |  9737 |
| 大田区役所         | 14755 |
| 袖ケ浦市役所       | 37101 |
| 木更津市役所       | 40091 |
| 君津市役所         | 44167 |
| 富津市役所         | 45442 |
| 鋸南町役場         | 65781 |
| 大多喜町役場       | 66923 |
| 南房総市役所       | 73264 |
| 鴨川市役所         | 73686 |
| 館山市役所         | 78835 |
| 御宿町役場         | 80801 |
| 勝浦市役所         | 82183 |
+--------------------+-------+
21 rows in set (0.32 sec)

大田区に加えて上総国と安房国が入ってきました。地図で見てみるとこんな感じです。
f:id:dupont_kedama:20180905194658p:plain

さらに10倍1000kmにするとどうでしょうか。

+--------------------+--------+
| name               | DIST   |
+--------------------+--------+
| 東京都庁           |   1175 |
  (中略)
| 品川区役所         |   9737 |
| 大田区役所         |  14755 |
| 袖ケ浦市役所       |  37101 |
| 木更津市役所       |  40091 |
| 君津市役所         |  44167 |
| 富津市役所         |  45442 |
| 鋸南町役場         |  65781 |
| 大多喜町役場       |  66923 |
| 南房総市役所       |  73264 |
| 鴨川市役所         |  73686 |
| 館山市役所         |  78835 |
| 御宿町役場         |  80801 |
| 勝浦市役所         |  82183 |
| 八丈町役場         | 286454 |
| 青ヶ島村役場       | 358008 |
| 小笠原村役場       | 982304 |
+--------------------+--------+
24 rows in set (1.24 sec)

東京の島嶼部が入ってきました。（地図は省略）
（改めて、小笠原遠いですね。）

ただちょっと、秒数を見てください。
10km以内のとき：0.22 sec
100km以内のとき：0.32 sec
1000km以内のとき：1.24 sec
ポータル候補数は同等とはいえ、リンク数は比較になりません。
ゲーム内の実装は色々な部分で違いそうな予感がしますね。

【2018/09/06追記】
SRID=4326からSRID=4612に変更したことでかなりパフォーマンスが変わりました。 
SRID=4326での結果は以下です。
10km以内のとき：0.33 sec
100km以内のとき：0.68 sec
1000km以内のとき：2.07 sec

次回はIngressからちょっと離れて「複数のPOINT型からLINESTRING型を作る方法」について考えます。

参考

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
- 地図画像を使わせてもらいました
- 注：渋谷区役所の位置が旧庁舎の場所を指していたのに気づくのが遅れたため、地図上での検証とクエリの結果が違い混乱しました。地図は生ものですね。