DE-9IM

次元拡張9交点モデル（DE-9IM）は、幾何学、点集合トポロジー^、地理空間トポロジー、およびコンピュータ空間解析に関連する分野において、 2つの領域（2次元R2における2つのジオメトリ）の空間的関係を記述するために使用されるトポロジーモデルおよび標準規格です。このモデルによって表現される空間的関係は、回転、平行移動、および拡大縮小変換に対して不変です。

この行列は、幾何学的関係を分類するための手法を提供する。大まかに言えば、真偽行列の領域では、512通りの2次元トポロジー関係が存在し、これらを二値分類スキームにグループ化することができる。英語には、「交差する」「接する」「等しい」など、約10種類のスキーム（関係）が存在する。2つの幾何学的関係をあるスキームに照らし合わせてテストすると、その結果は、そのスキームによって命名された空間述語となる。

このモデルは、クレメンティーニら^{[ 1 ] [ 2 ]}がエゲンホーファーらの先駆的な研究^{[ 3 ] [ 4 ]}に基づいて開発しました。地理情報システム（GIS）や空間データベースにおけるクエリとアサーションの標準の基礎として使用されています。

DE-9IMモデルは、以下の形式の3×3交差行列に基づいています。

どこで${\displaystyle \dim }$⁠は、形状aとbの内部(I)、境界(B)、および外部(E)の交差(∩)の寸法です。

この記事で使用されている「内部」と「境界」という用語は、一般トポロジーで使用される意味ではなく、代数トポロジーや多様体理論で使用される意味で使用されています。例えば、線分の内部とは、その両端点を除いた線分であり、その境界は両端点のみです（一般トポロジーでは、平面上の線分の内部は空であり、線分自体が境界となります）。

位相空間演算子の表記では、行列要素は次のように表すこともできます。

空集合(∅)の次元は−1 またはF (偽)で表されます。空でない集合 (¬∅) の次元は、交差の最大次元数で表され、具体的には点の場合は0、線の場合は1、領域の場合は2 となります。したがって、モデルの定義域は{ 0 , 1 , 2 , F }となります。

簡略版${\displaystyle \dim(x)}$値は、値{ 0,1,2 }をT (真)にマッピングすることによって得られます。つまり、ブール領域{ T , F }を使用します。演算子で表された行列は、次のように表現できます。

行列の要素は、以下のように命名できます。

次元領域とブール領域の両方を持つ行列形式は、 「 DE-9IM文字列コード」としてシリアル化することができ、これはそれらを1行の文字列パターンで表現します。1999年以降、文字列コードは標準^{[ 5 ]}フォーマットになっています。

出力チェックやパターン解析では、行列値（または文字列コード）を「マスク」でチェックできます。マスクとは、ワイルドカードとしてオプションのアスタリスク記号（つまり、「*」は設計者が気にしない出力位置（自由値または「気にしない位置」）を示す）を含む、目的の出力値です。マスク要素のドメインは、{ 0 , 1 , 2 , F , * }、またはブール形式の場合は{ T , F , * }です。

空間関係を表現するために、DE-9IM より前に、より単純なモデルである4-Intersectionと9-Intersectionが提案されました^{[ 6 ]} (そして、 4IMと9IMという用語の由来となりました)。入力条件が特定の制約を満たす場合、DE-9IM の代わりにこれらを使用して計算を最適化できます。

DE-9IM の二項空間関係に基づく位相的性質はすべて空間述語です。使いやすさのために、いくつかの一般的な関係に対して「名前付き空間述語」が定義され、後に標準述語となりました。DE -9IM から導出できる空間述語関数には次のものがあります。 ^{[ 4 ] [ 8 ]}

ドメイン{ T , F , * }のマスクで定義された述語:

最後の列に示すように、論理否定またはパラメータ反転（行列転置）によって上記から得られる述語：

入力次元を利用し、ドメイン{ 0 , 1 , T , * }のマスクで定義される述語:

以下の点にご注目ください。

• 位相的に等しいという定義は、それらが同じ点を持つことを意味するものではなく、また、それらが同じクラスに属することを意味するものでもない。

• の出力⁠${\displaystyle \operatorname {DE-9IM} (a,b)}$幾何学aとbに関するすべての解釈可能な述語のリストに含まれる情報を持っています。

• すべての述語はマスクによって計算されます。クロスとオーバーラップのみ、追加の条件があります。${\displaystyle \dim(a)}$そして​​${\displaystyle \dim(b)}$⁠ .

• すべてのマスク文字列コードはで終わります*。これは、EEが自明に真であるため、有用な情報を提供しないためです。

• Equalsマスクは、 Contains ( ) とWithin ( )の「マージ」です。 ( II ∧ ~ EI ∧ ~ EB ) ∧ ( II ∧ ~ IE ∧ ~ BE )。T*F**FFF*T*****FF*T*F**F***

• マスクは、ContainsとCoversのT*****FF*両方の定義に含まれています。Covers はより包括的な関係です。特に、Containsとは異なり、ジオメトリの境界内の点と内部の点を区別しません。ほとんどの場合、ContainsよりもCoversを使用することをお勧めします。

