¿Cómo describo una relación especial entre los bordes conectados?

11

Considere esta situación simple donde tres bordes se conectan en un nodo:

relaciones de borde

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:

  1. 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!)

  2. 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.

andytilia
fuente
¿Por qué no adjuntas a cada nodo la lista de aristas conectadas ordenadas por dirección?
julien
1
Parece que estás buscando un DCEL . Tenga en cuenta que cuando dualiza un gráfico plano , las caras se convierten en nodos. En la ilustración hay piezas de tres caras alfa , beta y gamma , con el borde A separando beta de gamma , el borde B separando gamma de alfa y el borde C separando alfa de beta . Eso produce un gráfico cíclico que contiene toda la información que está buscando, y de hecho es adyacencia en el gráfico dual.
whuber
@julien, gracias, esa es una idea de implementación decente; Voy a tratar de salir. Pero primero ... Estoy buscando una palabra o frase para describir este tipo de relación.
andytilia
@whuber, gracias por el consejo. No me he encontrado con DCEL antes. Parece que B es el "próximo" medio borde del norte, el medio borde hacia el oeste de A. Hm: entonces si quiero ir en sentido antihorario, entonces considero el medio borde hacia el sur de A. Y "hacia el oeste" está implícito en el nodo común. Me pregunto si funcionará cuando B no sea un límite frontal (es decir, una calle sin salida). Lo investigaré más a fondo.
andytilia
@julien, estoy leyendo tu comentario nuevamente. Ahora puedo ver que también me estás dando una frase sugerida. :-) Tal vez podría usar "ordenado por dirección" para describir la relación. Tengo que jugar un poco con eso.
andytilia

Respuestas:

1

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.

katahdin
fuente
¡Gracias! Me gusta el término "rotacionalmente adyacente". Solo necesita extenderse, como usted dice, con la convención para ordenar alrededor de un vértice. En mi caso, necesito definir esa convención caso por caso, así que voy a trabajar en la codificación de algo como isRotationallyAdarestTo (A, B, Direction) usando una permutación como usted sugiere. O en términos del caso anterior, "A es adyacente en sentido horario a R y R no es adyacente en sentido horario a C".
andytilia
Por cierto, todavía no había investigado el cálculo de la conexión de la región. Si bien no es exactamente lo que resuelve este problema (como usted menciona), no obstante es interesante. ¿Puedes señalarme los "trabajos posteriores" que tienes en mente por Randell, Cui y Cohn? (hm: los personajes de RC&C crearon un marco llamado RCC)
andytilia
4

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.

  • Cuando digo "Topología geoespacial" (1) me refiero a una estructura gráfica para representar las relaciones geométricas de las características (por ejemplo, lo que queda del borde A, qué cara está formada por los bordes [A, B, C], lo que está contenido en la cara B, etc.)
  • Cuando digo "Gráfico de enrutamiento" (2), me refiero a una estructura gráfica para resolver problemas de enrutamiento (por ejemplo, la ruta más corta para llegar desde A-> B con [X] restricciones / condiciones)

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 .

Topología completa de UKHO

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:

  • Tener nodos FROM conectados a nodos TO que crean bordes
  • Los bordes tienen atributos para el lado izquierdo y derecho (por ejemplo, rangos de direcciones).
  • Las uniones (es decir, los nodos donde se conectan los bordes) pueden tener un conjunto de restricciones. Entonces, básicamente, tendría una entrada de unión maestra para representar la unión en sí, y entradas individuales con entradas FROM y TO para representar las restricciones de flujo.

Buena suerte y háganos saber cómo resulta su proyecto.

Ragi Yaser Burhum
fuente
Muchas gracias por hacer la clara distinción entre dos tipos de gráficos. ¿Crees que es una distinción justa decir que los gráficos de enrutamiento generalmente contienen información sobre los bordes y / o nodos, mientras que la topología geoespacial nunca necesita atribución en los bordes y nodos (se basa solo en las relaciones espaciales entre los objetos)? Supongo que mi problema encaja firmemente en el dominio de la topología geoespacial: la relación entre los bordes A y B existe independientemente de cualquier atribución en los bordes. Pero todavía me falta una manera sucinta para nombrar esta relación ...
andytilia
Creo que es una afirmación demasiado fuerte como para decir que "la topología geoespacial nunca necesita atribución en los bordes y nodos", es realmente caso por caso. He visto gráficos de topología que contienen atribuciones que se comparten entre las características que tienen ese nodo. Ejemplos son los valores de Z o temperatura. Yo diría que solo diga simplemente llámelo nodo y haga la distinción del nodo conectado cuando sea necesario, pero por supuesto, no tengo suficiente contexto del problema general que está tratando de resolver.
Ragi Yaser Burhum
Ah, cierto, gracias: una representación gráfica plana de dos caminos que se cruzan en un puente. Podría haber un nodo con cuatro aristas, pero no todas las aristas se conectan entre sí. Por lo tanto, el nodo debe contener información sobre los niveles de cruce, para diferenciar esa situación de un cruce a nivel.
andytilia
1
Exactamente :). Por eso menciono Junctions. Estaba pensando en ese caso. Una forma de hacerlo es representar la unión como un "nodo maestro" con las entradas FROM-TO. Las situaciones de paso superior / inferior se producen todo el tiempo. Peor aún son los casos como el Puente de la Bahía o en Chicago, donde tiene bordes que coinciden en el espacio 2D (están efectivamente uno encima del otro) con un conjunto de bordes que fluyen hacia un lado, mientras que el otro conjunto fluye hacia el otro lado.
Ragi Yaser Burhum