Como descrevo um relacionamento especial entre arestas conectadas?

11

Considere esta situação simples em que três arestas se conectam em um nó:

relacionamentos de ponta

Eu gostaria de escrever uma descrição sucinta e clara do relacionamento entre A e B de modo a diferenciá-lo do relacionamento entre A e C. Algo como “ao atravessar o nó no sentido horário, A é adjacente? para B, mas A não é adjacente? para C. " Mas não é realmente adjacência.

Disse de uma maneira diferente: imagine que você está de pé no nó e está voltado para A. Você começa a girar no sentido horário. A próxima vantagem que você encontrará é B, não C.

Existe uma maneira de descrever essa relação entre A e B de uma maneira mais sucinta, formal ou correta do que escrevi acima?

Ele deve ser direcional (um relacionamento desse tipo existe no sentido horário de A e outro existe no sentido anti-horário). E deve escalar até casos em que mais de três arestas estão conectadas no nó. Talvez tenha algo a ver com roteamento? (Estou pensando sobre isso no contexto das redes rodoviárias.)

Duas abordagens que eu já tentei, mas ainda não fui longe:

  1. Referências de topologia semelhantes ao 9IM : Eu olhei para o DE-9IM e, embora eu não seja um matemático, acho que ainda posso dizer pelos diagramas e termos que ele não cobre esse tipo de relacionamento. Também não o encontro nas descrições de topologia da ajuda da ESRI ou da Oracle . (Talvez haja algo lá, mas eu ainda não o encontrei!)

  2. Rostos : brinquei com o fato de que o lado "norte" de A também pode ser delimitado por B, mas não por C. No entanto, como você pode ver no diagrama aqui, isso nem sempre é verdade. Imagine que meu diagrama é um extrato de uma rede de estradas em que A e C são vias arteriais e B é uma estrada sem saída curta.

Eu suspeito que pode não haver um único termo para o que estou tentando dizer; no mínimo, eu gostaria de descrever esse relacionamento de uma maneira mais simples do que eu fiz acima. Esta é uma pergunta independente de plataforma. No momento, estou apenas procurando as palavras certas. Mais tarde, tentarei implementar o conceito em python (pyqgis ou arcpy) em um shapefile, para que quaisquer respostas com esse ponto final em mente sejam particularmente interessantes, mas não necessárias.

andytilia
fonte
Por que você não anexa a cada nó a lista de arestas conectadas a ele, ordenadas por direção?
julien
1
Parece que você está procurando um DCEL . Observe que quando você dualiza um gráfico planar , as faces se tornam nós. Na ilustração, existem partes de três faces alfa , beta e gama , com a borda A separando beta de gama , a borda B separando gama de alfa e a borda C separando alfa de beta . Isso gera um gráfico cíclico que contém todas as informações que você está procurando - e de fato é realmente adjacência no gráfico duplo.
whuber
@ julien, obrigado - essa é uma idéia decente de implementação; Vou testá-lo. Mas primeiro ... estou procurando uma palavra ou frase para descrever esse tipo de relacionamento.
22712 Andytilia
@ whuber, obrigado pela dica. Eu não encontrei o DCEL antes. Parece que B é a "próxima" metade da aresta norte, na direção oeste da A. Hm: então, se eu quiser ir no sentido anti-horário, considero a metade da aresta sul de A. E "direção oeste" é implícito pelo nó comum. Gostaria de saber se funcionará quando B não for um limite de face (ou seja, estrada sem saída). Vou investigar melhor.
22712 Andytilia
@ Julien, estou lendo seu comentário novamente. Eu posso ver agora que você também está me sugerindo frases. :-) Talvez eu possa usar "ordenado por direção" para descrever o relacionamento. Tenho que brincar um pouco.
andytilia

Respostas:

1

Sei que estou um pouco atrasado para a festa aqui, mas isso é algo bastante interessante, e espero que minha resposta possa ser útil.

O que você está perguntando é uma relação qualitativa; o irmão muitas vezes ignorado da relação quantitativa. O raciocínio qualitativo surge com bastante frequência na ciência geoespacial. Exemplos de consultas incluem: Quais parcelas são adjacentes a esta? Quais recursos estão dentro da sobreposição da região A e da região B? Quais regiões são côncavas? Qual estrada está à esquerda? As relações são: adjacentes a, dentro de, côncavas e esquerdas de. As consultas qualitativas geralmente passam despercebidas ou desvalorizadas quando comparadas a perguntas quantitativas, como qual é maior, menor ou maior em número.

Uma relação qualitativa que recebe duas entradas é chamada de relação binária. Existem duas notações comuns para isso: - isLeftOf (A, B) Esta é uma notação de prefixo. - A isLeftOf B Esta é uma notação de infixo.

Nos exemplos acima, havia também uma relação unária: isConcave. Essa relação relaciona uma região a si mesma e retornaria um valor booleano.

Todos os predicados espaciais de Egenhofer no modelo de 9 interseções (referenciados no 9EIM) são relações binárias entre duas regiões. Você também pode estar interessado no RCC de Randell, Cui e Cohn (http://en.wikipedia.org/wiki/Region_connection_calculus). As relações qualitativas (topológicas) dadas nesta área de estudo relacionam regiões para regiões, e trabalhos posteriores relacionam linhas para regiões e linhas para linhas. No entanto, isso não é exatamente o que você está procurando.

OK, desculpe a digressão, mas espero que ajude com o aspecto terminológico da sua pergunta.

A @whuber estava no caminho certo ao sugerir a lista de arestas duplamente conectadas (DCEL). Este é um parente próximo de mapas combinatórios, frequentemente usados ​​sob as coberturas em sistemas CAD e bordas aladas. O conceito de borda alada (http://en.wikipedia.org/wiki/Winged_edge) é como o padrão de texto conhecido define um buraco em um polígono (http://en.wikipedia.org/wiki/Well-known_text #Geometric_objects). Observe no polígono que a ordem dos pontos externos é no sentido anti-horário e no sentido horário para os pontos internos. Uma pequena fada caminhando ao longo da fronteira nessa ordem sempre veria o interior da região à sua esquerda.

Nos mapas combinatórios e no DCEL, o ponto principal é que esses objetos sejam definidos em uma superfície orientável. Não precisamos entrar nas formalidades matemáticas - a idéia é bem simples: se você pode definir a direção na superfície, como em qualquer sistema de referência espacial em um GIS, então você tem uma superfície orientável. Portanto, se você pode definir uma direção, pode definir uma ordem direcional em torno de qualquer ponto da superfície. Com a ordem direcional, você pode definir isLeftOf (A, B), isRotationallyAdjacentTo (A, B) e assim por diante.

Definir a ordem em torno de um vértice em um gráfico incorporado em uma superfície requer duas atribuições: 1) atribuir etiquetas aos pontos finais da aresta e 2) atribuir uma convenção para ordem em torno de um vértice. Se a ordem dos elementos em uma matriz (por exemplo, [A, B, C] na sua imagem) estiver no sentido horário, podemos dizer qual aresta está à esquerda de B.

No seu exemplo, cada elemento é adjacente aos outros. Esse fato também é visível na matriz, porque na verdade representa uma permutação, ou seja, a ordem é importante, mas qual elemento é o primeiro não. Então [A, B, C] é equivalente a [C, A, B]. Em outras palavras, a matriz envolve o último elemento adjacente ao primeiro.

katahdin
fonte
Obrigado! Eu gosto do termo "Rotacionalmente Adjacente". Ele só precisa ser estendido, como você diz, com a convenção para solicitar em torno de um vértice. No meu caso, preciso definir essa convenção caso a caso. Então, eu vou trabalhar na codificação de algo como isRotationallyAdjacentTo (A, B, Direction) usando uma permutação como você sugere. Ou nos termos do caso acima, “A é rotacional no sentido horário adjacente a B e A não é rotacional no sentido horário adjacente a C”.
andytilia
A propósito, eu ainda não tinha estudado o Cálculo de Conexão por Região. Embora não seja exatamente o que resolve esse problema (como você mencionou), é interessante mesmo assim. Você pode me indicar os "trabalhos posteriores" que você tem em mente por Randell, Cui e Cohn? (hm: os personagens RC & C criou um quadro chamado RCC)
andytilia
4

Quando você olha para os gráficos de topologia e conectividade obtidos de fornecedores como Teleatlas, Navteq, ESRI, etc., você começará a ver um padrão (é claro que todos têm sua própria maneira "especial" de fazer as coisas).

Pessoalmente , embora 1) Topologia Geoespacial e 2) Gráficos de Roteamento sejam apenas Gráficos e possam ser generalizados para serem representados na mesma estrutura de dados, tento evitar isso o máximo possível.

