Skip to content

Instantly share code, notes, and snippets.

@mbostock mbostock/.block
Last active Sep 13, 2018

Embed
What would you like to do?
Smallest Enclosing Circle
license: gpl-3.0

The smallest circle that encloses a set of given circles can be computed using a variant of Welzl’s algorithm. Instead of testing whether a circle contains a point, test whether a circle contains another circle; likewise instead of computing the circle that intersects two or three points, compute the circle that has internal tangents to two or three circles. (The latter is Apollonius’ problem.)

Drag the circles to see the enclosing circle change.

<!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="//d3js.org/d3.v3.min.js"></script>
<script>
var circles = [
{x: 380, y: 250, r: 80},
{x: 600, y: 100, r: 20},
{x: 600, y: 300, r: 120},
{x: 500, y: 150, r: 40},
{x: 450, y: 400, r: 20}
];
var svg = d3.select("svg");
var circle = svg.selectAll(".circle")
.data(circles)
.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.append("g")
.attr("class", "ring");
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() {
var c = enclosingCircle(circles);
ring.attr("transform", "translate(" + c.x + "," + c.y + ")");
ring.select(".ring-inner").attr("r", c.r - 3);
ring.select(".ring-outer").attr("r", c.r);
}
// Returns a linked list from the specified array in random order.
function randomizedList(array) {
var i,
n = (array = array.slice()).length,
head = null,
node = head;
while (n) {
var next = {id: array.length - n, value: array[n - 1], next: null};
if (node) node = node.next = next;
else node = head = next;
array[i] = array[--n];
}
return {head: head, tail: node};
}
// Returns the smallest circle that contains the specified circles.
function enclosingCircle(circles) {
return enclosingCircleIntersectingCircles(randomizedList(circles), []);
}
// Returns the smallest circle that contains the circles L
// and intersects the circles B.
function enclosingCircleIntersectingCircles(L, B) {
var circle,
l0 = null,
l1 = L.head,
l2,
p1;
switch (B.length) {
case 1: circle = B[0]; break;
case 2: circle = circleIntersectingTwoCircles(B[0], B[1]); break;
case 3: circle = circleIntersectingThreeCircles(B[0], B[1], B[2]); break;
}
while (l1) {
p1 = l1.value, l2 = l1.next;
if (!circle || !circleContainsCircle(circle, p1)) {
// Temporarily truncate L before l1.
if (l0) L.tail = l0, l0.next = null;
else L.head = L.tail = null;
B.push(p1);
circle = enclosingCircleIntersectingCircles(L, B); // Note: reorders L!
B.pop();
// Move l1 to the front of L and reconnect the truncated list L.
if (L.head) l1.next = L.head, L.head = l1;
else l1.next = null, L.head = L.tail = l1;
l0 = L.tail, l0.next = l2;
} else {
l0 = l1;
}
l1 = l2;
}
L.tail = l0;
return circle;
}
// Returns true if the specified circle1 contains the specified circle2.
function circleContainsCircle(circle1, circle2) {
var xc0 = circle1.x - circle2.x,
yc0 = circle1.y - circle2.y;
return Math.sqrt(xc0 * xc0 + yc0 * yc0) < circle1.r - circle2.r + 1e-6;
}
// Returns the smallest circle that intersects the two specified circles.
function circleIntersectingTwoCircles(circle1, circle2) {
var x1 = circle1.x, y1 = circle1.y, r1 = circle1.r,
x2 = circle2.x, y2 = circle2.y, r2 = circle2.r,
x12 = x2 - x1, y12 = y2 - y1, r12 = r2 - r1,
l = Math.sqrt(x12 * x12 + y12 * y12);
return {
x: (x1 + x2 + x12 / l * r12) / 2,
y: (y1 + y2 + y12 / l * r12) / 2,
r: (l + r1 + r2) / 2
};
}
// Returns the smallest circle that intersects the three specified circles.
function circleIntersectingThreeCircles(circle1, circle2, circle3) {
var x1 = circle1.x, y1 = circle1.y, r1 = circle1.r,
x2 = circle2.x, y2 = circle2.y, r2 = circle2.r,
x3 = circle3.x, y3 = circle3.y, r3 = circle3.r,
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,
ab = a3 * b2 - a2 * b3,
xa = (b2 * d3 - b3 * d2) / ab - x1,
xb = (b3 * c2 - b2 * c3) / ab,
ya = (a3 * d2 - a2 * d3) / ab - y1,
yb = (a2 * c3 - a3 * c2) / ab,
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 {
x: xa + xb * r + x1,
y: ya + yb * r + y1,
r: r
};
}
</script>
@nadaasghar

This comment has been minimized.

Copy link

commented Nov 15, 2015

hello

please can you tell me how can i change the circle color and add text into it ?

thank you

nada asghar
nada.asghar@hotmail.com

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.