Consider this simple situation where three edges connect at a node:

edge relationships

I’d like to write a succinct and clear description of the relationship between A and B in such a way that differentiates it from the relationship between A and C. Something like “when traversing the node in the clockwise direction, A is adjacent? to B, but A is not adjacent? to C.” But it’s not really adjacency.

Said in a different way: imagine you’re standing on the node and you’re facing towards A. You start spinning yourself clockwise. The next edge you’ll come to is B, not C.

Is there a way to describe this relationship between A and B in a more succinct, formal, or correct way than I’ve written above?

It must be directional (one relationship of this type exists in the clockwise direction from A, and another exists in the counter-clockwise direction). And it must scale up to cases where more than three edges are connected at the node. Maybe it has something to do with routing? (I am thinking about this in the context of road networks.)

Two approaches I’ve tried already but haven't gotten far with:

  1. 9IM-like topology references: I’ve looked at the DE-9IM, and even though I'm not a mathematician, I think I can still tell from the diagrams and terms that it doesn’t cover this type of relationship. Neither do I find it yet in the topology descriptions at the ESRI help or Oracle help. (Maybe there's something there but I'm just not finding it yet!)

  2. Faces: I’ve played around with the fact that the face on the “north” side of A might also bounded also be by B, but not C. However, as you can see in the diagram here, that’s not always true. Imagine my diagram is an extract from a road network where A and C are arterial roads and B is a short dead-end road.

I suspect there may not be a single term for what I’m trying to say; at a minimum I’d like to be able to describe such a relationship in a simpler way than I’ve done above. This is a platform-independent question. Right now, I’m just looking for the right words. Later I will try to implement the concept in python (pyqgis or arcpy) on a shapefile, so any answers with that end point in mind will be particularly interesting, but not necessary.

  • Why do not you attach to each node the list of edges connected to it ordered by direction? – julien Oct 23 '12 at 14:37
  • 1
    It sounds like you're looking for a DCEL. Notice that when you dualize a planar graph, the faces become nodes. In the illustration there are pieces of three faces alpha, beta, and gamma, with edge A separating beta from gamma, edge B separating gamma from alpha, and edge C separating alpha from beta. That yields a cyclic graph which contains all the information you are looking for--and indeed it really is adjacency in the dual graph. – whuber Oct 23 '12 at 15:33
  • @julien, thanks -- that's a decent implementation idea; I'll try it out. But first... I'm looking for a word or phrase to describe this type of relationship. – andytilia Oct 23 '12 at 15:33
  • @whuber, thanks for the tip. I haven't encountered DCEL before. It looks like B is the "next" half-edge of the northfacing, westbound half-edge of A. Hm: then if I want to go counterclockwise, then I consider the south-facing half-edge of A. And "westbound" is implied by the common node. I wonder if it will work when B isn't a face boundary (ie. dead-end road). I'll look into it further. – andytilia Oct 23 '12 at 15:42
  • @julien, I'm reading your comment again. I can see now you're giving me suggested phrasing too. :-) Maybe I could use "ordered by direction" to describe the relationship. Gotta play around with it a bit. – andytilia Oct 23 '12 at 15:44

I know that I'm a bit late to the party here, but this is quite interesting stuff, and I hope that my answer can be of some use.

What you are asking about is a qualitative relation; the oft ignored sibling of the quantitative relation. Qualitative reasoning comes up quite often in geospatial science. Example queries include: Which parcels are adjacent to this one? What features are inside the overlap of region A and region B? Which regions are concave? Which road is on the left? The relations being: adjacent to, inside of, concave, and left of. Qualitative queries often get overlooked or undervalued when compared to quantitative questions like which is bigger, shorter, or greater in number.

A qualitative relation that takes two inputs is called a binary relation. There are two common notations for this: - isLeftOf(A,B) This is prefix notation. - A isLeftOf B This is infix notation.

In the examples above there was also a unary relation: isConcave. This relation relates a region to itself and would return a boolean value.

All of Egenhofer's spatial predicates in the 9-intersection model (referenced in the 9EIM) are binary relations between two regions. You may also be interested in Randell, Cui and Cohn's RCC (http://en.wikipedia.org/wiki/Region_connection_calculus). The qualitative (topological) relations given in this area of study relate regions to regions, and later works relate lines to regions and lines to lines. However, this is not quite what you are looking for.

OK, sorry for the digression, but hopefully that helps with the terminology aspect of your question.

@whuber was right on track with suggesting the doubly connected edge list (DCEL). This is a close relative of combinatorial maps, often used under the covers in CAD systems, and winged edges. The winged edge (http://en.wikipedia.org/wiki/Winged_edge) concept is how the well-known-text standard defines a hole in a polygon (http://en.wikipedia.org/wiki/Well-known_text#Geometric_objects). Note on the polygon that the order of the outer points is counter-clockwise, and clockwise for the inner points. A little fairy-person walking along the boundary in this order would always see the inside of the region on her left.

With combinatorial maps and DCEL the key point is that these objects are defined on a surface that is orientable. We don't need to get into the math formalities - the idea is pretty simple: if you can define direction on the surface, as you can with any spatial reference system in a GIS, then you have an orientable surface. So, if you can define a direction, then you can define a directional ordering around any point on the surface. With directional ordering you can define isLeftOf(A,B), isRotationallyAdjacentTo(A,B) and so on.

Defining ordering around a vertex in a graph embedded on a surface requires two assignments: 1) assigning labels to edge end points and 2) assigning a convention for order around a vertex. If element order in an array (e.g. [A,B,C] in your picture) is clockwise, then we can tell which edge is to the left of B.

