DE-9IM

次元拡張9 交差モデル( DE-9IM ) は、幾何学、点集合位相幾何学、地理空間 位相幾何学、およびコンピュータ空間解析に関連する分野において、2 つの領域 (2 次元の 2 つのジオメトリ、R 2) の空間関係を記述するために使用される位相モデル^および標準です。モデルによって表現される空間関係は、回転、平行移動、およびスケーリング変換 に対して不変です。

マトリックスは、ジオメトリ関係を分類するためのアプローチを提供します。大まかに言えば、真偽マトリックス ドメインでは、2 進分類スキームにグループ化できる 512 の 2D トポロジ関係があります。英語には、「交差する」、「接する」、「等しい」など、約 10 のスキーム (関係) があります。2 つのジオメトリをスキームに対してテストすると、結果はスキームによって名前が付けられた 空間述語になります。

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

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

ここで、⁠ ⁠ は、ジオメトリ${\displaystyle \dim}$aとbの内部(I)、境界(B)、外部(E)の交差(∩)の次元です。

この記事での内部と境界という用語は、一般位相幾何学で使用される意味ではなく、代数位相幾何学と多様体理論で使用される意味で使用されています。たとえば、線分の内部は端点のない線分であり、その境界は 2 つの端点のみです (一般位相幾何学では、平面上の線分の内部は空であり、線分自体の境界です)。

位相空間演算子の表記では、行列要素は次のようにも表される。

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

⁠ ⁠${\displaystyle \dim(x)}$値の簡略化されたバージョンは、値 { 0,1,2 } をT (true) にマッピングすることで得られます。つまり、ブールドメイン{ T , F } を使用します。演算子で示される行列は、次のように表すことができます。

行列の要素は以下のように名前が付けられます。

次元とブール値ドメインを持つ両方の行列形式は、「DE-9IM文字列コード」としてシリアル化することができ、単一行の文字列パターンで表現されます。1999年以来、文字列コードは標準^[5]形式になっています。

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

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

視覚的には、重なり合う2つの多角形ジオメトリの場合、関数DE_9IM( a , b )の結果は次のようになります。^[7]

この行列はシリアル化できます。左から右、上から下に読み取ると、結果は⁠ ⁠${\displaystyle II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\ ,EE=2}$です。したがって、文字列コードとしてのコンパクトな表現は ' 212101212 ' です。

DE-9IMの二元空間関係に基づく位相特性は空間述語である。使いやすさのために、いくつかの共通関係に対して「名前付き空間述語」が定義されており、後に標準述語となった。DE -9IMから派生できる空間述語関数^{には次のものがある: [4] [8]}

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

最後の列に示されているように、論理否定またはパラメータ反転 (行列転置)によって上記から取得できる述語:

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

次の点に注意してください:

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

• ⁠ ⁠${\displaystyle \operatorname {DE-9IM} (a,b)}$の出力には、ジオメトリaとbに関するすべての解釈可能な述語のリストに含まれる情報が含まれます。

• すべての述語はマスクによって計算されます。CrossesとOverlapsのみ、⁠ ⁠および⁠ ⁠に関する追加条件があります。${\displaystyle \dim(a)}$${\displaystyle \dim(b)}$

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

• 等しいマスクは、含む( ) と範囲内( )T*F**FFF*の「マージ」です: ( II ∧ ~ EI ∧ ~ EB ) ∧ ( II ∧ ~ IE ∧ ~ BE )。T*****FF*T*F**F***

• マスクは、 ContainsとCoversT*****FF*の両方の定義で発生します。 Coversはより包括的な関係です。特に、Containsとは異なり、境界内の点とジオメトリの内部の点を区別しません。ほとんどの場合、ContainsよりもCovers を使用する必要があります。

• 同様に、マスクはWithinとCoveredByT*F**F***の両方の定義に存在します。ほとんどの場合、WithinよりもCoveredBy を優先して使用する必要があります。

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

空間述語には、二項関係の次の特性があります。

• 再帰: Equals、Contains、Covers、CoveredBy、Intersects、Within
• 反反射的：分離
• 対称: 等しい、交差する、交差する、接する、重なる
• 推移的: Equals、Contains、Covers、CoveredBy、Within

空間述語の用語と意味の選択は、合理的な慣習と位相研究の伝統に基づいています。^[4] Intersects、Disjoint、Touches、Within、Equals （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 は より直感的なセマンティクス (定義を参照) を持ち、境界の考慮を回避します。

理解を深めるために、入力の次元は意味の複雑さを段階的に導入する正当化として使用できます。

ブール9IM行列で可能な結果の数は2 ⁹ =512で、DE-9IM行列では3 ⁹ =6561です。特定の述語を満たすこれらの結果の割合は次のように決定されます。

通常のアプリケーションでは、ジオメトリは事前に交差し、他の関係がチェックされます。

複合述語「Intersects OR Disjoint」と「Equals OR Different」の合計は 100% (常に true 述語) ですが、「Covers OR CoveredBy」は 41% で、これは合計ではありません。これは、これらが論理補完でも独立関係でもないためです。同様に、「Contains OR Within 」は 21% です。有効な入力セットが互いに素であるため、 「 Crosses OR Overlaps 」の重複する線を無視すると、合計 25% + 12.5% = 37.5% が得られます。

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かつTouches = true 」)、「すべての位相関係」の説明が不完全になります。述語は、ジオメトリの次元についても何も述べません ( aとbが線、領域、または点であるかどうかは関係ありません)。

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

通常のアプリケーションでは、空間述語の使用は、DE-9IM記述よりも人間にとって読みやすいという理由でも正当化されます。つまり、一般的なユーザーは、述語について (内部/境界/外部の交差のセットよりも) より優れた直感を持っています。

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

• 文字列コード「0F1F00102」と「0F1FF0102 」は、「交差と交差と重複」の意味を持ちます。
• 文字列コード「1FFF0FFF2 」は「 Equals 」の意味を持ちます。
• 文字列コード「F01FF0102」、「FF10F0102」、「FF1F00102」、「F01FFF102」、および「FF1F0F1F2 」には、「交差および接触」のセマンティクスがあります。

Open Geospatial Consortium (OGC) は、典型的な空間述語 (Contains、Crosse、Intersects、Touches など) をブール関数として標準化し、DE-9IM モデル^[16]を、{ 0、1、2、F }のドメイン (0 = ポイント、1 = 線、2 = 領域、F = 空集合) を持つ文字列 (DE-9IM コード) を返す関数として標準化しました。このDE - 9IM文字列コードは、データ交換のための標準化された形式です。

シンプルフィーチャアクセス（ISO 19125）標準^[17]の7.2.8章「ジオメトリタイプのSQLルーチン」では、すべてのジオメトリタイプに対してSQL/MM Spatial ^[18]（ISO 13249-3パート3：空間） ST_Dimension、ST_GeometryType、ST_IsEmpty、ST_IsSimple、ST_Boundaryをサポートするルーチンとして推奨しています。同じ標準は、SQL/MMの「パート1、条項6.1.2.3」の関係の定義と一致して、関数ラベルST_Equals、ST_Disjoint、ST_Intersects、ST_Touches、ST_Crosses、ST_Within、ST_Contains、ST_Overlaps 、およびST_Relateを推奨（サポート）しています。

OGC標準のDE-9IMでは、主要なOGC標準ジオメトリタイプに対して、次のような内部と境界の定義が使用されています。^[19]

PostGISなどのほとんどの空間データベースは、標準関数^[20]、、などによってDE-9IM()モデルを実装しています。この関数は標準OGCのDE-9IM文字列コードを出力します。 ST_RelateST_EqualsST_IntersectsST_Relate(a,b)

例: 2 つのジオメトリaとbが交差して点と接している場合 (たとえば⁠ ⁠${\displaystyle \dim(B(a)\cap I(b))=0}$および⁠ ⁠${\displaystyle \dim(I(a)\cap I(b))=F}$ST_Relate(a,b)='FF1F0F1F2' )、またはST_Relate(a,b)='FF10F0102'またはになりますST_Relate(a,b)='FF1F0F1F2'。 また、 および も満たしますST_Intersects(a,b)=true。ST_Touches(a,b)=trueの場合、返される DE-9IM コードは「Intersects(a,b) & Crosses(a,b) & Within(a,b) & CoveredBy(a,b)」のセマンティクスを持ちます。 ST_Relate(a,b)='0FFFFF212'つまり、trueブール式 を返します。ST_Intersects(a,b) AND ST_Crosses(a,b) AND ST_Within(a,b) AND ST_Coveredby(a,b)

ST_Relate()を使用すると、対応する述語のセットを直接計算するよりも高速になります。^[7] ST_Relate()を使用することが複雑な述語を計算する唯一の方法である場合があります。マルチポイント (ポイントの集合であるオブジェクト) を「交差」しないポイントのコードの例^[21]を参照してください。ただし、述語Crosses (マスクで定義されている場合)はtrue を返します。 0FFFFF0F2

ST_Relate () をオーバーロードするには、マスクパラメータを追加するか、返されたST_Relate(a,b)文字列をST_RelateMatch()関数で使用するのが一般的です。^[22] ST_Relate(a,b,mask) を使用すると、ブール値が返されます。例:

• ST_Relate(a,b,'*FF*FF212')またはの場合はtrueを返し、または の 場合はfalseを返します。ST_Relate(a,b)0FFFFF21201FFFF21201FFFF1220FF1FFFFF
• ST_RelateMatch('0FFFFF212','*FF*FF212')および は真ST_RelateMatch('01FFFF212','TTF*FF212')ですが、 は偽です。ST_RelateMatch('01FFFF122','*FF*FF212')

• 「エゲンホーファー行列」はブール領域の9IM 3x3行列の同義語です。 ^[23]
• 「クレメンティーニ行列」は、 { 0,1,2 , F }領域のDE - 9IM 3x3行列の同義語です。^[23]
• 「エゲンホーファー演算子」と「クレメンティーニ演算子」は、ブール演算で使用できる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 の図解チュートリアル