Force-Directed Sierpinski Triangle

Created by Christopher Manning

Summary

This generates a Sierpinski Triangle graph using a force-directed layout.

Controls

Use the mousewheel to increase or decrease the iterations.

References

<!DOCTYPE html>
<html>
  <head>
    <title>Force-Directed Sierpinski Triangle</title>
    <script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/d3/2.10.0/d3.v2.min.js"></script>
    <script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/dat-gui/0.5/dat.gui.min.js"></script> 
    <style type="text/css">
body, svg {
  margin: 0;
}
circle {
  fill: #fff;
  stroke: #999;
  stroke: steelBlue;
  stroke-width: 2.5px;
}

line {
  stroke: #999;
  stroke-width: 5px;
}

</style>
  </head>
  <body>
    <script type="text/javascript">
Math.TAU = Math.PI*2;

var width = window.innerWidth || 960,
    height = (window.innerHeight || 500) + 150

var config = { "iterations": 5, "simulate": true, "friction": 0.9, "linkStrength": 1, "linkDistance": 450, "charge": 10, "gravity": .01, "theta": .8 };
var gui = new dat.GUI();

var iterationsChanger = gui.add(config, "iterations", 1, 7).step(1).listen();
iterationsChanger.onChange(function(value) {
  sierpinski(value)
});

var fl = gui.addFolder('Force Layout');

var simulateChanger = fl.add(config, "simulate");
simulateChanger.onChange(function(value) {
  value ? force.start() : force.stop()
});

var frictionChanger = fl.add(config, "friction", 0, 1);
frictionChanger.onChange(function(value) {
  force.friction(value)
  force.start()
});

var linkDistanceChanger = fl.add(config, "linkDistance", 0, height);
linkDistanceChanger.onChange(function(value) {
  force.start()
});

var linkStrengthChanger = fl.add(config, "linkStrength", 0, 1);
linkStrengthChanger.onChange(function(value) {
  force.linkStrength(value)
  force.start()
});

var chargeChanger = fl.add(config,"charge", 0, 100);
chargeChanger.onChange(function(value) {
  force.charge(-value)
  force.start()
});

var gravityChanger = fl.add(config,"gravity", 0, 1);
gravityChanger.onChange(function(value) {
  force.gravity(value)
  force.start()
});

var thetaChanger = fl.add(config,"theta", 0, 1);
thetaChanger.onChange(function(value) {
  force.theta(value)
  force.start()
});

var cx = width/2,
    cy = height/2,
    radius = 3,
    nodes = [],
    links = [],
    triangles = [],
    node,
    link,
    stage = 0,
    currentIterations = 0

var zoom = d3.behavior.zoom()
.scale(config["iterations"])
.scaleExtent([1, 7])
.on("zoom", function(d,i) {
  config["iterations"] = Math.ceil(d3.event.scale)
  sierpinski(config["iterations"])
});

var force = d3.layout.force()
    .linkDistance(function(){ return config["linkDistance"] / Math.pow(2, config["iterations"] - 1) })
    .linkStrength(config["linkStrength"])
    .charge(-config["charge"])
    .gravity(config["gravity"])
    .friction(config["friction"])
    .theta(config["theta"])
    .size([width, height])

var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height)
    .call(zoom)

sierpinski(config['iterations'])

function sierpinski(iterations) {
  iterations = parseInt(iterations)

// prevent dat-gui from calling this more than once per iteration
  if (stage == iterations) return
  stage = iterations

do {
    currentIterations += currentIterations < iterations ? 1 : -1
    renderSierpinski(currentIterations)
  } while(currentIterations != iterations)

restart()
}

function renderSierpinski(iteration) {
  numLinks = Math.pow(3, iteration)
  numNodes = (Math.pow(3, iteration) + 3) / 2

if(links.length < numLinks) {
    // triangles are created counterclockwise
    if(iteration == 1) {
      r = config["linkDistance"]/Math.sqrt(3)
      // this triangle is upsidedown because the force layout flips the initial triangle
      nodes.push({x: cx + r*Math.cos(3*Math.TAU/4),  y: cy + r*Math.sin(3*Math.TAU/4)})
      nodes.push({x: cx + r*Math.cos(5*Math.TAU/12), y: cy + r*Math.sin(5*Math.TAU/12)})
      nodes.push({x: cx + r*Math.cos(Math.TAU/12), y: cy + r*Math.sin(Math.TAU/12)})
      links.push({source: nodes[0], target: nodes[1]})
      links.push({source: nodes[1], target: nodes[2]})
      links.push({source: nodes[2], target: nodes[0]})
      triangles.push([links[0], links[1], links[2]])
    } else {
        chunk = 3
        for (i=0,j=links.length; i<j; i+=chunk) {
          rl = links[i]
          bl = links[i+1]
          ll = links[i+2]

nodes.push({x: (rl.source.x + rl.target.x)/2, y: (rl.source.y + rl.target.y)/2})
          nodes.push({x: (bl.source.x + bl.target.x)/2, y: (bl.source.y + bl.target.y)/2})
          nodes.push({x: (ll.source.x + ll.target.x)/2, y: (ll.source.y + ll.target.y)/2})

nl = nodes.length
          rn = nodes[nl-3]
          bn = nodes[nl-2]
          ln = nodes[nl-1]

links.push({source: rl.source, target: rn})
          links.push({source: rn, target: ln})
          links.push({source: ln, target: rl.source})

links.push({source: rn, target: bl.source})
          links.push({source: bl.source, target: bn})
          links.push({source: bn, target: rn})

links.push({source: ln, target: bn})
          links.push({source: bn, target: ll.source})
          links.push({source: ll.source, target: ln})
        }
        links.splice(0, Math.pow(3, iteration-1))
    }
  } else {
    chunk = 9

for (i=0,j=links.length; j/chunk>0; j-=chunk,i++) {
      o = i * chunk
      links.push({source: links[o].source, target: links[o+3].target})
      links.push({source: links[o+3].target, target: links[o+7].target})
      links.push({source: links[o+7].target, target: links[o].source})
    }

links.splice(0, Math.pow(3, iteration+1))
    nodes.length = numNodes
  }
}

function restart() {
  force.nodes(nodes).links(links)
  force.start()

link = svg.selectAll("line.link")
  .data(links)

link.enter().insert("line")
  .attr("class", "link")

link.exit().remove()

node = svg.selectAll("circle.node")
  .data(nodes)

node.enter().insert("circle")
  .attr("class", "node")
  .attr("r", radius)
  .call(force.drag)

node.exit().remove()
}

force.on("tick", function() {
  node
  .attr("transform", function(d) {
    return "translate("+d.x+"," + 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 })

config['simulate'] ? null : force.stop()
})

</script>
  </body>
</html>

https://cdnjs.cloudflare.com/ajax/libs/d3/2.10.0/d3.v2.min.js

https://cdnjs.cloudflare.com/ajax/libs/dat-gui/0.5/dat.gui.min.js