逻辑将策略性地将项目放置在具有最小重叠连接的容器中
ke3*_*pup 10 javascript java algorithm layout
这更像是一个算法问题.我有一个页面,使用javaScript通过绘制从源到目标的箭头连接显示项目和项目与其他项目的关系(想想jsPlumb).每个项目可以有0个或更多连接.我面临的挑战是以最佳方式战略性地将div /圈放置在容器中.
- 最佳:最少连接数(连接两个圆圈的箭头)重叠
可视示例:下图是未经优化的显示版本,已将圆圈随机放置在容器内.
请注意,在上图中,连接(箭头)重叠的数量不必要地高.下图是一个优化的解决方案,在这个小例子中,圆圈位于更好的位置,导致连接没有重叠:
放置物品的容器尺寸为1020x800.存在大量圆圈的地方总会有重叠,因此我们的想法是尽量减少连接重叠的数量.我希望能够做到这一点的例子,因为我发现阅读算法文章有点令人生畏:(.
方法1
用于布局图的一类非常好的算法是基于仿真的算法.在这些算法中,您可以将图形建模为具有物理属性的物理对象.
在这种情况下,想象图形的节点是相互排斥的球,而边缘是弹簧或橡胶,将图形保持在一起.节点彼此越接近,例如它们的距离的倒数平方,排斥力越强,并且每个弹簧的张力与其长度成比例.排斥力将使节点尽可能远离其他节点,并且图形将解开.当然,你必须稍微试验系数才能获得最佳效果(但我保证 - 这很有趣).
这种方法的主要优点是:
- 易于编码 - 嵌套循环计算每个节点 - 节点对之间的力并更新节点位置
- 适用于各种平面或非平面图形
- 实验很有趣
- 如果你让它互动,例如允许用户用鼠标移动节点 - 它吸引人们,每个人都想"玩图表"
这种方法的缺点是:
- 它可能会陷入局部能量最低限度(摇动或帮助手动帮助)
- 它不是非常快(但可以做一个很好的动画)
类似的方法可用于布局/解开结.
示例代码
<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>
您可以在此处查看此代码的工作原理.刷新页面以获取不同的图形.当然,有时它找不到全局最小值并且有更多的交叉边缘 - 所以如果结果不满足你,你可以添加随机抖动.
方法2
这个问题类似于PCB设计中的布线问题.如果您对方法1提供的简单易用的解决方案不满意,您可以使用自动布线方法改进解决方案.例如,您可以将节点放在网格上,然后使用A*算法查找连接它们的最短路径.
- 使用方法1找到次优的初始解决方案(可选).
- 删除所有边缘.将节点放在网格上(将其坐标向上舍入).网格必须具有足够的分辨率,以便没有两个节点重叠.
- 按升序近似长度对边缘进行排序(使用欧几里得或曼哈顿度量).
- 对于每个边缘使用A*算法来查找连接节点的最短路径.作为成本函数,不仅使用距离源节点的距离,而且还为步进到先前路由的任何边缘已经采用的任何网格点上添加足够大的代价.
- 将上一步中找到的路径上的网格点标记为"已拍摄",因此所有下一条边将有利于不踩踏/与此路径相交的路径.
上面的算法是一种贪婪的启发式算法,遗憾的是它不能保证最优解,因为结果取决于路由边缘的顺序.您可以通过移除跨越另一条边的随机边缘并重新路由它来进一步改进解决方案.
步骤1.是可选的,使图形布局更规则,并使平均连接距离变小,但不应影响交叉点的数量(如果网格具有足够的分辨率).