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
<!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 = 960;
var height = 500;
var toDeg = 180/Math.PI
var Ra = 69; // starting radius
var Rb = 50;
var ratio = 0.8; //how much to decay radius
var adam = { x: width/2 - Ra, y: height/2, r: Ra, color: "#0d0" };
var eve = { x: width/2 + Rb, y: height/2, r: Rb, color: "#00d"};
var data = [adam, eve];
var quadtree = d3.quadtree(data)
.x(function(d) { return d.x })
.y(function(d) { return d.y })
.extent([[-1, -1], [width + 1, height + 1]]);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height)
var q = d3.queue()
function addCircle(a,b, ROTATE, flag) {
if(!ROTATE) ROTATE = 0;
//console.log("a,b", a,b)
// create a new circle given parents a & b
var flip = -1;
/*
if(b.r > a.r) {
console.log("swap", a, b)
var t = { x: b.x, y: b.y, r: b.r, color: b.color}
b.x = a.x;
b.y = a.y;
b.r = a.r;
b.color = a.color;
a.x = t.x;
a.y = t.y;
a.r = t.r;
a.color = t.color;
}*/
var child = { r: a.r };
child.r = ratio * 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);
if(flag) {
console.log("flagged", ptheta*toDeg, dx, dy)
} else {
console.log("acos", ptheta * toDeg, dx, dy);
}
// we flip the angle if its less than -90 degrees
var rotate = ptheta
if(ptheta < -Math.PI/2) rotate += Math.PI;
rotate += ROTATE
//if(ptheta > 0) ptheta *= -1;
//console.log("ptheta", ptheta * 180 / Math.PI)
// 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;
}
/*
var c = addCircle(adam, eve, Math.PI);
c.color = "#d00"
data.push(c)
var c2 = addCircle(c, adam, Math.PI);
c2.color = "#d00"
data.push(c2)
*/
/*
var c = addCircle(adam, eve);
c.color = "#d00"
data.push(c)
var d = addCircle(c,adam)
d.color = "#cc0"
data.push(d);
var e = addCircle(c,eve)
e.color = "#c0c"
data.push(e)
*/
var cc = addCircle(adam, eve, Math.PI);
data.push(cc)
var dd = addCircle(cc, adam, 0, true);
data.push(dd)
var c = addCircle(adam, eve);
data.push(c)
var d = addCircle(c, adam)
data.push(d)
var e = addCircle(d, adam, Math.PI)
data.push(e)
var f = addCircle(e, adam, Math.PI)
data.push(f)
var g = addCircle(f, adam, Math.PI, false)
data.push(g)
var h = addCircle(g,adam, Math.PI, true)
data.push(h)
var i = addCircle(h,adam, Math.PI, true)
data.push(i)
console.log(data);
function render() {
var circles = svg.selectAll("circle.main").data(data);
circles = circles.enter().append("circle").classed("main", true).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();
</script>
</body>