逻辑从战略上与最小重叠连接的容器放置物品容器、最小、逻辑、物品
这更多的是一个算法问题。我有一个网页，其中通过绘制一条从源箭头连接到目标（想想jsPlumb）使用JavaScript显示项目和项目关系到其他项目。每个项目可以有0个或更多的连接。我有挑战是战略上放置的div /圈与容器中的最优化方法。
This is more of a algorithmic question. I have a page which using javaScript displays items and items relationship to other item by drawing arrow connection from source to target (think jsPlumb). Each item can have 0 or more connections. The challenge i have is to place the divs/circles strategically with the container in the most optimum way .
最佳：连接（箭头连接两个圆）数量最少的重叠的视觉实施例：以下是图像显示器的一个未优化的版本，具有放置在圆内随机的容器。
Visual Example: Below picture is an unoptimised version of the display, having placed the circles randomly within the container .
请注意，在上面的图片连接（箭头）重叠的数量是不必要的高。下面的图片是放在更好的位置圈造成了这个小例子连接没有重叠一是优化解决方案：
Notice in above picture the number of connection (arrows) overlap is unnecessarily high. Below picture is one optimized solution with circles placed in better position resulting in no overlap of connection in this small example:
容器的大小，其中数据项都放置是1020x800。其中大量圆存在总是会有重叠这样的想法是为了减少连接的重叠量。我希望，例如，如何能够做到这一点，因为我觉得阅读文章的算法略有艰巨：（
The size of container in which items are placed is 1020x800. where large number of circles exist there will always be overlaps so the idea is to minimize the amount of connection overlap. I am hoping for example of how this could be done as i find reading algorithm articles slightly daunting :(.
推荐答案
一个pretty的漂亮类的布局图的算法是基于模拟的算法。在这些算法中，你的模型图，就好像它是与物理特性的物理对象。
Approach 1
A pretty nice class of algorithms for laying out graphs are simulation-based algorithms. In those algorithms, you model your graph as if it was a physical object with physical properties.
在这种情况下，可以想象的曲线图的节点是相互排斥，而边缘是弹簧或该保持图形一起橡胶球。的排斥力是强越接近节点彼此，例如它们之间的距离的平方成反比，每个弹簧的张力正比于它的长度。的排斥力将引起节点以获得尽可能从其他节点和图形将解开。当然，你必须尝试系数小，以获得最佳效果（但我保证 - 这是一个很大的乐趣）。
In this case imagine the nodes of the graph are balls that repel each other, while the edges are springs or rubbers that keep the graph together. The repelling force is stronger the closer the nodes are to each other e.g. inverse square of their distance, and the tension force of each spring is proportional to its length. The repelling force will cause the nodes to get as far as possible from the other nodes and the graph will untie. Of course, you'll have to experiment with coefficients a little to get the best results (but I guarantee - it is a lot of fun).
该方法的主要优点是：
易于code - 嵌套循环计算每一个节点，节点对和更新节点位置的力 适用于所有类型的图形平面或非平面 乐呵呵地试验 如果你把它的互动，例如允许用户移动节点使用鼠标 - 它吸引的人，每个人都希望用图形玩 easy to code - nested loops calculating force between every node-node pair and updating node position works for all kinds of graphs either planar or nonplanar lots of fun to experiment if you make it interactive, e.g. allow user to move nodes with a mouse - it attracts people and everyone wants to "play with the graph"这种方法的缺点是：
可以停留在一个局部的能量最低（摇动或手动帮助帮助） 在它不是非常快（但可以做一个漂亮的动画）有一个类似的方法可以用来布局/解开心结。
A similar method can be used to layout/untie knots.
<html>
<head>
</head>
<body>
<canvas id="canvas" width="800" height="600" style="border:1px solid black"/>
<script>
window.requestAnimFrame = (function(callback) {
return window.requestAnimationFrame || window.webkitRequestAnimationFrame ||
window.mozRequestAnimationFrame || window.oRequestAnimationFrame || window.msRequestAnimationFrame ||
function(callback) {
window.setTimeout(callback, 1000 / 120);
};
})();
var width = 800;
var height = 600;
function addEdge(nodeA, nodeB) {
if (nodeA.edges.indexOf(nodeB) == -1) {
nodeA.edges[nodeA.edges.length] = nodeB;
nodeB.edges[nodeB.edges.length] = nodeA;
}
}
function createGraph(count) {
var graph = new Array();
for (var i = 0; i < count; i++) {
var node = new Object();
node.x = Math.floor((Math.random() * width));
node.y = Math.floor((Math.random() * height));
node.edges = new Array();
graph[i] = node;
if (i > 0)
addEdge(graph[i], graph[i - 1]);
}
for (var i = 0; i < count / 2; i++) {
var a = Math.floor((Math.random() * count));
var b = Math.floor((Math.random() * count));
addEdge(graph[a], graph[b]);
}
return graph;
}
function drawEdges(ctx, node) {
for (var i = 0; i < node.edges.length; i++) {
var otherNode = node.edges[i];
ctx.beginPath();
ctx.moveTo(node.x, node.y);
ctx.lineTo(otherNode.x, otherNode.y);
ctx.stroke();
}
}
function drawNode(ctx, node) {
ctx.beginPath();
ctx.arc(node.x, node.y, 30, 0, 2 * Math.PI, false);
ctx.fillStyle = 'green';
ctx.fill();
ctx.lineWidth = 5;
ctx.strokeStyle = '#003300';
ctx.stroke();
}
function drawGraph(ctx, graph) {
ctx.fillStyle = 'white';
ctx.fillRect(0, 0, width, height);
for (var i = 0; i < graph.length; i++)
drawEdges(ctx, graph[i]);
for (var i = 0; i < graph.length; i++)
drawNode(ctx, graph[i]);
}
function distanceSqr(dx, dy) {
return dx * dx + dy * dy;
}
function force(nodeA, nodeB, distanceFn) {
var dx = nodeA.x - nodeB.x;
var dy = nodeA.y - nodeB.y;
var angle = Math.atan2(dy, dx);
var ds = distanceFn(distanceSqr(dx, dy));
return { x: Math.cos(angle) * ds, y: Math.sin(angle) * ds };
}
function repelForce(distanceSqr) {
return 5000.0 / distanceSqr;
}
function attractForce(distanceSqr) {
return -distanceSqr / 20000.0;
}
function gravityForce(distanceSqr) {
return -Math.sqrt(distanceSqr) / 1000.0;
}
function calculateForces(graph) {
var forces = new Array();
for (var i = 0; i < graph.length; i++) {
forces[i] = { x: 0.0, y: 0.0 };
// repelling between nodes:
for (var j = 0; j < graph.length; j++) {
if (i == j)
continue;
var f = force(graph[i], graph[j], repelForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
// attraction between connected nodes:
for (var j = 0; j < graph[i].edges.length; j++) {
var f = force(graph[i], graph[i].edges[j], attractForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
// gravity:
var center = { x: 400, y: 300 };
var f = force(graph[i], center, gravityForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
return forces;
}
function updateNodePositions(graph) {
var forces = calculateForces(graph);
for (var i = 0; i < graph.length; i++) {
graph[i].x += forces[i].x;
graph[i].y += forces[i].y;
}
}
function animate(graph) {
var ctx = document.getElementById("canvas").getContext("2d");
for (var i = 0; i < 20; i++)
updateNodePositions(graph);
drawGraph(ctx, graph);
requestAnimFrame(function() { animate(graph); });
}
animate(createGraph(8));
</script>
</body>
</html>
您可以看到这是如何code工作这里 。刷新页面以获得不同的图形。 当然，有时它没有找到全球最低，并有更多的交叉边缘比它是可能的 - 所以，如果结果不令你满意，你可以添加任意晃动
You can see how this code works here. Refresh the page to get different graphs. Of course, sometimes it doesn't find the global minimum and there are more crossing edges than it is possible - so if the results don't satisfy you, you can add random shaking.
这个问题类似于印刷电路板的设计布线问题。如果你不满意方法1提供的简单易用的解决方案，可以提高该解决方案通过使用自动布线方法。例如。你可以把一个网格的节点，然后用A *算法来寻找连接它们的最短路径。
This problem is similar to routing problem in design of PCBs. If you're not satisfied with the simple and easy solution provided by Approach 1, you can improve the solution by using autorouting methods. E.g. you can put your nodes on a grid and then use A* algorithm to find the shortest paths connecting them.
使用方法1找到一个次优的初步解决方案（可选）。 删除所有边缘。放置在一个网格节点（圆了自己的坐标）。电网必须具有足够的分辨率，以便没有两个节点重叠。 按升序边缘近似长度（使用欧几里德或曼哈顿的度量）。 对于每一个边缘用A *算法找到连接节点的最短路线。作为一个成本函数的使用不仅可以从源节点的距离，同时也补充足够大的惩罚踏上已经采取的任何优势，任何网格点排到previously。 标记的网格点在previous一步发现为取，那么后面所有的边将有利于不踩着/交叉与此路径路径的路径上。上面的算法是一种启发式贪婪和不幸的是它不能保证最优解，因为该结果取决于路由的边缘的数量级上。您可以进一步完善的解决方案通过removng随机边缘跨越另一边，并重新路由它。
The above algorithm is a greedy heuristic and unfortunately it doesn't guarantee the optimal solution, because the result depends on the order of routing the edges. You can further improve the solution by removng a random edge that crosses another edge and reroute it.
步骤1.是可选使图形布局更规则，并进行平均连接距离小，但它不应该影响交叉点的数目（如果该网格具有足够的分辨率）。
Step 1. is optional to make the graph layout more regular and make the average connection distance small, however it should not affect the number of intersections (if the grid has enough resolution).
上一篇：图同构同构
