Skip to content

Instantly share code, notes, and snippets.

@elsherbini

elsherbini/README.md

Forked from mbostock/.block
Last active September 8, 2015 18:07
Show Gist options
  • Save elsherbini/f3c2151d2ea960c50bf1 to your computer and use it in GitHub Desktop.
Save elsherbini/f3c2151d2ea960c50bf1 to your computer and use it in GitHub Desktop.
Download ZIP
Apollonius’ Problem II
Raw
README.md

Apollonius’ problem is to compute the circle that is tangent to three given circles. There are up to eight such circles.

Drag the circles to see the tangent circles change.

Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.circle {
fill-opacity: .5;
}
.ring {
fill: none;
stroke: #000;
pointer-events: none;
}
.ring-inner {
stroke-width: 5px;
stroke-opacity: .25;
}
</style>
<svg width="960" height="500"></svg>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.6/d3.min.js" charset="utf-8"></script>
<script>
function apolloniusCircle(x1, y1, r1, x2, y2, r2, x3, y3, r3) {
// The quadratic equation (1):
//
// 0 = (x - x1)² + (y - y1)² - (r ± r1)²
// 0 = (x - x2)² + (y - y2)² - (r ± r2)²
// 0 = (x - x3)² + (y - y3)² - (r ± r3)²
//
// Use a negative radius to choose a different circle.
// We must rewrite this in standard form Ar² + Br + C = 0 to solve for r.
// Per http://mathworld.wolfram.com/ApolloniusProblem.html
var a2 = 2 * (x1 - x2),
b2 = 2 * (y1 - y2),
c2 = 2 * (r2 - r1),
d2 = x1 * x1 + y1 * y1 - r1 * r1 - x2 * x2 - y2 * y2 + r2 * r2,
a3 = 2 * (x1 - x3),
b3 = 2 * (y1 - y3),
c3 = 2 * (r3 - r1),
d3 = x1 * x1 + y1 * y1 - r1 * r1 - x3 * x3 - y3 * y3 + r3 * r3;
// Giving:
//
// x = (b2 * d3 - b3 * d2 + (b3 * c2 - b2 * c3) * r) / (a3 * b2 - a2 * b3)
// y = (a3 * d2 - a2 * d3 + (a2 * c3 - a3 * c2) * r) / (a3 * b2 - a2 * b3)
//
// Expand x - x1, substituting definition of x in terms of r.
//
// x - x1 = (b2 * d3 - b3 * d2 + (b3 * c2 - b2 * c3) * r) / (a3 * b2 - a2 * b3) - x1
// = (b2 * d3 - b3 * d2) / (a3 * b2 - a2 * b3) + (b3 * c2 - b2 * c3) / (a3 * b2 - a2 * b3) * r - x1
// = bd / ab + bc / ab * r - x1
// = xa + xb * r
//
// Where:
var ab = a3 * b2 - a2 * b3,
xa = (b2 * d3 - b3 * d2) / ab - x1,
xb = (b3 * c2 - b2 * c3) / ab;
// Likewise expand y - y1, substituting definition of y in terms of r.
//
// y - y1 = (a3 * d2 - a2 * d3 + (a2 * c3 - a3 * c2) * r) / (a3 * b2 - a2 * b3) - y1
// = (a3 * d2 - a2 * d3) / (a3 * b2 - a2 * b3) + (a2 * c3 - a3 * c2) / (a3 * b2 - a2 * b3) * r - y1
// = ad / ab + ac / ab * r - y1
// = ya + yb * r
//
// Where:
var ya = (a3 * d2 - a2 * d3) / ab - y1,
yb = (a2 * c3 - a3 * c2) / ab;
// Expand (x - x1)², (y - y1)² and (r - r1)²:
//
// (x - x1)² = xb * xb * r² + 2 * xa * xb * r + xa * xa
// (y - y1)² = yb * yb * r² + 2 * ya * yb * r + ya * ya
// (r - r1)² = r² - 2 * r1 * r + r1 * r1.
//
// Substitute back into quadratic equation (1):
//
// 0 = xb * xb * r² + yb * yb * r² - r²
// + 2 * xa * xb * r + 2 * ya * yb * r + 2 * r1 * r
// + xa * xa + ya * ya - r1 * r1
//
// Rewrite in standard form Ar² + Br + C = 0,
// then plug into the quadratic formula to solve for r, x and y.
var A = xb * xb + yb * yb - 1,
B = 2 * (xa * xb + ya * yb + r1),
C = xa * xa + ya * ya - r1 * r1,
r = (-B - Math.sqrt(B * B - 4 * A * C)) / (2 * A);
return isNaN(r) ? null : {x: xa + xb * r + x1, y: ya + yb * r + y1, r: r < 0 ? -r : r};
}
var c1 = {x: 380, y: 250, r: 80},
c2 = {x: 600, y: 100, r: 20},
c3 = {x: 600, y: 300, r: 120};
var color = d3.scale.category10();
var svg = d3.select("svg");
var circle = svg.selectAll(".circle")
.data([c1, c2, c3])
.enter().append("g")
.attr("class", "circle")
.attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; })
.call(d3.behavior.drag()
.origin(function(d) { return d; })
.on("dragstart", dragstarted)
.on("drag", dragged));
circle.append("circle")
.attr("r", function(d) { return d.r; });
var ring = svg.selectAll(".ring")
.data([
function() { return apolloniusCircle(c1.x, c1.y, +c1.r, c2.x, c2.y, +c2.r, c3.x, c3.y, +c3.r); },
function() { return apolloniusCircle(c1.x, c1.y, +c1.r, c2.x, c2.y, +c2.r, c3.x, c3.y, -c3.r); },
function() { return apolloniusCircle(c1.x, c1.y, +c1.r, c2.x, c2.y, -c2.r, c3.x, c3.y, +c3.r); },
function() { return apolloniusCircle(c1.x, c1.y, +c1.r, c2.x, c2.y, -c2.r, c3.x, c3.y, -c3.r); },
function() { return apolloniusCircle(c1.x, c1.y, -c1.r, c2.x, c2.y, +c2.r, c3.x, c3.y, +c3.r); },
function() { return apolloniusCircle(c1.x, c1.y, -c1.r, c2.x, c2.y, +c2.r, c3.x, c3.y, -c3.r); },
function() { return apolloniusCircle(c1.x, c1.y, -c1.r, c2.x, c2.y, -c2.r, c3.x, c3.y, +c3.r); },
function() { return apolloniusCircle(c1.x, c1.y, -c1.r, c2.x, c2.y, -c2.r, c3.x, c3.y, -c3.r); }
])
.enter().insert("g", ".circle")
.attr("class", "ring")
.style("stroke", function(d, i) { return color(i); });
ring.append("circle")
.attr("class", "ring-outer");
ring.append("circle")
.attr("class", "ring-inner");
update();
function dragstarted(d) {
this.parentNode.appendChild(this);
}
function dragged(d) {
d3.select(this).attr("transform", "translate(" + (d.x = d3.event.x) + "," + (d.y = d3.event.y) + ")");
update();
}
function update() {
ring.each(function(f) {
var c = f();
if (c) {
var ring = d3.select(this).style("display", null).attr("transform", "translate(" + c.x + "," + c.y + ")");
ring.select(".ring-inner").attr("r", c.r - 3);
ring.select(".ring-outer").attr("r", c.r);
} else {
d3.select(this).style("display", "none");
}
});
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment