Comment décrire une relation spéciale entre les arêtes connectées?

Considérez cette situation simple où trois arêtes se connectent à un nœud:

Je voudrais écrire une description succincte et claire de la relation entre A et B de manière à la différencier de la relation entre A et C. Quelque chose comme «lors de la traversée du nœud dans le sens horaire, A est adjacent? à B, mais A n'est pas adjacent? à C. " Mais ce n'est pas vraiment de la contiguïté.

Dit d'une manière différente: imaginez que vous vous tenez sur le nœud et que vous êtes face à A. Vous commencez à vous tourner dans le sens des aiguilles d'une montre. Le bord suivant où vous arriverez est B, pas C.

Existe-t-il un moyen de décrire cette relation entre A et B d'une manière plus succincte, formelle ou correcte que ce que j'ai écrit ci-dessus?

Elle doit être directionnelle (une relation de ce type existe dans le sens horaire à partir de A et une autre dans le sens antihoraire). Et il doit évoluer jusqu'aux cas où plus de trois arêtes sont connectées au nœud. Peut-être que cela a quelque chose à voir avec le routage? (J'y pense dans le contexte des réseaux routiers.)

J'ai déjà essayé deux approches mais je ne suis pas allé bien loin:

1. Références de topologie de type 9IM : J'ai regardé le DE-9IM , et même si je ne suis pas mathématicien, je pense que je peux toujours dire à partir des diagrammes et des termes qu'il ne couvre pas ce type de relation. Je ne le trouve pas encore non plus dans les descriptions de topologie de l' aide ESRI ou de l' aide Oracle . (Peut-être y a-t-il quelque chose mais je ne le trouve pas encore!)

2. Visages : J'ai joué avec le fait que le visage du côté «nord» de A pourrait également être délimité par B, mais pas C. Cependant, comme vous pouvez le voir sur le diagramme ici, ce n'est pas toujours vrai. Imaginez que mon diagramme est un extrait d'un réseau routier où A et C sont des artères et B est une courte route sans issue.

Je soupçonne qu'il n'y a pas un seul terme pour ce que j'essaie de dire; Au minimum, j'aimerais pouvoir décrire une telle relation d'une manière plus simple que je l'ai fait ci-dessus. Il s'agit d'une question indépendante de la plateforme. En ce moment, je cherche juste les bons mots. Plus tard, j'essaierai d'implémenter le concept en python (pyqgis ou arcpy) sur un fichier de formes, donc toutes les réponses avec ce point final à l'esprit seront particulièrement intéressantes, mais pas nécessaires.

Je sais que je suis un peu en retard à la fête ici, mais c'est quelque chose d'assez intéressant et j'espère que ma réponse pourra être utile.

Ce que vous demandez, c'est une relation qualitative; le frère souvent ignoré de la relation quantitative. Le raisonnement qualitatif revient assez souvent dans les sciences géospatiales. Exemples de requêtes: quelles parcelles sont adjacentes à celle-ci? Quelles caractéristiques se trouvent à l'intérieur du chevauchement de la région A et de la région B? Quelles régions sont concaves? Quelle route est à gauche? Les relations étant: adjacentes à, à l'intérieur de, concaves et à gauche de. Les requêtes qualitatives sont souvent négligées ou sous-évaluées par rapport aux questions quantitatives telles que celles qui sont plus grandes, plus courtes ou plus nombreuses.

Une relation qualitative qui prend deux entrées est appelée relation binaire. Il existe deux notations courantes à cet effet: - isLeftOf (A, B) Il s'agit de la notation de préfixe. - A isLeftOf B Il s'agit de la notation infixe.

Dans les exemples ci-dessus, il y avait aussi une relation unaire: isConcave. Cette relation relie une région à elle-même et renverrait une valeur booléenne.

