Skip to content

Instantly share code, notes, and snippets.

@enjalot
Last active August 1, 2016 00:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save enjalot/82d843e5447185b1aa48da636b68478b to your computer and use it in GitHub Desktop.
Save enjalot/82d843e5447185b1aa48da636b68478b to your computer and use it in GitHub Desktop.
Adjacent circles
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

<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment