D3 Examples - d3 Force Layout Bound to N Sided Random Polygon

d3 Force Layout Bound to N Sided Random Polygon

Originally coded for this Stackoverflow Question. First, it causes the force layout to converge on a different foci then the default width/2, height/2. The new foci should be the centroid of the triangle computed with this d3 helper method. Second, now that we are converging on the centroid of the polygon, our nodes our bound inside the polygon by calculating the intersections between lines drawn from the centroid to the node and the line of the edge of the polygon (intersection calculation from this question). No intersections on all sides means the circle is in the polygon, and an intersection on any edge means we need to bring the circle onto that edge.

xxxxxxxxxx
 
<!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>
  
  <div style="position: absolute;">
    <label for="ns">Number of Sides:</label>
    <input type="number" style="width:50px" id="ns" value="10" min="3"/>
    <button id="gen">Generate!</button>
  </div>
  
  <script>
  
    d3.select('#gen')
      .on("click", function(d){
        var i = d3.select("#ns")
            nS = i.property("value");
        if (nS < 3){
          nS = 3
          i.property("value", nS)
        }
        generateLayout(nS);
      });
  
    var width = 500,
        height = 500,
        radius = 10;
​
    var svg = d3.select("body").append("svg")
      .attr("width", width)
      .attr("height", height)
      .style("background", "#eee");
​
    // center of svg
    var px = width / 2,
        py = height / 2,
        nodes = d3.range(20).map(function(d){ return {} });
        
    generateLayout(d3.select("#ns").property("value"));
        
    function generateLayout(ns){
      
      svg.selectAll("*").remove();
      
      if (!ns) ns = parseInt(Math.random() * 5) + 4;
      
      var ang = d3.range(ns).map(function(d){ return Math.random() * (2 * Math.PI) }).sort();
        
      var polyPoints = ang.map(function(a){
        var r = (Math.random() * Math.min(width, height)) / 2,
            x = r * Math.cos(a) + px;
            y = r * Math.sin(a) + py;
        return [x, y];
      });
      
      var cent = d3.geom.polygon(polyPoints).centroid();
  
      svg.append("polygon")
        .style("stroke", "black")
        .style("fill", "none")
        .attr("points", polyPoints.join(" "));
  
      var force = d3.layout.force()
        .size([width, height])
        .nodes(nodes)
        .links([]);
        
      force.linkDistance(100);
      force.charge(-200);
  
      var node = svg.selectAll('.node')
        .data(nodes)
        .enter().append('circle')
        .attr('class', 'node')
        .call(force.drag);
  
      var N = polyPoints.length;
      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])),
              inter = false;
            
            for (var i = 0; i < N; i++){
              var f = i;
                  s = (i + 1) < N ? (i + 1) : 0;
              inter = getLineIntersection(polyPoints[f][0], polyPoints[f][1],
                polyPoints[s][0], polyPoints[s][1], cent[0], cent[1], x, y)
              
              if (inter){
                x = inter.x;
                y = inter.y;
                break;
              } 
            }
          
            return "translate(" + x + "," + y + ")";
          });
      });
      
      force.start();
    }
​
    // 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;
    }
​
  </script>
</body>
​
</html>
    