In your example, each element is adjacent to the others. That fact is also visible in the array because the array actually represents a permutation, i.e., the order matters, but which element is first doesn't. So [A,B,C] is equivalent to [C,A,B]. In other words, the array wraps around making the last element adjacent to the first.

  • Thanks! I like the term “Rotationally Adjacent”. It just needs to be extended, like you say, with the convention for ordering around a vertex. In my case I need to define that convention case by case.So I’m going to work on coding something like isRotationallyAdjacentTo(A,B,Direction) using a permutation like you suggest. Or in terms of the case above “A is clockwise-rotationally adjacent to B, and A is not clockwise-rotationally adjacent to C”. – andytilia Dec 13 '12 at 19:54
  • By the way, I hadn’t looked into Region Connection Calculus yet. While it’s not quite what solves this problem (as you mention), it is interesting nonetheless. Can you point me to the “later works” you have in mind by Randell, Cui and Cohn? (hm: the RC&C characters created a framework called RCC) – andytilia Dec 13 '12 at 19:55

When you look at topology and connectivity graphs that you get from vendors like Teleatlas, Navteq, ESRI, etc, you will start seeing a pattern (of course everyone has their own "special" way of doing things).

Personally, even though 1) Geospatial Topology and 2) Routing Graphs are just Graphs and can be generalized to be represented in the same data structure, I try to avoid that as much as possible.

I try to make a distinction in my head.

  • When I say "Geospatial Topology" (1) I mean a graph structure for representing geometric relationships of the features (e.g what is left of edge A, what face is formed by edges [A,B,C], what is contained by face B, etc).
  • When I say "Routing Graph" (2), I mean a graph structure for solving routing problems (e.g. shortest path for getting from A->B with [X] restrictions/conditions)

They are just graphs, and they belong to the breadth of science, but there is a clear advantage as not generalizing as the same thing. They serve different purposes, and it is much easier to optimize and apply operations when they are specialized to that particular purpose.

ESRI does this. They have a graph structure for Geospatial Topology (TopologyGraph) and a different Graph structure for Routing Problems(network dataset). Heck, they even have an older Graph Structure - Geometric Networks - that serves well for flow problems in utility networks.

Arguably, in the PostgreSQL/PostGIS world, we also encounter this. There is a data structure for routing and another one for geospatial topology.

In your question, you are talking about graphs and navigating them clockwise and counter-clockwise, as well as faces, which make me thing that you want a specialized structure for (1).

For "Geospatial Topology", I think a nice way of representing this kind of Topology is the way the UK Hydrographic Office does in their S57 Topology Description of Full Topology.

UKHO Full Topology

Very similar to what all the main implementations do.

Now, if what you are looking for is routing, then the graph becomes different based on whether you need single direction or bi-directional connectivity. At the end, it boils down to:

  • Having FROM nodes connected to TO nodes which create Edges
  • The Edges have attributes for left and right side (e.g. address ranges).
  • The Junctions (i.e the nodes where the edges connect) can have a set of restrictions. So you basically would have a master junction entry to represent the junction itself, and individual entries with FROM and TO entries for representing the flow restrictions.

Good luck, and let us know how your project turns out.

  • Many thanks for making the clear distinction between two types of graphs. Do you think it’s a fair distinction to say that Routing Graphs generally contain some information on the edges and/or nodes, whereas Geospatial Topology never needs attribution on the edges and nodes (it is based only on the spatial relationships between objects)? I guess my problem fits solidly in the domain of Geospatial Topology: the relationship between Edges A and B exists regardless of any attribution on the edges. But I’m still missing a succinct way to name this relationship... – andytilia Dec 13 '12 at 19:21
  • I think it is too strong of a statement to say that "Geospatial Topology never needs attribution on the edges and nodes", it is really on a case-by-case basis. I have seen Topology Graphs that contain attribution that is shared among features that have that node. Examples are Z or Temperature values. I would say just say just call it node and make the connected node distinction when necessary, but of course, I don't have enough context of the overall problem you are trying to solve. – Ragi Yaser Burhum Dec 13 '12 at 19:56
  • Ah, right, thanks: a planar graph representation of two roads crossing at a bridge. There could be one node with four edges, but not all the edges connect to each other. So the node needs to contain information about crossing levels, to differentiate that situation from an at-grade crossing. – andytilia Dec 13 '12 at 20:04
  • 1
    Exactly :). That is why I mention Junctions. I was thinking about that case. One way of doing it is to represent the junction as a "master node" with the FROM-TO entries. Overpass/underpass situations occur all the time. Even worst are the cases like the Bay Bridge or in Chicago where you have edges that match in 2D space (they are effectively on top of each other) with a set of edges flowing one way, while the other set flows the other way. – Ragi Yaser Burhum Dec 13 '12 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.