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

11

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

relations de bord

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.

andytilia
la source
Pourquoi ne rattachez-vous pas à chaque nœud la liste des arêtes qui lui sont connectées ordonnée par direction?
julien
1
Il semble que vous recherchiez un DCEL . Notez que lorsque vous dualisez un graphe planaire , les faces deviennent des nœuds. Dans l'illustration, il y a des morceaux de trois faces alpha , bêta et gamma , avec le bord A séparant la bêta du gamma , le bord B séparant le gamma de l' alpha et le bord C séparant l' alpha de la bêta . Cela donne un graphique cyclique qui contient toutes les informations que vous recherchez - et en fait c'est vraiment la contiguïté dans le graphique double.
whuber
@julien, merci - c'est une idée de mise en œuvre décente; Je vais l'essayer. Mais d'abord ... je cherche un mot ou une expression pour décrire ce type de relation.
andytilia
@whuber, merci pour le conseil. Je n'ai jamais rencontré DCEL auparavant. Il semble que B soit le demi-bord "suivant" du demi-bord orienté vers le nord de A. Hm: alors si je veux aller dans le sens antihoraire, je considère le demi-bord de A. orienté au sud. est impliqué par le nœud commun. Je me demande si cela fonctionnera lorsque B n'est pas une limite de face (c'est-à-dire une route sans issue). Je vais approfondir la question.
andytilia
@julien, je relis ton commentaire. Je peux voir maintenant que vous me donnez aussi une formulation suggérée. :-) Peut-être pourrais-je utiliser "ordonné par direction" pour décrire la relation. Je dois jouer un peu avec.
andytilia

Réponses:

1

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.

katahdin
la source
Merci! J'aime le terme «adjacent à rotation». Il suffit de l'étendre, comme vous le dites, avec la convention de classement autour d'un sommet. Dans mon cas, je dois définir cette convention au cas par cas, je vais donc travailler sur le codage de quelque chose comme isRotationallyAdjacentTo (A, B, Direction) en utilisant une permutation comme vous le suggérez. Ou, dans le cas ci-dessus, "A est adjacent en rotation dans le sens horaire à B, et A n'est pas adjacent en rotation dans le sens horaire à C".
andytilia
Soit dit en passant, je n'avais pas encore examiné le calcul des connexions régionales. Bien que ce ne soit pas tout à fait ce qui résout ce problème (comme vous le mentionnez), il est néanmoins intéressant. Pouvez-vous m'indiquer les «œuvres ultérieures» que vous avez en tête de Randell, Cui et Cohn? (hm: les personnages de RC&C ont créé un framework appelé RCC)
andytilia
4

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 .

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

Ragi Yaser Burhum
la source
Merci beaucoup d'avoir fait la distinction claire entre deux types de graphiques. Pensez-vous que c'est une distinction juste de dire que les graphiques de routage contiennent généralement des informations sur les bords et / ou les nœuds, alors que la topologie géospatiale n'a jamais besoin d'être attribuée sur les bords et les nœuds (elle est basée uniquement sur les relations spatiales entre les objets)? Je suppose que mon problème s'inscrit solidement dans le domaine de la topologie géospatiale: la relation entre les bords A et B existe indépendamment de toute attribution sur les bords. Mais je manque encore une manière succincte de nommer cette relation ...
andytilia
Je pense qu'il est trop fort d'un énoncé de dire que "la topologie géospatiale n'a jamais besoin d'être attribuée sur les bords et les nœuds", c'est vraiment au cas par cas. J'ai vu des graphiques de topologie qui contiennent une attribution partagée entre les entités qui ont ce nœud. Les exemples sont les valeurs Z ou Température. Je dirais simplement dire juste l'appeler nœud et faire la distinction entre les nœuds connectés si nécessaire, mais bien sûr, je n'ai pas assez de contexte sur le problème global que vous essayez de résoudre.
Ragi Yaser Burhum
Ah, à droite, merci: une représentation graphique plane de deux routes traversant un pont. Il pourrait y avoir un nœud avec quatre arêtes, mais toutes les arêtes ne sont pas connectées les unes aux autres. Le nœud doit donc contenir des informations sur les niveaux de franchissement, afin de différencier cette situation d'un croisement à niveau.
andytilia
1
Exactement :). C'est pourquoi je mentionne les jonctions. Je pensais à ce cas. Une façon de le faire est de représenter la jonction comme un "nœud maître" avec les entrées FROM-TO. Des situations de passage supérieur / inférieur se produisent tout le temps. Pire encore, dans les cas comme le Bay Bridge ou à Chicago, où vous avez des bords qui correspondent dans l'espace 2D (ils sont effectivement les uns au-dessus des autres) avec un ensemble de bords qui coule dans un sens, tandis que l'autre ensemble coule dans l'autre sens.
Ragi Yaser Burhum