
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.
El modelo DE-9IM se basa en una matriz de intersección de 3×3 con la forma:
|
|
(1) |
donde 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 aplicando los valores {0,1,2} a T (verdadero), utilizando así el dominio booleano {T,F}. La matriz, denotada mediante operadores, puede expresarse como
|
|
(3) |
Los elementos de la matriz pueden denominarse como se muestra a continuación:
|
|
(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.
Visualmente, para dos geometrías poligonales superpuestas, el resultado de la función DE_9IM(a,b) tiene el siguiente aspecto:
| ||||||||||||||||||
|
|
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'.
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:
| 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 |
|
Dentro de & Contiene | |||||||||||
T*F**FFF* |
|||||||||||||
| Disjuntos |
|
No intersecan | |||||||||||
FF*FF**** |
|||||||||||||
| Se tocan (se encuentran) |
|
||||||||||||
FT******* |
F**T***** |
F***T**** | |||||||||||
| Contiene |
|
Dentro de(b,a) | |||||||||||
T*****FF* | |||||||||||||
| Cubre |
|
Cubierto por(b,a) | |||||||||||
T*****FF* |
*T****FF* |
***T**FF* |
****T*FF* | ||||||||||
| Interseca | 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) |
a está dentro de b: a se halla en el interior de b. | Contiene(b,a) | ||||
T*F**F*** | ||||||
| Cubierto por | 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*** | |||
| Cruza o dim(any)= 1 |
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 (excepto para rectas / entradas de rectas, que estén permitidas), en caso contrario el predicado es falso:
| ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
T*T****** |
T*****T** |
0******** dim(any)= 1 | |||||||||||
| Superpone |
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 , de lo contrario, el predicado es falso:
| ||||||||||||
T*T***T** dim= 0 or 2 |
1*T***T** dim= 1 | ||||||||||||
Obsérvese que:
*. Esto se debe a que EE es trivialmente verdadero y, por tanto, no aporta información útil.T*F**FFF*, es la fusión de Contiene (T*****FF*) y de Dentro de (T*F**F***): (II ∧ ~EI ∧ ~EB) ∧ (II ∧ ~IE ∧ ~BE).T*****FF* aparece en la definición tanto de Contiene como de Cubre, que es una relación más inclusiva. En particular, a diferencia de Contiene, no distingue entre puntos situados en el límite y puntos en el interior de las geometrías. En la mayoría de las situaciones, debería utilizarse Cubre en lugar de Contiene.T*F**F*** aparece en la definición tanto de Dentro de como de Cubierto por. En la mayoría de las situaciones, se debe utilizar Cubierto por en lugar de Dentro de.Los predicados espaciales poseen las siguientes propiedades de relaciones binarias:

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:
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. |
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.
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:
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)). | |||
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 y ), 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.T*****FF*.| Estándares: | Sistemas de programación: | Cuestiones relacionadas: |