地図上のジオメトリオブジェクトの重なりを判定する

はじめに

ラクスルのAM(エリアマーケティング)チームでエンジニアをしている藤田です。

AMチームでは、ポスティングや折込といったサービスに関連するシステムの開発をしています。

印刷から配布(ポスティング・折込)までを一気通貫で注文できる点が、通常のポスティングサービスと異なっています。

ポスティング商品を購入する時には、上図のように地図上でポリゴン(地図上の四角いエリアを指します)を選択し、配布するエリアを決めます。

エンドユーザーは、地図上に表示されている円を動かしたり大きさを縮小・拡大することができ、円の中に含まれるポリゴンが選択されるようなUIになっています。(円を使わないでポリゴンを手動で選択するUIも提供しています)

今回は、このポリゴン選択に関連して、地図上のジオメトリオブジェクトの重なりを判定するロジックについて考えてみたいと思います。

ポリゴンのデータ構造と描画

本題に入る前に、地図上のポリゴンのデータ構造と描画方法について簡単に触れておきます。

ポリゴンは、WKT(Well-Known Text)というジオメトリオブジェクトを表現するためのフォーマットを元に描画されています。具体的には、MySQLのGeometry型のカラムにWKTでポリゴンの情報を保存しておき、選択されたポリゴンをGoogleMapのAPIによって描画しています。

WKTでは、ポリゴンを「座標(緯度と経度から成る点)の集合」として扱います。例えば、下記では一つのポリゴンを4つの座標の集合として表現しています。

'POLYGON((緯度1 経度1,緯度2 経度2,緯度3 経度3,緯度4 経度4,緯度1 経度1))'

描画時には、下図のように4つの座標を線でつないだ図形の内部がポリゴンとなります。

シンプルな重なり判定方法

さて、ここからが本題です。

ポスティングの地図画面では「円の中に含まれるポリゴンが選択される」と前述しましたが、「円の中にポリゴンが含まれているかどうか」をどのように実装すれば良いでしょうか？

まず思い浮かぶのは、上図のようにポリゴン毎に基準の座標を1点だけ決めておき、円の中に基準座標が含まれる場合に「円の中にポリゴンが含まれている」とみなすという方法です。

これは、円の中心点の座標と半径が分かれば、下記のように判定することができます。

円の中心点の座標からポリゴンの基準座標の距離 <= 円の半径

この方法は、実装が比較的容易であるというのが利点です。

一方で、基準座標という1点のみを元に判定しているため、円とポリゴンが深く重なっていても基準座標に重ならない限りは選択と見なされず、ポリゴンの形や大きさによってはあまり適切な方法とは言えないかもしれません。

ジオメトリオブジェクトの重なりを厳密に判定する方法

次に、「円とポリゴンが少しでも重なっていたら選択とみなす」という方法について考えてみたいと思います。これは、前述のようにシンプルに実装するのは難しそうです。

そこで、MySQLのSpatial Functionというジオメトリオブジェクトに対して使える分析関数を眺めてみます。すると、ST_Intersectsというまさにジオメトリオブジェクト同士が重なっているかを判定する関数がありました。

-- polygonとpointが重なっている場合
SET @polygon = (SELECT ST_GeomFromText('POLYGON((0 0,10 0,10 10,0 10,0 0))'));
SET @point = (SELECT ST_GeomFromText('POINT(0 0)'));

-- 1 が返却される
SELECT ST_Intersects(@polygon, @point);

-- polygonとpointが重なっていない場合
SET @polygon = (SELECT ST_GeomFromText('POLYGON((0 0,10 0,10 10,0 10,0 0))'));
SET @point = (SELECT ST_GeomFromText('POINT(-1 -1)'));

-- 0 が返却される
SELECT ST_Intersects(@polygon, @point);

ST_Intersectsの引数はジオメトリオブジェクトなので、地図上の円をジオメトリオブジェクトに変換した上でST_Intersectsに渡します。

-- @circle: 円をGeometry型に変換したもの
-- areas.polygon: Geometry型のカラム
SELECT * FROM areas WHERE ST_Intersects(@circle, areas.polygon) = 1

なお、円の中心座標と半径を元にジオメトリオブジェクトを生成する関数はMySQLでは提供していないため、自分で実装する必要があります。(Javascriptであればライブラリがあります)

円をジオメトリオブジェクトに変換するには、円周上の点の座標を求めることになります。長くなってしまうので詳細は割愛しますが、円周上の点の座標を求めるにあたっては、三角関数や地球半径を使う必要がありなかなか興味深いです。

パフォーマンスの向上

ST_Intersectsを使えば円とポリゴンの重なりを厳密に判定できることが分かりましたが、パフォーマンスはどうでしょうか？

実は、単純にST_Intersectsだけを使って対象のポリゴンの検索をしようとすると、非常にパフォーマンスが悪くなります。円やポリゴンの複雑さにもよりますが、データベースに約20万件のポリゴンデータが入っている状態で前述のSQLを実行したところ、15秒以上の時間がかかってしまいました。これは、Webアプリケーションにとっては致命的です。

パフォーマンス向上のための対策の一つは、MBRIntersectsというパフォーマンスの優れた関数で事前に対象のレコードを絞り込むことです。この関数は、基本的にはST_Intersectsと同様にジオメトリオブジェクト同士の重なりを判定するのですが、厳密に重なりを判定するのではなくジオメトリオブジェクトのminimum bounding rectangleを使って重なりを判定するため高速に動作します。

以下のように、ST_IntersectsをMBRIntersectsに置き換えてSQLを実行したところ、今度は200ms程度で完了しました。

-- @circle: 円をGeometry型に変換したもの
-- areas.polygon: Geometry型のカラム
SELECT * FROM areas WHERE MBRIntersects(@circle, areas.polygon) = 1

パフォーマンス向上のもう一つの方法はSpatial indexを使うことです。Geometry型のカラムに対してSpatial indexを張ることにより、Spatial functionのパフォーマンスを向上させることができます。

ただし、私が試した限りではST_Intersectsを使うSQLの実行計画を確認してもSpatial indexが使われていませんでした。一方、MBRIntersectsについては引数となるジオメトリオブジェクトによってSpatial indexが使われるかどうかが変わっていました。

いずれにせよ、MBRIntersectsである程度絞り込んだ後にST_Intersectsで厳密な重なり判定をすることはパフォーマンス向上のために非常に有効なので、Webアプリケーションに組み込む時は必須になると思います。

まとめ

• ジオメトリオブジェクトはWKT形式で表現可能
• ジオメトリオブジェクト同士の厳密な重なり判定にはST_Intersectsが有効
• パフォーマンス向上のためにMBRIntersectsが有効