DE-9IM

Los 9 casos de intersección entre dos elementos bidimensionales

El Modelo de 9 intersecciones dimensionalmente extendido (su nombre original en inglés es Dimensionally Extended 9-Intersection Model, del que procede la abreviatura DE-9IM) es un modelo topológico y un estándar utilizado para describir las relaciones espaciales de dos regiones (en dos dimensiones, R2), en los dominios de la geometría, la topología general, la topología geoespacial y campos relacionados con el análisis espacial por computadora. Las relaciones espaciales expresadas por el modelo son invariantes ante transformaciones de rotación, tranlación y escalamiento.

La matriz que contempla los nueve casos de intersección proporciona un enfoque para clasificar relaciones geométricas. En términos generales, con un dominio matricial de verdadero/falso, existen 512 posibles relaciones topológicas en 2D, que pueden agruparse en esquemas de clasificación binaria. El idioma inglés contiene alrededor de 10 esquemas (relaciones), tales como "interseca", "toca" e "iguales". Al evaluar dos geometrías frente a un esquema, el resultado es un predicado espacial denominado según dicho esquema.

El modelo fue desarrollado por Clementini y otros basándose en los trabajos fundamentales de Egenhofer y otros. Se ha utilizado como base para estándares de consulta y de aseveraciones en sistemas de información geográfica (SIG) y en bases de datos espaciales.

Modelo matricial

El modelo DE-9IM se basa en una matriz de intersección de 3×3 con la forma:

DE9IM⁡(a,b)=[dim⁡(I(a)∩I(b))dim⁡(I(a)∩B(b))dim⁡(I(a)∩E(b))dim⁡(B(a)∩I(b))dim⁡(B(a)∩B(b))dim⁡(B(a)∩E(b))dim⁡(E(a)∩I(b))dim⁡(E(a)∩B(b))dim⁡(E(a)∩E(b))]

 

 

 

 

(1)

donde ⁠dim⁠ es la dimensión de la intersección (∩) del interior (I), de la frontera (B) y del exterior (E) de las geometrías a y b.

Los términos interior y frontera en este artículo se utilizan en el sentido empleado en topología algebraica y teoría de variedades, no en el sentido utilizado en topología general: por ejemplo, el interior de un segmento de recta es el segmento sin sus extremos, y su frontera son simplemente los dos extremos (en topología general, el interior de un segmento de recta en el plano es vacío y el segmento es su propia frontera). En la notación de operadores de espacios topológicos, los elementos de la matriz también pueden expresarse como

I(a)=ao    B(a)=∂a    E(a)=ae

 

 

 

 

(2)

La dimensión de los conjuntos vacíos (∅) se denota como −1 o F (falso). La dimensión de los conjuntos no vacíos (¬∅) se denota mediante el número máximo de dimensiones de la intersección; específicamente, 0 para puntos, 1 para rectas y 2 para áreas. Entonces, el dominio del modelo es {0,1,2,F}.

Se obtiene una versión simplificada de ⁠dim⁡(x)⁠ aplicando los valores {0,1,2} a T (verdadero), utilizando así el dominio booleano {T,F}. La matriz, denotada mediante operadores, puede expresarse como

bin⁡(DE9IM⁡(a,b))=9IM⁡(a,b)=[ao∩bo≠∅︀ao∩∂b≠∅︀ao∩be≠∅︀∂a∩bo≠∅︀∂a∩∂b≠∅︀∂a∩be≠∅︀ae∩bo≠∅︀ae∩∂b≠∅︀ae∩be≠∅︀]

 

 

 

 

(3)

Los elementos de la matriz pueden denominarse como se muestra a continuación:

[IIIBIEBIBBBEEIEBEE]

 

 

 

 

(4)

Ambas formas matriciales, con dominios dimensionales y booleanos, pueden ser serializados mediante "códigos de cadena DE-9IM", que las representan en un patrón de cadena de una sola línea. Desde 1999, los "códigos de cadena" tienen un formato estándar.

Para la verificación de resultados o el análisis de patrones, un valor matricial (o un código de cadena) puede comprobarse mediante una "máscara": un valor de salida deseado con símbolos asterisco opcionales que actúan como comodines; es decir, un "*" que indica posiciones de salida que no son relevantes para el diseñador (valores libres o posiciones "sin importancia"). El dominio de los elementos de la máscara es {0,1,2,F,*}, o {T,F,*} para la forma booleana.

Los modelos más simples "4-Intersection" (4-Intersección) y "9-Intersection" (9-Intersección) se propusieron antes que DE-9IM para expresar "relaciones espaciales" (y dieron origen a los términos "4IM" y "9IM"). Pueden utilizarse en lugar de DE-9IM para optimizar el cálculo cuando las condiciones de entrada cumplen restricciones específicas.

Ilustración

Visualmente, para dos geometrías poligonales superpuestas, el resultado de la función DE_9IM(a,b) tiene el siguiente aspecto:

b  
a
Interior Frontera Exterior
Interior

  dim⁡[I(a)∩I(b)]=2  

  dim⁡[I(a)∩B(b)]=1  

  dim⁡[I(a)∩E(b)]=2  

Frontera

  dim⁡[B(a)∩I(b)]=1  

  dim⁡[B(a)∩B(b)]=0  

  dim⁡[B(a)∩E(b)]=1  

Exterior

  dim⁡[E(a)∩I(b)]=2  

  dim⁡[E(a)∩B(b)]=1  

  dim⁡[E(a)∩E(b)]=2  

Esta matriz puede expresarse como serializada. Así, leyéndola de izquierda a derecha y de arriba abajo, el resultado es II=2, IB=1, IE=2, BI=1, BB=0, BE=1, EI=2, EB=1, EE=2. Por tanto, en una representación compacta como código de cadena, es '212101212'.

Predicados espaciales

Cualquier propiedad topológica basada en una relación espacial binaria DE-9IM es un predicado espacial . Para facilitar su uso, se han definido "predicados espaciales con nombre" para algunas relaciones comunes, que posteriormente se convirtieron en predicados estándar. Las funciones de predicado espacial que se pueden derivar de DE-9IM incluyen:

Las funciones de predicados espaciales que pueden derivarse del modelo DE-9IM incluyen:

Predicados definidos mediante máscaras del dominio {T,F,*}:
Nombre (sinónomo) Matriz de intersección y cadena de código de máscara
(O booleano entre matrices)
Significado y definición Equivalente
Iguales [T∗F∗∗FFF∗]

II ∧ ~IE ∧ ~BE ∧ ~EI ∧ ~EB

 

 

 

 

(5)

a y b son topológicamente iguales. "Dos geometrías son topológicamente iguales si sus interiores se intersecan y ninguna parte del interior o del límite de una geometría interseca el exterior de la otra".
Dentro de & Contiene
T*F**FFF*
Disjuntos [FF∗FF∗∗∗∗]

~II ∧ ~IB ∧ ~BI ∧ ~BB

 

 

 

 

(6)

a y b son disjuntos: no tienen puntos en común. Forman un conjunto de geometrías desconectadas.
No intersecan
FF*FF****
Se tocan
(se encuentran)
[FT∗∗∗∗∗∗∗] [F∗∗T∗∗∗∗∗] [F∗∗∗T∗∗∗∗]

~II ∧ (IB ∨ BI ∨ BB)

 

 

 

 

(7)

a toca a b: Tienen al menos un punto en común, pero sus interiores no se intersecan.
FT******* F**T***** F***T****
Contiene [T∗∗∗∗∗FF∗]

II ∧ ~EI ∧ ~EB

 

 

 

 

(8)

a contiene a b: la geometría de b está contenida en a, y los interiores se cruzan. Otra definición: "a contiene a b si y solo si ningún punto de b se halla en el exterior de a, y al menos un punto del interior de b se encuentra en el interior de a".
Dentro de(b,a)
T*****FF*
Cubre [T∗∗∗∗∗FF∗] [∗T∗∗∗∗FF∗] [∗∗∗T∗∗FF∗] [∗∗∗∗T∗FF∗]

(II ∨ IB ∨ BI ∨ BB) ∧ ~EI ∧ ~EB

 

 

 

 

(9)

a cubre a b: la geometría de b se halla en a. Otras definiciones: "Al menos un punto de b se halla en a, y ningún punto de b se halla en el exterior de a", o "Todo punto de b es un punto de (el interior o la frontera de) a".
Cubierto por(b,a)
T*****FF* *T****FF* ***T**FF* ****T*FF*
Predicados que pueden obtenerse a partir de los anteriores mediante negación lógica o inversión de parámetros (trasponiendo la matriz), tal como indica la última columna:
Interseca [T∗∗∗∗∗∗∗∗] [∗T∗∗∗∗∗∗∗] [∗∗∗T∗∗∗∗∗] [∗∗∗∗T∗∗∗∗] a interseca b: las geometrías de a y de b tienen al menos un punto en común. No disjuntos
T******** *T******* ***T***** ****T****
Dentro de
(dentro)
[T∗F∗∗F∗∗∗] a está dentro de b: a se halla en el interior de b. Contiene(b,a)
T*F**F***
Cubierto por [T∗F∗∗F∗∗∗] [∗TF∗∗F∗∗∗] [∗∗FT∗F∗∗∗] [∗∗F∗TF∗∗∗] a está cubierto por b (extiende Dentro): la geometría de a se halla en b. Otras definiciones: "Al menos un punto de a se halla en b, y ningún punto de a se halla en el exterior de b", o "Todo punto de a es un punto de (el interior o la frontera de) b". Cubre(b,a)
T*F**F*** *TF**F*** **FT*F*** **F*TF***
Predicados que utilizan las dimensiones de entrada y se definen mediante máscaras del dominio {0,1,T,*}:
Cruza
⁠dim⁡(a)≠dim⁡(b)⁠ o
dim(any)= 1
[T∗T∗∗∗∗∗∗] [T∗∗∗∗∗T∗∗] [0∗∗∗∗∗∗∗∗] a cruza b: tienen algunos, pero no todos, puntos interiores en común, y la dimensión de la intersección es menor que la de al menos uno de ellos. Las siguientes reglas de selección de máscara deben solo verificarse cuando ⁠dim⁡(a)≠dim⁡(b)⁠ (excepto para rectas / entradas de rectas, que estén permitidas), en caso contrario el predicado es falso:

(II=0) para rectas, (II ∧ IE) cuando ⁠dim⁡(a)<dim⁡(b)⁠, (II ∧ EI) cuando ⁠dim⁡(a)>dim⁡(b)⁠

 

 

 

 

(10)

T*T******
⁠dim⁡(a)<dim⁡(b)⁠
T*****T**
⁠dim⁡(a)>dim⁡(b)⁠
0********
dim(any)= 1
Superpone
⁠dim⁡(a)=dim⁡(b)⁠
[T∗T∗∗∗T∗∗] [1∗T∗∗∗T∗∗] a se superpone a b: tienen algunos puntos en común, pero no todos; tienen la misma dimensión, y la intersección de los interiores de las dos geometrías tiene la misma dimensión que las geometrías mismas. Las siguientes reglas de selección de máscara deben solo verificarse cuando ⁠dim⁡(a)=dim⁡(b)⁠, de lo contrario, el predicado es falso:

(II ∧ IE ∧ EI) para puntos o superficies, (II=1 ∧ IE ∧ EI) para rectas

 

 

 

 

(11)

T*T***T**
dim= 0 or 2
1*T***T**
dim= 1

Obsérvese que:

Propiedades

Los predicados espaciales poseen las siguientes propiedades de relaciones binarias:

  • Reflexiva: Iguales, Contiene, Cubre, Cubierto por, Interseca, Dentro de
  • Antireflexiva: Disjuntos
  • Simétrica: Iguales, Intersecan, Cruzan, Tocan, Solapan
  • Transitiva: Iguales, Contiene, Cubre, Cubierto por, Dentro de

Interpretación

Ejemplos de relaciones espaciales

La elección de la terminología y la semántica para los predicados espaciales se basa en convenciones razonables y en la tradición de los estudios topológicos. Relaciones tales como Intersects, Disjoint, Touches, Within y Equals (entre dos geometrías a y b) tienen una semántica evidente:

Iguales
a = b, es decir, (a ∩ b= a) ∧ (a ∩ b= b)
Dentro de
a ∩ b= a
Interseca
a ∩ b ≠ ∅
Toca
(a ∩ b ≠ ∅) ∧ (aο ∩ bο= ∅)

Los predicados Contiene y Dentro de presentan aspectos sutiles en su definición que resultan contraintuitivos. Por ejemplo, una línea L que está completamente contenida en la frontera de un polígono P no se considera contenida en P. Esta particularidad puede expresarse diciendo que los polígonos no contienen su propia frontera. Este problema se debe a la última cláusula de la definición de Contiene presentada anteriormente: al menos un punto del interior de B se encuentra en el interior de A. En este caso, el predicado Cubre posee una semántica más intuitiva (véase la definición), lo que evita tener que considerar los límites.

