算法：从邻接表到可视化图
我正在用java编写一个类似Risk的棋盘游戏。一个功能是玩家可以设计自己的地图并将其存储在文本文件中。该文本文件列出了世界地图中的所有领土（==国家），然后是它们的直接邻居。然后，游戏扫描该文件并创建领土及其相应邻接列表的集合。
下一步是将这个图转换成图形表示。这意味着我想用矩形或其他简单的形状来表示每个区域。我还不想讨论领土之间复杂、尖锐的边界。所以基本上这些领土看起来就像一些具有水平和垂直边界的非洲或北美国家。
现在我的问题是：虽然很容易可视化一个图形，其中边界由它们之间绘制的边表示，但我发现很难将区域（==顶点）直接彼此相邻放置。换句话说，这些领土应该相互“接触”，就像在现实世界中一样。
尤其困难的是，因为有 4 个或更多领土彼此接壤的地方（考虑美国的四个角落，包括亚利桑那州、科罗拉多州、新墨西哥州和犹他州）。
现在我想知道是否有人尝试过做类似的事情，或者是否存在处理这个问题的现有算法。我将不胜感激任何帮助和创造性的投入。谢谢！
I'm writing a Risk-like board game in java. A feature is that players can design their own maps which they store in a text file. The text file lists all territories (== countries) in the world map followed by their direct neighbors. The game then scans the file and creates a collection of the territories with their corresponding adjacency lists.
The next step would be to translate this graph into a graphical representation. That means I want to represent each territory by a rectangle or some other simple shape. I don't want to go into complex, edgy borders between territories yet. So basically the territories will look like some African or North American nations with horizontal and vertical borders.
Now my problem is: While it would be easy to visualize a graph where the borders are represented by drawn edges between them, I find it difficult to place the territories (== vertices) directly adjacent to each other. In other words the territories should "touch" each other, like in the real world.
In particular, it is difficult because of such places where 4 or more territories border with each other (Consider Four Corners in USA with Arizona, Colorado, New Mexico, and Utah).
Now I was wondering if anybody ever tried to do something similar or if there are even existing algorithms dealing with this problem. I would appreciate any help and creative input. Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您可以使用像 graphviz 这样的图形布局工具来获得图形的平面投影，那么您可以考虑计算图形上点的 voronoi 图，然后您可以扭曲该图以使事情在视觉上更加有趣。 （您可能还需要注意，以确保在计算 voronoi 图时不会最终更改邻接属性，因为它取决于点的相对间距。您可能还需要检测必须插入“海洋”单元格才能使两个区域不相邻。）
If you can use a graph layout tool like graphviz to get a planar projection of your graph, then you can look into computing the voronoi diagram of the points on your graph, which you could then distort to make things more visually interesting. (You may also need to watch out to make sure that you don't end up changing the adjacency properties when you compute the voronoi diagram, since it depends on the relative spacing of the points. You will probably also have to detect places where an "ocean" cell will have to be inserted in order to make two territories non-adjacent.)
GMap 正是我想要的。他们结合了多种技术，包括 Voronoi 图（这里有一篇关于该算法的论文）。现在我只需要弄清楚如何获得它......
GMap is exactly what I want. They're combining a variety of techniques, including Voronoi diagrams (here's a paper on the algorithm). Now I just have to figure out how to get it...