1d:{"title":"d3.packEnclose","cells":[{"id":1960,"value":"

d3.packEnclose

\n\n# d3.packEnclose\n\n[d3.packEnclose](https://d3js.org/d3-hierarchy/pack#packEnclose) computes the smallest circle that encloses the given circles. Given an array of objects [{*x*, *y*, *r*}, …] representing circles centered at ${tex`\\langle x,y \\rangle`} with radius ${tex`r`}, it returns an object {*x*, *y*, *r*} that represents the smallest enclosing circle.","pinned":false,"hidden":false,"mode":"md"},{"id":1972,"value":"circles = Array.from({length: 20}, () => ({\n x: ((Math.random() - 0.5) / 2 + 0.5) * width,\n y: ((Math.random() - 0.5) / 2 + 0.5) * height,\n r: (Math.random() + 0.5) * 20\n}))","pinned":true,"hidden":false,"mode":"ojs"},{"id":1974,"value":"enclosingCircle = d3.packEnclose(circles)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1979,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":2016,"value":"d3.packEnclose is used in conjunction with [d3.packSiblings](https://d3js.org/d3-hierarchy/pack#packSiblings) by [d3.pack](/@d3/circle-packing) to compute the bounding circle for each internal node in a circle-packing diagram.\n\nBut how does d3.packEnclose work? Let’s watch!","pinned":false,"hidden":false,"mode":"md"},{"id":1146,"value":"viewof replay = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":1096,"value":"$1f","pinned":false,"hidden":false,"mode":"ojs"},{"id":1249,"value":"To start, let’s think about how to represent an enclosing circle. As you drag circles *L* below, notice that the enclosing circle *e* only moves when you move a circle that is *tangent* to the enclosing circle, and that the set of tangent circles depends on how the circles are arranged.","pinned":false,"hidden":false,"mode":"md"},{"id":35,"value":"$20","pinned":false,"hidden":false,"mode":"ojs"},{"id":89,"value":"Depending on how you arrange the circles, there can be one, two or three tangent circles. This set of tangent circles is called the *basis* for the enclosing circle.\n\nBut before we can compute this basis, we’ll first need to be able to test whether a circle encloses another circle. A circle *a* encloses a circle *b* if and only if *a*’s radius is greater than or equal to *b*’s radius plus the distance between the two circles’ centers. Expressed as an inequality:","pinned":false,"hidden":false,"mode":"md"},{"id":1055,"value":"tex.block`r_a \\geq r_b + \\sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1052,"value":"In the diagram below, the larger circle represents *a* and\nthe smaller circle represents *b*. The inequality value can be seen\nas the radius of gray circle . Drag the circle *b* to see how its position affects whether or not it is enclosed by *a*.","pinned":false,"hidden":false,"mode":"md"},{"id":595,"value":"$21","pinned":false,"hidden":false,"mode":"ojs"},{"id":652,"value":"To avoid the square root, we can instead test two equivalent inequalities:","pinned":false,"hidden":false,"mode":"md"},{"id":1070,"value":"tex.block`r_a - r_b \\geq 0`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1072,"value":"tex.block`(r_a - r_b)^2 \\geq (x_a - x_b)^2 + (y_a - y_b)^2`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1068,"value":"This works because the square root is a monotonic function. In code:","pinned":false,"hidden":false,"mode":"md"},{"id":1592,"value":"// Given two circles a and b, returns true iff b ⊆ a.\nfunction encloses(a, b) {\n const dr = a.r - b.r;\n const dx = b.x - a.x;\n const dy = b.y - a.y;\n return dr >= 0 && dr * dr > dx * dx + dy * dy;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1648,"value":"To test whether a given circle *a* encloses all of the circles in array *B*, a loop:","pinned":false,"hidden":false,"mode":"md"},{"id":1652,"value":"// Given a circle a and set B, returns true iff b ⊆ a for every b ∈ B.\nfunction enclosesAll(a, B) {\n for (var i = 0; i < B.length; ++i) {\n if (!encloses(a, B[i])) {\n return false;\n }\n }\n return true;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1661,"value":"The final implementation uses slightly different “weak” variations of these methods that use a small epsilon to address imprecise floating point calculations.","pinned":false,"hidden":false,"mode":"md"},{"id":46,"value":"function enclosesWeak(a, b) {\n const dr = a.r - b.r + 1e-6;\n const dx = b.x - a.x;\n const dy = b.y - a.y;\n return dr > 0 && dr * dr > dx * dx + dy * dy;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":49,"value":"function enclosesWeakAll(a, B) {\n for (var i = 0; i < B.length; ++i) {\n if (!enclosesWeak(a, B[i])) {\n return false;\n }\n }\n return true;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":165,"value":"### Finding an Initial Basis\n\nArmed with only this test, we have the start of a potential algorithm—we’ll call it dumb luck: we can pick the first of the input circles and test whether it encloses the other circles. In fact, this is a reasonable strategy not only if you are lucky, but if there is only one input circle: the circle encloses itself by definition.","pinned":false,"hidden":false,"mode":"md"},{"id":1832,"value":"// Given the set L = {a}, returns the enclosing circle.\nfunction enclose1(a) {\n return encloseBasis1(a);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":43,"value":"// Given the basis B = {a}, returns the enclosing circle.\nfunction encloseBasis1(a) {\n return {x: a.x, y: a.y, r: a.r};\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1683,"value":"But what if there is more than one input circle? Or if none of the input circles contains all the other input circles? We’ll need to handle these cases, too. Let’s work our way up slowly.\n\nIf we have two input circles, and neither contains the other, we can compute the smallest circle that contains them using only geometry: the enclosing circle is [internally tangent](http://mathworld.wolfram.com/TangentCircles.html) to the two input circles. The diameter of this tangent circle is the distance between the centers of *a* and *b* plus the radii of *a* and *b*. Likewise, the center of the tangent circle lies on the line intersecting the two centers of *a* and *b*.","pinned":false,"hidden":false,"mode":"md"},{"id":176,"value":"$22","pinned":false,"hidden":false,"mode":"ojs"},{"id":205,"value":"In code:","pinned":false,"hidden":false,"mode":"md"},{"id":1665,"value":"// Given the basis B = {a, b}, returns the enclosing circle.\nfunction encloseBasis2(a, b) {\n const x1 = a.x, y1 = a.y, r1 = a.r;\n const x2 = b.x, y2 = b.y, r2 = b.r;\n const x21 = x2 - x1, y21 = y2 - y1, r21 = r2 - r1;\n const l = Math.sqrt(x21 * x21 + y21 * y21);\n return {\n x: (x1 + x2 + x21 / l * r21) / 2,\n y: (y1 + y2 + y21 / l * r21) / 2,\n r: (l + r1 + r2) / 2\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1667,"value":"The tangent circle is the smallest enclosing circle for *a* and *b* if and only if *a* does not enclose *b* and *b* does not enclose *a*. If *a* ⊆ *b*, then *b* is the smallest enclosing circle of *a* and *b*; likewise if *b* ⊆ *a*, then *a* is the smallest enclosing circle. This property, *a* ⊈ *b* and *b* ⊈ *a*, means that the set {*a*, *b*} forms a *basis*. A basis represents the smallest enclosing circle as a set of tangent circles.\n\nWe can test whether two circles *a* and *b* form a basis as follows:","pinned":false,"hidden":false,"mode":"md"},{"id":1688,"value":"// Returns true iff the set {a, b} forms a basis.\nfunction isBasis2(a, b) {\n return !encloses(a, b)\n && !encloses(b, a);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1690,"value":"Similarly, we can write a function that computes the smallest enclosing circle of any two circles:","pinned":false,"hidden":false,"mode":"md"},{"id":1692,"value":"// Given the set L = {a, b}, returns the enclosing circle.\nfunction enclose2(a, b) {\n return encloses(a, b) ? a\n : encloses(b, a) ? b\n : encloseBasis2(a, b);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1694,"value":"So we’re making progress!\n\nBut what if we have three circles? Well, again, if we know that these circles form a basis, we can apply geometry to compute the internally tangent circle. A basis test for three circles looks like this:","pinned":false,"hidden":false,"mode":"md"},{"id":1696,"value":"// Returns true iff the set {a, b, c} forms a basis.\nfunction isBasis3(a, b, c) {\n return isBasis2(a, b) && !encloses(encloseBasis2(a, b), c)\n && isBasis2(a, c) && !encloses(encloseBasis2(a, c), b)\n && isBasis2(b, c) && !encloses(encloseBasis2(b, c), a);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1698,"value":"The two-bases are shown below in gray ; the three-basis is shown in red . Notice that a two-basis disappears when one of its circles encloses the other circle, and that the three-basis disappears if *any* two-basis disappears, *or* a two-basis contains the remaining third circle.","pinned":false,"hidden":false,"mode":"md"},{"id":233,"value":"$23","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"I’ll omit the geometric solution for the three-circle case as it is a bit complicated.\n(See [Apollonius’ Problem](/@d3/apollonius-problem).)\nIt requires solving a system of three quadratic equations:","pinned":false,"hidden":false,"mode":"md"},{"id":1079,"value":"tex.block`0 = (x - x_a)^2 + (y - y_a)^2 - (r - r_a)^2`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1087,"value":"tex.block`0 = (x - x_b)^2 + (y - y_b)^2 - (r - r_b)^2`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1089,"value":"tex.block`0 = (x - x_c)^2 + (y - y_c)^2 - (r - r_c)^2`","pinned":false,"hidden":false,"mode":"ojs"},{"id":37,"value":"function encloseBasis3(a, b, c) {\n const x1 = a.x, y1 = a.y, r1 = a.r;\n const x2 = b.x, y2 = b.y, r2 = b.r;\n const x3 = c.x, y3 = c.y, r3 = c.r;\n const a2 = x1 - x2;\n const a3 = x1 - x3;\n const b2 = y1 - y2;\n const b3 = y1 - y3;\n const c2 = r2 - r1;\n const c3 = r3 - r1;\n const d1 = x1 * x1 + y1 * y1 - r1 * r1;\n const d2 = d1 - x2 * x2 - y2 * y2 + r2 * r2;\n const d3 = d1 - x3 * x3 - y3 * y3 + r3 * r3;\n const ab = a3 * b2 - a2 * b3;\n const xa = (b2 * d3 - b3 * d2) / (ab * 2) - x1;\n const xb = (b3 * c2 - b2 * c3) / ab;\n const ya = (a3 * d2 - a2 * d3) / (ab * 2) - y1;\n const yb = (a2 * c3 - a3 * c2) / ab;\n const A = xb * xb + yb * yb - 1;\n const B = 2 * (r1 + xa * xb + ya * yb);\n const C = xa * xa + ya * ya - r1 * r1;\n const r = -(A ? (B + Math.sqrt(B * B - 4 * A * C)) / (2 * A) : C / B);\n return {\n x: x1 + xa + xb * r,\n y: y1 + ya + yb * r,\n r: r\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":321,"value":"### Extending a Basis\n\nNow let’s generalize from three circles to an arbitrary number of circles. In two dimensions, it’s not possible to have a basis of four or more circles, so we only need to consider bases of three or fewer.\n\nAssume we have a basis *B* that consists of zero, one, two or three circles, and represents the smallest enclosing circle for circles {*L*[*0*], … *L*[*i* - 1]}. We can compute the tangent circle for the basis *B* as follows:","pinned":false,"hidden":false,"mode":"md"},{"id":58,"value":"// Given a basis B, returns the enclosing circle.\nfunction encloseBasis(B) {\n switch (B.length) {\n case 1: return encloseBasis1(B[0]);\n case 2: return encloseBasis2(B[0], B[1]);\n case 3: return encloseBasis3(B[0], B[1], B[2]);\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1716,"value":"Next we test whether this tangent circle encloses the next circle, *p* = *L*[*i*]. If it does, then we can continue to use the basis *B*, and move on to the next circle. If it doesn’t, then we need to compute a new basis.\n\nThe most conservative new basis (the smallest increase from our previous basis *B*) considers only circles in *B* ∪ *p*; we’ll call this operation “extending” *B* to enclose *p*. Because *p* was outside the old enclosing circle, we know that the new basis must include *p*. We also know that the resulting basis must contain either one, two or three circles in total; so, there may be one or two circles from the old basis *B* that remain in the new basis. Thus, computing the new basis is simply a matter of testing each possible basis, starting with the simplest one-basis, {*p*}. In code:","pinned":false,"hidden":false,"mode":"md"},{"id":1723,"value":"// Given a basis B and a circle p ⊈ B, returns the new basis Bʹ.\nfunction extendBasis(B, p) {\n var i, j;\n\n if (enclosesWeakAll(p, B)) return [p];\n\n // If we get here then B must have at least one element.\n for (i = 0; i < B.length; ++i) {\n if (!encloses(p, B[i])\n && enclosesWeakAll(encloseBasis2(B[i], p), B)) {\n return [B[i], p];\n }\n }\n\n // If we get here then B must have at least two elements.\n for (i = 0; i < B.length - 1; ++i) {\n for (j = i + 1; j < B.length; ++j) {\n if (!encloses(encloseBasis2(B[i], B[j]), p)\n && !encloses(encloseBasis2(B[i], p), B[j])\n && !encloses(encloseBasis2(B[j], p), B[i])\n && enclosesWeakAll(encloseBasis3(B[i], B[j], p), B)) {\n return [B[i], B[j], p];\n }\n }\n }\n\n // If we get here then something is very wrong.\n throw new Error;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1725,"value":"Let’s look at examples of each of these three cases.","pinned":false,"hidden":false,"mode":"md"},{"id":1320,"value":"#### One-Basis\n\nIf *p* encloses every circle in *B* , {*p*} is the new basis. The old enclosing circle is replaced with *p*. If *B* is empty, {*p*} encloses it trivially.","pinned":false,"hidden":false,"mode":"md"},{"id":859,"value":"{\n var svg = d3.select(DOM.svg(width, height - 100))\n .datum([\n {\"x\":328,\"y\":85,\"r\":47},\n {\"x\":415,\"y\":182,\"r\":23},\n {\"x\":257,\"y\":218,\"r\":22},\n {\"x\":325,\"y\":138,\"r\":130,color:\"steelblue\"}\n ]);\n\n svg.append(\"g\")\n .attr(\"stroke\", \"black\")\n .attr(\"fill-opacity\", 0.1)\n .selectAll(\"circle\")\n .data(d => d)\n .enter().append(\"circle\")\n .attr(\"stroke\", d => d.color)\n .attr(\"fill\", d => d.color)\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"r\", d => d.r);\n\n svg.append(\"circle\")\n .datum(enclose(svg.datum().slice(0, 3)))\n .attr(\"stroke\", \"red\")\n .attr(\"fill\", \"none\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"r\", d => d.r);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":852,"value":"$24","pinned":false,"hidden":false,"mode":"md"},{"id":905,"value":"{\n var svg = d3.select(DOM.svg(width, height - 100))\n .datum([\n {\"x\":328,\"y\":85,\"r\":47},\n {\"x\":415,\"y\":182,\"r\":23},\n {\"x\":257,\"y\":218,\"r\":22},\n {\"x\":430,\"y\":105,\"r\":30,color:\"steelblue\"}\n ]);\n\n svg.append(\"circle\")\n .datum(enclose(svg.datum().slice(0, 3)))\n .attr(\"stroke\", \"red\")\n .attr(\"fill\", \"none\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"r\", d => d.r);\n\n svg.append(\"circle\")\n .datum(enclose(svg.datum()))\n .attr(\"stroke\", \"black\")\n .attr(\"fill\", \"none\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"r\", d => d.r);\n\n svg.append(\"g\")\n .attr(\"stroke\", \"black\")\n .attr(\"fill-opacity\", 0.1)\n .selectAll(\"circle\")\n .data(d => d)\n .enter().append(\"circle\")\n .attr(\"stroke\", d => d.color)\n .attr(\"fill\", d => d.color)\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"r\", d => d.r);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":853,"value":"#### Three-Basis\n\nIf no suitable one- or two-basis is found, there must be a three-basis {*B*[*i*], *B*[*j*], *p*} that encloses every circle in *B* . Below, *p* replaces a circle from *B* to form the new three-basis.","pinned":false,"hidden":false,"mode":"md"},{"id":921,"value":"{\n var svg = d3.select(DOM.svg(width, height - 100))\n .datum([\n {\"x\":328,\"y\":85,\"r\":47},\n {\"x\":415,\"y\":182,\"r\":23},\n {\"x\":257,\"y\":218,\"r\":22},\n {\"x\":430,\"y\":210,\"r\":30,color:\"steelblue\"}\n ]);\n\n svg.append(\"circle\")\n .datum(enclose(svg.datum().slice(0, 3)))\n .attr(\"stroke\", \"red\")\n .attr(\"fill\", \"none\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"r\", d => d.r);\n\n svg.append(\"circle\")\n .datum(enclose(svg.datum()))\n .attr(\"stroke\", \"black\")\n .attr(\"fill\", \"none\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"r\", d => d.r);\n\n svg.append(\"g\")\n .attr(\"stroke\", \"black\")\n .attr(\"fill-opacity\", 0.1)\n .selectAll(\"circle\")\n .data(d => d)\n .enter().append(\"circle\")\n .attr(\"stroke\", d => d.color)\n .attr(\"fill\", d => d.color)\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"r\", d => d.r);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":856,"value":"$25","pinned":false,"hidden":false,"mode":"md"},{"id":942,"value":"$26","pinned":false,"hidden":false,"mode":"ojs"},{"id":944,"value":"Fortunately, finding the new basis *B*ʹ is easy! We simply start over from the first circle each time we extend the basis by setting *i* back to zero:","pinned":false,"hidden":false,"mode":"md"},{"id":1739,"value":"function enclose(L) {\n var i = 0, n = d3.shuffle(L = L.slice()).length, B = [], p, e;\n\n while (i < n) {\n p = L[i];\n if (e && enclosesWeak(e, p)) ++i;\n else e = encloseBasis(B = extendBasis(B, p)), i = 0;\n }\n\n return e.basis = B, e;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1944,"value":"The algorithm must terminate because extending a basis always makes it bigger and there are only a finite number of possible bases in *L*.\n\nAnd that’s the [Matoušek-Sharir-Welzl algorithm](http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf)!","pinned":false,"hidden":false,"mode":"md"},{"id":387,"value":"---\n\n## Appendix\n\nMany thanks to [Robin Houston](https://github.com/robinhouston) for contributing an implementation of the MSW algorithm to [d3-hierarchy](https://d3js.org/d3-hierarchy) as [d3.packEnclose](https://d3js.org/d3-hierarchy/pack#packEnclose), and for reviewing this article. This article was previously published under the title “Miniball.”","pinned":false,"hidden":false,"mode":"md"},{"id":1817,"value":"function* encloseStar(L) {\n var i = 0, n = d3.shuffle(L = L.slice()).length, B = [], p, e;\n\n while (i < n) {\n p = L[i];\n yield {p: p, e: e, i: i, B: B, L: L.slice(0, i)};\n if (e && enclosesWeak(e, p)) ++i;\n else e = encloseBasis(B = extendBasis(B, p)), i = 0;\n }\n\n yield {e: e, i: i, B: B, L: L};\n return e;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1630,"value":"path = \"M0,-300l100,100h-50v150h150v-50L300,0l-100,100v-50h-150v150h50L0,300l-100,-100h50v-150h-150v50L-300,0l100,-100v50h150v-150h-50z\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":1940,"value":"width = 640","pinned":true,"hidden":false,"mode":"ojs"},{"id":10,"value":"height = 400","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W27","stdlib":"1"}