8
\$\begingroup\$

I want to draw a 2d polygon map based on data provided by another source to ease analysing actions on the map. The data has the following format:

1 ['2', '4', '5', '7', '17', '10']
2 ['1', '3', '4']
3 ['2', '11', '4']
4 ['1', '2', '3', '11', '13', '18', '5']
5 ['1', '4', '18', '17']
6 ['7', '8']
...

The first number is the ID of a node, the following list contains the IDs of its neighbours. As a node's number of neighbours differs I need to draw a polygon map.

So I tried to use Voronoi polygons for the map representation. The problem is: How can I determine the points to satisfy all neighbourhood relations? I guess my first try is more or less an error in my try and error cycle. I used the sfdp tool of graphviz to get the point positions of the graph:

sample graph representation using sfdp

Using the positions of the points resulted in the following map representation:

sample map using voronoi diagram

The problem of this approach is that for example nodes 4 and 1 are neighbours but in the Voronoi diagram they aren't because of the position of the nodes. So for me this approach failed.

Googling, I found a lot of tutorials generating maps with polygons or tiles but I haven't found out yet how I can create a map for my given data. I guess there is an approach using (multiple) hexagons/triangles/squares or a mixture to achieve what I need but I don't know what I shall search for.

Is there a keyword or an algorithm which can help me here?

Update/Result: For completeness: This is my result after using the suggestions of the accepted answer: result

\$\endgroup\$
  • \$\begingroup\$ From the data given, multiple maps could be created, especially with points 12 and 9 which only have 1 relationship. Is this a particular problem? \$\endgroup\$ – lewisjb May 26 '15 at 0:04
  • \$\begingroup\$ @Pyro: no this is not a problem. Its just used for analysis. \$\endgroup\$ – maggie May 26 '15 at 12:13
  • \$\begingroup\$ you will find algorithm for this dual problem listed as Delaunay triangulation and Voronoi diagrams. \$\endgroup\$ – tinyfiledialogs May 26 '15 at 17:26
12
\$\begingroup\$

What you want is to produce a dual graph; that is, a graph produced by converting faces to vertices, and connecting them based on adjacent faces in the original graph. Example:

dual graph

The problem, as you can see, is that if you want to keep the same layout of the graph, you'll get some really curvy edges in the dual graph. Also, you'll often end up with a multigraph - a graph where some vertices have multiple edges between them. It is guaranteed to be planar though, so that's something.

To use your example, we can produce the dual graph in the following steps:

Step 1: For each face in the original graph, create a vertex

centroids and outer ring

Note that we create an outer "ring" to represent the outermost "vertex" - this is so we can have a nicer looking graph at the end, without the crazy curvy edges.

Step 2: For each edge in the original graph, connect the two face-vertices with an edge

Also, you're going to have to do something about these edges not overlapping each other. The gap between 3 and 12 is especially problematic. These new edges may need to be bendy to make this possible. It's what you get for having a concave graph.

edges

Step 3: Play Risk

coloured graph

\$\endgroup\$
  • \$\begingroup\$ Thanks for the hint. I started a similar approach before my voronoi thing but i didnt bring it to the end. I will do this and post my results then. \$\endgroup\$ – maggie May 26 '15 at 6:58
  • \$\begingroup\$ This is interesting, also, if it helps you out, try to seek some information on voronoi-delaunay duality. This is a good start to at least understanding it: scicomp.stackexchange.com/questions/771/… \$\endgroup\$ – Gustavo Maciel May 26 '15 at 8:24
  • 1
    \$\begingroup\$ One additional question: Which approach would you use if you dont have the help of sfdp? Is there a general approach to create a suitable graph representation to get the needed node positions? \$\endgroup\$ – maggie May 26 '15 at 10:34
  • \$\begingroup\$ @maggie you'll want something that performs planar graph layouts. It's not a trivial problem, and I can't recommend a specific package, but there are options here and here. \$\endgroup\$ – congusbongus May 26 '15 at 23:21
1
\$\begingroup\$

If the first image, where each point is a small square with certain color, is what you are searching for, you need to build the Delaunay's triangulation.

\$\endgroup\$
  • 1
    \$\begingroup\$ This could use a little more content to make the answer a little more concise. \$\endgroup\$ – Tom 'Blue' Piddock May 26 '15 at 11:12

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.