Force chart d3.js inside a triangle

Question

I'm studying d3.js force chart and I have a question. Is it possible to make a force chart inside a triangle with some coordinates?

Here is my code:

var width = 500;
var height = 500;
//margin
var marginLeft = 10;
var marginTop = 10;
var marginRight = 10;
var marginBottom = 10;
var margin = { left: marginLeft , top: marginTop, right: marginRight, bottom: marginBottom};

//size of canvas
var innerWidth = width - margin.left - margin.right;
var innerHeight = height - margin.top - margin.bottom;

var radius = 10;

var svg = d3.select(".forcechart").append("svg")
    .attr("width", width) 
    .attr("height", height)
    .style("background", "#eee");

var tr = svg.append("polygon")       // attach a polygon
    .style("stroke", "black")  // colour the line
    .style("fill", "none")     // remove any fill colour
    .attr("points", "250,0, 12,173,  250,250");  // x,y points 

var group = svg.append("g")
    .attr("transform",  "translate(" + margin.left + "," + margin.top + ")");

var graph = {
    "nodes": [  { "x": 0, "y": 0 },
                { "x": 100,  "y":  100 },
                { "x": 500, "y": 500 },
                     { "x": 300, "y": 0 },
                   { "x": 300, "y": 0 },
                  { "x": 100,  "y":  100 },
                { "x": 500, "y": 500 },
                     { "x": 300, "y": 0 },
                   { "x": 300, "y": 0 },
                  { "x": 100,  "y":  100 },
                { "x": 500, "y": 500 },
                     { "x": 300, "y": 0 },
                   { "x": 300, "y": 0 },
                  { "x": 100,  "y":  100 },
                { "x": 500, "y": 500 },
                     { "x": 300, "y": 0 },
                   { "x": 300, "y": 0 },
                  { "x": 100,  "y":  100 },
                { "x": 500, "y": 500 },
                     { "x": 300, "y": 0 },
                   { "x": 300, "y": 0 },
            ],
    "links": []
    };


var nodes = graph.nodes,
    links = graph.links;

var force = d3.layout.force()
    .size([innerWidth, innerHeight])
    .nodes(nodes)
    .links(links);

force.linkDistance(100);
force.charge(-200);

var link = group.selectAll('.link')
    .data(links)
    .enter().append('line')
    .attr('class', 'link');

var node = group.selectAll('.node')
    .data(nodes)
    .enter().append('circle')
    .attr('class', 'node');

force.on('tick', function() {
    node.attr('r', radius)
        .attr('cx', function(d) { return d.x; })
        .attr('cy', function(d) { return d.y; });

    link.attr('x1', function(d) { return d.source.x; })
        .attr('y1', function(d) { return d.source.y; })
        .attr('x2', function(d) { return d.target.x; })
        .attr('y2', function(d) { return d.target.y; });

});


force.start();

Full code is here: http://codepen.io/Balzzac/pen/vGWXdQ. Now it is a force chart inside "group", I need to make it is inside triangle "tr" so no one node is outside of boundaries of my triangle.

Thanks for help!

PS Sorry for my English =)

This probably involves some computer graphics algorithms. without a solid background in algorithms it would be hard to implement. would be nice if someone can invest some time and code a solution for this. — paradite, Apr 30 '16 at 10:46
Have a look here: http://stackoverflow.com/questions/9573178/d3-force-directed-layout-with-bounding-box — Gerardo Furtado, Apr 30 '16 at 11:09
To fix the `cx` and `cy`, the math is here: https://bl.ocks.org/milkbread/11000965 — Alvin K., Apr 30 '16 at 17:03

score 6 · Accepted Answer · edited May 23 '17 at 11:44

There's really two parts to this question. First, you need your force layout to converge on a different foci then the default width/2, height/2. This new foci should be the centroid of the triangle. Luckily d3 has a helper method to compute this for polygons. Second, now that we are converging on the centroid of the triangle, how do we bound our nodes inside that triangle. The method I use below calculates the intersections between lines drawn from the centroid to the node and the line of the edge of the triangle (intersection calculation from this question). No intersections on all 3 edges means the circle is in the triangle, and an intersection on any edge means we need to bring the circle onto that edge.

UPDATE -- generalized the code a bit and converted it to a block here to work with N sided polygons.

Let's get to the code:

<!DOCTYPE html>
<html>

<head>
  <script data-require="d3@3.5.3" data-semver="3.5.3" src="//cdnjs.cloudflare.com/ajax/libs/d3/3.5.3/d3.js"></script>
</head>

<body>
  <script>
    var width = 500,
        height = 500,
        radius = 10;

    var svg = d3.select("body").append("svg")
      .attr("width", width)
      .attr("height", height)
      .style("background", "#eee");

    // our polygon
    var trianglePoints = [
      [250, 0],
      [12, 173],
      [250, 250]
    ];

    var tr = svg.append("polygon") // attach a polygon
      .style("stroke", "black") // colour the line
      .style("fill", "none") // remove any fill colour
      .attr("points", trianglePoints.join(" ")); // x,y points 

    var group = svg.append("g");

    var nodes = d3.range(20).map(function(d){ return {} }),
      links = [],
      cent = d3.geom.polygon(trianglePoints).centroid();

    var force = d3.layout.force()
      .size([width, height])
      .nodes(nodes)
      .links(links);

    force.linkDistance(100);
    force.charge(-200);

    var link = group.selectAll('.link')
      .data(links)
      .enter().append('line')
      .attr('class', 'link');

    var node = group.selectAll('.node')
      .data(nodes)
      .enter().append('circle')
      .attr('class', 'node')
      .call(force.drag); //<-- make them draggable to test

    force.on('tick', function(e) {

      node.attr('r', radius)
        .attr('transform', function(d) {

          // change focus to the center of the triangle
          var x = (d.x - (width / 2 - cent[0])),
            y = (d.y - (height / 2 - cent[1]));

          // test intersections on all 3 edges
          var i = 
            getLineIntersection(trianglePoints[0][0], trianglePoints[0][1],
              trianglePoints[1][0], trianglePoints[1][1], cent[0], cent[1], x, y) ||
            getLineIntersection(trianglePoints[1][0], trianglePoints[1][1],
              trianglePoints[2][0], trianglePoints[2][1], cent[0], cent[1], x, y) ||
            getLineIntersection(trianglePoints[0][0], trianglePoints[0][1],
                trianglePoints[2][0], trianglePoints[2][1], cent[0], cent[1], x, y) ||
            false;
          
          // set it to intersection
          if (i){
            x = i.x;
            y = i.y;
          }

          return "translate(" + x + "," + y + ")";

        });

      link.attr('x1', function(d) {
          return d.source.x;
        })
        .attr('y1', function(d) {
          return d.source.y;
        })
        .attr('x2', function(d) {
          return d.target.x;
        })
        .attr('y2', function(d) {
          return d.target.y;
        });

    });

    // from https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
    function getLineIntersection(p0_x, p0_y, p1_x, p1_y, p2_x, p2_y, p3_x, p3_y) {
      var s1_x, s1_y, s2_x, s2_y;
      s1_x = p1_x - p0_x;
      s1_y = p1_y - p0_y;
      s2_x = p3_x - p2_x;
      s2_y = p3_y - p2_y;
      var s, t;
      s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
      t = (s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

      if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
        var intX = p0_x + (t * s1_x);
        var intY = p0_y + (t * s1_y);
        return {
          x: intX,
          y: intY
        };
      }
      return false;
    }

    force.start();
  </script>
</body>

</html>

Force chart d3.js inside a triangle

1 Answers1

Linked