Tous les prédicats spatiaux d'Egenhofer dans le modèle à 9 intersections (référencés dans le 9EIM) sont des relations binaires entre deux régions. Vous pouvez également être intéressé par Randell, Cui et Cohn's RCC (http://en.wikipedia.org/wiki/Region_connection_calculus). Les relations qualitatives (topologiques) données dans ce domaine d'étude relient les régions aux régions, et les travaux ultérieurs relient les lignes aux régions et les lignes aux lignes. Cependant, ce n'est pas tout à fait ce que vous recherchez.

OK, désolé pour la digression, mais j'espère que cela aide avec l'aspect terminologique de votre question.

@whuber était en bonne voie pour suggérer la liste de périphérie doublement connectée (DCEL). Il s'agit d'un proche parent des cartes combinatoires, souvent utilisées sous les couvertures dans les systèmes de CAO, et des bords ailés. Le concept de bord ailé (http://en.wikipedia.org/wiki/Winged_edge) est la façon dont la norme de texte bien connue définit un trou dans un polygone (http://en.wikipedia.org/wiki/Well-known_text #Geometric_objects). Notez sur le polygone que l'ordre des points extérieurs est dans le sens antihoraire et dans le sens horaire pour les points intérieurs. Une petite fée marchant le long de la frontière dans cet ordre verrait toujours l'intérieur de la région sur sa gauche.

Avec les cartes combinatoires et DCEL, le point clé est que ces objets sont définis sur une surface orientable. Nous n'avons pas besoin d'entrer dans les formalités mathématiques - l'idée est assez simple: si vous pouvez définir la direction sur la surface, comme vous pouvez le faire avec n'importe quel système de référence spatiale dans un SIG, alors vous avez une surface orientable. Donc, si vous pouvez définir une direction, vous pouvez définir un ordre directionnel autour de n'importe quel point de la surface. Avec l'ordre directionnel, vous pouvez définir isLeftOf (A, B), isRotationallyAdjacentTo (A, B) et ainsi de suite.

La définition de l'ordre autour d'un sommet dans un graphique incorporé sur une surface nécessite deux affectations: 1) l'attribution d'étiquettes aux extrémités des arêtes et 2) l'attribution d'une convention pour l'ordre autour d'un sommet. Si l'ordre des éléments dans un tableau (par exemple [A, B, C] dans votre image) est dans le sens horaire, alors nous pouvons dire quel bord est à gauche de B.

Dans votre exemple, chaque élément est adjacent aux autres. Ce fait est également visible dans le tableau parce que le tableau représente en fait une permutation, c'est-à-dire que l'ordre compte, mais quel élément est le premier non. Donc [A, B, C] est équivalent à [C, A, B]. En d'autres termes, le tableau s'enroule en faisant le dernier élément adjacent au premier.

Lorsque vous regardez les graphiques de topologie et de connectivité que vous obtenez de fournisseurs comme Teleatlas, Navteq, ESRI, etc., vous commencez à voir un modèle (bien sûr, tout le monde a sa propre façon "spéciale" de faire les choses).

Personnellement , même si 1) la topologie géospatiale et 2) les graphiques de routage ne sont que des graphiques et peuvent être généralisés pour être représentés dans la même structure de données, j'essaie d'éviter cela autant que possible.

J'essaie de faire une distinction dans ma tête.

• Quand je dis "Topologie géospatiale" (1) je veux dire une structure graphique pour représenter les relations géométriques des entités (par exemple ce qui reste du bord A, quelle face est formée par les bords [A, B, C], ce qui est contenu par la face B, etc.).
• Quand je dis "Routing Graph" (2), je veux dire une structure graphique pour résoudre les problèmes de routage (par exemple le chemin le plus court pour aller de A-> B avec [X] restrictions / conditions)

Ce ne sont que des graphiques, et ils appartiennent à l' étendue de la science , mais il y a un avantage évident à ne pas généraliser comme la même chose. Ils servent à des fins différentes, et il est beaucoup plus facile d'optimiser et d'appliquer des opérations lorsqu'elles sont spécialisées dans ce but particulier.

ESRI fait cela. Ils ont une structure graphique pour la topologie géospatiale (TopologyGraph) et une structure graphique différente pour les problèmes de routage (jeu de données réseau). Heck, ils ont même une ancienne structure de graphique - Réseaux géométriques - qui sert bien pour les problèmes de flux dans les réseaux de services publics.

On peut dire que dans le monde PostgreSQL / PostGIS, nous rencontrons également cela. Il existe une structure de données pour le routage et une autre pour la topologie géospatiale .

Dans votre question, vous parlez de graphiques et de les parcourir dans le sens horaire et antihoraire, ainsi que des visages, ce qui me fait penser que vous voulez une structure spécialisée pour (1).

Pour "Topologie géospatiale", je pense qu'une bonne façon de représenter ce type de topologie est la façon dont le UK Hydrographic Office fait dans sa description de topologie S57 de la topologie complète .

Très similaire à ce que font toutes les implémentations principales.

Maintenant, si ce que vous recherchez est un routage, le graphique devient différent selon que vous avez besoin d'une connectivité unidirectionnelle ou bidirectionnelle. À la fin, cela se résume à:

• Avoir des nœuds FROM connectés à des nœuds TO qui créent des bords
• Les bords ont des attributs pour les côtés gauche et droit (par exemple, les plages d'adresses).
• Les jonctions (c'est-à-dire les nœuds où les bords se connectent) peuvent avoir un ensemble de restrictions. Donc, vous auriez essentiellement une entrée de jonction principale pour représenter la jonction elle-même, et des entrées individuelles avec des entrées FROM et TO pour représenter les restrictions de flux.

Bonne chance et faites-nous savoir comment se déroule votre projet.