algorithm for block generation from nodes and relationships

Question

I have list of nodes and lines between them, it looks like this:

What I need is to generate blocks, in this case it would be like this: block1:1,2,14,11 block2:2,13,12,14 block3:2,3,4,5,6,12,13 block4:6,7,12 etc...

Doeas anybody have any idea how to create algorithm for this? thx

Answer 1

You could first sort the edges for each node into clockwise order. (e.g. sort based on the key atan2(dy,dx) where dx,dy is the vector along the edge.)

Then with each edge (and both directions along the edge) as a starting point, follow the edges anti-clockwise around the blocks.

To follow anti-clockwise you find the incoming edge in the sorted list for the destination node, and exit along the next edge in the list.

For example, if you started with the edge 11->14, then when you reach the node 14 you would know to take the edge 14->2 next (because the edges for node 14 would be in the clockwise order 14->12, 14->11, 14->2). When you reach the starting node you have identified a block.

You can mark edges as used when you follow them to avoid generating the same block twice. (Skip starting edges if they have already been marked as used in that direction.)

This would also generate a block 0 consisting of the background region.

Answer 2

It seems to me that you are trying to generate the dual of a planar graph.

http://en.wikipedia.org/wiki/Dual_graph

Might be a good place to start.