Considere esta situación simple donde tres bordes se conectan en un nodo:
Me gustaría escribir una descripción sucinta y clara de la relación entre A y B de tal manera que la diferencie de la relación entre A y C. Algo así como “cuando se atraviesa el nodo en el sentido de las agujas del reloj, ¿A está adyacente? a B, pero A no es adyacente? a C. " Pero no es realmente adyacencia.
Dicho de otra manera: imagina que estás parado en el nodo y estás mirando hacia A. Empiezas a girar en el sentido de las agujas del reloj. La siguiente ventaja a la que llegarás es B, no C.
¿Hay alguna manera de describir esta relación entre A y B de una manera más sucinta, formal o correcta que la que he escrito anteriormente?
Debe ser direccional (una relación de este tipo existe en la dirección de las agujas del reloj desde A, y otra existe en la dirección de las agujas del reloj). Y debe escalar a casos en los que más de tres bordes están conectados en el nodo. Tal vez tiene algo que ver con el enrutamiento? (Estoy pensando en esto en el contexto de las redes de carreteras).
Dos enfoques que ya he probado pero con los que no he llegado lejos:
Referencias de topología similares a 9IM : he mirado el DE-9IM , y aunque no soy matemático, creo que todavía puedo decir por los diagramas y términos que no cubre este tipo de relación. Tampoco lo encuentro aún en las descripciones de topología en la ayuda de ESRI o la ayuda de Oracle . (¡Quizás haya algo allí, pero todavía no lo encuentro!)
Caras : He jugado con el hecho de que la cara en el lado "norte" de A también podría estar limitada por B, pero no por C. Sin embargo, como puede ver en el diagrama aquí, eso no siempre es cierto. Imagine que mi diagrama es un extracto de una red de carreteras donde A y C son arteriales y B es un camino corto sin salida.
Sospecho que puede que no haya un solo término para lo que estoy tratando de decir; Como mínimo, me gustaría poder describir esa relación de una manera más simple que lo que he hecho anteriormente. Esta es una pregunta independiente de la plataforma. En este momento, solo estoy buscando las palabras correctas. Más adelante intentaré implementar el concepto en python (pyqgis o arcpy) en un shapefile, por lo que cualquier respuesta con ese punto final en mente será particularmente interesante, pero no necesaria.
fuente
Respuestas:
Sé que llego un poco tarde a la fiesta aquí, pero esto es algo bastante interesante, y espero que mi respuesta pueda ser útil.
Lo que estás preguntando es una relación cualitativa; El hermano a menudo ignorado de la relación cuantitativa. El razonamiento cualitativo aparece con bastante frecuencia en la ciencia geoespacial. Las consultas de ejemplo incluyen: ¿Qué parcelas son adyacentes a esta? ¿Qué características hay dentro de la superposición de la región A y la región B? ¿Qué regiones son cóncavas? ¿Qué camino está a la izquierda? Las relaciones son: adyacente, interior, cóncava e izquierda de. Las consultas cualitativas a menudo se pasan por alto o se infravaloran en comparación con las preguntas cuantitativas, como cuál es mayor, menor o mayor en número.
Una relación cualitativa que toma dos entradas se llama relación binaria. Hay dos notaciones comunes para esto: - isLeftOf (A, B) Esta es la notación de prefijo. - A isLeftOf B Esta es la notación infija.
En los ejemplos anteriores también hubo una relación unaria: isConcave. Esta relación relaciona una región consigo misma y devolvería un valor booleano.
Todos los predicados espaciales de Egenhofer en el modelo de 9 intersecciones (referenciados en el 9EIM) son relaciones binarias entre dos regiones. También te puede interesar el RCC de Randell, Cui y Cohn (http://en.wikipedia.org/wiki/Region_connection_calculus). Las relaciones cualitativas (topológicas) dadas en esta área de estudio relacionan regiones con regiones, y trabajos posteriores relacionan líneas con regiones y líneas con líneas. Sin embargo, esto no es exactamente lo que estás buscando.
OK, perdón por la digresión, pero espero que eso ayude con el aspecto terminológico de su pregunta.
@whuber estaba encaminado al sugerir la lista de bordes doblemente conectados (DCEL). Este es un pariente cercano de los mapas combinatorios, a menudo utilizados debajo de las cubiertas en los sistemas CAD, y los bordes alados. El concepto de borde alado (http://en.wikipedia.org/wiki/Winged_edge) es cómo el estándar de texto conocido define un agujero en un polígono (http://en.wikipedia.org/wiki/Well-known_text #Geometric_objects). Tenga en cuenta en el polígono que el orden de los puntos externos es en sentido antihorario y en sentido horario para los puntos internos. Una pequeña persona de hadas caminando por el límite en este orden siempre vería el interior de la región a su izquierda.
Con los mapas combinatorios y DCEL, el punto clave es que estos objetos se definen en una superficie orientable. No necesitamos entrar en las formalidades matemáticas: la idea es bastante simple: si puede definir la dirección en la superficie, como puede hacerlo con cualquier sistema de referencia espacial en un SIG, entonces tiene una superficie orientable. Entonces, si puede definir una dirección, puede definir un orden direccional alrededor de cualquier punto en la superficie. Con el ordenamiento direccional puede definir isLeftOf (A, B), isRotationallyAdarestTo (A, B), etc.
La definición del orden alrededor de un vértice en un gráfico incrustado en una superficie requiere dos asignaciones: 1) asignar etiquetas a los puntos finales del borde y 2) asignar una convención para ordenar alrededor de un vértice. Si el orden de los elementos en una matriz (por ejemplo, [A, B, C] en su imagen) está en el sentido de las agujas del reloj, entonces podemos decir qué borde está a la izquierda de B.
En su ejemplo, cada elemento es adyacente a los demás. Ese hecho también es visible en la matriz porque la matriz en realidad representa una permutación, es decir, el orden importa, pero qué elemento es primero no. Entonces [A, B, C] es equivalente a [C, A, B]. En otras palabras, la matriz se envuelve haciendo que el último elemento sea adyacente al primero.
fuente
Cuando observa los gráficos de topología y conectividad que obtiene de proveedores como Teleatlas, Navteq, ESRI, etc., comenzará a ver un patrón (por supuesto, cada uno tiene su propia forma "especial" de hacer las cosas).
Personalmente , a pesar de que 1) la topología geoespacial y 2) los gráficos de enrutamiento son solo gráficos y pueden generalizarse para representarse en la misma estructura de datos, trato de evitar eso tanto como sea posible.
Trato de hacer una distinción en mi cabeza.
Son solo gráficos, y pertenecen a la amplitud de la ciencia , pero existe una clara ventaja de no generalizar como lo mismo. Sirven para diferentes propósitos, y es mucho más fácil optimizar y aplicar operaciones cuando están especializados para ese propósito en particular.
ESRI hace esto. Tienen una estructura gráfica para la topología geoespacial (TopologyGraph) y una estructura gráfica diferente para los problemas de enrutamiento (dataset de red). Diablos, incluso tienen una estructura gráfica más antigua, redes geométricas , que sirve bien para problemas de flujo en redes de servicios públicos.
Posiblemente, en el mundo PostgreSQL / PostGIS, también nos encontramos con esto. Hay una estructura de datos para el enrutamiento y otra para la topología geoespacial .
En su pregunta, está hablando de gráficos y navegándolos en sentido horario y antihorario, así como en caras, lo que me hace pensar que desea una estructura especializada para (1).
Para "Topología geoespacial", creo que una buena manera de representar este tipo de topología es la forma en que lo hace la Oficina Hidrográfica del Reino Unido en su Descripción de topología completa de topología S57 .
Muy similar a lo que hacen todas las implementaciones principales.
Ahora, si lo que está buscando es enrutamiento, entonces el gráfico se vuelve diferente en función de si necesita conectividad de dirección única o bidireccional. Al final, se reduce a:
Buena suerte y háganos saber cómo resulta su proyecto.
fuente