将项目战略性地放置在具有最小重叠连接的容器中的逻辑 [英] Logic to strategically place items in a container with minimum overlapping connections
问题描述
这更像是一个算法问题.我有一个页面，它使用 javaScript 通过绘制从源到目标的箭头连接来显示项目和项目与其他项目的关系(想想 jsPlumb).每个项目可以有 0 个或多个连接.我面临的挑战是以最优化的方式将 div/circles 与容器战略性地放置在一起.
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 .
- optimum : 最少数量的连接(连接两个圆圈的箭头)重叠
视觉示例:下图是未优化版本的显示，将圆圈随机放置在容器内.
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 :(.
推荐答案
方法一
一类非常好的用于布置图形的算法是基于模拟的算法.在这些算法中，您可以将图形建模为具有物理属性的物理对象.
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).
这种方法的主要优点是:
The main pros of this approach are:
- 易于编码 - 嵌套循环计算每个节点-节点对之间的力并更新节点位置
- 适用于各种平面图或非平面图
- 尝试很多乐趣
- 如果您使它具有交互性，例如允许用户用鼠标移动节点 - 它吸引了人们，每个人都想玩图"
- 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>
您可以在此处查看此代码的工作原理.刷新页面以获取不同的图表.当然，有时它找不到全局最小值，并且交叉边比可能的多 - 所以如果结果不满足您，您可以添加随机抖动.
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.
这个问题类似于PCB设计中的布线问题.如果您对方法 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* 算法找到连接节点的最短路径.作为成本函数，不仅要使用与源节点的距离，还要为步入任何先前路由的边已经采用的任何网格点添加足够大的惩罚.
- 将上一步中找到的路径上的网格点标记为已采用"，因此所有接下来的边都将有利于不踩踏/与此路径相交的路径.
上述算法是一种贪婪的启发式算法，不幸的是它不能保证最优解，因为结果取决于路由边缘的顺序.您可以通过移除与另一条边交叉的随机边并重新路由它来进一步改进解决方案.
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.
Step 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).
这篇关于将项目战略性地放置在具有最小重叠连接的容器中的逻辑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
