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 : Least number of connections (arrows connecting two circles) overlaps

Visual Example: Below picture is an unoptimised version of the display, having placed the circles randomly within the container .

enter image description here

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:

enter image description here

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 :(.

标签： java javascript algorithm layout

3条回答

等我变得足够好

2楼-- · 2019-01-16 11:12

It looks like simple closed polygon extraction to me. try this:

forget about direction of connections remove all redundant connections (bidirectional ones are duplicate)
find all closed loops

start point is always container with more than 2 connections (or just with 1) so loop through unused neighboring containers until get back to the start point (set this path as used) or until reach endpoint (1 connection only, also set this path as used) or until reach crossroad (connections > 2, also set this path as used).
repeat until there are no unused line between containers left.

after this you have your graph decomposed to non intersecting parts.

now join them back together so no connection is intersecting. Shared connections are inside and non shared connections are on the outside. Open loop (with endpoints) can be anywhere.

I hope this helps

0人赞添加讨论(0) 举报

Bombasti

3楼-- · 2019-01-16 11:22

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"

The downsides of this approach are:

it can get stuck in a local energy minimum (shaking or helping manually helps)
it is not extremely fast (but can make a nice animation)

A similar method can be used to layout/untie knots.

Sample code

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

Approach 2

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.

Use Approach 1 to find a suboptimal initial solution (optional).
Remove all edges. Place the nodes on a grid (round up their coordinates). The grid must have enough resolution so that no two nodes overlap.
Sort the edges in ascending approximated length (use Euclidean or Manhattan metric).
For each edge use A* algorithm to find the shortest route to connect the nodes. As a cost function use not only the distance from the source node, but also add enough large penalty for stepping onto any grid points that are already taken by any edge routed previously.
Mark the grid points on the path found in the previous step as "taken", so all next edges will favour paths not stepping on / intersecting with this path.

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

0人赞添加讨论(0) 举报

地球回转人心会变

4楼-- · 2019-01-16 11:24

I think the simulation-based algorithm would be the bbest choice, however, since your goal is to minimize overlapping arcs and not to optimize the distribution of nodes you should apply a repelling force between arcs (not between nodes) and use the nodes as springs.

Iteration:

For each arc in the graph compute its central point (averaging the starting point with the ending point)
for each couple of arcs apply a repulsion between their centres (both extremes of the arc move accordingly)
for each node in the graph compute its new position as the average of the connected arcs and update the related endpoint of the arc

You can also add a contraction phase with the nodes attracted to the middle of the graph (average of the coordinates of all the nodes).

Stop iterating when some stability threshold is reached.

0人赞添加讨论(0) 举报

Logic to strategically place items in a container

Approach 1

Sample code

Approach 2

采纳回答

编辑标签

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

付费偷看金额在0.1-10元之间