Zenn
🌏

ST_CONTAINS(), ST_COVERS(), ST_INTERSECTS() の違いを理解する

2021/06/04に公開
MySQL
Database
postgis
GIS
Snowflake
tech

最近仕事で GIS に触れることが多いのですが、ST_CONTAINS() と ST_COVERS() と ST_INTERSECTS() の違いがわかりにくすぎるので、未来の自分のために解説していきます。

Interior, Boundary, Exterior

ST_CONTAINS(), ST_COVERS(), ST_INTERSECTS() といった関数は OpenGIS 標準で定義されており、それぞれ Contains, Covers, Intersects という関係に対応します。

この「関係」は Spatial Predicates という名前がついており、DE-9IM (Dimensionally Extended 9-Intersection Model) というモデルにより定義されていて、Geometry 同士の Interior (内部), Boundary (境界), Exterior (外部) がどういう位置関係かになっているかによって評価が定義されています。

そこで、まず Geometry にとっての Interior, Boundary, Exterior が何なのかを確認していきます。

(Wikipedia をソースにするのは気が引けるのですが、標準は公開文書じゃないし、かなりわかりやすかったので参照します。)

https://en.wikipedia.org/wiki/DE-9IM#Standards

今回は Point, LineString, Polygon だけのシンプルな世界で考えるので、この部分を抜き出すと以下のような定義になります。

Geometry Type Interior Boundary
Point 点自身 なし
LineString 終端を除く線上のすべての点 終端の 2 点
Polygon 境界線内の点すべて 境界線の点すべて

Exterior は上記以外の点がすべでなので省略します。

この概念は、これ以降の話を理解するのに非常に重要なので抑えておいてください。つまるところ、空間上のすべての点は、ある Geometry g の Interior, Boundary, Exterior のいずれかに分類されます。

ST_CONTAINS(), ST_COVERS(), ST_INTERSECTS()

さて、本題に入りましょう。

https://en.wikipedia.org/wiki/DE-9IM#Spatial_predicates

上記から Contains, Covers, Intersects の定義を確認すると

  • a contains b (ST_CONTAINS(a, b)):
    • a の Exterior に b の Interior/Boundary の点が含まれない
    • a の Interior に b の Interior のいずれかの点が含まれる
  • a covers b (ST_COVERS(a, b)):
    • a の Exterior に b の Interior/Boundary の点が含まれない
    • (a の Interior/Boundary に b の Interior/Boundary のいずれかの点が含まれる) → 無視できる
  • a intersects b (ST_INTERSECTS(a, b)):
    • a の Interior/Boundary に b の Interior/Boundary のいずれかの点が含まれる

という形になります。

ここで、a covers b の「a の Interior/Boundary に b の Interior/Boundary のいずれかの点が含まれる」条件は「a の Exterior に b の Interior/Boundary の点が含まれない」を満たしていれば自動的に満たされる[1]ため、無視できます。

つまり、Contains と Covers の違いは b が a に含まれているべき点が Interior に限定されるか Boundary も含むか、であり、Covers と Intersects の違いは a の Exterior に存在する b の点が許容されるかどうかになります。

ちなみに、ST_WITHIN(), ST_COVEREDBY(), ST_DISJOINT() は上記の定義を元に、下記のように考えることができます。

  • ST_WITHIN(a, b) = ST_CONTAINS(b, a)
  • ST_COVEREDBY(a, b) = ST_COVERS(b, a)
  • ST_INTERSECTS(a, b) = NOT ST_DISJOINT(a, b)

つまりどうなるか

上記の定義を整理しましょう。Point, LineString, Polygon 同士の重なり合わせは、基本的に以下のケースで網羅されます。[2] (1〜5 は図省略)

  1. Point a 上に Point b が存在する
  2. LineString a 上に Point b が存在する
  3. LineString a の端点に Point b が存在する
  4. Polygon a の内部に Point b が存在する
  5. Polygon a の境界線上に Point b が存在する
  6. Polygon a の内部に LineString b が存在する
  7. Polygon a の境界線上に重なるように LineString b が存在する
  8. Polygon a の境界線上に LineString b の端点 p が存在し、a の内部に端点 q が存在する
  9. Polygon a の境界線上に LineString b の端点 p, q が存在し、a の内部を横切っている
6 7 8 9

これらのケースに各関数を適用した場合、下記のようになります。

Function 1 2 3 4 5 6 7 8 9
ST_CONTAINS(a, b) True True False True False True False True True
ST_COVERS(a, b) True True True True True True True True True
ST_INTERSECTS(a, b) True True True True True True True True True

3, 5, 7 のケースのみが ST_CONTAINS() で False を返しています。

3 のケースは、LineString a の端点は Interior ではなく Boundary で、Point にはその点以外の点が存在しないため、「a の Interior に b の Interior のいずれかの点が含まれる」が満たされないため、False となります。

5 のケースも同様に、Polygon a の境界線は Boundary なので、「a の Interior に b の Interior のいずれかの点が含まれる」が満たされないため、False となります。

7 のケースは、Polygon a の Boundary 上に LineString b のすべての点が乗ってしまっているため、a の Interior に 1 点も存在しなくなり、False となります。

逆に 8 や 9 のケースでは、LineString b の Boundary は Polygon a の Boundary 上にありますが、b の Interior の一部が a の Interior に含まれているため、True となります。混乱しがちなポイントですが、Contains (ST_CONTAINS()) は a の Boundary 上に b の点が含まれることを禁止しているわけではなく、あくまで a の Interior に何らかの b の点があれば True です。

ちなみに上記の真理値表では ST_COVERS() と ST_INTERSECTS() はまったく同じように見えますが、これは今回 a の Exterior に b がはみ出しているケースを考えていないからであって、そのようなケースでは ST_COVERS() は False になり、ST_INTERSECTS() のみが True を取り得ます。

つまりどういうことなの

つまり(定義のセクションで書いたこととほぼ同じですが)下記のルールを覚えておけば OK です。

  • b のすべてが a の Boundary に乗っている場合に True になるのが ST_COVERS(a, b)、False になるのが ST_CONTAINS(a, b)
  • b の一部が a の Exterior にはみ出してしまった場合に True になるのが ST_INTERSECTS(a, b)、False になるのが ST_COVERS(a, b)

したがって ST_CONTAINS() がこの 3 つの中で最も厳しい条件で、ST_INTERSECTS() が最もゆるい条件になります。

これがわかると何がうれしいの

WHERE 句を書くときに間違えなくなります……というのは当然として、実はもう少しメリットがあります。

前述の通り、ST_CONTAINS() は複合条件なのに対し、ST_COVERS() は事実上単一条件で、 ST_INTERSECTS() はそもそも単一条件です。

処理系にも依りますが、上記の定義の通りに正しく実装されているとすると、ST_CONTAINS() が最も重い処理になり、ST_INTERSECTS() が最も軽い処理である可能性が高いことになります。

とはいえ大した差でもないのでは、と思うかもしれませんが、これが実際 10 億行に対して適用されるフィルタの一部だったとしたら、これらは 10 億回ずつ呼ばれることになり、仮に性能差が 0.1 msec だったとしても乱暴に言えば[3]累計で 27 時間分ぐらいの差になるわけです。

つまり、例えば ST_CONTAINS() の実行がボトルネックになっている場合に、本当は ST_CONTAINS() じゃなくて ST_COVERS() でもシステムの要件を満たせるのだとしたら、その性能差分だけ損をしていることになり、逆に言えば ST_COVERS() に書き変えるだけで性能が改善する可能性があります。

ST_INTERSECTS() についても同様です。聡明な読者の方は「なぜこの並びに ST_INTERSECTS() がいるんだ」とずっと思いながら読んでいたかもしれませんが、このときのためでした。

実際のユースケースにおいて ST_CONTAINS() とその仲間たちを使いたいケースでは、だいたいの場合で対象の Geometry Type は決まっているかと思います。すなわち、単一のクエリ内で Polygon と LineString だったり LineString と Point だったりが行によっていろいろ比較される、みたいなユースケースはおそらくレアです。

ST_INTERSECTS() はそんな Geometry Type が決まっているユースケース、特に「Polygon に Point が含まれるか」を確認したいときに有効になるケースがあります。

Point は単一の点であるため、ST_INTERSECTS() が True　になるケース、すなわち「a の Interior/Boundary に b の Interior/Boundary のいずれかの点が含まれる」を満たすとき、b はそれ以外の点を持っていません。

すなわち、b の点が a の Exterior に含まれることは論理的にあり得ないため、Polygon と Point の比較においては実質的に ST_COVERS() とまったく同じ動作になります。したがって、仮に ST_COVERS() の性能が ST_CONTAINS() とそんなに変わらないような処理系があった場合には、このケースにおいては ST_INTERSECTS() に書き換えることで高速化を計れる可能性があります。

もちろん、意味的には当然正しくなく、かつデータの正しさを無条件で信頼してしまっているため、クエリの可読性としては大いに問題がある書き換えだとは思いますが、背に腹は代えられないということもあるかと思うので、頭の片隅に選択肢として持っておくといいかもしれません。

落とし穴(1): 浮動小数点数の丸め誤差

例えば地図上の座標を扱う場合、だいたいのケースで座標は経度・緯度になるため、かなり細かい小数点となります。

このときに、例えば Polygon の Boundary 上の点 p から点 q までの LineString が重なっているようなケースの場合、当該 LineString や当該 Polygon の中間点は計算で求めることになり、またその結果にかかる浮動小数点数の丸め誤差は始点・終点によって微妙にずれる可能性があるため、一部の点が Exterior にあると判断されたりすることがあります。

こういった丸め誤差のケースは基本的に実装によってカバーされていることが多いですが、たまにハマることがあるので、原因の候補の一つとして覚えておくといいかもしれません。

落とし穴(2): 空間参照系

下記のクエリを見てください。

with g as (
  select
    st_geomfromtext('POLYGON((0 0, 90 0, 90 90, 0 90, 0 0))') a,
    st_geomfromtext('LINESTRING(0 0, 90 90)') b
)
select st_contains(a, b) from g;

この Polygon は (0, 0), (90, 0), (90, 90), (0, 90) を頂点に持つ四角形で、LineString は (0, 0) から (90, 90) に引かれた線、すなわち対角線です。

これは前述の 9 のパターンのため、ST_CONTAINS() は True を返します。実際これを MySQL で実行すると True (MySQL では 1) が返ります。

mysql> with g as (
    ->   select
    ->     st_geomfromtext('POLYGON((0 0, 90 0, 90 90, 0 90, 0 0))') a,
    ->     st_geomfromtext('LINESTRING(0 0, 90 90)') b
    -> )
    -> select st_contains(a, b) from g;
+-------------------+
| st_contains(a, b) |
+-------------------+
|                 1 |
+-------------------+
1 row in set (0.05 sec)

しかし、これを試しに Snowflake で実行すると False が返ります。

with g as (
   select
     to_geography('POLYGON((0 0, 90 0, 90 90, 0 90, 0 0))') a,
     to_geography('LINESTRING(0 0, 90 90)') b
 )
 select st_contains(a, b) from g;
+-------------------+
| ST_CONTAINS(A, B) |
|-------------------|
| False             |
+-------------------+
1 Row(s) produced. Time Elapsed: 0.679s

なぜでしょうか。Snowflake のバグでしょうか。

実はこれが空間参照系 (SRS : Spatial Reference System) の落とし穴です。

MySQL ではデフォルトの SRS が SRID 0、すなわちデカルト座標系になっています。その一方で、Snowflake は GEOGRAPHY 型のみに対応しているので SRS は SRID 4326、すなわち WGS84 世界測地系になっており、平面座標系ではなく地球を想定した球面座標系になっています。

GEOGRAPHY の世界では、座標は (x, y) ではなく (longitude, latitude) になるため、(90, 90) は東経 90 度・北緯 90 度の点を表します。

ではここで、(90, 90) と (0, 90) の点が地球上でどこに位置するかを考えてみましょう。これらの点はどちらも北緯 90 度ですが、地球上には北緯 90 度の点は 1 つしかありません。北極点です。

つまり、POLYGON((0 0, 90 0, 90 90, 0 90, 0 0)) は一見四角形に見え、実際デカルト座標系では四角形ですが、WGS84 世界測地系においては (90, 90) と (0, 90) が同一点になるため、事実上 POLYGON((0 0, 90 0, 90 90, 0 0)) となり、三角形になります。

したがって LINESTRING(0 0, 90 90) は対角線ではなく、三角形の一辺になるため、LineString 全体が Boundary に乗ってしまっている状態、すなわち前述の 7 のケースになるため、ST_CONTAINS() が False を返しているわけです。

実際に MySQL でも、SRID を 4326 に設定することで同じ動作が確認できます。

mysql> with g as (
    ->   select
    ->     st_geomfromtext('POLYGON((0 0, 90 0, 90 90, 0 90, 0 0))', 4326) a,
    ->     st_geomfromtext('LINESTRING(0 0, 90 90)', 4326) b
    -> )
    -> select st_contains(a, b) from g;
+-------------------+
| st_contains(a, b) |
+-------------------+
|                 0 |
+-------------------+
1 row in set (0.05 sec)

このように Geospatial のデータの扱いや計算結果は、どの SRS を使用しているかによって大きく変化するため、用途に応じた SRS を選択し、その座標系における正しい動作に着目して使用する必要があります。

結論

だいぶタイトルから横道に逸れましたが、タイトルの件については以下の点がキーポイントになります。

  • b のすべてが a の Boundary に乗っている場合に True になるのが ST_COVERS(a, b)、False になるのが ST_CONTAINS(a, b)
  • b の一部が a の Exterior にはみ出してしまった場合に True になるのが ST_INTERSECTS(a, b)、False になるのが ST_COVERS(a, b)

そしてこれらの区別ができるようになることで、以下の利点を得ることができます。

  • 要件にあった正しい関数が使えるようになる
  • 要件や Geometry Type に応じてより負荷の低い関数を使えるようになる
    • ST_CONTAINS() > ST_COVERS() >= ST_INTERSECTS()

ただし、そもそもの Geometry が重なっているかどうかなどの位置関係は、空間参照系 (SRS) つまり座標系によって大きく変化するため、要件にあった正しい SRS を選択することも重要になります。

このように GIS (Geospatial) はわりと複雑な話が多いですが、正しく理解して使えるとだいぶ便利なツールだし、何よりめちゃめちゃに面白いので、ぜひみなさんにも楽しんでいただきたいです。

最後に宣伝ですが、Snowflake でも Geospatial が先日リリースされ、順次機能拡張しておりますので、ぜひご活用いただければと思います。

https://docs.snowflake.com/ja/sql-reference/data-types-geospatial.html

脚注

  1. 空間上のあらゆる点は a の Interior, Boundary, Exterior のいずれかに分類可能であるため、b の点が a の Exterior に含まれていなければ、自動的に a の Interior か Boundary のいずれかに含まれることになる。 ↩︎

  2. Point には Boundary が存在しないため、あらかじめ除いています。また、b のほうが次元が大きい場合は、基本的に a の Exterior に b のいずれかの点が存在することになるため、ST_CONTAINS()/ST_COVERS() は常に False を返し、ST_INTERSECTS() は Interior/Boundary のいずれかの点が共有されていれば True、それ以外は False を返します。 ↩︎

  3. 実際はもちろん最適化とか並列実行とかいろいろ絡んでくるのでこんなに単純な線形にはならないことは十分承知しております… ↩︎

Discussion