如何从Java中的字符串列表中绘制游戏世界地图的平面图

Question

基本上，我有一个游戏，它有一个由116个领土组成的大地图。每个区域都有一个名称、一些其他属性，还有一个与其邻居名称相关的String[]。并不是每个地区都相互连接(我认为一个地区至少有1个连接，最多有9个连接(。

因此，像绘制图一样绘制领土应该会得到一个平面图。我试着使用JUNG库(正如本网站和其他网站上所建议的那样(来做到这一点，但他们的每一种布局算法都只会产生一个有很多交叉边的图，这正是我想要避免的。在我的代码下面(Territory类又一次有一个name属性和一个邻居名称的String[]。传递到方法中的map有Territory的名称作为关键字(。

所以我的问题是：有没有一种布局算法可以用来从领土地图上绘制平面图？我应该用的另一个图书馆？我可以遵循的教程？提前感谢各位！

public static void drawMap(Map<String, Territory> allTerritories) {
// TODO Auto-generated constructor stub
DirectedSparseGraph<String, String> g = new DirectedSparseGraph<>();
Game game = new Game();
int counter = 0;
for (Territory t : allTerritories.values()) {
g.addVertex(t.getName() + "(" + game.getID(t.getColor()) + ")");
for (String s : t.getNeighbours()) {
Territory neighbour = allTerritories.get(s);
g.addEdge("Edge" + counter, t.getName() + "(" + game.getID(t.getColor()) + ")",
s + "(" + game.getID(neighbour.getColor()) + ")");
counter++;
}
}
Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
int width = screenSize.width;
int height = screenSize.height;
// KKLayout does a sort of good job
CircleLayout<String, String> layout = new CircleLayout<String, String>(g);
VisualizationImageServer<String, String> vv = new VisualizationImageServer<String, String>(layout,
new Dimension(width, height));
Function<String, String> transformer = new Function<String, String>() {
@Override
public String apply(String arg0) {
if (arg0.contains("-1")) {
String noNumber = arg0.replace(arg0.substring(arg0.length() - 4), "");
return noNumber;
} else {
String noNumber = arg0.replace(arg0.substring(arg0.length() - 3), "");
return noNumber;
}
}
};
vv.getRenderContext().setVertexLabelTransformer((Function<? super String, String>) transformer);
vv.getRenderer().setVertexRenderer(new MyRenderer());
// The following code adds capability for mouse picking of
// vertices/edges. Vertices can even be moved!
JFrame frame = new JFrame();
frame.getContentPane().add(vv);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.pack();
frame.setVisible(true);
}'

(使用JUNG库，我的进口清单：

import edu.uci.ics.jung.algorithms.layout.CircleLayout;
import edu.uci.ics.jung.algorithms.layout.ISOMLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.visualization.RenderContext;
import edu.uci.ics.jung.visualization.VisualizationImageServer;
import edu.uci.ics.jung.visualization.renderers.Renderer;
import edu.uci.ics.jung.visualization.transform.shape.GraphicsDecorator;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Rectangle;
import java.awt.Shape;
import java.awt.Toolkit;
import java.awt.geom.Point2D;
import java.util.Map;
import javax.swing.JFrame;

game.getID((方法是我在另一个类中编写的一个方法，用于将颜色(与区域相关，可以是灰色、橙色、品红色或蓝色(转换为整数。顶点也应该是那种颜色，我的代码实际上做到了！

我尝试使用以下布局：KKLayout、FRLayout、SpringLayout、ISOMLLayout、CircleLayout。

Answer 1

这里有两种情况：

1. 您有115个领土的实际(地理(地图，或者
2. 你只知道它们之间的边界关系(也就是说，你所知道的只是哪个领土与其他领土接壤(

在情况1中，可以根据区域的位置进行布局：为每个区域选择一个点，并使用该位置创建一个节点。可以使用StaticLayout指定已知节点位置。WorldMapGraphDemo中有一个这样的例子。

在情况2中，根据图形是如何生成的，您可能实际上并不确定它是平面的；你还没有说明你是怎么知道的。如果您不确定，可以使用以下算法之一进行测试：https://en.wikipedia.org/wiki/Planarity_testing

如果你发现这个图真的是平面的，而JUNG布局算法对你没有帮助，我没有任何即时的建议。避免图形布局中的边交叉通常是一个NP难题，并且这些算法都没有试图直接解决它。