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

Question

Considera esta sencilla situación en la que tres bordes que se conectan a un nodo:

Me gustaría escribir una breve y clara descripción de la relación entre a y B, de tal manera que la diferencia de la relación entre a y C. Algo así como "al atravesar el nodo en la dirección de las agujas, es adyacente? a B, pero no es adyacente? C." Pero no es realmente de adyacencia.

Dicho de otro modo: imagina que estás de pie en el nodo y que usted está mirando hacia A. Usted empieza a girar a ti mismo de las agujas del reloj. El próximo edge llegará a es B, C. no

Es allí una manera de describir esta relación entre a y B de una manera más sucinta, formal, o, de manera correcta, de lo que he escrito arriba?

Debe ser direccional (una relación de este tipo existe en el sentido de las agujas de Una y otra existe en el sentido antihorario). Y se debe aumentar la escala de los casos donde más de tres bordes están conectados al nodo. Quizás tiene algo que ver con enrutamiento? (Estoy pensando sobre esto en el contexto de las redes de carreteras.)

Dos enfoques he intentado, pero ya no los he conseguido, de momento, con:

1. 9IM-como la topología referencias: he mirado en el DE-9IM, y a pesar de que yo no soy un matemático, creo que todavía puedo decir a partir de los diagramas de y términos que no cubre este tipo de relación. Ni puedo encontrar aún en la topología de las descripciones en el ESRI ayuda o ayuda de Oracle. (Tal vez hay algo ahí, pero no estoy encontrando todavía!)

2. Caras: he jugado un poco con el hecho de que la cara en el "norte" de lado de Un posible también delimitada también por B, pero no en C. sin Embargo, como se puede ver en el diagrama de aquí, que no es siempre cierto. Imaginen mi diagrama es un extracto de una carretera de la red, donde a y C son caminos y B es un corto callejón carretera.

Sospecho que hay no puede ser un término único para lo que estoy tratando de decir; como mínimo me gustaría ser capaz de describir esta relación de una manera más sencilla que he hecho anteriormente. Esta es una plataforma independiente de la cuestión. Ahora mismo, estoy buscando las palabras adecuadas. Más adelante voy a tratar de poner en práctica el concepto en python (pyqgis o arcpy) en un shapefile, por lo que cualquier respuesta con que el punto final en mente será particularmente interesante, pero no es necesario.

Answer 1

Cuando usted mira a la topología y la conectividad de los gráficos que se obtienen de los proveedores como Teleatlas, Navteq, ESRI, etc, usted comenzará a ver un patrón (por supuesto cada uno tiene su propio "especial" manera de hacer las cosas).

Personalmente, aunque 1) Geoespacial de la Topología y 2) de Enrutamiento de los Gráficos son sólo Gráficos y puede ser generalizado para ser representados en la misma estructura de datos, trato de evitar tanto como sea posible.

Yo intente hacer una distinción en mi cabeza.

• Cuando digo "Geoespaciales Topología" (1) me refiero a una estructura de grafo para representar las relaciones geométricas de las características (e.g lo que está a la izquierda de la arista a, qué cara está formado por los bordes [a,B,C], lo que es contenida por la cara B, etc).
• Cuando digo "de Enrutamiento Gráfico" (2), me refiero a una estructura de grafo para la resolución de problemas de enrutamiento (por ejemplo, la ruta más corta para llegar de a->B [X] restricciones/condiciones)

Ellos son sólo los gráficos, y que pertenecen a la amplitud de la ciencia, pero hay una clara ventaja de no generalizar como la misma cosa. Que sirven a propósitos diferentes, y es mucho más fácil de optimizar y aplicar las operaciones cuando son especializados para el fin determinado.

ESRI hace esto. Tienen una estructura de grafo para Geoespacial de la Topología (TopologyGraph) y una diferente estructura de Grafo para Problemas de Enrutamientode red(conjunto de datos). Heck, incluso tienen una mayor Estructura de Grafo - Redes Geométricas - que sirve también para problemas de flujo en redes de servicios públicos.

Podría decirse que, en el PostgreSQL/PostGIS mundo, nos encontramos también con esta. Hay una estructura de datos para el enrutamiento y la otra para geoespacial de la topología.

En su pregunta, usted está hablando acerca de los gráficos y navegar por ellos en sentido horario y antihorario, así como caras, que hacen de mí lo que desea una estructura especializada para (1).

Para "Geoespaciales Topología", creo que una buena manera de representar este tipo de Topología es la forma en que la Oficina Hidrográfica del reino unido en su S57 Topología Descripción de la Topología Completa.

Muy similar a lo que todas las principales implementaciones de hacer.

Ahora, si lo que se busca es la de enrutamiento, a continuación, el gráfico se convierte en diferente si usted necesita sola dirección o bi-direccional de conectividad. Al final, todo se reduce a:

• Tener a partir DE nodos conectados A los nodos que crear Bordes
• Los Bordes tienen atributos para el lado izquierdo y derecho (por ejemplo, rangos de direcciones).
• Las Uniones (he.e los nodos donde los bordes de conectar) puede tener un conjunto de restricciones. Así que, básicamente, tendría un maestro de unión de entrada para representar a la unión en sí, y cada una de las entradas con , DESDE y PARA las entradas para la representación de las restricciones de flujo.

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

Answer 2

Sé que estoy un poco tarde a la fiesta aquí, pero esto es bastante interesante, y espero que mi respuesta puede ser de alguna utilidad.

Lo que están pidiendo es una cualitativo de la relación; la tantas veces ignorado hermano de la relación cuantitativa. El razonamiento cualitativo viene muy a menudo en geoespacial de la ciencia. Consultas de ejemplo incluyen: parcelas adyacentes a éste? Cuáles son las funciones dentro de la superposición de Una región y la región B? Cuáles son las regiones cóncavas? Cuál es el camino que está a la izquierda? Las relaciones: adyacente, dentro de, cóncava, y a la izquierda de. Cualitativa consultas a menudo ignoradas o menospreciadas, cuando en comparación con preguntas cuantitativas como que es mayor, menor o mayor en número.

Una cualitativo de la relación que lleva dos entradas que se llama una relación binaria. Existen dos notaciones para esto: - isLeftOf(a,B) Esta es la notación de prefijo. - Un isLeftOf B Esta es la notación de infijo.

En los ejemplos anteriores también hubo un unario relación: isConcave. Esta relación se refiere a una región, a sí misma y devuelve un valor booleano.

Todos Egenhofer espacial de los predicados en el 9-intersección (modelo de referencia en el 9EIM) son binarios de las relaciones entre las dos regiones. Usted también podría estar interesado en Randell, Cui y Cohn RCC (http://en.wikipedia.org/wiki/Region_connection_calculus). La cualitativa (topológico) de las relaciones dadas en esta área de estudio se refieren a las regiones a las regiones, y más tarde las obras se relacionan las líneas de las regiones y líneas de líneas. Sin embargo, esto no es exactamente lo que usted está buscando.

OK, perdón por la digresión, pero espero que ayude con la terminología aspecto de su pregunta.

@whuber estaba en el camino correcto con lo que sugiere la doble conectado borde de la lista (DCEL). Este es un pariente cercano de la combinatoria de los mapas, a menudo se utiliza bajo las cubiertas en sistemas CAD, y alado de los bordes. Las alas de borde (http://en.wikipedia.org/wiki/Winged_edge el concepto es como el conocido texto estándar define un agujero en un polígono (http://en.wikipedia.org/wiki/Well-known_text#Geometric_objects). Nota en el polígono que el orden de los exteriores de los puntos en contra de las agujas del reloj y en sentido horario para los puntos interiores. Un poco de cuento de la persona que camina a lo largo de la frontera en este orden siempre ver el interior de la región a su izquierda.

Con la combinatoria de los mapas y DCEL el punto clave es que estos objetos están definidos en una superficie que es orientable. No necesitamos entrar en la de matemáticas trámites - la idea es bastante simple: si usted puede definir la dirección en la superficie, como usted puede con cualquier sistema de referencia espacial en un SIG, entonces usted tiene una superficie orientable. Por lo tanto, si usted puede definir una dirección, entonces usted puede definir una direccional de pedido alrededor de cualquier punto en la superficie. Con direccional de pedido puede definir isLeftOf(a,B), isRotationallyAdjacentTo(a,B) y así sucesivamente.

La definición de pedidos de alrededor de un vértice en un gráfico incrustado en una superficie requiere dos tareas: 1) asignación de etiquetas a borde de los puntos finales y 2) la asignación de un convenio para el fin de alrededor de un vértice. Si el elemento de orden en un conjunto (por ejemplo, [a,B,C] en la imagen) es de las agujas del reloj, entonces podemos decir que el borde está a la izquierda de B.

En tu ejemplo, cada elemento es adyacente a los demás. Este hecho es también visible en la matriz debido a que la matriz representa, en realidad, una permutación, es decir, el orden de las cosas, pero que es el elemento primero no. Por lo tanto [a,B,C] es equivalente a [C,a,B]. En otras palabras, la matriz se envuelve alrededor de hacer el último elemento adyacente a la primera.