26. Dimensionally Extended 9-Intersection Model

"Dimensionally Extended 9-Intersection Model" (DE9IM) は、二つの空間オブジェクトがどのように相互作用しているかをモデル化するためのフレームワークです。

最初に、あらゆる空間オブジェクトは次に示すものを持っています:

• 内部

• 境界

• 外部

ポリゴンの場合、内部、境界、外部は明確です:

内部はリングで囲まれた部分で、境界はリング自体です。外部は平面上のポリゴンを除く全てです。

線についての内部、境界と外部はあまり知られていません:

内部は端点に挟まれたラインの一部です。境界は線の端点です。外部は平面上の他のすべてです。

ポイントでは、さらに奇妙です: 内部はポイントで、境界は空集合で、外部は平面上の他のすべてです。

これらの内部、外部、境界の定義を使うと、二つの空間地物間の内部/境界/外部について9個の可能性のある交差の次元を使って、二つの空間地物の間の関係を特徴づけることができます。

上の例のポリゴンについては、内部の交差は2次元領域ですので、マトリクスの一部に "2" が入ります。境界はポイントで交差していますが、0次元ですので、マトリクスの一部に 0 が入ります。

要素間に交差が無いときは、正方行列は "F" で埋められます。

他の例を示します。ポリゴンに一部が入っているラインストリングです:

この場合のDE9IM行列は次のようになります:

二つのオブジェクトの境界は実際には交差していない (ラインの端点がポリゴンの内部に影響していますが、境界には影響しておらず、逆も同様です) ため、B/C セルは "F" で埋められます。

DE9IM行列を埋めるのは視覚的には楽しいですが、コンピュータに任せられるなら、その方がいいです。ST_Relate 関数がそのためにあります。

前の例では、単純なボックスとラインを使って、ポリゴンとラインストリングと同じ空間関係となるよう単純化できました:

SQLでDE9IM情報を生成することができます:

SELECT ST_Relate(
         'LINESTRING(0 0, 2 0)',
         'POLYGON((1 -1, 1 1, 3 1, 3 -1, 1 -1))'
       );

答 (1010F0212) は視覚的に計算したものと同じですが、1行目、2行目、3行目がまとめて追加された9文字の文字列として返されています。

101
0F0
212

しかしながら、DE9IM の威力はこれらを生成することではなく、非常に限定的な相互関係を持つジオメトリを探索するための一致するキーとして使われることで発揮されます。

CREATE TABLE lakes ( id serial primary key, geom geometry );
CREATE TABLE docks ( id serial primary key, good boolean, geom geometry );

INSERT INTO lakes ( geom )
  VALUES ( 'POLYGON ((100 200, 140 230, 180 310, 280 310, 390 270, 400 210, 320 140, 215 141, 150 170, 100 200))');

INSERT INTO docks ( geom, good )
  VALUES
        ('LINESTRING (170 290, 205 272)',true),
        ('LINESTRING (120 215, 176 197)',true),
        ('LINESTRING (290 260, 340 250)',false),
        ('LINESTRING (350 300, 400 320)',false),
        ('LINESTRING (370 230, 420 240)',false),
        ('LINESTRING (370 180, 390 160)',false);

**湖**と**ドック**が存在するデータモデルを考えます。ドックは湖の内側になければならず、ドックの一方の端点はドックのある湖の境界に接している必要があるとします。このルールに従うドックを見つけることができるでしょうか?

要件に合致するドックには次の特徴があります:

• ドックの内部と湖の内部との交差は線形 (1次元)

• ドックの境界は湖の内部と点 (0次元) の交差

• ドックの境界は湖の境界*とも*点 (0次元) の交差

• ドックの内部は湖の外部と交差しない (F)

これらより DE9IM 行列は次のようになります。

全てのドックを見つけるには、湖とインタセクトするドック (結合のキーに使用する**潜在的な**候補のスーパーセット) を見つけて、その後、要件に合致する全てのドックを見つけます。

SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, '1FF00F212');

-- Answer: our two good docks

ST_Relate の3パラメータ版は、パターンに合致すると TRUE を返し、合致しないと FALSE を返すことに注意して下さい。これのように完全に定義されたパターンについては、3パラメータ版は必要ではありません --文字列の等価演算子を使うことができたかも知れません。

しかしながら、緩いパターンの検索では、3パラメータでパターン文字列に代用文字を入れることが可能です。次のようになります:

• "*" は「このセルには任意の値が受け入れられる」ことを示しています

• "T" は「FALSE でない値 (0, 1, 2) が受け入れられる」ことを示しています

たとえば、本例の図で含まれなかった、可能性のあるドックの一つは、湖の境界とのインタセクト部分が2次元になるドックです:

INSERT INTO docks ( geom, good )
  VALUES ('LINESTRING (140 230, 150 250, 210 230)',true);

この例を「要件に合致する」ドックに入れる場合には、クエリの関連パターンを変更する必要があります。特に、ドックの内部と湖の境界とのインタセクトする部分は、1 (新しいケース) または F (元からのケース) のどちらかになりえます。パターンで "*" によってすべて受け入れるようにします。

SQLは次のようになります:

SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, '1*F00F212');

-- Answer: our (now) three good docks

前の例からより厳格な SQL が新しいドックを"返さない"ことを確認します。

26.1. データ品質テスト

TIGER データは、準備される時に、慎重な品質管理がされています。厳格な標準を満たすことを期待しています。例えば、統計調査街区で他の街区とオーバラップすることはありません。それをテストできるでしょうか?

もちろんです!

SELECT a.gid, b.gid
FROM nyc_census_blocks a, nyc_census_blocks b
WHERE ST_Intersects(a.geom, b.geom)
  AND ST_Relate(a.geom, b.geom, '2********')
  AND a.gid != b.gid
LIMIT 10;

-- Answer: 10, there's some funny business

同様に、道路データが全て端点にしかノードが無いと期待されます。つまり、インタセクトする部分はラインの端点で発生し、中間点では発生しないと期待されます。

インタセクトする (結合する) けれども境界間でインタセクトしている部分が 0 次元でない (つまり端点が接触しない) ストリートを探すことでテストできます:

SELECT a.gid, b.gid
FROM nyc_streets a, nyc_streets b
WHERE ST_Intersects(a.geom, b.geom)
  AND NOT ST_Relate(a.geom, b.geom, '****0****')
  AND a.gid != b.gid
LIMIT 10;

-- Answer: This happens, so the data is not end-noded.

26.1.1. 関数リスト

ST_Relate(geometry A, geometry B): ジオメトリ間の DE9IM の関係を表現するテキスト文字列を返します。