El modelo de 9 intersecciones dimensionalmente extendido ( DE-9IM ) es un modelo topológico y un estándar que se utiliza para describir las relaciones espaciales de dos regiones (dos geometrías en dos dimensiones , R 2 ), en geometría , topología de conjunto de puntos , topología geoespacial y campos relacionados con el análisis espacial informático . Las relaciones espaciales expresadas por el modelo son invariantes a las transformaciones de rotación , traslación y escalado .
La matriz proporciona un enfoque para clasificar las relaciones geométricas. En términos generales, con un dominio de matriz verdadero / falso, hay 512 posibles relaciones topológicas 2D, que se pueden agrupar en esquemas de clasificación binaria . El idioma inglés contiene alrededor de 10 esquemas (relaciones), como "intersecta", "toca" e "igual". Cuando se prueban dos geometrías contra un esquema, el resultado es un predicado espacial nombrado por el esquema.
El modelo fue desarrollado por Clementini y otros [1] [2] basado en los trabajos seminales de Egenhofer y otros. [3] [4] Se ha utilizado como base para estándares de consultas y afirmaciones en sistemas de información geográfica (SIG) y bases de datos espaciales .
Modelo de matriz
El modelo DE-9IM se basa en una matriz de intersección de 3 × 3 con la forma:
( 1 )
dónde es la dimensión de la intersección (∩) del interior (I), límite (B), y exterior (E) de geometrías una y b .
Los términos interior y límite en este artículo se usan en el sentido usado en topología algebraica y teoría de variedades, no en el sentido usado en topología general: por ejemplo, el interior de un segmento de línea es el segmento de línea sin sus puntos finales, y su límite. son solo los dos puntos finales (en la topología general, el interior de un segmento de línea en el plano está vacío y el segmento de línea es su propio límite).
En la notación de operadores espaciales topológicos, los elementos de la matriz también se pueden expresar como
- Yo ( a ) = a o B ( a ) = ∂ a E ( a ) = a e
( 2 )
La dimensión de los conjuntos vacíos (∅) se denota como -1 o F (falso). La dimensión de conjuntos no vacíos (¬∅) se denota con el número máximo de dimensiones de la intersección, específicamente 0 para puntos , 1 para líneas , 2 para áreas . Entonces, el dominio del modelo es { 0 , 1 , 2 , F }.
Una versión simplificada de los valores se obtienen mapeando los valores { 0,1,2 } a T (verdadero), entonces usando el dominio booleano { T , F }. La matriz, denotada con operadores, se puede expresar como
( 3 )
Los elementos de la matriz se pueden nombrar como se muestra a continuación:
( 4 )
Ambas formas matriciales, con dominios dimensionales y booleanos, se pueden serializar como " códigos de cadena DE-9IM ", que los representan en un patrón de cadena de una sola línea. Desde 1999, los códigos de cadena tienen un formato estándar [5] .
Para la verificación de salida o el análisis de patrones, un valor de matriz (o un código de cadena) se puede verificar mediante una " máscara ": un valor de salida deseado con símbolos de asterisco opcionales como comodines , es decir, " * "indica posiciones de salida que al diseñador no le interesan (valores libres o" posiciones indiferentes "). 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-Intersección y 9-Intersección fueron propuestos antes de DE-9IM para expresar relaciones espaciales [6] (y originaron los términos 4IM y 9IM ). Se pueden utilizar en lugar del DE-9IM para optimizar el cálculo cuando las condiciones de entrada satisfacen restricciones específicas.
Ilustración
Visualmente, para dos geometrías poligonales superpuestas, esto se ve así: [7]
| ||||||||||||||||||
|
|
Leyendo de izquierda a derecha y de arriba a abajo, el código de cadena DE-9IM ( a , b ) es ' 212101212 ', la representación compacta de.
Predicados espaciales
Los predicados espaciales son relaciones espaciales binarias topológicamente invariantes basadas en el DE-9IM. Para facilitar su uso, se han definido "predicados espaciales con nombre" para algunas relaciones comunes.
Las funciones de predicado espacial que se pueden derivar (expresadas por máscaras) de DE-9IM incluyen: [4] [8]
Predicados definidos con máscaras de dominio { T , F , * }
Nombre (sinónimo) | Matriz de intersección y cadena de código de máscara ( booleano O entre matrices) | Significado y definición [4] | Equivalente | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Igual |
| Dentro y contiene | |||||||||||
T*F**FFF* | |||||||||||||
Desarticular |
| no interseca | |||||||||||
FF*FF**** | |||||||||||||
Toca (se encuentra) |
| ||||||||||||
FT******* | F**T***** | F***T**** | |||||||||||
Contiene |
| Dentro de ( b , a ) | |||||||||||
T*****FF* | |||||||||||||
Cubiertas |
| Cubierto por ( b , a ) | |||||||||||
T*****FF* | *T****FF* | ***T**FF* | ****T*FF* |
Predicados que se pueden obtener de lo anterior mediante negación lógica o inversión de parámetros ( transposición de matrices ), como lo indica la última columna:
Intersecta | un intersecta b : geometrías a y b tienen al menos un punto en común. | no disjunto | ||||
---|---|---|---|---|---|---|
T******** | *T******* | ***T***** | ****T**** | |||
Dentro (dentro) | a está dentro de b : a se encuentra en el interior de b . | Contiene ( b , a ) | ||||
T*F**F*** | ||||||
Cubierto por | a está cubierto por b (se extiende dentro ): la geometría a está en b . Otras definiciones: "Al menos un punto de a está en b , y ningún punto de a está en el exterior de b ", o "Cada punto de a es un punto de (el interior o límite de) b ". | Cubre ( b , a ) | ||||
T*F**F*** | *TF**F*** | **FT*F*** | **F*TF*** |
Predicados que utilizan las dimensiones de entrada y se definen con máscaras de dominio { 0 , 1 , T , * }
Cruces o tenue (cualquiera) = 1 | a cruces b : tienen algunos puntos interiores en común, pero no todos, y la dimensión de la intersección es menor que la de al menos uno de ellos. Las reglas de selección de máscaras se comprueban solo cuando, excepto por entradas de línea / línea, de lo contrario es falso: [11]
| ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
T*T****** | T*****T** | 0******** dim (cualquiera) = 1 | |||||||||||
Superposiciones | a superposiciones 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 reglas de selección de máscaras se comprueban solo cuando, de lo contrario es falso:
| ||||||||||||
T*T***T** dim = 0 o 2 | 1*T***T** tenue = 1 |
Darse cuenta de:
- La definición topológicamente igual no implica que tengan los mismos puntos o incluso que sean de la misma clase.
- La salida de tener la información contenida en una lista de todos los predicados interpretables sobre geometrías una y b .
- Todos los predicados se calculan mediante máscaras. Solo las cruces y superposiciones tienen condiciones adicionales sobre y .
- Todos los códigos de cadena de máscara terminan en
*
. Esto se debe a que EE es trivialmente cierto y, por lo tanto, no proporciona información útil. - La máscara Equals``
T*F**FFF*
es la "fusión" de Contiene (T*****FF*
) y Dentro (T*F**F***
): ( II ∧ ~ EI ∧ ~ EB ) ∧ ( II ∧ ~ IE ∧ ~ BE ) . - La máscara
T*****FF*
aparece en la definición de Contiene y Cubre . Covers es una relación más inclusiva. En particular, a diferencia de Contiene , no distingue entre puntos en el límite y en el interior de las geometrías. Para la mayoría de las situaciones, se deben usar las fundas en lugar de las que contienen . - Del mismo modo, la máscara
T*F**F***
se produce en la definición de ambos Dentro y CoveredBy . Para la mayoría de las situaciones, CoveredBy se debe utilizar con preferencia a Within .
Propiedades
Los predicados espaciales tienen las siguientes propiedades de relaciones binarias :
- Reflexivo : Igual, Contiene, Cubre, CoveredBy, Intersects, Within
- Anti-reflexivo : Desarticulado
- Simétrico : igual, intersecta, cruza, toca, superpone
- Transitivo : Igual, Contiene, Cubre, CoveredBy, Within
Interpretación
La elección de la terminología y la semántica de los predicados espaciales se basa en convenciones razonables y la tradición de los estudios topológicos. [4] relaciones tales como Intersects , disjunto , toques , Dentro , Igual a (entre dos geometrías una y b ) tienen un obvio semántica: [10] [12]
- Igual
- a = b es decir ( a ∩ b = a ) ∧ ( a ∩ b = b )
- Dentro
- a ∩ b = a
- Intersecta
- a ∩ b ≠ ∅
- Toques
- ( a ∩ b ≠ ∅) ∧ ( a ο ∩ b ο = ∅)
Los predicados Contiene y Dentro tienen aspectos sutiles en su definición que son contrarios a la intuición. Por ejemplo, [10] una línea L que está completamente contenida en el límite de un polígono P se no considera estar contenidos en P . Esta peculiaridad se puede expresar como "Los polígonos no contienen su límite". Este problema se debe a la cláusula final de la definición de Contiene anterior: "al menos un punto del interior de B se encuentra en el interior de A". Para este caso, el predicado Covers tiene una semántica más intuitiva (ver definición), evitando consideraciones de límites.
Para una mejor comprensión, la dimensionalidad de las entradas se puede utilizar como justificación para una introducción gradual de la complejidad semántica:
Relaciones entre Predicados apropiados Semántica agregada punto / punto Igual , disjunto Otros predicados válidos se colapsan en Equals . punto / línea agrega intersecciones Intersects es un refinamiento de Equals : "algún punto igual en la línea". linea / linea añade toques , cruces , ... Touches es un refinamiento de Intersects , solo sobre "límites". Cruces se trata de "solo un punto".
Cobertura sobre posibles resultados de la matriz
El número de resultados posibles en una matriz booleana 9IM es 2 9 = 512, y en una matriz DE-9IM es 3 9 = 6561. El porcentaje de estos resultados que satisfacen un predicado específico se determina de la siguiente manera,
Probabilidad | Nombre |
---|---|
93,7% | Intersecta |
43,8% | Toques |
25% | Cruces (para entradas válidas, 0% en caso contrario) |
23,4% | Covers y CoveredBy |
12,5% | Contiene , superposiciones (para entradas válidas, 0% en caso contrario) y dentro |
6,3% | Desarticular |
3,1% | Igual |
En las aplicaciones habituales, las geometrías se cruzan a priori y se comprueban las demás relaciones.
Los predicados compuestos " Intersects OR Disjoint " y " Equals OR Different " tienen la suma 100% (predicados siempre verdaderos), pero " Covers OR CoveredBy " tienen 41%, que no es la suma, porque no son complementos lógicos ni relaciones independientes. ; ídem " Contiene O Dentro ", que tienen el 21%. La suma 25% + 12.5% = 37.5% se obtiene al ignorar la superposición de líneas en " Cruces O Superposiciones ", porque los conjuntos de entrada válidos son disjuntos.
Consultas y afirmaciones
El DE-9IM ofrece una afirmación descriptiva completa sobre las 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 la verdad , la comparación de tres vías , un mapa de Karnaugh o un diagrama de Venn . Cada valor de salida es como una línea de tabla de verdad, que representa relaciones de entradas específicas.
Como se ilustra anteriormente, la salida '212101212' resultado de DE-9IM ( un , b ) es una descripción completa de todas las relaciones topológicas entre geometrías específicas una y b . Nos dice que.
Por otro lado, si verificamos predicados como Intersects ( a , b ) o Touches ( a , b ) - para el mismo ejemplo tenemos " Intersects = verdadero y toca = verdadera "- es una descripción incompleta de 'todas las relaciones topológicas' Los predicados también no dicen nada acerca de la dimensionalidad de las geometrías (no importa si. un y b son líneas, áreas o puntos).
Esta independencia del tipo de geometría y la falta de completitud , en los predicados , son útiles para consultas generales sobre dos geometrías:
semántica interior / límite / exterior semántica habitual Afirmaciones más descriptiva
" una y B tienen DE-9IM ( un , b ) = '212101212' "menos descriptivo
" a toca b "Consultas más restrictivo
"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 )"
Para aplicaciones habituales, el uso de predicados espaciales también se justifica por ser más legible por humanos que las descripciones DE-9IM : un usuario típico tiene mejor intuición sobre los predicados (que un conjunto de intersecciones interiores / fronterizas / exteriores).
Los predicados tienen una semántica útil en aplicaciones habituales, por lo que es útil la traducción de una descripción DE-9IM en una lista de todos los predicados asociados, [13] [14] que es como un proceso de conversión entre los dos tipos semánticos diferentes. Ejemplos:
- Los códigos de cadena " 0F1F00102 "y" 0F1FF0102 "tienen la semántica de" Se cruza, se cruza y se superpone ".
- El código de cadena " 1FFF0FFF2 "tienen la semántica de" Equals ".
- Los códigos de cadena " F01FF0102 "," FF10F0102 "," FF1F00102 "," F01FFF102 "y" FF1F0F1F2 "tienen la semántica de" Intersects & Touches ".
Estándares
El Consorcio Geoespacial Abierto (OGC) ha estandarizado los predicados espaciales típicos (Contiene, Cruza, Intersecta, Toca, etc.) como funciones booleanas, y el modelo DE-9IM, [15] como una función que devuelve una cadena (el DE- 9IM código), con dominio de { 0 , 1 , 2 , F }, que significa 0 = punto, 1 = línea, 2 = área y F = "conjunto vacío". Este código de cadena DE-9IM es un formato estandarizado para el intercambio de datos.
El estándar Simple Feature Access (ISO 19125), [16] en el capítulo 7.2.8, "Rutinas SQL en tipo Geometría", recomienda como rutinas admitidas SQL / MM Spatial [17] (ISO 13249-3 Part 3: Spatial) ST_Dimension , ST_GeometryType , ST_IsEmpty , ST_IsSimple , ST_Boundary para todos los tipos de geometría. El mismo estándar, de acuerdo con las definiciones de relaciones en la "Parte 1, Cláusula 6.1.2.3" del SQL / MM, recomienda (se admitirán ) 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 usa las siguientes definiciones de Interior y Límite, para los principales tipos de geometría estándar OGC: [18]
Subtipos | Oscuro | Interior ( I ) | límite ( B ) |
---|---|---|---|
Punto, multipunto | 0 | Punto, puntos | Vacío |
LineString, Line | 1 | Puntos que quedan cuando se eliminan los puntos de contorno. | Dos puntos finales. |
LinearRing | 1 | Todos los puntos a lo largo de la geometría. | Vacío. |
MultilineString | 1 | Puntos que quedan cuando se eliminan los puntos de contorno. | Aquellos puntos que se encuentran en los límites de un número impar de sus elementos (curvas). |
Polígono | 2 | Puntos dentro de los anillos. | Juego de anillos. |
MultiPolygon | 2 | Puntos dentro de los anillos. | Conjunto de anillos de sus elementos (polígonos). |
AVISO: los puntos exteriores (E) son puntos p que no están en el interior o en el límite , por lo que no necesitan interpretación adicional, E (p) = no (I (p) o B (p)) . |
Implementación y uso práctico
Bases de datos espaciales mayoría, como PostGIS , implementa la DE-9IM () modelo por las funciones estándar: [19] ST_Relate
, ST_Equals
, ST_Intersects
, etc. La función ST_Relate(a,b)
salidas el estándar de OGC código cadena DE-9IM .
Ejemplos: dos geometrías, un y b , que se cruza y toques con un punto (por ejemplo con y ), puede 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 "Se cruza (a, b) y se cruza (a, b) y dentro (a, b) y CoveredBy (a, b)", es decir, devuelve true
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. [7] Hay casos en los que el uso ST_Relate () es la única forma de calcular un predicado complejo; consulte el ejemplo del código 0FFFFF0F2
, [20] de un punto que no "cruza" un multipunto (un objeto que es un conjunto de puntos), sino que el predicado cruza (cuando se define por una máscara) devuelve verdadero .
Es habitual sobrecargar el ST_Relate () agregando un parámetro de máscara, o use un ST_Relate (a, b) en la cadena Función ST_RelateMatch () . [21] Al usar ST_Relate (a, b, mask) , devuelve un booleano. Ejemplos:
ST_Relate(a,b,'*FF*FF212')
devuelve verdadero cuandoST_Relate(a,b)
es0FFFFF212
o01FFFF212
, y devuelve falso cuando01FFFF122
o0FF1FFFFF
.ST_RelateMatch('0FFFFF212','*FF*FF212')
yST_RelateMatch('01FFFF212','TTF*FF212')
son verdaderas ,ST_RelateMatch('01FFFF122','*FF*FF212')
es falsa .
Sinónimos
- "Egenhofer-Matrix" es un sinónimo de la matriz 9IM 3x3 de dominio booleano. [22]
- "Clementini-Matrix" es un sinónimo de la matriz DE-9IM 3x3 de { 0 , 1 , 2 , F } dominio. [22]
- Los "operadores de Egenhofer" y los "operadores de Clementini" son a veces una referencia a elementos de la matriz como II , IE , etc. que se pueden utilizar en operaciones booleanas. Ejemplo: el predicado " G 1 contiene G 2 " puede ser expresado por " ⟨ G 1 | II ∧ ~ EI ∧ ~ EB | G 1 ⟩ ", que puede ser traducido para enmascarar la sintaxis,
T*****FF*
. - Predicados "encuentra" es sinónimo de toques ; "dentro" es sinónimo de dentro
- "ANYINTERACT" de Oracle [14] es un sinónimo de intersects y "OVERLAPBDYINTERSECT" es un sinónimo de superposiciones . Su "OVERLAPBDYDISJOINT" no tiene un predicado con nombre correspondiente.
- En la región, los operadores de cálculo de conexión ofrecen algunos sinónimos para los predicados : disjunto es DC (desconectado), touch es EC (conectado externamente), es igual a EQ. Otros, como Overlaps como PO (parcialmente superpuesto), necesitan análisis de contexto o composición. [23] [24]
Ver también
Estándares:
| Software:
| Temas relacionados:
|
Referencias
- ^ Clementini, Eliseo; Di Felice, Paolino; van Oosterom, Peter (1993). "Un pequeño conjunto de relaciones topológicas formales adecuadas para la interacción del usuario final". En Abel, David; Ooi, Beng Chin (eds.). Avances en bases de datos espaciales: Tercer Simposio Internacional, SSD '93 Singapur, 23 al 25 de junio de 1993 Actas . Apuntes de conferencias en informática. 692/1993. Saltador. págs. 277–295. doi : 10.1007 / 3-540-56869-7_16 . ISBN 978-3-540-56869-8.
- ^ Clementini, Eliseo; Sharma, Jayant; Egenhofer, Max J. (1994). "Modelado de relaciones espaciales topológicas: estrategias para el procesamiento de consultas". Computadoras y Gráficos . 18 (6): 815–822. doi : 10.1016 / 0097-8493 (94) 90007-8 .
- ^ Egenhofer, MJ; Franzosa, RD (1991). "Relaciones espaciales topológicas de conjunto de puntos" . En t. J. GIS . 5 (2): 161-174. doi : 10.1080 / 02693799108927841 .
- ^ a b c d Egenhofer, MJ; Herring, JR (1990). "Un marco matemático para la definición de relaciones topológicas" (PDF) . Archivado desde el original (PDF) el 14 de junio de 2010. Cite journal requiere
|journal=
( ayuda ) - ^ La "Especificación de características simples de OpenGIS para SQL", revisión 1.1 , se publicó el 5 de mayo de 1999. Fue el primer estándar internacional en establecer las convenciones de formato para los códigos de cadena DE-9IM y los nombres de los "predicados de relación espacial con nombre basado en el DE-9IM "(ver sección con este título).
- ^ MJ Egenhofer, J. Sharma y D. Mark (1993) " Una comparación crítica de los modelos de 4 intersecciones y 9 intersecciones para las relaciones espaciales: análisis formal Archivado el 14 de junio de 2010en la Wayback Machine ", en: Auto -Carto XI Archivado el 25 de septiembre de 2014 en la Wayback Machine .
- ^ a b Capítulo 4. Uso de PostGIS: gestión de datos y consultas
- ^ JTS: Class IntersectionMatrix , Vivid Solutions, Inc., archivado desde el original el 21 de marzo de 2011
- ^ Especificaciones técnicas de JTS de 2003.
- ^ a b c M. Davis (2007), " Caprichos del predicado espacial 'Contiene' ".
- ^ ST_Crosses
- ^ Câmara, G .; Freitas, UM; Casanova, MA (1995). "Álgebras de campos y objetos para operaciones SIG". CiteSeerX 10.1.1.17.991 . Cite journal requiere
|journal=
( ayuda ) - ^ Un traductor DE-9IM , de todos los predicados asociados de una relación espacial.
- ^ a b Nota. La función espacial del oráculo SDO_RELATE () Archivado 2013-07-21 en Wayback Machine hace solo una traducción parcial, internamente, ofreciendo al usuario una máscara para que se verifique una lista o de predicados, en lugar de la cadena DE-9IM.
- ^ "Especificación de implementación de OpenGIS para información geográfica - Acceso a funciones simples - Parte 2: opción SQL", OGC , http://www.opengeospatial.org/standards/sfs
- ^ Open Geospatial Consortium Inc. (2007), "Estándar de implementación de OpenGIS® para información geográfica - Acceso a funciones simples - Parte 2: opción SQL", documento OGC 06-104r4 versión 1.2.1 (revisión de 2010-08-04).
- ^ ISO 13249-3 Parte 3: Espacial, resumido en Paquetes de aplicaciones y multimedia SQL (SQL / MM) Archivado el 14 de febrero de 2010en Wayback Machine .
- ^ "Enciclopedia de GIS", editado por Shashi Shekhar y Hui Xiong. SpringerScience 2008. pág. 242
- ^ Documentación en línea de la funciónST_Relate () PostGIS .
- ^ Caso de prueba JTS de "punto A dentro de uno de los puntos B", http://www.vividsolutions.com/jts/tests/Run1Case4.html Archivado el 4 de marzo de 2016 en Wayback Machine.
- ^ Documentación en línea de la funciónST_RelateMatch () PostGIS .
- ^ a b "Enciclopedia de SIG", S. Shekhar, H. Xiong. ISBN 978-0-387-35975-5 .
- ^ "Cálculo de conexión de región multidimensional" (2017), http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf
- ^ "Identificación de relaciones en el cálculo de conexión de la región: 9-intersección reducida a 3+-predicados de intersección" (2013), https://web.archive.org/web/20181001104247/https://pdfs.semanticscholar.org/8184 /abc9b25ed340f9195cc904249bda415bb0c3.pdf
enlaces externos
- Teoría de conjuntos de puntos y la matriz DE-9IM
- Tutorial ilustrado para DE-9IM