Para facilitar la comprensión, la dimensionalidad de las entradas puede servir de justificación para introducir gradualmente la complejidad semántica:

Relaciones entre Predicados adecuados Semántica añadida
punto/punto Iguales, Disjuntos Otros predicados válidos se reducen a Iguales.
punto/línea Se añade Interseca Interseca es un refinamiento de Iguales: algún punto igual en la línea.
width="180"|Se añade Toca, Cruza, ... Toca es un refinamiento de Interseca, se refiere únicamente a fronteras. Cruza se refiere a un único punto.

Cobertura de los posibles resultados de la matriz

El número de resultados posibles en una matriz booleana "9IM" es 29=512, y en una matriz DE-9IM es 39=6561. El porcentaje de estos resultados que satisfacen un predicado específico se determina de la siguiente manera:

Probabilidad Nombre
93.7%Interseca
43.8%Toca
25%Cruza (para entradas válidas; 0% en caso contrario)
23.4%Cubre y Cubierto por
12.5%Contiene, Superpone (para entradas válidas; 0% en caso contrario) y Dentro de
6.3%Disjuntos
3.1%Iguales

En las aplicaciones habituales, las geometrías se intersecan a priori, y posteriormente se verifican las demás relaciones.

Los predicados compuestos (Interseca O Disjuntos) e (Iguales O Diferentes) suman un 100 % (predicados siempre verdaderos).

Sin embargo, (Cubre O Cubierto por) suman un 41 % —una cifra distinta a la suma aritmética simple—, ya que no son ni complementos lógicos ni relaciones independientes.

De forma análoga, (Contiene O Dentro de) suman un 21 %. La suma del 25 % + 12,5 % = 37,5 % se obtiene al ignorar las líneas superpuestas en (Cruza O Solapa), dado que los conjuntos de entrada válidos son disjuntos.

Consultas y aseveraciones

El modelo "DE-9IM" ofrece una descripción completa de las relaciones entre dos geometrías de entrada. Es una función matemática que representa un conjunto completo de todas las relaciones posibles entre dos entidades, como una tabla de verdad, la comparación a tres sentidos, un mapa de Karnaugh o un diagrama de Venn. Cada valor de salida equivale a una fila de una tabla de verdad que representa las relaciones de unas entradas específicas.

Como se ilustra arriba, el resultado '212101212' obtenido de "DE-9IM"('a','b') constituye una descripción completa de todas las relaciones topológicas entre las geometrías específicas de a y de b. Esto indica que II=2, IB=1, IE=2, BI=1, BB=0, BE=1, EI=2, EB=1, EE=2.

Por otro lado, si se examinan predicados como Interseca(a,b) o Toca(a,b) —para el mismo ejemplo se tiene que Interseca=true y Toca=true—, se obtiene una descripción incompleta de todas las relaciones topológicas. Además, los predicados no aportan información sobre la dimensionalidad de las geometrías (es irrelevante si a y b son líneas, áreas o puntos).

Esta independencia respecto al tipo de geometría y la ausencia de completitud en los predicados resultan útiles para consultas generales acerca de la relación entre dos geometrías:

Semántica Interior/Frontera/Exterior Semántica usual
Aseveraciones Más descriptiva
" a y b tienen DE-9IM(a,b)='212101212' "
Menos descriptiva
" a Toca b "
Consultas Más restrictiva
" Mostrar todos los pares de geometrías donde DE-9IM(a,b)='212101212' "
Más general
" Mostrar todos los pares de geometrías donde Toca(a,b) "

En aplicaciones habituales, el uso de predicados espaciales también se justifica por ser más inteligible por humanos que las descripciones "DE-9IM": un usuario típico tiene una intuición más clara sobre los predicados (que sobre un conjunto de intersecciones entre interiores, bordes y exteriores).

Los predicados tienen una semántica útil en aplicaciones habituales, por lo que es útil traducir una descripción DE-9IM a una lista de todos los predicados asociados, que es como un proceso de conversión de tipos entre los dos tipos semánticos diferentes. Ejemplos:

Normas

El Open Geospatial Consortium (OGC) ha estandarizado los típicos predicados espaciales (Contiene, Cruza, Intersecta, Toca, etc.) como funciones booleanas, y el modelo DE-9IM, como una función que devuelve una cadena (el código DE-9IM), con dominio de {0, 1, 2, F}. Este código de cadena DE-9IM es un formato estandarizado para el intercambio de datos.

El estándar Simple Feature Access (ISO 19125), en el capítulo 7.2.8, "Rutinas SQL en geometría de tipo", recomienda como rutinas soportadas SQL/MM Spatial (ISO 13249-3 Parte 3: Espacial) utiliza ST_Dimension, ST_GeometryType, ST_IsEmpty, ST_IsSimple, ST_Boundary para todos los tipos de geometría.

El mismo estándar, consistente con las definiciones de relaciones en la "Parte 1, Cláusula 6.1.2.3" del SQL/MM, recomienda (deberá ser compatible) las etiquetas de función: ST_Equals, ST_Disjoint, ST_Intersects, ST_Touches, ST_Crosses, ST_Within, ST_Contains, ST_Overlaps y ST_Relate.

El DE-9IM en los estándares OGC utiliza las siguientes definiciones de Interior y Frontera, para los principales tipos de geometría estándar OGC:

Subtipos Dim Interior (I) Frontera (B)
Punto, Multipunto 0 Punto, Puntos Vacío
Poligonal, Recta 1 Puntos que quedan tras eliminar los puntos del límite. Dos puntos extremos
Anillo lineal 1 Todos los puntos a lo largo de la geometría Vacío
Cadena multilínea 1 Puntos que quedan tras eliminar los puntos de la frontera Aquellos puntos que se encuentran en las fronteras de un número impar de sus elementos (curvas).
Polígono 2 Puntos dentro de los anillos Conjunto de anillos
Multipolígono 2 Puntos dentro de los anillos Conjunto de anillos de sus elementos (polígonos).
NOTA: puntos exteriores (E) son puntos p que no están en el interior o la frontera, así que no requiere interpretación adicional, E(p)=not(I(p) or B(p)).

Implementación y uso práctico

La mayoría de las bases de datos espaciales, como PostGIS, implementan el modelo DE-9IM() mediante las funciones estándar: ST_Relate, ST_Equals, ST_Intersects, etc. La función ST_Relate(a,b) genera el código de cadena DE-9IM del OGC estándar.

Ejemplos: dos geometrías, a y b, que se cruzan y tocan con un punto (por ejemplo con ⁠dim⁡(B(a)∩I(b))=0⁠ y ⁠dim⁡(I(a)∩I(b))=F⁠), pueden ser ST_Relate(a,b)='FF1F0F1F2' o ST_Relate(a,b)='FF10F0102' o ST_Relate(a,b)='FF1F0F1F2'. También satisface ST_Intersects(a,b)=true y ST_Touches(a,b)=true. Cuando ST_Relate(a,b)='0FFFFF212', el código DE-9IM devuelto tiene la semántica de Intersects(a,b) & Crosses(a,b) & Within(a,b) & CoveredBy(a,b), es decir, devuelve true en la expresión booleana ST_Intersects(a,b) AND ST_Crosses(a,b) AND ST_Within(a,b) AND ST_Coveredby(a,b).

El uso de ST_Relate() es más rápido que el cálculo directo de un conjunto de predicados correspondientes. Hay casos en los que usar ST_Relate() es la única forma de calcular un predicado complejo; consulte el ejemplo del código 0FFFFF0F2, de un punto que no "cruza" un multipunto (un objeto que es un conjunto de puntos), pero el predicado Cruce (cuando se define mediante una máscara) devuelve verdadero.

Es habitual el desbordamiento de ST_Relate() al agregar un parámetro de máscara, o al utilizar una cadena ST_Relate(a,b) devuelta en la función ST_RelateMatch(). Cuando se utiliza ST_Relate(a,b,mask), devuelve un valor booleano. Ejemplos:

  • ST_Relate(a,b,'*FF*FF212') devuelve "verdadero" cuando ST_Relate(a,b) es 0FFFFF212 o 01FFFF212, y devuelve "falso" cuando 01FFFF122 o 0FF1FFFFF.
  • ST_RelateMatch('0FFFFF212','*FF*FF212') y ST_RelateMatch('01FFFF212','TTF*FF212') son verdaderos, ST_RelateMatch('01FFFF122','*FF*FF212') es falso.

Sinónimos

Véase también

Estándares:       Sistemas de programación:       Cuestiones relacionadas: