Created by Christopher Manning
This generates a Sierpinski Triangle graph using a force-directed layout.
- Use the mousewheel to increase or decrease the iterations.
Last active
October 14, 2015 01:17
-
-
Save christophermanning/4285420 to your computer and use it in GitHub Desktop.
Force-Directed Sierpinski Triangle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment