11

这更像是一个算法问题。我有一个页面，它使用 javaScript 通过绘制从源到目标的箭头连接来显示项目和项目与其他项目的关系（想想 jsPlumb）。每个项目可以有 0 个或多个连接。我面临的挑战是以最优化的方式将 divs/circles 策略性地放置在容器中。

  • 最佳：最少数量的连接（连接两个圆圈的箭头）重叠

视觉示例：下图是未优化的显示版本，将圆圈随机放置在容器内。

在此处输入图像描述

请注意，在上图中，连接（箭头）重叠的数量不必要地高。下图是一个优化的解决方案，在这个小例子中，圆圈放置在更好的位置，导致连接没有重叠：

在此处输入图像描述

放置物品的容器大小为 1020x800。在存在大量圆圈的情况下，总会有重叠，因此我们的想法是尽量减少连接重叠的数量。我希望例如如何做到这一点，因为我发现阅读算法文章有点令人生畏:(。

4

3 回答 3

8

方法一

用于布局图形的一类非常好的算法是基于模拟的算法。在这些算法中，您将图形建模为具有物理属性的物理对象。

在这种情况下，想象图的节点是相互排斥的球，而边缘是使图保持在一起的弹簧或橡胶。节点之间的距离越近，排斥力越大，例如它们的距离的平方成反比，并且每个弹簧的张力与其长度成正比。排斥力将导致节点尽可能远离其他节点，并且图将解开。当然，您必须对系数进行一些试验才能获得最佳结果（但我保证 - 这很有趣）。

这种方法的主要优点是：

  1. 易于编码 - 嵌套循环计算每个节点-节点对之间的力并更新节点位置
  2. 适用于平面或非平面的各种图形
  3. 很多有趣的实验
  4. 如果您使它具有交互性，例如允许用户用鼠标移动节点 - 它会吸引人们并且每个人都想“玩图形”

这种方法的缺点是：

  1. 它可能会陷入局部能量最小值（摇晃或手动帮助）
  2. 它不是非常快（但可以制作出漂亮的动画）

类似的方法可用于布局/解开结。

示例代码

<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>

您可以在此处查看此代码的工作原理。刷新页面以获取不同的图表。当然，有时它找不到全局最小值，并且交叉边缘比可能的多 - 所以如果结果不满足您，您可以添加随机抖动。

方法二

这个问题类似于PCB设计中的布线问题。如果您对方法 1 提供的简单易用的解决方案不满意，您可以使用自动布线方法来改进解决方案。例如，您可以将节点放在网格上，然后使用 A* 算法找到连接它们的最短路径。

  1. 使用方法 1 找到次优的初始解决方案（可选）。
  2. 去除所有边缘。将节点放在网格上（四舍五入它们的坐标）。网格必须具有足够的分辨率，以便没有两个节点重叠。
  3. 按升序近似长度对边进行排序（使用欧几里得或曼哈顿度量）。
  4. 对于每条边，使用 A* 算法找到连接节点的最短路径。作为成本函数，不仅使用与源节点的距离，而且还为踩到先前路由的任何边缘已经占据的任何网格点添加足够大的惩罚。
  5. 将在上一步中找到的路径上的网格点标记为“已采用”，因此所有下一个边缘都将支持不踩到/与该路径相交的路径。

上述算法是一种贪婪的启发式算法，不幸的是它不能保证最优解，因为结果取决于路由边的顺序。您可以通过删除与另一条边交叉的随机边并重新路由来进一步改进解决方案。

第 1 步是可选的，以使图形布局更规则，并使平均连接距离变小，但它不应该影响交叉点的数量（如果网格有足够的分辨率）。

于 2013-09-19T17:40:57.053 回答
2

对我来说，它看起来像是简单的封闭多边形提取。尝试这个：

  1. 忘记连接方向删除所有冗余连接（双向连接是重复的）

  2. 找到所有闭环

    起点始终是具有超过 2 个连接（或仅具有 1 个）的容器，因此循环遍历未使用的相邻容器，直到返回起点（将此路径设置为已使用）或直到到达端点（仅 1 个连接，也将此路径设置为使用）或直到到达十字路口（连接> 2，也将此路径设置为已使用）。

  3. 重复，直到容器之间没有未使用的行。

在此之后，您将图表分解为不相交的部分。

现在将它们重新连接在一起，因此没有任何连接相交。共享连接在内部，非共享连接在外部。开环（带端点）可以在任何地方。

我希望这有帮助

于 2013-09-16T17:07:13.260 回答
0

我认为基于模拟的算法将是最好的选择，但是，因为您的目标是最小化重叠弧而不是优化节点的分布，您应该在弧之间（而不是节点之间）施加排斥力并将节点用作弹簧.

迭代：

  1. 对于图中的每个弧计算其中心点（平均起点和终点）
  2. 对于每对弧线，在它们的中心之间施加排斥力（弧线的两个极端都会相应地移动）
  3. 对于图中的每个节点，计算其新位置作为连接弧的平均值并更新弧的相关端点

您还可以添加一个收缩阶段，将节点吸引到图形的中间（所有节点的坐标的平均值）。

当达到某个稳定性阈值时停止迭代。

于 2013-09-20T13:54:38.507 回答