Eu tento fazer uma distinção na minha cabeça.

  • Quando digo "Topologia Geoespacial" (1), quero dizer uma estrutura gráfica para representar relações geométricas dos recursos (por exemplo, o que resta da aresta A, que face é formada pelas arestas [A, B, C], o que está contido pela face B, etc).
  • Quando digo "Routing Graph" (2), refiro-me a uma estrutura gráfica para resolver problemas de roteamento (por exemplo, o caminho mais curto para ir de A-> B com [X] restrições / condições)

São apenas gráficos e pertencem à abrangência da ciência , mas há uma clara vantagem de não generalizar como a mesma coisa. Eles servem a propósitos diferentes e é muito mais fácil otimizar e aplicar operações quando são especializados para esse objetivo específico.

A ESRI faz isso. Eles possuem uma estrutura gráfica para Topologia Geoespacial (TopologyGraph) e uma estrutura Gráfico diferente para Problemas de Roteamento (conjunto de dados da rede). Caramba, eles ainda têm uma Estrutura Gráfica mais antiga - Redes Geométricas - que serve bem para problemas de fluxo em redes de serviços públicos.

Indiscutivelmente, no mundo PostgreSQL / PostGIS, também encontramos isso. Existe uma estrutura de dados para roteamento e outra para topologia geoespacial .

Na sua pergunta, você está falando sobre gráficos e navegando neles no sentido horário e anti-horário, bem como faces, o que me faz pensar que você deseja uma estrutura especializada para (1).

Para "Topologia geoespacial", acho que uma boa maneira de representar esse tipo de topologia é o que o Escritório Hidrográfico do Reino Unido faz em sua Descrição de topologia completa da57 .

Topologia Completa do UKHO

Muito parecido com o que todas as principais implementações fazem.

Agora, se o que você está procurando é roteamento, o gráfico se torna diferente com base na necessidade de conectividade unidirecional ou bidirecional. No final, tudo se resume a:

  • Ter nós FROM conectados a nós TO que criam bordas
  • As arestas têm atributos para os lados esquerdo e direito (por exemplo, intervalos de endereços).
  • As junções (ou seja, os nós nos quais as arestas se conectam) podem ter um conjunto de restrições. Portanto, você basicamente teria uma entrada de junção principal para representar a própria junção e entradas individuais com entradas FROM e TO para representar as restrições de fluxo.

Boa sorte e deixe-nos saber como é o seu projeto.

Ragi Yaser Burhum
fonte
Muito obrigado por fazer a distinção clara entre dois tipos de gráficos. Você acha que é uma distinção justa dizer que os Gráficos de Roteamento geralmente contêm algumas informações nas arestas e / ou nós, enquanto a Topologia Geoespacial nunca precisa de atribuição nas arestas e nós (é baseada apenas nas relações espaciais entre os objetos)? Acho que meu problema se encaixa firmemente no domínio da topologia geoespacial: o relacionamento entre as arestas A e B existe independentemente de qualquer atribuição nas arestas. Mas eu ainda estou sentindo falta de uma forma sucinta para citar esta relação ...
andytilia
Eu acho que é uma afirmação muito forte dizer que "A topologia geoespacial nunca precisa de atribuição nas bordas e nos nós", é realmente caso a caso. Vi gráficos de topologia que contêm atribuição compartilhada entre os recursos que possuem esse nó. Exemplos são Z ou valores de temperatura. Eu diria que basta dizer apenas chamá-lo de e fazer a distinção entre nós quando necessário, mas é claro que não tenho um contexto suficiente do problema geral que você está tentando resolver.
Ragi Yaser Burhum
Ah, certo, obrigado: uma representação gráfica plana de duas estradas que cruzam em uma ponte. Pode haver um nó com quatro arestas, mas nem todas as arestas se conectam. Portanto, o nó precisa conter informações sobre níveis de cruzamento, para diferenciar essa situação de um cruzamento na série.
andytilia
1
Exatamente :). É por isso que mencionei Junções. Eu estava pensando sobre esse caso. Uma maneira de fazer isso é representar a junção como um "nó principal" com as entradas FROM-TO. As situações de passagem superior / inferior ocorrem o tempo todo. Pior ainda são os casos como a Bay Bridge ou em Chicago, onde você tem arestas que correspondem no espaço 2D (elas estão efetivamente em cima umas das outras) com um conjunto de arestas fluindo para um lado, enquanto o outro conjunto flui para o outro lado.
Ragi Yaser Burhum