Skip to content

Instantly share code, notes, and snippets.

@enjalot
Last active September 6, 2016 05:10
Show Gist options
  • Save enjalot/6eca57f6399374c8c50a0013bb46b251 to your computer and use it in GitHub Desktop.
Save enjalot/6eca57f6399374c8c50a0013bb46b251 to your computer and use it in GitHub Desktop.
Circle packing 2x2
license: gpl-3.0

Following this circle packing tutorial trying to get to this rendering tutorial.

This adjacency placement algorithm has some problems. You need to pass in the parent with the biggest radius first. I think I'm missing some key piece of math that would make sure the proper angle is always used.

We need to use some trigonometry to find the center of the circle we want to place adjacent to its two parents.

SSS rule for finding angle with three known sides

Isosceles relationships for finding perpendicular segment for placing child circle.

Built with blockbuilder.org

forked from enjalot's block: Adjacent circles

<!DOCTYPE html>
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/d3-queue.v2.min.js"></script>
<style>
body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
circle.main {
fill: none;
stroke: #111;
stroke-width: 2;
}
</style>
</head>
<body>
<script>
var width = window.innerWidth || 960;
var height = window.innerHeight || 500;
var Ra = 20; // starting radius
var Rb = 20;
var maxRadius = Ra;
//var ratio = 0.8; //how much to decay radius
var ratio = [0.8, 1.4];
//var ratio = [1, 1]
var maxLevel = 20;
var adam = { x: width/2 - Ra, y: height/2, r: Ra, color: "#111", level: 0 };
var eve = { x: width/2 + Rb, y: height/2, r: Rb, color: "#111", level: 0};
var data = [adam, eve];
var quadtree = d3.quadtree()
.x(function(d) { return d.x })
.y(function(d) { return d.y })
.extent([[-1, -1], [width + 1, height + 1]]);
quadtree.add(adam)
quadtree.add(eve)
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height)
function addCircle(a,b, ROTATE) {
//console.log("a,b", a,b)
// create a new circle given parents a & b
var child = { r: a.r };
var randomRatio = Math.random() * (ratio[1] - ratio[0]) + ratio[0]
//var randomRatio = 0.9
child.r = randomRatio * child.r;
// we want to find our child's center by
// finding the 3rd point in the triangle
// with the base defined by the parents centers
var AC = a.r + child.r;
var AB = a.r + b.r;
var BC = child.r + b.r;
// SSS rule to find the angle between parents segment and a -> child segment
var atheta = Math.acos((AC*AC + AB*AB - BC*BC)/(2*AC*AB));
// base of the right triangle made by dropping perpendicular line from child
// down to the segment between a and b
var base = Math.cos(atheta) * AC;
// length of the above mentioned line segment that is perpendicular
var altitude = Math.sin(atheta) * AC;
var dx = b.x - a.x;
var dy = b.y - a.y;
var magnitude = Math.sqrt(dx*dx + dy*dy);
var normalized = {
x: dx/magnitude,
y: dy/magnitude
}
// the angle between the parent segment (connection between a and b)
// and the x-axis (we essentially rotate our altitude)
var ptheta = -Math.acos(dx/magnitude) * (dy<0 ? -1 : 1);
var rotate = ptheta
if(ptheta < -Math.PI/2) rotate += Math.PI;
rotate += ROTATE
// we find the point perpendicular
var perp = {
x: a.x + normalized.x * base,
y: a.y + normalized.y * base
}
/*
svg.append("circle")
.attr("cx", perp.x)
.attr("cy", perp.y)
.attr("r", 5)
.style("fill", b.color)
*/
child.x = perp.x - Math.sin(rotate)*altitude;
child.y = perp.y - Math.cos(rotate)*altitude;
return child;
}
function recurseCircle(a,b) {
if(a.level > maxLevel) return;
var c1 = addCircle(a,b, 0);
c1.level = a.level + 1;
if(c1.r > maxRadius) maxRadius = c1.r;
// check if new circle collides
var hits = [];
quadtree.visit(nearest(c1, maxRadius, hits))
if(!hits.length && c1.x > c1.r + 2 && c1.x < width - 2 - c1.r && c1.y > c1.r + 2 && c1.y < height - 2 - c1.r ) {
data.push(c1)
quadtree.add(c1)
render();
setTimeout(function() {
recurseCircle(c1, a);
}, 150)
setTimeout(function() {
recurseCircle(c1, b)
}, 300)
};
var c2 = addCircle(a,b, Math.PI);
c2.level = a.level + 1;
if(c2.r > maxRadius) maxRadius = c2.r;
// check if new circle collides
var hits = [];
quadtree.visit(nearest(c2, maxRadius, hits))
if(!hits.length && c2.x > c2.r + 2 && c2.x < width - 2 - c2.r && c2.y > c2.r + 2 && c2.y < height - 2 - c2.r ) {
data.push(c2)
quadtree.add(c2)
render();
setTimeout(function() {
recurseCircle(c2, a);
}, 150)
setTimeout(function() {
recurseCircle(c2, b)
}, 300)
};
}
recurseCircle(adam, eve)
function render() {
var circles = svg.selectAll("circle.main").data(data);
circles = circles.enter().append("circle")
.classed("main", true)
.on("click", function(d) { console.log(d)})
.merge(circles);
circles
.attr("cx", function(d) { return d.x})
.attr("cy", function(d) { return d.y})
.attr("r", function(d) { return d.r})
.style("stroke", function(d) { return d.color || "#111" })
}
render();
function nearest(node, radius, hits) {
if(!hits) hits = [];
// we want to find everything within radius
var nx1 = node.x - radius;
var nx2 = node.x + radius;
var ny1 = node.y - radius;
var ny2 = node.y + radius;
return function(quad, x1, y1, x2, y2) {
if (quad.data && (quad.data !== node)) {
var x = node.x - quad.data.x,
y = node.y - quad.data.y,
l = Math.sqrt(x * x + y * y) + 1e-7,
r = node.r + quad.data.r;
if (l < r) {
hits.push(quad.data)
} else {
}
}
return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
}
}
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment