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:
Using the positions of the points resulted in the following map representation:
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: