Public
Edited
Jul 31, 2023
2 forks
14 stars
Apollonius’ Problem
Also listed in…
d3-drag
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 //mathworld.wolfram.com/ApolloniusProblem.html
const 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:
const 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:
const 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.
const A = xb * xb + yb * yb - 1,
B = 2 * (xa * xb + ya * yb + r1),
C = xa * xa + ya * ya - r1 * r1,
r = A ? (-B - Math.sqrt(B * B - 4 * A * C)) / (2 * A) : (-C / B);
return {x: xa + xb * r + x1, y: ya + yb * r + y1, r};
}
function clamp(x, lo, hi) {
return x < lo ? lo : x > hi ? hi : x;
}
<style>
.circle {
fill-opacity: .5;
}
.ring {
fill: none;
stroke: #000;
pointer-events: none;
}
.ring-inner {
stroke-width: 5px;
stroke-opacity: .25;
}
</style>
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