• 同様に、マスクはWithinとCoveredBy のT*F**F***両方の定義に含まれています。ほとんどの場合、WithinよりもCoveredBy を使用することをお勧めします。

• 歴史的に、空間述語を表現するために他の用語や他の形式的アプローチが使用されてきました。たとえば、領域接続計算は1992 年に^{[ 12 ]} Randell、Cohn、Cohnによって導入されました。

解釈

空間述語の用語と意味の選択は、合理的な慣習と位相幾何学研究の伝統に基づいています。^{[ 4 ]}交差、分離、接触、内部、等しい （2 つの幾何学aとbの間） などの関係には、明らかな意味があります。^{[ 10 ] [ 13 ]}

等しい

a = b つまり ( a ∩ b = a ) ∧ ( a ∩ b = b )

内で

a ∩ b = a

交差する

a ∩ b ≠ ∅

タッチ

( a ∩ b ≠ ∅) ∧ ( a ^ο ∩ b ^ο = ∅)

述語ContainsとWithin には 、直感に反する微妙な定義上の側面があります。たとえば、^{[ 10 ]}多角形Pの境界内に完全に含まれる 線Lは、 Pに含まれているとはみなされません。この特異性は、「多角形は境界を含まない」と表現できます。この問題は、上記のContainsの定義の最後の節、「B の内部の少なくとも 1 点が A の内部にある」によって引き起こされます。この場合、境界の考慮を回避した述語Covers の方 が、より直感的な意味を持ちます (定義を参照)。

理解を深めるために、入力の次元性を、意味的複雑性を段階的に導入する根拠として用いることができる。

DE -9IMは、 2つの入力ジオメトリに関する完全な記述的アサーションを提供します。これは、真理値表、3方向比較、カルノー図、ベン図など、 2つのエンティティに関するすべての可能な関係の完全なセットを表す数学関数です。各出力値は、特定の入力の関係を表す真理値表の行のようなものです。

上記のように、 DE-9IM ( a , b )から得られた出力「212101212」は、特定のジオメトリaとbの間のすべてのトポロジ関係を完全に記述したものです。これは、次のことを示しています。${\displaystyle II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\,EE=2}$⁠ .

一方、Intersects ( a , b )や Touches ( a , b )のような述語をチェックする場合（同じ例で「Intersects = true and Touches = true 」となる）、これは「すべての位相関係」を不完全に記述しているに過ぎません。また、述語はジオメトリの次元性についても何も述べていません（ aとbが線、領域、点のいずれであっても関係ありません）。

幾何学的タイプの独立性と述語の完全性の欠如は、2つの幾何学に関する一般的なクエリに役立ちます。

一般的な用途においては、空間述語の使用は、DE-9IM記述よりも人間にとって読みやすいという点でも正当化されます。典型的なユーザーは、述語（内部／境界／外部の交差の集合よりも）についてより直感的に理解できるからです。

述語は、通常のアプリケーションにおいて有用な意味論的性質を持つため、 DE-9IM記述を関連するすべての述語のリストに変換することは有用である。 ^{[ 14 ] [ 15 ]}これは、2 つの異なる意味論的タイプ間の型変換プロセスのようなものである。例:

• 文字列コード「0F1F00102」と「0F1FF0102 」は、「交差、交差、重なり」の意味を持ちます。
• 文字列コード「1FFF0FFF2 」は「等しい」という意味を持ちます。
• 文字列コード「F01FF0102」、「FF10F0102」、「FF1F00102」、「F01FFF102」、「FF1F0F1F2 」は「交差および接触」の意味を持ちます。

• 「エゲンホーファー行列」は、ブール領域の9IM 3x3行列の同義語です。^{[ 23 ]}
• 「クレメンティーニ行列」は、{ 0 , 1 , 2 , F }領域のDE-9IM 3x3 行列の同義語です。^{[ 23 ]}
• 「Egenhofer演算子」と「Clementini演算子」は、ブール演算で使用できる行列要素II、IEなどを指す場合があります。例: 述語「 G ₁はG ₂を含む」は、「 ⟨ G ₁ | II ∧ ~EI ∧ ~EB | G ₁ ⟩ 」で表現でき、これはマスク構文に変換できますT*****FF*。
• 述語「meets」は「touches」の同義語です。「inside」は「within」の同義語です。
• Oracleの^{[ 15 ]} 「ANYINTERACT」は交差の同義語であり、「OVERLAPBDYINTERSECT」は重複の同義語です。その「OVERLAPBDYDISJOINT」には対応する名前付き述語がありません。
• 領域接続計算では、演算子は述語 の同義語をいくつか提供します。disjointはDC (切断)、touchesは EC (外部接続)、equalsは EQ です。OverlapsがPO (部分的に重なり合う) であるなど、その他のものは文脈分析または合成が必要です。^{[ 24 ] [ 25 ]}

• 点集合理論とDE-9IM行列
• DE-9IMの図解チュートリアル