Skip to content

Instantly share code, notes, and snippets.

@mbostock

mbostock/.block

Last active April 23, 2020 23:35
Download ZIP

Revisions

  1. mbostock revised this gist Apr 23, 2020. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions .block
    View file
    Original file line number Diff line number Diff line change
    @@ -1,2 +1,3 @@
    license: gpl-3.0
    height: 960
    redirect: https://observablehq.com/@mbostock/rainbow-pack
  2. mbostock revised this gist May 3, 2016. 1 changed file with 4 additions and 10 deletions.
    14 changes: 4 additions & 10 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -13,7 +13,7 @@

    </style>
    <svg width="960" height="960"><g transform="translate(480,480)"></g></svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.34.min.js"></script>
    <script src="//d3js.org/d3.v4.0.0-alpha.35.min.js"></script>
    <script>

    var svg = d3.select("svg"),
    @@ -26,14 +26,13 @@

    var circles = d3.packSiblings(d3.range(2000)
    .map(d3.randomUniform(8, 26))
    .map(function(r) { return {r: r}; }));

    var envelope = d3.packEnclose(circles);
    .map(function(r) { return {r: r}; }))
    .filter(function(d) { return -500 < d.x && d.x < 500 && -500 < d.y && d.y < 500; });

    svg
    .select("g")
    .selectAll("circle")
    .data(circles.filter(offset))
    .data(circles)
    .enter().append("circle")
    .style("fill", function(d) { return color(d.angle = Math.atan2(d.y, d.x)); })
    .attr("cx", function(d) { return Math.cos(d.angle) * (size / Math.SQRT2 + 30); })
    @@ -46,9 +45,4 @@
    .attr("cx", function(d) { return d.x; })
    .attr("cy", function(d) { return d.y; });

    function offset(d) {
    d.x -= envelope.x, d.y -= envelope.y;
    return -500 < d.x && d.x < 500 && -500 < d.y && d.y < 500;
    }

    </script>
  3. mbostock revised this gist May 2, 2016. 1 changed file with 15 additions and 7 deletions.
    22 changes: 15 additions & 7 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -13,34 +13,42 @@

    </style>
    <svg width="960" height="960"><g transform="translate(480,480)"></g></svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.29.min.js"></script>
    <script src="//d3js.org/d3.v4.0.0-alpha.34.min.js"></script>
    <script>

    var svg = d3.select("svg"),
    size = +svg.attr("width");
    width = +svg.attr("width"),
    height = +svg.attr("height"),
    size = Math.max(width, height);

    var color = d3.scaleRainbow()
    .domain([0, 2 * Math.PI]);

    var circles = d3.range(2000)
    var circles = d3.packSiblings(d3.range(2000)
    .map(d3.randomUniform(8, 26))
    .map(function(r) { return {r: Math.max(1, r)}; });
    .map(function(r) { return {r: r}; }));

    var envelope = d3.packEnclose(circles);

    svg
    .select("g")
    .selectAll("circle")
    .data(d3.packSiblings(circles)
    .filter(function(d) { return -500 < d.x && d.x < 500 && -500 < d.y && d.y < 500; }))
    .data(circles.filter(offset))
    .enter().append("circle")
    .style("fill", function(d) { return color(d.angle = Math.atan2(d.y, d.x)); })
    .attr("cx", function(d) { return Math.cos(d.angle) * (size / Math.SQRT2 + 30); })
    .attr("cy", function(d) { return Math.sin(d.angle) * (size / Math.SQRT2 + 30); })
    .attr("r", function(d) { return d.r - 0.25; })
    .transition()
    .ease(d3.easeCubicOut)
    .delay(function(d, i) { return Math.sqrt(i) * 250; })
    .delay(function(d) { return Math.sqrt(d.x * d.x + d.y * d.y) * 10; })
    .duration(1000)
    .attr("cx", function(d) { return d.x; })
    .attr("cy", function(d) { return d.y; });

    function offset(d) {
    d.x -= envelope.x, d.y -= envelope.y;
    return -500 < d.x && d.x < 500 && -500 < d.y && d.y < 500;
    }

    </script>
  4. mbostock revised this gist Apr 5, 2016. 1 changed file with 2 additions and 3 deletions.
    5 changes: 2 additions & 3 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -13,8 +13,7 @@

    </style>
    <svg width="960" height="960"><g transform="translate(480,480)"></g></svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
    <script src="//d3js.org/d3-hierarchy.v0.2.min.js"></script>
    <script src="//d3js.org/d3.v4.0.0-alpha.29.min.js"></script>
    <script>

    var svg = d3.select("svg"),
    @@ -30,7 +29,7 @@
    svg
    .select("g")
    .selectAll("circle")
    .data(d3_hierarchy.packSiblings(circles)
    .data(d3.packSiblings(circles)
    .filter(function(d) { return -500 < d.x && d.x < 500 && -500 < d.y && d.y < 500; }))
    .enter().append("circle")
    .style("fill", function(d) { return color(d.angle = Math.atan2(d.y, d.x)); })
  5. mbostock revised this gist Apr 5, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -14,7 +14,7 @@
    </style>
    <svg width="960" height="960"><g transform="translate(480,480)"></g></svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
    <script src="//d3js.org/d3-hierarchy.v0.1.min.js"></script>
    <script src="//d3js.org/d3-hierarchy.v0.2.min.js"></script>
    <script>

    var svg = d3.select("svg"),
  6. mbostock revised this gist Mar 31, 2016. 2 changed files with 1 addition and 2 deletions.
    1 change: 0 additions & 1 deletion d3-hierarchy.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +0,0 @@
    !function(n,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function e(n){var e,r,t,i,u=this,o=[u];do for(e=o.reverse(),o=[];null!=(u=e.pop());)if(n(u),r=u.children)for(t=0,i=r.length;i>t;++t)o.push(r[t]);while(o.length);return this}function r(n){for(var e,r,t=this,i=[t];null!=(t=i.pop());)if(n(t),e=t.children)for(r=e.length-1;r>=0;--r)i.push(e[r]);return this}function t(n){for(var e,r,t,i=this,u=[i],o=[];null!=(i=u.pop());)if(o.push(i),e=i.children)for(r=0,t=e.length;t>r;++r)u.push(e[r]);for(;null!=(i=o.pop());)n(i);return this}function i(n){return this.eachAfter(function(e){for(var r=+n(e.data)||0,t=e.children,i=t&&t.length;--i>=0;)r+=t[i].value;e.value=r})}function u(n){return this.eachBefore(function(e){e.children&&e.children.sort(n)})}function o(){for(var n=this,e=[n];n=n.parent;)e.push(n);return e}function a(){var n=[];return this.each(function(e){n.push(e)}),n}function f(){var n=[];return this.eachBefore(function(e){e.children||n.push(e)}),n}function c(n){for(var e,r,t,i,u,o=new l(n),a=+n.value&&(o.value=n.value),f=[o];null!=(e=f.pop());)if(a&&(e.value=+e.data.value),(t=e.data.children)&&(u=t.length))for(e.children=new Array(u),i=u-1;i>=0;--i)f.push(r=e.children[i]=new l(t[i])),r.parent=e,r.depth=e.depth+1;return o}function h(){return c(this).eachBefore(function(n){n.data=n.data.data})}function l(n){this.data=n,this.depth=0,this.parent=null}function d(n){this._=n,this.next=null}function p(n){for(var e,r=(n=n.slice()).length,t=null,i=t;r;){var u=new d(n[r-1]);i=i?i.next=u:t=u,n[e]=n[--r]}return{head:t,tail:i}}function s(n){return x(p(n),[])}function v(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r-e.r;return i*i+1e-6>r*r+t*t}function x(n,e){var r,t,i,u=null,o=n.head;switch(e.length){case 1:r=e[0];break;case 2:r=y(e[0],e[1]);break;case 3:r=g(e[0],e[1],e[2])}for(;o;)i=o._,t=o.next,r&&v(r,i)?u=o:(u?(n.tail=u,u.next=null):n.head=n.tail=null,e.push(i),r=x(n,e),e.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),u=n.tail,u.next=t),o=t;return n.tail=u,r}function y(n,e){var r=n.x,t=n.y,i=n.r,u=e.x,o=e.y,a=e.r,f=u-r,c=o-t,h=a-i,l=Math.sqrt(f*f+c*c);return{x:(r+u+f/l*h)/2,y:(t+o+c/l*h)/2,r:(l+i+a)/2}}function g(n,e,r){var t=n.x,i=n.y,u=n.r,o=e.x,a=e.y,f=e.r,c=r.x,h=r.y,l=r.r,d=2*(t-o),p=2*(i-a),s=2*(f-u),v=t*t+i*i-u*u-o*o-a*a+f*f,x=2*(t-c),y=2*(i-h),g=2*(l-u),w=t*t+i*i-u*u-c*c-h*h+l*l,_=x*p-d*y,m=(p*w-y*v)/_-t,B=(y*s-p*g)/_,M=(x*v-d*w)/_-i,q=(d*g-x*s)/_,A=B*B+q*q-1,E=2*(m*B+M*q+u),k=m*m+M*M-u*u,b=(-E-Math.sqrt(E*E-4*A*k))/(2*A);return{x:m+B*b+t,y:M+q*b+i,r:b}}function w(n,e,r){var t=n.x,i=n.y,u=e.r+r.r,o=n.r+r.r,a=e.x-t,f=e.y-i,c=a*a+f*f;if(c){var h=.5+((o*=o)-(u*=u))/(2*c),l=Math.sqrt(Math.max(0,2*u*(o+c)-(o-=c)*o-u*u))/(2*c);r.x=t+h*a+l*f,r.y=i+h*f-l*a}else r.x=t+o,r.y=i}function _(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r+e.r;return i*i>r*r+t*t}function m(n){this._=n,this.next=null,this.previous=null,this.score=n.x*n.x+n.y*n.y}function B(n){if(!(c=n.length))return n;var e,r,t,i,u,o,a,f,c;if(e=n[0],e.x=e.r,e.y=0,!(c>1))return n;if(r=n[1],r.x=-r.r,r.y=0,!(c>2))return n;w(r,e,t=n[2]),e=new m(e),r=new m(r),t=new m(t),e.next=t.previous=r,r.next=e.previous=t,t.next=r.previous=e;n:for(i=3;c>i;++i){if(w(e._,r._,t=n[i]),t=new m(t),(o=e.previous)===(u=r.next)){if(_(u._,t._)){e=r,r=u,--i;continue n}}else{a=u._.r,f=o._.r;do if(f>=a){if(_(u._,t._)){r=u,e.next=r,r.previous=e,--i;continue n}u=u.next,a+=u._.r}else{if(_(o._,t._)){e=o,e.next=r,r.previous=e,--i;continue n}o=o.previous,f+=o._.r}while(u!==o.next)}for(t.previous=e,t.next=r,e.next=r.previous=r=t;(t=t.next)!==r;)t.score<e.score&&(e=t);r=e.next}return n}function M(n){return null==n?null:q(n)}function q(n){if("function"!=typeof n)throw new Error;return n}function A(n){return Math.sqrt(n.value)}function E(){function n(n){return n.x=r/2,n.y=t/2,e?n.eachBefore(k(e)).eachAfter(I(i/2)).eachBefore(S(1)):(n.eachBefore(k(A)).eachAfter(b),i&&n.eachAfter(I(i*n.r/Math.min(r,t))),n.eachBefore(S(Math.min(r,t)/(2*n.r)))),n}var e=null,r=1,t=1,i=0;return n.radius=function(r){return arguments.length?(e=M(r),n):e},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=Math.max(0,+e||0),n):i},n}function k(n){return function(e){e.children||(e.r=Math.max(0,+n(e)||0))}}function b(n){if(e=n.children){B(e);var e,r,t,i=s(e),u=e.length;for(t=0;u>t;++t)r=e[t],r.x-=i.x,r.y-=i.y;n.r=i.r}}function I(n){return function(e){if(r=e.children){var r,t,i=r.length;for(t=0;i>t;++t)r[t].r+=n;for(b(e),t=0;i>t;++t)r[t].r-=n;e.r+=n}}}function S(n){return function(e){var r=e.parent;e.r*=n,r&&(e.x=r.x+n*e.x,e.y=r.y+n*e.y)}}function z(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function T(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(t-e)/n.value;++a<f;)u=o[a],u.y0=r,u.y1=i,u.x0=e,u.x1=e+=u.value*c}function D(n){var e=0;return n.eachBefore(function(n){n.depth>e&&(e=n.depth)}),e}function L(){function n(n){var o=D(n)+1;return n.x0=n.y0=i,n.x1=r,n.y1=t/o,n.eachBefore(e(t,o)),u&&n.eachBefore(z),n}function e(n,e){return function(r){r.children&&T(r,r.x0,n*(r.depth+1)/e,r.x1,n*(r.depth+2)/e);var t=r.x0,u=r.y0,o=r.x1-i,a=r.y1-i;t>o&&(t=o=(t+o)/2),u>a&&(u=a=(u+a)/2),r.x0=t,r.y0=u,r.x1=o,r.y1=a}}var r=1,t=1,i=0,u=!1;return n.round=function(e){return arguments.length?(u=!!e,n):u},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=+e,n):i},n}function O(n){return n.id}function R(n){return n.parentId}function j(){function n(n){var t,i,u,o,a,f,c,h=n.length,d=new Array(h),p={};for(i=0;h>i;++i)if(t=n[i],a=d[i]=new l(t),null!=(f=e(t,i,n))&&(f+="")){if(c=U+(a.id=f),c in p)throw new Error("duplicate: "+f);p[c]=a}for(i=0;h>i;++i)if(a=d[i],f=r(n[i],i,n),null!=f&&(f+="")){if(o=p[U+f],!o)throw new Error("missing: "+f);o.children?o.children.push(a):o.children=[a],a.parent=o}else{if(u)throw new Error("multiple roots");u=a}if(!u)throw new Error("no root");if(u.parent=V,u.eachBefore(function(n){n.depth=n.parent.depth+1,--h}),u.parent=null,h>0)throw new Error("cycle");return u}var e=O,r=R;return n.id=function(r){return arguments.length?(e=q(r),n):e},n.parentId=function(e){return arguments.length?(r=q(e),n):r},n}function $(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(i-r)/n.value;++a<f;)u=o[a],u.x0=e,u.x1=t,u.y0=r,u.y1=r+=u.value*c}function C(n,e,r,t,i){for(var u,o,a,f,c=n._squarify,h=-1,l=c.length,d=n.value;++h<l;){for(u=c[h],o=u.children,a=u.value=0,f=o.length;f>a;++a)u.value+=o[a].value;u.dice?T(u,e,r,t,r+=(i-r)*u.value/d):$(u,e,r,e+=(t-e)*u.value/d,i),d-=u.value}}function F(){return 0}function G(n){return function(){return n}}function H(n){delete n._padding}function J(){function n(n){return r=a(n)/2,n.x0=-r,n.y0=-r,n.x1=u+r,n.y1=o+r,n.eachBefore(e).eachBefore(H),i&&n.eachBefore(z),n}function e(n){var e=n.parent?n.parent._padding:r,i=n.x0+e,u=n.y0+e,o=n.x1-e,d=n.y1-e;i>o&&(i=o=(i+o)/2),u>d&&(u=d=(u+d)/2),n.x0=i,n.y0=u,n.x1=o,n.y1=d,n.children&&(e=n._padding=a(n)/2,i+=l(n)-e,u+=f(n)-e,o-=c(n)-e,d-=h(n)-e,i>o&&(i=o=(i+o)/2),u>d&&(u=d=(u+d)/2),t(n,i,u,o,d))}var r,t=W,i=!1,u=1,o=1,a=F,f=F,c=F,h=F,l=F;return n.round=function(e){return arguments.length?(i=!!e,n):i},n.size=function(e){return arguments.length?(u=+e[0],o=+e[1],n):[u,o]},n.tile=function(e){return arguments.length?(t=q(e),n):t},n.padding=function(e){return arguments.length?n.paddingInner(e).paddingOuter(e):n.paddingInner()},n.paddingInner=function(e){return arguments.length?(a="function"==typeof e?e:G(+e),n):a},n.paddingOuter=function(e){return arguments.length?n.paddingTop(e).paddingRight(e).paddingBottom(e).paddingLeft(e):n.paddingTop()},n.paddingTop=function(e){return arguments.length?(f="function"==typeof e?e:G(+e),n):f},n.paddingRight=function(e){return arguments.length?(c="function"==typeof e?e:G(+e),n):c},n.paddingBottom=function(e){return arguments.length?(h="function"==typeof e?e:G(+e),n):h},n.paddingLeft=function(e){return arguments.length?(l="function"==typeof e?e:G(+e),n):l},n}function K(n,e,r,t,i){var u=n.children;N(u,0,u.length,n.value,e,r,t,i)}function N(n,e,r,t,i,u,o,a){if(e>=r-1)return n=n[e],n.x0=i,n.y0=u,n.x1=o,n.y1=a,void 0;var f=e,c=t/2,h=0;do h+=n[f].value;while(++f<r-1&&c>h);var l=t-h;if(a-u>o-i){var d=(u*l+a*h)/t;N(n,e,f,h,i,u,o,d),N(n,f,r,l,i,d,o,a)}else{var p=(i*l+o*h)/t;N(n,e,f,h,i,u,p,a),N(n,f,r,l,p,u,o,a)}}function P(n,e,r,t,i){(1&n.depth?$:T)(n,e,r,t,i)}var Q="0.0.2";l.prototype=c.prototype={constructor:l,each:e,eachAfter:t,eachBefore:r,sum:i,sort:u,ancestors:o,descendants:a,leaves:f,copy:h};var U="$",V={depth:-1},W=function X(n){function e(e,r,t,i,u){if(e._squarify)return C(e,r,t,i,u);for(var o,a,f,c,h,l,d,p,s,v,x,y,g=e._squarify=[],w=e.children,_=0,m=w.length,B=e.value;m>_;){for(c=i-r,h=u-t,d=p=l=w[_].value,x=Math.max(h/c,c/h)/(B*n),y=l*l*x,v=Math.max(p/y,y/d),f=_+1;m>f;++f){if(l+=a=w[f].value,d>a&&(d=a),a>p&&(p=a),y=l*l*x,s=Math.max(p/y,y/d),s>v){l-=a;break}v=s}g.push(o={value:l,dice:h>c,children:w.slice(_,f)}),o.dice?T(o,r,t,i,t+=h*l/B):$(o,r,t,r+=c*l/B,u),B-=l,_=f}}return e.ratio=function(n){return X((n=+n)>1?n:1)},e}((1+Math.sqrt(5))/2,!1);n.version=Q,n.hierarchy=c,n.pack=E,n.packSiblings=B,n.packEnclose=s,n.partition=L,n.stratify=j,n.treemap=J,n.treemapBinary=K,n.treemapDice=T,n.treemapSlice=$,n.treemapSliceDice=P,n.treemapSquarify=W});
    2 changes: 1 addition & 1 deletion index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -14,7 +14,7 @@
    </style>
    <svg width="960" height="960"><g transform="translate(480,480)"></g></svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
    <script src="d3-hierarchy.min.js"></script>
    <script src="//d3js.org/d3-hierarchy.v0.1.min.js"></script>
    <script>

    var svg = d3.select("svg"),
  7. mbostock revised this gist Mar 30, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion d3-hierarchy.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    !function(n,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function e(n){var e,r,t,i,u=this,o=[u];do for(e=o.reverse(),o=[];null!=(u=e.pop());)if(n(u),r=u.children)for(t=0,i=r.length;i>t;++t)o.push(r[t]);while(o.length);return this}function r(n){for(var e,r,t=this,i=[t];null!=(t=i.pop());)if(n(t),e=t.children)for(r=e.length-1;r>=0;--r)i.push(e[r]);return this}function t(n){for(var e,r,t,i=this,u=[i],o=[];null!=(i=u.pop());)if(o.push(i),e=i.children)for(r=0,t=e.length;t>r;++r)u.push(e[r]);for(;null!=(i=o.pop());)n(i);return this}function i(n){return this.eachAfter(function(e){for(var r=+n(e.data)||0,t=e.children,i=t&&t.length;--i>=0;)r+=t[i].value;e.value=r})}function u(n){return this.eachBefore(function(e){e.children&&e.children.sort(n)})}function o(){for(var n=this,e=[n];n=n.parent;)e.push(n);return e}function a(){var n=[];return this.each(function(e){n.push(e)}),n}function f(){var n=[];return this.eachBefore(function(e){e.children||n.push(e)}),n}function c(n){for(var e,r,t,i,u,o=new l(n),a=+n.value&&(o.value=n.value),f=[o];null!=(e=f.pop());)if(a&&(e.value=+e.data.value),(t=e.data.children)&&(u=t.length))for(e.children=new Array(u),i=u-1;i>=0;--i)f.push(r=e.children[i]=new l(t[i])),r.parent=e,r.depth=e.depth+1;return o}function h(){return c(this).eachBefore(function(n){n.data=n.data.data})}function l(n){this.data=n,this.depth=0,this.parent=null}function d(n){this._=n,this.next=null}function p(n){for(var e,r=(n=n.slice()).length,t=null,i=t;r;){var u=new d(n[r-1]);i=i?i.next=u:t=u,n[e]=n[--r]}return{head:t,tail:i}}function s(n){return x(p(n),[])}function v(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r-e.r;return i*i+1e-6>r*r+t*t}function x(n,e){var r,t,i,u=null,o=n.head;switch(e.length){case 1:r=e[0];break;case 2:r=y(e[0],e[1]);break;case 3:r=g(e[0],e[1],e[2])}for(;o;)i=o._,t=o.next,r&&v(r,i)?u=o:(u?(n.tail=u,u.next=null):n.head=n.tail=null,e.push(i),r=x(n,e),e.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),u=n.tail,u.next=t),o=t;return n.tail=u,r}function y(n,e){var r=n.x,t=n.y,i=n.r,u=e.x,o=e.y,a=e.r,f=u-r,c=o-t,h=a-i,l=Math.sqrt(f*f+c*c);return{x:(r+u+f/l*h)/2,y:(t+o+c/l*h)/2,r:(l+i+a)/2}}function g(n,e,r){var t=n.x,i=n.y,u=n.r,o=e.x,a=e.y,f=e.r,c=r.x,h=r.y,l=r.r,d=2*(t-o),p=2*(i-a),s=2*(f-u),v=t*t+i*i-u*u-o*o-a*a+f*f,x=2*(t-c),y=2*(i-h),g=2*(l-u),w=t*t+i*i-u*u-c*c-h*h+l*l,_=x*p-d*y,m=(p*w-y*v)/_-t,B=(y*s-p*g)/_,M=(x*v-d*w)/_-i,q=(d*g-x*s)/_,A=B*B+q*q-1,E=2*(m*B+M*q+u),k=m*m+M*M-u*u,b=(-E-Math.sqrt(E*E-4*A*k))/(2*A);return{x:m+B*b+t,y:M+q*b+i,r:b}}function w(n,e,r){var t=n.x,i=n.y,u=e.r+r.r,o=n.r+r.r,a=e.x-t,f=e.y-i,c=a*a+f*f;if(c){var h=.5+((o*=o)-(u*=u))/(2*c),l=Math.sqrt(Math.max(0,2*u*(o+c)-(o-=c)*o-u*u))/(2*c);r.x=t+h*a+l*f,r.y=i+h*f-l*a}else r.x=t+o,r.y=i}function _(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r+e.r;return i*i>r*r+t*t}function m(n){this._=n,this.next=null,this.previous=null,this.score=n.x*n.x+n.y*n.y}function B(n){if(!(c=n.length))return n;var e,r,t,i,u,o,a,f,c;if(e=n[0],e.x=e.r,e.y=0,!(c>1))return n;if(r=n[1],r.x=-r.r,r.y=0,!(c>2))return n;w(r,e,t=n[2]),e=new m(e),r=new m(r),t=new m(t),e.next=t.previous=r,r.next=e.previous=t,t.next=r.previous=e;n:for(i=3;c>i;++i){if(w(e._,r._,t=n[i]),t=new m(t),(o=e.previous)===(u=r.next)){if(_(u._,t._)){e=r,r=u,--i;continue n}}else{a=u._.r,f=o._.r;do if(f>=a){if(_(u._,t._)){r=u,e.next=r,r.previous=e,--i;continue n}u=u.next,a+=u._.r}else{if(_(o._,t._)){e=o,e.next=r,r.previous=e,--i;continue n}o=o.previous,f+=o._.r}while(u!==o.next)}for(t.previous=e,t.next=r,e.next=r.previous=r=t;(t=t.next)!==r;)t.score<e.score&&(e=t,r=e.next)}return n}function M(n){return null==n?null:q(n)}function q(n){if("function"!=typeof n)throw new Error;return n}function A(n){return Math.sqrt(n.value)}function E(){function n(n){return n.x=r/2,n.y=t/2,e?n.eachBefore(k(e)).eachAfter(I(i/2)).eachBefore(S(1)):(n.eachBefore(k(A)).eachAfter(b),i&&n.eachAfter(I(i*n.r/Math.min(r,t))),n.eachBefore(S(Math.min(r,t)/(2*n.r)))),n}var e=null,r=1,t=1,i=0;return n.radius=function(r){return arguments.length?(e=M(r),n):e},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=Math.max(0,+e||0),n):i},n}function k(n){return function(e){e.children||(e.r=Math.max(0,+n(e)||0))}}function b(n){if(e=n.children){B(e);var e,r,t,i=s(e),u=e.length;for(t=0;u>t;++t)r=e[t],r.x-=i.x,r.y-=i.y;n.r=i.r}}function I(n){return function(e){if(r=e.children){var r,t,i=r.length;for(t=0;i>t;++t)r[t].r+=n;for(b(e),t=0;i>t;++t)r[t].r-=n;e.r+=n}}}function S(n){return function(e){var r=e.parent;e.r*=n,r&&(e.x=r.x+n*e.x,e.y=r.y+n*e.y)}}function z(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function T(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(t-e)/n.value;++a<f;)u=o[a],u.y0=r,u.y1=i,u.x0=e,u.x1=e+=u.value*c}function D(n){var e=0;return n.eachBefore(function(n){n.depth>e&&(e=n.depth)}),e}function L(){function n(n){var o=D(n)+1;return n.x0=n.y0=i,n.x1=r,n.y1=t/o,n.eachBefore(e(t,o)),u&&n.eachBefore(z),n}function e(n,e){return function(r){r.children&&T(r,r.x0,n*(r.depth+1)/e,r.x1,n*(r.depth+2)/e);var t=r.x0,u=r.y0,o=r.x1-i,a=r.y1-i;t>o&&(t=o=(t+o)/2),u>a&&(u=a=(u+a)/2),r.x0=t,r.y0=u,r.x1=o,r.y1=a}}var r=1,t=1,i=0,u=!1;return n.round=function(e){return arguments.length?(u=!!e,n):u},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=+e,n):i},n}function O(n){return n.id}function R(n){return n.parentId}function j(){function n(n){var t,i,u,o,a,f,c,h=n.length,d=new Array(h),p={};for(i=0;h>i;++i)if(t=n[i],a=d[i]=new l(t),null!=(f=e(t,i,n))&&(f+="")){if(c=U+(a.id=f),c in p)throw new Error("duplicate: "+f);p[c]=a}for(i=0;h>i;++i)if(a=d[i],f=r(n[i],i,n),null!=f&&(f+="")){if(o=p[U+f],!o)throw new Error("missing: "+f);o.children?o.children.push(a):o.children=[a],a.parent=o}else{if(u)throw new Error("multiple roots");u=a}if(!u)throw new Error("no root");if(u.parent=V,u.eachBefore(function(n){n.depth=n.parent.depth+1,--h}),u.parent=null,h>0)throw new Error("cycle");return u}var e=O,r=R;return n.id=function(r){return arguments.length?(e=q(r),n):e},n.parentId=function(e){return arguments.length?(r=q(e),n):r},n}function $(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(i-r)/n.value;++a<f;)u=o[a],u.x0=e,u.x1=t,u.y0=r,u.y1=r+=u.value*c}function C(n,e,r,t,i){for(var u,o,a,f,c=n._squarify,h=-1,l=c.length,d=n.value;++h<l;){for(u=c[h],o=u.children,a=u.value=0,f=o.length;f>a;++a)u.value+=o[a].value;u.dice?T(u,e,r,t,r+=(i-r)*u.value/d):$(u,e,r,e+=(t-e)*u.value/d,i),d-=u.value}}function F(){return 0}function G(n){return function(){return n}}function H(n){delete n._padding}function J(){function n(n){return r=a(n)/2,n.x0=-r,n.y0=-r,n.x1=u+r,n.y1=o+r,n.eachBefore(e).eachBefore(H),i&&n.eachBefore(z),n}function e(n){var e=n.parent?n.parent._padding:r,i=n.x0+e,u=n.y0+e,o=n.x1-e,d=n.y1-e;i>o&&(i=o=(i+o)/2),u>d&&(u=d=(u+d)/2),n.x0=i,n.y0=u,n.x1=o,n.y1=d,n.children&&(e=n._padding=a(n)/2,i+=l(n)-e,u+=f(n)-e,o-=c(n)-e,d-=h(n)-e,i>o&&(i=o=(i+o)/2),u>d&&(u=d=(u+d)/2),t(n,i,u,o,d))}var r,t=W,i=!1,u=1,o=1,a=F,f=F,c=F,h=F,l=F;return n.round=function(e){return arguments.length?(i=!!e,n):i},n.size=function(e){return arguments.length?(u=+e[0],o=+e[1],n):[u,o]},n.tile=function(e){return arguments.length?(t=q(e),n):t},n.padding=function(e){return arguments.length?n.paddingInner(e).paddingOuter(e):n.paddingInner()},n.paddingInner=function(e){return arguments.length?(a="function"==typeof e?e:G(+e),n):a},n.paddingOuter=function(e){return arguments.length?n.paddingTop(e).paddingRight(e).paddingBottom(e).paddingLeft(e):n.paddingTop()},n.paddingTop=function(e){return arguments.length?(f="function"==typeof e?e:G(+e),n):f},n.paddingRight=function(e){return arguments.length?(c="function"==typeof e?e:G(+e),n):c},n.paddingBottom=function(e){return arguments.length?(h="function"==typeof e?e:G(+e),n):h},n.paddingLeft=function(e){return arguments.length?(l="function"==typeof e?e:G(+e),n):l},n}function K(n,e,r,t,i){var u=n.children;N(u,0,u.length,n.value,e,r,t,i)}function N(n,e,r,t,i,u,o,a){if(e>=r-1)return n=n[e],n.x0=i,n.y0=u,n.x1=o,n.y1=a,void 0;var f=e,c=t/2,h=0;do h+=n[f].value;while(++f<r-1&&c>h);var l=t-h;if(a-u>o-i){var d=(u*l+a*h)/t;N(n,e,f,h,i,u,o,d),N(n,f,r,l,i,d,o,a)}else{var p=(i*l+o*h)/t;N(n,e,f,h,i,u,p,a),N(n,f,r,l,p,u,o,a)}}function P(n,e,r,t,i){(1&n.depth?$:T)(n,e,r,t,i)}var Q="0.0.2";l.prototype=c.prototype={constructor:l,each:e,eachAfter:t,eachBefore:r,sum:i,sort:u,ancestors:o,descendants:a,leaves:f,copy:h};var U="$",V={depth:-1},W=function X(n){function e(e,r,t,i,u){if(e._squarify)return C(e,r,t,i,u);for(var o,a,f,c,h,l,d,p,s,v,x,y,g=e._squarify=[],w=e.children,_=0,m=w.length,B=e.value;m>_;){for(c=i-r,h=u-t,d=p=l=w[_].value,x=Math.max(h/c,c/h)/(B*n),y=l*l*x,v=Math.max(p/y,y/d),f=_+1;m>f;++f){if(l+=a=w[f].value,d>a&&(d=a),a>p&&(p=a),y=l*l*x,s=Math.max(p/y,y/d),s>v){l-=a;break}v=s}g.push(o={value:l,dice:h>c,children:w.slice(_,f)}),o.dice?T(o,r,t,i,t+=h*l/B):$(o,r,t,r+=c*l/B,u),B-=l,_=f}}return e.ratio=function(n){return X((n=+n)>1?n:1)},e}((1+Math.sqrt(5))/2,!1);n.version=Q,n.hierarchy=c,n.pack=E,n.packSiblings=B,n.packEnclose=s,n.partition=L,n.stratify=j,n.treemap=J,n.treemapBinary=K,n.treemapDice=T,n.treemapSlice=$,n.treemapSliceDice=P,n.treemapSquarify=W});
    !function(n,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function e(n){var e,r,t,i,u=this,o=[u];do for(e=o.reverse(),o=[];null!=(u=e.pop());)if(n(u),r=u.children)for(t=0,i=r.length;i>t;++t)o.push(r[t]);while(o.length);return this}function r(n){for(var e,r,t=this,i=[t];null!=(t=i.pop());)if(n(t),e=t.children)for(r=e.length-1;r>=0;--r)i.push(e[r]);return this}function t(n){for(var e,r,t,i=this,u=[i],o=[];null!=(i=u.pop());)if(o.push(i),e=i.children)for(r=0,t=e.length;t>r;++r)u.push(e[r]);for(;null!=(i=o.pop());)n(i);return this}function i(n){return this.eachAfter(function(e){for(var r=+n(e.data)||0,t=e.children,i=t&&t.length;--i>=0;)r+=t[i].value;e.value=r})}function u(n){return this.eachBefore(function(e){e.children&&e.children.sort(n)})}function o(){for(var n=this,e=[n];n=n.parent;)e.push(n);return e}function a(){var n=[];return this.each(function(e){n.push(e)}),n}function f(){var n=[];return this.eachBefore(function(e){e.children||n.push(e)}),n}function c(n){for(var e,r,t,i,u,o=new l(n),a=+n.value&&(o.value=n.value),f=[o];null!=(e=f.pop());)if(a&&(e.value=+e.data.value),(t=e.data.children)&&(u=t.length))for(e.children=new Array(u),i=u-1;i>=0;--i)f.push(r=e.children[i]=new l(t[i])),r.parent=e,r.depth=e.depth+1;return o}function h(){return c(this).eachBefore(function(n){n.data=n.data.data})}function l(n){this.data=n,this.depth=0,this.parent=null}function d(n){this._=n,this.next=null}function p(n){for(var e,r=(n=n.slice()).length,t=null,i=t;r;){var u=new d(n[r-1]);i=i?i.next=u:t=u,n[e]=n[--r]}return{head:t,tail:i}}function s(n){return x(p(n),[])}function v(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r-e.r;return i*i+1e-6>r*r+t*t}function x(n,e){var r,t,i,u=null,o=n.head;switch(e.length){case 1:r=e[0];break;case 2:r=y(e[0],e[1]);break;case 3:r=g(e[0],e[1],e[2])}for(;o;)i=o._,t=o.next,r&&v(r,i)?u=o:(u?(n.tail=u,u.next=null):n.head=n.tail=null,e.push(i),r=x(n,e),e.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),u=n.tail,u.next=t),o=t;return n.tail=u,r}function y(n,e){var r=n.x,t=n.y,i=n.r,u=e.x,o=e.y,a=e.r,f=u-r,c=o-t,h=a-i,l=Math.sqrt(f*f+c*c);return{x:(r+u+f/l*h)/2,y:(t+o+c/l*h)/2,r:(l+i+a)/2}}function g(n,e,r){var t=n.x,i=n.y,u=n.r,o=e.x,a=e.y,f=e.r,c=r.x,h=r.y,l=r.r,d=2*(t-o),p=2*(i-a),s=2*(f-u),v=t*t+i*i-u*u-o*o-a*a+f*f,x=2*(t-c),y=2*(i-h),g=2*(l-u),w=t*t+i*i-u*u-c*c-h*h+l*l,_=x*p-d*y,m=(p*w-y*v)/_-t,B=(y*s-p*g)/_,M=(x*v-d*w)/_-i,q=(d*g-x*s)/_,A=B*B+q*q-1,E=2*(m*B+M*q+u),k=m*m+M*M-u*u,b=(-E-Math.sqrt(E*E-4*A*k))/(2*A);return{x:m+B*b+t,y:M+q*b+i,r:b}}function w(n,e,r){var t=n.x,i=n.y,u=e.r+r.r,o=n.r+r.r,a=e.x-t,f=e.y-i,c=a*a+f*f;if(c){var h=.5+((o*=o)-(u*=u))/(2*c),l=Math.sqrt(Math.max(0,2*u*(o+c)-(o-=c)*o-u*u))/(2*c);r.x=t+h*a+l*f,r.y=i+h*f-l*a}else r.x=t+o,r.y=i}function _(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r+e.r;return i*i>r*r+t*t}function m(n){this._=n,this.next=null,this.previous=null,this.score=n.x*n.x+n.y*n.y}function B(n){if(!(c=n.length))return n;var e,r,t,i,u,o,a,f,c;if(e=n[0],e.x=e.r,e.y=0,!(c>1))return n;if(r=n[1],r.x=-r.r,r.y=0,!(c>2))return n;w(r,e,t=n[2]),e=new m(e),r=new m(r),t=new m(t),e.next=t.previous=r,r.next=e.previous=t,t.next=r.previous=e;n:for(i=3;c>i;++i){if(w(e._,r._,t=n[i]),t=new m(t),(o=e.previous)===(u=r.next)){if(_(u._,t._)){e=r,r=u,--i;continue n}}else{a=u._.r,f=o._.r;do if(f>=a){if(_(u._,t._)){r=u,e.next=r,r.previous=e,--i;continue n}u=u.next,a+=u._.r}else{if(_(o._,t._)){e=o,e.next=r,r.previous=e,--i;continue n}o=o.previous,f+=o._.r}while(u!==o.next)}for(t.previous=e,t.next=r,e.next=r.previous=r=t;(t=t.next)!==r;)t.score<e.score&&(e=t);r=e.next}return n}function M(n){return null==n?null:q(n)}function q(n){if("function"!=typeof n)throw new Error;return n}function A(n){return Math.sqrt(n.value)}function E(){function n(n){return n.x=r/2,n.y=t/2,e?n.eachBefore(k(e)).eachAfter(I(i/2)).eachBefore(S(1)):(n.eachBefore(k(A)).eachAfter(b),i&&n.eachAfter(I(i*n.r/Math.min(r,t))),n.eachBefore(S(Math.min(r,t)/(2*n.r)))),n}var e=null,r=1,t=1,i=0;return n.radius=function(r){return arguments.length?(e=M(r),n):e},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=Math.max(0,+e||0),n):i},n}function k(n){return function(e){e.children||(e.r=Math.max(0,+n(e)||0))}}function b(n){if(e=n.children){B(e);var e,r,t,i=s(e),u=e.length;for(t=0;u>t;++t)r=e[t],r.x-=i.x,r.y-=i.y;n.r=i.r}}function I(n){return function(e){if(r=e.children){var r,t,i=r.length;for(t=0;i>t;++t)r[t].r+=n;for(b(e),t=0;i>t;++t)r[t].r-=n;e.r+=n}}}function S(n){return function(e){var r=e.parent;e.r*=n,r&&(e.x=r.x+n*e.x,e.y=r.y+n*e.y)}}function z(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function T(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(t-e)/n.value;++a<f;)u=o[a],u.y0=r,u.y1=i,u.x0=e,u.x1=e+=u.value*c}function D(n){var e=0;return n.eachBefore(function(n){n.depth>e&&(e=n.depth)}),e}function L(){function n(n){var o=D(n)+1;return n.x0=n.y0=i,n.x1=r,n.y1=t/o,n.eachBefore(e(t,o)),u&&n.eachBefore(z),n}function e(n,e){return function(r){r.children&&T(r,r.x0,n*(r.depth+1)/e,r.x1,n*(r.depth+2)/e);var t=r.x0,u=r.y0,o=r.x1-i,a=r.y1-i;t>o&&(t=o=(t+o)/2),u>a&&(u=a=(u+a)/2),r.x0=t,r.y0=u,r.x1=o,r.y1=a}}var r=1,t=1,i=0,u=!1;return n.round=function(e){return arguments.length?(u=!!e,n):u},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=+e,n):i},n}function O(n){return n.id}function R(n){return n.parentId}function j(){function n(n){var t,i,u,o,a,f,c,h=n.length,d=new Array(h),p={};for(i=0;h>i;++i)if(t=n[i],a=d[i]=new l(t),null!=(f=e(t,i,n))&&(f+="")){if(c=U+(a.id=f),c in p)throw new Error("duplicate: "+f);p[c]=a}for(i=0;h>i;++i)if(a=d[i],f=r(n[i],i,n),null!=f&&(f+="")){if(o=p[U+f],!o)throw new Error("missing: "+f);o.children?o.children.push(a):o.children=[a],a.parent=o}else{if(u)throw new Error("multiple roots");u=a}if(!u)throw new Error("no root");if(u.parent=V,u.eachBefore(function(n){n.depth=n.parent.depth+1,--h}),u.parent=null,h>0)throw new Error("cycle");return u}var e=O,r=R;return n.id=function(r){return arguments.length?(e=q(r),n):e},n.parentId=function(e){return arguments.length?(r=q(e),n):r},n}function $(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(i-r)/n.value;++a<f;)u=o[a],u.x0=e,u.x1=t,u.y0=r,u.y1=r+=u.value*c}function C(n,e,r,t,i){for(var u,o,a,f,c=n._squarify,h=-1,l=c.length,d=n.value;++h<l;){for(u=c[h],o=u.children,a=u.value=0,f=o.length;f>a;++a)u.value+=o[a].value;u.dice?T(u,e,r,t,r+=(i-r)*u.value/d):$(u,e,r,e+=(t-e)*u.value/d,i),d-=u.value}}function F(){return 0}function G(n){return function(){return n}}function H(n){delete n._padding}function J(){function n(n){return r=a(n)/2,n.x0=-r,n.y0=-r,n.x1=u+r,n.y1=o+r,n.eachBefore(e).eachBefore(H),i&&n.eachBefore(z),n}function e(n){var e=n.parent?n.parent._padding:r,i=n.x0+e,u=n.y0+e,o=n.x1-e,d=n.y1-e;i>o&&(i=o=(i+o)/2),u>d&&(u=d=(u+d)/2),n.x0=i,n.y0=u,n.x1=o,n.y1=d,n.children&&(e=n._padding=a(n)/2,i+=l(n)-e,u+=f(n)-e,o-=c(n)-e,d-=h(n)-e,i>o&&(i=o=(i+o)/2),u>d&&(u=d=(u+d)/2),t(n,i,u,o,d))}var r,t=W,i=!1,u=1,o=1,a=F,f=F,c=F,h=F,l=F;return n.round=function(e){return arguments.length?(i=!!e,n):i},n.size=function(e){return arguments.length?(u=+e[0],o=+e[1],n):[u,o]},n.tile=function(e){return arguments.length?(t=q(e),n):t},n.padding=function(e){return arguments.length?n.paddingInner(e).paddingOuter(e):n.paddingInner()},n.paddingInner=function(e){return arguments.length?(a="function"==typeof e?e:G(+e),n):a},n.paddingOuter=function(e){return arguments.length?n.paddingTop(e).paddingRight(e).paddingBottom(e).paddingLeft(e):n.paddingTop()},n.paddingTop=function(e){return arguments.length?(f="function"==typeof e?e:G(+e),n):f},n.paddingRight=function(e){return arguments.length?(c="function"==typeof e?e:G(+e),n):c},n.paddingBottom=function(e){return arguments.length?(h="function"==typeof e?e:G(+e),n):h},n.paddingLeft=function(e){return arguments.length?(l="function"==typeof e?e:G(+e),n):l},n}function K(n,e,r,t,i){var u=n.children;N(u,0,u.length,n.value,e,r,t,i)}function N(n,e,r,t,i,u,o,a){if(e>=r-1)return n=n[e],n.x0=i,n.y0=u,n.x1=o,n.y1=a,void 0;var f=e,c=t/2,h=0;do h+=n[f].value;while(++f<r-1&&c>h);var l=t-h;if(a-u>o-i){var d=(u*l+a*h)/t;N(n,e,f,h,i,u,o,d),N(n,f,r,l,i,d,o,a)}else{var p=(i*l+o*h)/t;N(n,e,f,h,i,u,p,a),N(n,f,r,l,p,u,o,a)}}function P(n,e,r,t,i){(1&n.depth?$:T)(n,e,r,t,i)}var Q="0.0.2";l.prototype=c.prototype={constructor:l,each:e,eachAfter:t,eachBefore:r,sum:i,sort:u,ancestors:o,descendants:a,leaves:f,copy:h};var U="$",V={depth:-1},W=function X(n){function e(e,r,t,i,u){if(e._squarify)return C(e,r,t,i,u);for(var o,a,f,c,h,l,d,p,s,v,x,y,g=e._squarify=[],w=e.children,_=0,m=w.length,B=e.value;m>_;){for(c=i-r,h=u-t,d=p=l=w[_].value,x=Math.max(h/c,c/h)/(B*n),y=l*l*x,v=Math.max(p/y,y/d),f=_+1;m>f;++f){if(l+=a=w[f].value,d>a&&(d=a),a>p&&(p=a),y=l*l*x,s=Math.max(p/y,y/d),s>v){l-=a;break}v=s}g.push(o={value:l,dice:h>c,children:w.slice(_,f)}),o.dice?T(o,r,t,i,t+=h*l/B):$(o,r,t,r+=c*l/B,u),B-=l,_=f}}return e.ratio=function(n){return X((n=+n)>1?n:1)},e}((1+Math.sqrt(5))/2,!1);n.version=Q,n.hierarchy=c,n.pack=E,n.packSiblings=B,n.packEnclose=s,n.partition=L,n.stratify=j,n.treemap=J,n.treemapBinary=K,n.treemapDice=T,n.treemapSlice=$,n.treemapSliceDice=P,n.treemapSquarify=W});
  8. mbostock revised this gist Mar 30, 2016. 2 changed files with 8 additions and 12 deletions.
    2 changes: 1 addition & 1 deletion d3-hierarchy.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    !function(n,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function e(n){var e,r,t,i,u=this,o=[u];do for(e=o.reverse(),o=[];null!=(u=e.pop());)if(n(u),r=u.children)for(t=0,i=r.length;i>t;++t)o.push(r[t]);while(o.length);return this}function r(n){for(var e,r,t=this,i=[t];null!=(t=i.pop());)if(n(t),e=t.children)for(r=e.length-1;r>=0;--r)i.push(e[r]);return this}function t(n){for(var e,r,t,i=this,u=[i],o=[];null!=(i=u.pop());)if(o.push(i),e=i.children)for(r=0,t=e.length;t>r;++r)u.push(e[r]);for(;null!=(i=o.pop());)n(i);return this}function i(n){return this.eachAfter(function(e){for(var r=+n(e.data)||0,t=e.children,i=t&&t.length;--i>=0;)r+=t[i].value;e.value=r})}function u(n){return this.eachBefore(function(e){e.children&&e.children.sort(n)})}function o(){for(var n=this,e=[n];n=n.parent;)e.push(n);return e}function a(){var n=[];return this.each(function(e){n.push(e)}),n}function f(){var n=[];return this.eachBefore(function(e){e.children||n.push(e)}),n}function c(n){for(var e,r,t,i,u,o=new l(n),a=+n.value&&(o.value=n.value),f=[o];null!=(e=f.pop());)if(a&&(e.value=+e.data.value),(t=e.data.children)&&(u=t.length))for(e.children=new Array(u),i=u-1;i>=0;--i)f.push(r=e.children[i]=new l(t[i])),r.parent=e,r.depth=e.depth+1;return o}function h(){return c(this).eachBefore(function(n){n.data=n.data.data})}function l(n){this.data=n,this.depth=0,this.parent=null}function d(n){this._=n,this.next=null}function p(n){for(var e,r=(n=n.slice()).length,t=null,i=t;r;){var u=new d(n[r-1]);i=i?i.next=u:t=u,n[e]=n[--r]}return{head:t,tail:i}}function s(n){return x(p(n),[])}function v(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r-e.r;return i*i+1e-6>r*r+t*t}function x(n,e){var r,t,i,u=null,o=n.head;switch(e.length){case 1:r=e[0];break;case 2:r=y(e[0],e[1]);break;case 3:r=g(e[0],e[1],e[2])}for(;o;)i=o._,t=o.next,r&&v(r,i)?u=o:(u?(n.tail=u,u.next=null):n.head=n.tail=null,e.push(i),r=x(n,e),e.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),u=n.tail,u.next=t),o=t;return n.tail=u,r}function y(n,e){var r=n.x,t=n.y,i=n.r,u=e.x,o=e.y,a=e.r,f=u-r,c=o-t,h=a-i,l=Math.sqrt(f*f+c*c);return{x:(r+u+f/l*h)/2,y:(t+o+c/l*h)/2,r:(l+i+a)/2}}function g(n,e,r){var t=n.x,i=n.y,u=n.r,o=e.x,a=e.y,f=e.r,c=r.x,h=r.y,l=r.r,d=2*(t-o),p=2*(i-a),s=2*(f-u),v=t*t+i*i-u*u-o*o-a*a+f*f,x=2*(t-c),y=2*(i-h),g=2*(l-u),w=t*t+i*i-u*u-c*c-h*h+l*l,m=x*p-d*y,_=(p*w-y*v)/m-t,B=(y*s-p*g)/m,M=(x*v-d*w)/m-i,q=(d*g-x*s)/m,A=B*B+q*q-1,E=2*(_*B+M*q+u),I=_*_+M*M-u*u,b=(-E-Math.sqrt(E*E-4*A*I))/(2*A);return{x:_+B*b+t,y:M+q*b+i,r:b}}function w(n,e,r){var t=n.x,i=n.y,u=e.r+r.r,o=n.r+r.r,a=e.x-t,f=e.y-i,c=a*a+f*f;if(c){var h=.5+((o*=o)-(u*=u))/(2*c),l=Math.sqrt(Math.max(0,2*u*(o+c)-(o-=c)*o-u*u))/(2*c);r.x=t+h*a+l*f,r.y=i+h*f-l*a}else r.x=t+o,r.y=i}function m(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r+e.r;return i*i>r*r+t*t}function _(n){this._=n,this.next=null,this.previous=null,this.score=n.x*n.x+n.y*n.y}function B(n){if(c=n.length){var e,r,t,i,u,o,a,f,c;if(e=n[0],e.x=e.r,e.y=0,c>1&&(r=n[1],r.x=-r.r,r.y=0,c>2)){w(r,e,t=n[2]),e=new _(e),r=new _(r),t=new _(t),e.next=t.previous=r,r.next=e.previous=t,t.next=r.previous=e;n:for(i=3;c>i;++i){if(w(e._,r._,t=n[i]),t=new _(t),(o=e.previous)===(u=r.next)){if(m(u._,t._)){e=r,r=u,--i;continue n}}else{a=u._.r,f=o._.r;do if(f>=a){if(m(u._,t._)){r=u,e.next=r,r.previous=e,--i;continue n}u=u.next,a+=u._.r}else{if(m(o._,t._)){e=o,e.next=r,r.previous=e,--i;continue n}o=o.previous,f+=o._.r}while(u!==o.next)}for(t.previous=e,t.next=r,e.next=r.previous=r=t;(t=t.next)!==r;)t.score<e.score&&(e=t,r=e.next)}}}}function M(n){return null==n?null:q(n)}function q(n){if("function"!=typeof n)throw new Error;return n}function A(n){return Math.sqrt(n.value)}function E(){function n(n){return n.x=r/2,n.y=t/2,e?n.eachBefore(I(e)).eachAfter(k(i/2)).eachBefore(z(1)):(n.eachBefore(I(A)).eachAfter(b),i&&n.eachAfter(k(i*n.r/Math.min(r,t))),n.eachBefore(z(Math.min(r,t)/(2*n.r)))),n}var e=null,r=1,t=1,i=0;return n.radius=function(r){return arguments.length?(e=M(r),n):e},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=Math.max(0,+e||0),n):i},n}function I(n){return function(e){e.children||(e.r=Math.max(0,+n(e)||0))}}function b(n){if(e=n.children){B(e);var e,r,t,i=s(e),u=e.length;for(t=0;u>t;++t)r=e[t],r.x-=i.x,r.y-=i.y;n.r=i.r}}function k(n){return function(e){if(r=e.children){var r,t,i=r.length;for(t=0;i>t;++t)r[t].r+=n;for(b(e),t=0;i>t;++t)r[t].r-=n;e.r+=n}}}function z(n){return function(e){var r=e.parent;e.r*=n,r&&(e.x=r.x+n*e.x,e.y=r.y+n*e.y)}}function S(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function T(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(t-e)/n.value;++a<f;)u=o[a],u.y0=r,u.y1=i,u.x0=e,u.x1=e+=u.value*c}function D(n){var e=0;return n.eachBefore(function(n){n.depth>e&&(e=n.depth)}),e}function L(){function n(n){var o=D(n)+1;return n.x0=n.y0=i,n.x1=r,n.y1=t/o,n.eachBefore(e(t,o)),u&&n.eachBefore(S),n}function e(n,e){return function(r){r.children&&T(r,r.x0,n*(r.depth+1)/e,r.x1,n*(r.depth+2)/e);var t=r.x0,u=r.y0,o=r.x1-i,a=r.y1-i;t>o&&(t=o=(t+o)/2),u>a&&(u=a=(u+a)/2),r.x0=t,r.y0=u,r.x1=o,r.y1=a}}var r=1,t=1,i=0,u=!1;return n.round=function(e){return arguments.length?(u=!!e,n):u},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=+e,n):i},n}function O(n){return n.id}function R(n){return n.parentId}function j(){function n(n){var t,i,u,o,a,f,c,h=n.length,d=new Array(h),p={};for(i=0;h>i;++i)if(t=n[i],a=d[i]=new l(t),null!=(f=e(t,i,n))&&(f+="")){if(c=Q+(a.id=f),c in p)throw new Error("duplicate: "+f);p[c]=a}for(i=0;h>i;++i)if(a=d[i],f=r(n[i],i,n),null!=f&&(f+="")){if(o=p[Q+f],!o)throw new Error("missing: "+f);o.children?o.children.push(a):o.children=[a],a.parent=o}else{if(u)throw new Error("multiple roots");u=a}if(!u)throw new Error("no root");if(u.parent=U,u.eachBefore(function(n){n.depth=n.parent.depth+1,--h}),u.parent=null,h>0)throw new Error("cycle");return u}var e=O,r=R;return n.id=function(r){return arguments.length?(e=q(r),n):e},n.parentId=function(e){return arguments.length?(r=q(e),n):r},n}function $(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(i-r)/n.value;++a<f;)u=o[a],u.x0=e,u.x1=t,u.y0=r,u.y1=r+=u.value*c}function C(n,e,r,t,i){for(var u,o,a,f,c=n._squarify,h=-1,l=c.length,d=n.value;++h<l;){for(u=c[h],o=u.children,a=u.value=0,f=o.length;f>a;++a)u.value+=o[a].value;u.dice?T(u,e,r,t,r+=(i-r)*u.value/d):$(u,e,r,e+=(t-e)*u.value/d,i),d-=u.value}}function F(){return 0}function G(n){return function(){return n}}function H(){function n(n){var r=o(n)/2;return n.x0=-r,n.y0=-r,n.x1=i+r,n.y1=u+r,n.eachBefore(e),t&&n.eachBefore(S),n}function e(n){var e=o(n)/2,t=n.x0+e,i=n.y0+e,u=n.x1-e,l=n.y1-e;t>u&&(t=u=(t+u)/2),i>l&&(i=l=(i+l)/2),n.x0=t,n.y0=i,n.x1=u,n.y1=l,n.children&&(i+=a(n)-e,u-=f(n)-e,l-=c(n)-e,t+=h(n)-e,t>u&&(t=u=(t+u)/2),i>l&&(i=l=(i+l)/2),r(n,t,i,u,l))}var r=V,t=!1,i=1,u=1,o=F,a=F,f=F,c=F,h=F;return n.round=function(e){return arguments.length?(t=!!e,n):t},n.size=function(e){return arguments.length?(i=+e[0],u=+e[1],n):[i,u]},n.tile=function(e){return arguments.length?(r=q(e),n):r},n.padding=function(e){return arguments.length?n.paddingInner(e).paddingOuter(e):n.paddingInner()},n.paddingInner=function(e){return arguments.length?(o="function"==typeof e?e:G(+e),n):o},n.paddingOuter=function(e){return arguments.length?n.paddingTop(e).paddingRight(e).paddingBottom(e).paddingLeft(e):n.paddingTop()},n.paddingTop=function(e){return arguments.length?(a="function"==typeof e?e:G(+e),n):a},n.paddingRight=function(e){return arguments.length?(f="function"==typeof e?e:G(+e),n):f},n.paddingBottom=function(e){return arguments.length?(c="function"==typeof e?e:G(+e),n):c},n.paddingLeft=function(e){return arguments.length?(h="function"==typeof e?e:G(+e),n):h},n}function J(n,e,r,t,i){var u=n.children;K(u,0,u.length,n.value,e,r,t,i)}function K(n,e,r,t,i,u,o,a){if(e>=r-1)return n=n[e],n.x0=i,n.y0=u,n.x1=o,n.y1=a,void 0;var f=e,c=t/2,h=0;do h+=n[f].value;while(++f<r-1&&c>h);var l=t-h;if(a-u>o-i){var d=(u*l+a*h)/t;K(n,e,f,h,i,u,o,d),K(n,f,r,l,i,d,o,a)}else{var p=(i*l+o*h)/t;K(n,e,f,h,i,u,p,a),K(n,f,r,l,p,u,o,a)}}function N(n,e,r,t,i){(1&n.depth?$:T)(n,e,r,t,i)}var P="0.0.2";l.prototype=c.prototype={constructor:l,each:e,eachAfter:t,eachBefore:r,sum:i,sort:u,ancestors:o,descendants:a,leaves:f,copy:h};var Q="$",U={depth:-1},V=function W(n){function e(e,r,t,i,u){if(e._squarify)return C(e,r,t,i,u);for(var o,a,f,c,h,l,d,p,s,v,x,y,g=e._squarify=[],w=e.children,m=0,_=w.length,B=e.value;_>m;){for(c=i-r,h=u-t,d=p=l=w[m].value,x=Math.max(h/c,c/h)/(B*n),y=l*l*x,v=Math.max(p/y,y/d),f=m+1;_>f;++f){if(l+=a=w[f].value,d>a&&(d=a),a>p&&(p=a),y=l*l*x,s=Math.max(p/y,y/d),s>v){l-=a;break}v=s}g.push(o={value:l,dice:h>c,children:w.slice(m,f)}),o.dice?T(o,r,t,i,t+=h*l/B):$(o,r,t,r+=c*l/B,u),B-=l,m=f}}return e.ratio=function(n){return W((n=+n)>1?n:1)},e}((1+Math.sqrt(5))/2,!1);n.version=P,n.hierarchy=c,n.pack=E,n.partition=L,n.stratify=j,n.treemap=H,n.treemapBinary=J,n.treemapDice=T,n.treemapSlice=$,n.treemapSliceDice=N,n.treemapSquarify=V});
    !function(n,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function e(n){var e,r,t,i,u=this,o=[u];do for(e=o.reverse(),o=[];null!=(u=e.pop());)if(n(u),r=u.children)for(t=0,i=r.length;i>t;++t)o.push(r[t]);while(o.length);return this}function r(n){for(var e,r,t=this,i=[t];null!=(t=i.pop());)if(n(t),e=t.children)for(r=e.length-1;r>=0;--r)i.push(e[r]);return this}function t(n){for(var e,r,t,i=this,u=[i],o=[];null!=(i=u.pop());)if(o.push(i),e=i.children)for(r=0,t=e.length;t>r;++r)u.push(e[r]);for(;null!=(i=o.pop());)n(i);return this}function i(n){return this.eachAfter(function(e){for(var r=+n(e.data)||0,t=e.children,i=t&&t.length;--i>=0;)r+=t[i].value;e.value=r})}function u(n){return this.eachBefore(function(e){e.children&&e.children.sort(n)})}function o(){for(var n=this,e=[n];n=n.parent;)e.push(n);return e}function a(){var n=[];return this.each(function(e){n.push(e)}),n}function f(){var n=[];return this.eachBefore(function(e){e.children||n.push(e)}),n}function c(n){for(var e,r,t,i,u,o=new l(n),a=+n.value&&(o.value=n.value),f=[o];null!=(e=f.pop());)if(a&&(e.value=+e.data.value),(t=e.data.children)&&(u=t.length))for(e.children=new Array(u),i=u-1;i>=0;--i)f.push(r=e.children[i]=new l(t[i])),r.parent=e,r.depth=e.depth+1;return o}function h(){return c(this).eachBefore(function(n){n.data=n.data.data})}function l(n){this.data=n,this.depth=0,this.parent=null}function d(n){this._=n,this.next=null}function p(n){for(var e,r=(n=n.slice()).length,t=null,i=t;r;){var u=new d(n[r-1]);i=i?i.next=u:t=u,n[e]=n[--r]}return{head:t,tail:i}}function s(n){return x(p(n),[])}function v(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r-e.r;return i*i+1e-6>r*r+t*t}function x(n,e){var r,t,i,u=null,o=n.head;switch(e.length){case 1:r=e[0];break;case 2:r=y(e[0],e[1]);break;case 3:r=g(e[0],e[1],e[2])}for(;o;)i=o._,t=o.next,r&&v(r,i)?u=o:(u?(n.tail=u,u.next=null):n.head=n.tail=null,e.push(i),r=x(n,e),e.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),u=n.tail,u.next=t),o=t;return n.tail=u,r}function y(n,e){var r=n.x,t=n.y,i=n.r,u=e.x,o=e.y,a=e.r,f=u-r,c=o-t,h=a-i,l=Math.sqrt(f*f+c*c);return{x:(r+u+f/l*h)/2,y:(t+o+c/l*h)/2,r:(l+i+a)/2}}function g(n,e,r){var t=n.x,i=n.y,u=n.r,o=e.x,a=e.y,f=e.r,c=r.x,h=r.y,l=r.r,d=2*(t-o),p=2*(i-a),s=2*(f-u),v=t*t+i*i-u*u-o*o-a*a+f*f,x=2*(t-c),y=2*(i-h),g=2*(l-u),w=t*t+i*i-u*u-c*c-h*h+l*l,_=x*p-d*y,m=(p*w-y*v)/_-t,B=(y*s-p*g)/_,M=(x*v-d*w)/_-i,q=(d*g-x*s)/_,A=B*B+q*q-1,E=2*(m*B+M*q+u),k=m*m+M*M-u*u,b=(-E-Math.sqrt(E*E-4*A*k))/(2*A);return{x:m+B*b+t,y:M+q*b+i,r:b}}function w(n,e,r){var t=n.x,i=n.y,u=e.r+r.r,o=n.r+r.r,a=e.x-t,f=e.y-i,c=a*a+f*f;if(c){var h=.5+((o*=o)-(u*=u))/(2*c),l=Math.sqrt(Math.max(0,2*u*(o+c)-(o-=c)*o-u*u))/(2*c);r.x=t+h*a+l*f,r.y=i+h*f-l*a}else r.x=t+o,r.y=i}function _(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r+e.r;return i*i>r*r+t*t}function m(n){this._=n,this.next=null,this.previous=null,this.score=n.x*n.x+n.y*n.y}function B(n){if(!(c=n.length))return n;var e,r,t,i,u,o,a,f,c;if(e=n[0],e.x=e.r,e.y=0,!(c>1))return n;if(r=n[1],r.x=-r.r,r.y=0,!(c>2))return n;w(r,e,t=n[2]),e=new m(e),r=new m(r),t=new m(t),e.next=t.previous=r,r.next=e.previous=t,t.next=r.previous=e;n:for(i=3;c>i;++i){if(w(e._,r._,t=n[i]),t=new m(t),(o=e.previous)===(u=r.next)){if(_(u._,t._)){e=r,r=u,--i;continue n}}else{a=u._.r,f=o._.r;do if(f>=a){if(_(u._,t._)){r=u,e.next=r,r.previous=e,--i;continue n}u=u.next,a+=u._.r}else{if(_(o._,t._)){e=o,e.next=r,r.previous=e,--i;continue n}o=o.previous,f+=o._.r}while(u!==o.next)}for(t.previous=e,t.next=r,e.next=r.previous=r=t;(t=t.next)!==r;)t.score<e.score&&(e=t,r=e.next)}return n}function M(n){return null==n?null:q(n)}function q(n){if("function"!=typeof n)throw new Error;return n}function A(n){return Math.sqrt(n.value)}function E(){function n(n){return n.x=r/2,n.y=t/2,e?n.eachBefore(k(e)).eachAfter(I(i/2)).eachBefore(S(1)):(n.eachBefore(k(A)).eachAfter(b),i&&n.eachAfter(I(i*n.r/Math.min(r,t))),n.eachBefore(S(Math.min(r,t)/(2*n.r)))),n}var e=null,r=1,t=1,i=0;return n.radius=function(r){return arguments.length?(e=M(r),n):e},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=Math.max(0,+e||0),n):i},n}function k(n){return function(e){e.children||(e.r=Math.max(0,+n(e)||0))}}function b(n){if(e=n.children){B(e);var e,r,t,i=s(e),u=e.length;for(t=0;u>t;++t)r=e[t],r.x-=i.x,r.y-=i.y;n.r=i.r}}function I(n){return function(e){if(r=e.children){var r,t,i=r.length;for(t=0;i>t;++t)r[t].r+=n;for(b(e),t=0;i>t;++t)r[t].r-=n;e.r+=n}}}function S(n){return function(e){var r=e.parent;e.r*=n,r&&(e.x=r.x+n*e.x,e.y=r.y+n*e.y)}}function z(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function T(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(t-e)/n.value;++a<f;)u=o[a],u.y0=r,u.y1=i,u.x0=e,u.x1=e+=u.value*c}function D(n){var e=0;return n.eachBefore(function(n){n.depth>e&&(e=n.depth)}),e}function L(){function n(n){var o=D(n)+1;return n.x0=n.y0=i,n.x1=r,n.y1=t/o,n.eachBefore(e(t,o)),u&&n.eachBefore(z),n}function e(n,e){return function(r){r.children&&T(r,r.x0,n*(r.depth+1)/e,r.x1,n*(r.depth+2)/e);var t=r.x0,u=r.y0,o=r.x1-i,a=r.y1-i;t>o&&(t=o=(t+o)/2),u>a&&(u=a=(u+a)/2),r.x0=t,r.y0=u,r.x1=o,r.y1=a}}var r=1,t=1,i=0,u=!1;return n.round=function(e){return arguments.length?(u=!!e,n):u},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=+e,n):i},n}function O(n){return n.id}function R(n){return n.parentId}function j(){function n(n){var t,i,u,o,a,f,c,h=n.length,d=new Array(h),p={};for(i=0;h>i;++i)if(t=n[i],a=d[i]=new l(t),null!=(f=e(t,i,n))&&(f+="")){if(c=U+(a.id=f),c in p)throw new Error("duplicate: "+f);p[c]=a}for(i=0;h>i;++i)if(a=d[i],f=r(n[i],i,n),null!=f&&(f+="")){if(o=p[U+f],!o)throw new Error("missing: "+f);o.children?o.children.push(a):o.children=[a],a.parent=o}else{if(u)throw new Error("multiple roots");u=a}if(!u)throw new Error("no root");if(u.parent=V,u.eachBefore(function(n){n.depth=n.parent.depth+1,--h}),u.parent=null,h>0)throw new Error("cycle");return u}var e=O,r=R;return n.id=function(r){return arguments.length?(e=q(r),n):e},n.parentId=function(e){return arguments.length?(r=q(e),n):r},n}function $(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(i-r)/n.value;++a<f;)u=o[a],u.x0=e,u.x1=t,u.y0=r,u.y1=r+=u.value*c}function C(n,e,r,t,i){for(var u,o,a,f,c=n._squarify,h=-1,l=c.length,d=n.value;++h<l;){for(u=c[h],o=u.children,a=u.value=0,f=o.length;f>a;++a)u.value+=o[a].value;u.dice?T(u,e,r,t,r+=(i-r)*u.value/d):$(u,e,r,e+=(t-e)*u.value/d,i),d-=u.value}}function F(){return 0}function G(n){return function(){return n}}function H(n){delete n._padding}function J(){function n(n){return r=a(n)/2,n.x0=-r,n.y0=-r,n.x1=u+r,n.y1=o+r,n.eachBefore(e).eachBefore(H),i&&n.eachBefore(z),n}function e(n){var e=n.parent?n.parent._padding:r,i=n.x0+e,u=n.y0+e,o=n.x1-e,d=n.y1-e;i>o&&(i=o=(i+o)/2),u>d&&(u=d=(u+d)/2),n.x0=i,n.y0=u,n.x1=o,n.y1=d,n.children&&(e=n._padding=a(n)/2,i+=l(n)-e,u+=f(n)-e,o-=c(n)-e,d-=h(n)-e,i>o&&(i=o=(i+o)/2),u>d&&(u=d=(u+d)/2),t(n,i,u,o,d))}var r,t=W,i=!1,u=1,o=1,a=F,f=F,c=F,h=F,l=F;return n.round=function(e){return arguments.length?(i=!!e,n):i},n.size=function(e){return arguments.length?(u=+e[0],o=+e[1],n):[u,o]},n.tile=function(e){return arguments.length?(t=q(e),n):t},n.padding=function(e){return arguments.length?n.paddingInner(e).paddingOuter(e):n.paddingInner()},n.paddingInner=function(e){return arguments.length?(a="function"==typeof e?e:G(+e),n):a},n.paddingOuter=function(e){return arguments.length?n.paddingTop(e).paddingRight(e).paddingBottom(e).paddingLeft(e):n.paddingTop()},n.paddingTop=function(e){return arguments.length?(f="function"==typeof e?e:G(+e),n):f},n.paddingRight=function(e){return arguments.length?(c="function"==typeof e?e:G(+e),n):c},n.paddingBottom=function(e){return arguments.length?(h="function"==typeof e?e:G(+e),n):h},n.paddingLeft=function(e){return arguments.length?(l="function"==typeof e?e:G(+e),n):l},n}function K(n,e,r,t,i){var u=n.children;N(u,0,u.length,n.value,e,r,t,i)}function N(n,e,r,t,i,u,o,a){if(e>=r-1)return n=n[e],n.x0=i,n.y0=u,n.x1=o,n.y1=a,void 0;var f=e,c=t/2,h=0;do h+=n[f].value;while(++f<r-1&&c>h);var l=t-h;if(a-u>o-i){var d=(u*l+a*h)/t;N(n,e,f,h,i,u,o,d),N(n,f,r,l,i,d,o,a)}else{var p=(i*l+o*h)/t;N(n,e,f,h,i,u,p,a),N(n,f,r,l,p,u,o,a)}}function P(n,e,r,t,i){(1&n.depth?$:T)(n,e,r,t,i)}var Q="0.0.2";l.prototype=c.prototype={constructor:l,each:e,eachAfter:t,eachBefore:r,sum:i,sort:u,ancestors:o,descendants:a,leaves:f,copy:h};var U="$",V={depth:-1},W=function X(n){function e(e,r,t,i,u){if(e._squarify)return C(e,r,t,i,u);for(var o,a,f,c,h,l,d,p,s,v,x,y,g=e._squarify=[],w=e.children,_=0,m=w.length,B=e.value;m>_;){for(c=i-r,h=u-t,d=p=l=w[_].value,x=Math.max(h/c,c/h)/(B*n),y=l*l*x,v=Math.max(p/y,y/d),f=_+1;m>f;++f){if(l+=a=w[f].value,d>a&&(d=a),a>p&&(p=a),y=l*l*x,s=Math.max(p/y,y/d),s>v){l-=a;break}v=s}g.push(o={value:l,dice:h>c,children:w.slice(_,f)}),o.dice?T(o,r,t,i,t+=h*l/B):$(o,r,t,r+=c*l/B,u),B-=l,_=f}}return e.ratio=function(n){return X((n=+n)>1?n:1)},e}((1+Math.sqrt(5))/2,!1);n.version=Q,n.hierarchy=c,n.pack=E,n.packSiblings=B,n.packEnclose=s,n.partition=L,n.stratify=j,n.treemap=J,n.treemapBinary=K,n.treemapDice=T,n.treemapSlice=$,n.treemapSliceDice=P,n.treemapSquarify=W});
    18 changes: 7 additions & 11 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -12,7 +12,7 @@
    }

    </style>
    <svg width="960" height="960"></svg>
    <svg width="960" height="960"><g transform="translate(480,480)"></g></svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
    <script src="d3-hierarchy.min.js"></script>
    <script>
    @@ -27,19 +27,15 @@
    .map(d3.randomUniform(8, 26))
    .map(function(r) { return {r: Math.max(1, r)}; });

    var pack = d3_hierarchy.pack()
    .size([size, size])
    .radius(function(d) { return d.data.r; });

    svg
    .select("g")
    .selectAll("circle")
    .data(pack(d3_hierarchy.hierarchy({children: circles}))
    .leaves()
    .filter(function(d) { return -30 < d.x && d.x < size + 30 && -30 < d.y && d.y < size + 30; }))
    .data(d3_hierarchy.packSiblings(circles)
    .filter(function(d) { return -500 < d.x && d.x < 500 && -500 < d.y && d.y < 500; }))
    .enter().append("circle")
    .style("fill", function(d) { return color(d.angle = Math.atan2(d.y - size / 2, d.x - size / 2)); })
    .attr("cx", function(d) { return size / 2 + Math.cos(d.angle) * (size / Math.SQRT2 + 30); })
    .attr("cy", function(d) { return size / 2 + Math.sin(d.angle) * (size / Math.SQRT2 + 30); })
    .style("fill", function(d) { return color(d.angle = Math.atan2(d.y, d.x)); })
    .attr("cx", function(d) { return Math.cos(d.angle) * (size / Math.SQRT2 + 30); })
    .attr("cy", function(d) { return Math.sin(d.angle) * (size / Math.SQRT2 + 30); })
    .attr("r", function(d) { return d.r - 0.25; })
    .transition()
    .ease(d3.easeCubicOut)
  9. mbostock revised this gist Mar 29, 2016. 2 changed files with 4 additions and 5 deletions.
    2 changes: 1 addition & 1 deletion d3-hierarchy.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    !function(n,r){"object"==typeof exports&&"undefined"!=typeof module?r(exports):"function"==typeof define&&define.amd?define(["exports"],r):r(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function r(n){return n.value}function t(n,r){return r.value-n.value}function e(n){return null==n?null:u(n)}function u(n){if("function"!=typeof n)throw new Error;return n}function i(n,r){for(var t,e,u=[n];null!=(n=u.pop());)if(r(n),t=n.children)for(e=t.length-1;e>=0;--e)u.push(t[e])}function o(n){return n.id}function a(n){return n.parentId}function f(){function n(n){var e,u,o,a,f,c,l,h,d=n.length,x=new Array(d),s={};for(o=0;d>o;++o){e=n[o],c=x[o]={};for(u in e)u in R||(c[u]=e[u]);if(null!=(l=r(e,o,n))&&(l+="")){if(h=Q+(c.id=l),h in s)throw new Error("duplicate: "+l);s[h]=c}}for(o=0;d>o;++o)if(c=x[o],l=t(n[o],o,n),null!=l&&(l+="")){if(f=s[Q+l],!f)throw new Error("missing: "+l);f.children?f.children.push(c):f.children=[c]}else{if(a)throw new Error("multiple roots");a=c}if(!a)throw new Error("no root");if(i(a,function(){--d}),d>0)throw new Error("cycle");return a}var r=o,t=a;return n.id=function(t){return arguments.length?(r=u(t),n):r},n.parentId=function(r){return arguments.length?(t=u(r),n):t},n}function c(){for(var n=this,r=[n];n=n.parent;)r.push(n);return r}function l(n,r){var t,e,u,i,o=[n];do for(t=o.reverse(),o=[];null!=(n=t.pop());)if(r(n),e=n.children)for(u=0,i=e.length;i>u;++u)o.push(e[u]);while(o.length)}function h(){var n=[];return l(this,function(r){n.push(r)}),n}function d(){var n=[];return l(this,function(r){r.children||n.push(r)}),n}function x(n){for(var r,t,e,u,i,o=new v(n),a=[o];null!=(r=a.pop());)if((e=r.data.children)&&(i=e.length))for(r.children=new Array(i),u=i-1;u>=0;--u)a.push(t=r.children[u]=new v(e[u])),t.parent=r,t.depth=r.depth+1;return o}function s(){var n=x(this);return i(n,function(n){n.data=n.data.data}),n}function v(n){this.data=n,this.depth=0,this.parent=null}function p(n){return _(y(n),[])}function y(n){for(var r,t=(n=n.slice()).length,e=null,u=e;t;){var i={circle:n[t-1],next:null};u=u?u.next=i:e=i,n[r]=n[--t]}return{head:e,tail:u}}function g(n,r){var t=r.x-n.x,e=r.y-n.y,u=n.r-r.r;return u*u+1e-6>t*t+e*e}function _(n,r){var t,e,u,i=null,o=n.head;switch(r.length){case 1:t=r[0];break;case 2:t=w(r[0],r[1]);break;case 3:t=m(r[0],r[1],r[2])}for(;o;)u=o.circle,e=o.next,t&&g(t,u)?i=o:(i?(n.tail=i,i.next=null):n.head=n.tail=null,r.push(u),t=_(n,r),r.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),i=n.tail,i.next=e),o=e;return n.tail=i,t}function w(n,r){var t=n.x,e=n.y,u=n.r,i=r.x,o=r.y,a=r.r,f=i-t,c=o-e,l=a-u,h=Math.sqrt(f*f+c*c);return{x:(t+i+f/h*l)/2,y:(e+o+c/h*l)/2,r:(h+u+a)/2}}function m(n,r,t){var e=n.x,u=n.y,i=n.r,o=r.x,a=r.y,f=r.r,c=t.x,l=t.y,h=t.r,d=2*(e-o),x=2*(u-a),s=2*(f-i),v=e*e+u*u-i*i-o*o-a*a+f*f,p=2*(e-c),y=2*(u-l),g=2*(h-i),_=e*e+u*u-i*i-c*c-l*l+h*h,w=p*x-d*y,m=(x*_-y*v)/w-e,M=(y*s-x*g)/w,q=(p*v-d*_)/w-u,E=(d*g-p*s)/w,b=M*M+E*E-1,k=2*(m*M+q*E+i),I=m*m+q*q-i*i,z=(-k-Math.sqrt(k*k-4*b*I))/(2*b);return{x:m+M*z+e,y:q+E*z+u,r:z}}function M(n,r){for(var t,e,u,i=[n],o=[];null!=(n=i.pop());)if(o.push(n),t=n.children)for(e=0,u=t.length;u>e;++e)i.push(t[e]);for(;null!=(n=o.pop());)r(n)}function q(n,r){M(n,function(n){for(var t=+r(n.data)||0,e=n.children,u=e&&e.length;--u>=0;)t+=e[u].value;n.value=t})}function E(n,r){i(n,function(n){n.children&&n.children.sort(r)})}function b(n,r,t){var e=n._,u=r._,i=t._,o=e.x,a=e.y,f=u.r+i.r,c=e.r+i.r,l=u.x-o,h=u.y-a,d=l*l+h*h;if(d){var x=.5+((c*=c)-(f*=f))/(2*d),s=Math.sqrt(Math.max(0,2*f*(c+d)-(c-=d)*c-f*f))/(2*d);i.x=o+x*l+s*h,i.y=a+x*h-s*l}else i.x=o+c,i.y=a;t.score=i.x*i.x+i.y*i.y}function k(n,r){var t=r.x-n.x,e=r.y-n.y,u=n.r+r.r;return u*u>t*t+e*e}function I(n){return{_:n,next:null,previous:null,score:NaN}}function z(n){if(c=n.length){n=n.map(I);var r,t,e,u,i,o,a,f,c;if(r=n[0],r.score=r._.r*r._.r,r._.x=r._.r,r._.y=0,c>1&&(t=n[1],t.score=t._.r*t._.r,t._.x=-t._.r,t._.y=0,c>2)){b(t,r,e=n[2]),r.next=e.previous=t,t.next=r.previous=e,e.next=t.previous=r;n:for(u=3;c>u;++u){if(b(r,t,e=n[u]),(o=r.previous)===(i=t.next)){if(k(i._,e._)){r=t,t=i,--u;continue n}}else{a=i._.r,f=o._.r;do if(f>=a){if(k(i._,e._)){t=i,r.next=t,t.previous=r,--u;continue n}i=i.next,a+=i._.r}else{if(k(o._,e._)){r=o,r.next=t,t.previous=r,--u;continue n}o=o.previous,f+=o._.r}while(i!==o.next)}for(e.previous=r,e.next=t,r.next=t.previous=t=e;(e=e.next)!==t;)e.score<r.score&&(r=e,t=r.next)}}}}function N(n){return Math.sqrt(n.value)}function S(){function n(n){var r=x(n);return o&&q(r,o),a&&E(r,a),r.x=f/2,r.y=c/2,u?(i(r,A(u)),M(r,D(l/2)),i(r,j(1))):(i(r,A(N)),M(r,B),l&&M(r,D(l*r.r/Math.min(f,c))),i(r,j(Math.min(f,c)/(2*r.r)))),r}var u=null,o=r,a=t,f=1,c=1,l=0;return n.radius=function(r){return arguments.length?(u=e(r),n):u},n.value=function(r){return arguments.length?(o=e(r),n):o},n.sort=function(r){return arguments.length?(a=e(r),n):a},n.size=function(r){return arguments.length?(f=+r[0],c=+r[1],n):[f,c]},n.padding=function(r){return arguments.length?(l=Math.max(0,+r||0),n):l},n}function A(n){return function(r){r.children||(r.r=Math.max(0,+n(r)||0))}}function B(n){if(r=n.children){z(r);var r,t,e,u=p(r),i=r.length;for(e=0;i>e;++e)t=r[e],t.x-=u.x,t.y-=u.y;n.r=u.r}}function D(n){return function(r){if(t=r.children){var t,e,u=t.length;for(e=0;u>e;++e)t[e].r+=n;for(B(r),e=0;u>e;++e)t[e].r-=n;r.r+=n}}}function j(n){return function(r){var t=r.parent;r.r*=n,t&&(r.x=t.x+n*r.x,r.y=t.y+n*r.y)}}function O(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function $(n,r,t,e,u){for(var i,o=n.children,a=-1,f=o.length,c=(e-r)/n.value;++a<f;)i=o[a],i.y0=t,i.y1=u,i.x0=r,i.x1=r+=i.value*c}function C(n){var r=n.depth;return n.eachBefore(function(n){n.depth>r&&(r=n.depth)}),r}function F(){function n(n){var r=x(n);q(r,a),f&&E(r,f);var t=C(r)+1;return r.x0=r.y0=h,r.x1=c,r.y1=l/t,i(r,o(l,t)),d&&i(r,O),r}function o(n,r){return function(t){t.children&&$(t,t.x0,n*(t.depth+1)/r,t.x1,n*(t.depth+2)/r);var e=t.x0,u=t.y0,i=t.x1-h,o=t.y1-h;e>i&&(e=i=(e+i)/2),u>o&&(u=o=(u+o)/2),t.x0=e,t.y0=u,t.x1=i,t.y1=o}}var a=r,f=t,c=1,l=1,h=0,d=!1;return n.value=function(r){return arguments.length?(a=u(r),n):a},n.sort=function(r){return arguments.length?(f=e(r),n):f},n.round=function(r){return arguments.length?(d=!!r,n):d},n.size=function(r){return arguments.length?(c=+r[0],l=+r[1],n):[c,l]},n.padding=function(r){return arguments.length?(h=+r,n):h},n}function G(){function n(n){var r=x(n);return q(r,f),c&&E(r,c),o(r)}function o(n){return n.x0=n.y0=-d,n.x1=l+d,n.y1=h+d,i(n,a),y&&i(n,O),n}function a(n){var r=n.x0+d,t=n.y0+d,e=n.x1-d,u=n.y1-d;r>e&&(r=e=(r+e)/2),t>u&&(t=u=(t+u)/2),n.x0=r,n.y0=t,n.x1=e,n.y1=u,n.children&&(r+=v,t+=v,e-=v,u-=v,r>e&&(r=e=(r+e)/2),t>u&&(t=u=(t+u)/2),p(n,r,t,e,u))}var f=r,c=t,l=1,h=1,d=0,s=0,v=0,p=T,y=!1;return n.update=function(n){return q(n,f),o(n)},n.value=function(r){return arguments.length?(f=u(r),n):f},n.sort=function(r){return arguments.length?(c=e(r),n):c},n.round=function(r){return arguments.length?(y=!!r,n):y},n.size=function(r){return arguments.length?(l=+r[0],h=+r[1],n):[l,h]},n.tile=function(r){return arguments.length?(p=u(r),n):p},n.padding=function(r){return arguments.length?(d=(s=+r)/2,v=d,n):2*d},n.paddingInner=function(r){return arguments.length?(d=r/2,v=s-d,n):2*d},n.paddingOuter=function(r){return arguments.length?(s=+r,v=s-d,n):s},n}function H(n,r,t,e,u){var i=n.children;J(i,0,i.length,n.value,r,t,e,u)}function J(n,r,t,e,u,i,o,a){if(r>=t-1)return n=n[r],n.x0=u,n.y0=i,n.x1=o,n.y1=a,void 0;var f=r,c=e/2,l=0;do l+=n[f].value;while(++f<t-1&&c>l);var h=e-l;if(a-i>o-u){var d=(i*h+a*l)/e;J(n,r,f,l,u,i,o,d),J(n,f,t,h,u,d,o,a)}else{var x=(u*h+o*l)/e;J(n,r,f,l,u,i,x,a),J(n,f,t,h,x,i,o,a)}}function K(n,r,t,e,u){for(var i,o=n.children,a=-1,f=o.length,c=(u-t)/n.value;++a<f;)i=o[a],i.x0=r,i.x1=e,i.y0=t,i.y1=t+=i.value*c}function L(n,r,t,e,u){(1&n.depth?K:$)(n,r,t,e,u)}var P="0.0.2",Q="$",R={id:1,parentId:1,children:1};v.prototype=x.prototype={constructor:v,ancestors:c,descendants:h,leaves:d,copy:s};var T=function U(n){function r(r,t,e,u,i){for(var o,a,f,c,l,h,d,x,s,v,p,y,g,_,w=r.children,m=0,M=w.length,q=r.value;M>m;){if(h=u-t,d=i-e,x=(o=w[m]).value,o._squarify)for(f=m+1;f<Math.abs(o._squarify);++f)x+=w[f].value;else{for(s=v=x,p=Math.max(d/h,h/d)/(q*n),y=x*x*p,_=Math.max(v/y,y/s),f=m+1;M>f;++f){if(x+=a=w[f].value,s>a&&(s=a),a>v&&(v=a),y=x*x*p,g=Math.max(v/y,y/s),g>_){x-=a;break}_=g}o._squarify=d>h?f:-f}if(o._squarify>0){for(c=t,l=e+d*x/q,h/=x;f>m;++m)o=w[m],o.x0=c,o.y0=e,o.y1=l,o.x1=c+=o.value*h;o.x1=u,e=l}else{for(l=e,c=t+h*x/q,d/=x;f>m;++m)o=w[m],o.y0=l,o.x0=t,o.x1=c,o.y1=l+=o.value*d;o.y1=i,t=c}q-=x}o.x1=u,o.y1=i}return r.ratio=function(n){return U((n=+n)>1?n:1)},r}((1+Math.sqrt(5))/2);n.version=P,n.hierarchy=f,n.hierarchyNode=x,n.pack=S,n.partition=F,n.treemap=G,n.treemapBinary=H,n.treemapDice=$,n.treemapSlice=K,n.treemapSliceDice=L,n.treemapSquarify=T});
    !function(n,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function e(n){var e,r,t,i,u=this,o=[u];do for(e=o.reverse(),o=[];null!=(u=e.pop());)if(n(u),r=u.children)for(t=0,i=r.length;i>t;++t)o.push(r[t]);while(o.length);return this}function r(n){for(var e,r,t=this,i=[t];null!=(t=i.pop());)if(n(t),e=t.children)for(r=e.length-1;r>=0;--r)i.push(e[r]);return this}function t(n){for(var e,r,t,i=this,u=[i],o=[];null!=(i=u.pop());)if(o.push(i),e=i.children)for(r=0,t=e.length;t>r;++r)u.push(e[r]);for(;null!=(i=o.pop());)n(i);return this}function i(n){return this.eachAfter(function(e){for(var r=+n(e.data)||0,t=e.children,i=t&&t.length;--i>=0;)r+=t[i].value;e.value=r})}function u(n){return this.eachBefore(function(e){e.children&&e.children.sort(n)})}function o(){for(var n=this,e=[n];n=n.parent;)e.push(n);return e}function a(){var n=[];return this.each(function(e){n.push(e)}),n}function f(){var n=[];return this.eachBefore(function(e){e.children||n.push(e)}),n}function c(n){for(var e,r,t,i,u,o=new l(n),a=+n.value&&(o.value=n.value),f=[o];null!=(e=f.pop());)if(a&&(e.value=+e.data.value),(t=e.data.children)&&(u=t.length))for(e.children=new Array(u),i=u-1;i>=0;--i)f.push(r=e.children[i]=new l(t[i])),r.parent=e,r.depth=e.depth+1;return o}function h(){return c(this).eachBefore(function(n){n.data=n.data.data})}function l(n){this.data=n,this.depth=0,this.parent=null}function d(n){this._=n,this.next=null}function p(n){for(var e,r=(n=n.slice()).length,t=null,i=t;r;){var u=new d(n[r-1]);i=i?i.next=u:t=u,n[e]=n[--r]}return{head:t,tail:i}}function s(n){return x(p(n),[])}function v(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r-e.r;return i*i+1e-6>r*r+t*t}function x(n,e){var r,t,i,u=null,o=n.head;switch(e.length){case 1:r=e[0];break;case 2:r=y(e[0],e[1]);break;case 3:r=g(e[0],e[1],e[2])}for(;o;)i=o._,t=o.next,r&&v(r,i)?u=o:(u?(n.tail=u,u.next=null):n.head=n.tail=null,e.push(i),r=x(n,e),e.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),u=n.tail,u.next=t),o=t;return n.tail=u,r}function y(n,e){var r=n.x,t=n.y,i=n.r,u=e.x,o=e.y,a=e.r,f=u-r,c=o-t,h=a-i,l=Math.sqrt(f*f+c*c);return{x:(r+u+f/l*h)/2,y:(t+o+c/l*h)/2,r:(l+i+a)/2}}function g(n,e,r){var t=n.x,i=n.y,u=n.r,o=e.x,a=e.y,f=e.r,c=r.x,h=r.y,l=r.r,d=2*(t-o),p=2*(i-a),s=2*(f-u),v=t*t+i*i-u*u-o*o-a*a+f*f,x=2*(t-c),y=2*(i-h),g=2*(l-u),w=t*t+i*i-u*u-c*c-h*h+l*l,m=x*p-d*y,_=(p*w-y*v)/m-t,B=(y*s-p*g)/m,M=(x*v-d*w)/m-i,q=(d*g-x*s)/m,A=B*B+q*q-1,E=2*(_*B+M*q+u),I=_*_+M*M-u*u,b=(-E-Math.sqrt(E*E-4*A*I))/(2*A);return{x:_+B*b+t,y:M+q*b+i,r:b}}function w(n,e,r){var t=n.x,i=n.y,u=e.r+r.r,o=n.r+r.r,a=e.x-t,f=e.y-i,c=a*a+f*f;if(c){var h=.5+((o*=o)-(u*=u))/(2*c),l=Math.sqrt(Math.max(0,2*u*(o+c)-(o-=c)*o-u*u))/(2*c);r.x=t+h*a+l*f,r.y=i+h*f-l*a}else r.x=t+o,r.y=i}function m(n,e){var r=e.x-n.x,t=e.y-n.y,i=n.r+e.r;return i*i>r*r+t*t}function _(n){this._=n,this.next=null,this.previous=null,this.score=n.x*n.x+n.y*n.y}function B(n){if(c=n.length){var e,r,t,i,u,o,a,f,c;if(e=n[0],e.x=e.r,e.y=0,c>1&&(r=n[1],r.x=-r.r,r.y=0,c>2)){w(r,e,t=n[2]),e=new _(e),r=new _(r),t=new _(t),e.next=t.previous=r,r.next=e.previous=t,t.next=r.previous=e;n:for(i=3;c>i;++i){if(w(e._,r._,t=n[i]),t=new _(t),(o=e.previous)===(u=r.next)){if(m(u._,t._)){e=r,r=u,--i;continue n}}else{a=u._.r,f=o._.r;do if(f>=a){if(m(u._,t._)){r=u,e.next=r,r.previous=e,--i;continue n}u=u.next,a+=u._.r}else{if(m(o._,t._)){e=o,e.next=r,r.previous=e,--i;continue n}o=o.previous,f+=o._.r}while(u!==o.next)}for(t.previous=e,t.next=r,e.next=r.previous=r=t;(t=t.next)!==r;)t.score<e.score&&(e=t,r=e.next)}}}}function M(n){return null==n?null:q(n)}function q(n){if("function"!=typeof n)throw new Error;return n}function A(n){return Math.sqrt(n.value)}function E(){function n(n){return n.x=r/2,n.y=t/2,e?n.eachBefore(I(e)).eachAfter(k(i/2)).eachBefore(z(1)):(n.eachBefore(I(A)).eachAfter(b),i&&n.eachAfter(k(i*n.r/Math.min(r,t))),n.eachBefore(z(Math.min(r,t)/(2*n.r)))),n}var e=null,r=1,t=1,i=0;return n.radius=function(r){return arguments.length?(e=M(r),n):e},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=Math.max(0,+e||0),n):i},n}function I(n){return function(e){e.children||(e.r=Math.max(0,+n(e)||0))}}function b(n){if(e=n.children){B(e);var e,r,t,i=s(e),u=e.length;for(t=0;u>t;++t)r=e[t],r.x-=i.x,r.y-=i.y;n.r=i.r}}function k(n){return function(e){if(r=e.children){var r,t,i=r.length;for(t=0;i>t;++t)r[t].r+=n;for(b(e),t=0;i>t;++t)r[t].r-=n;e.r+=n}}}function z(n){return function(e){var r=e.parent;e.r*=n,r&&(e.x=r.x+n*e.x,e.y=r.y+n*e.y)}}function S(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function T(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(t-e)/n.value;++a<f;)u=o[a],u.y0=r,u.y1=i,u.x0=e,u.x1=e+=u.value*c}function D(n){var e=0;return n.eachBefore(function(n){n.depth>e&&(e=n.depth)}),e}function L(){function n(n){var o=D(n)+1;return n.x0=n.y0=i,n.x1=r,n.y1=t/o,n.eachBefore(e(t,o)),u&&n.eachBefore(S),n}function e(n,e){return function(r){r.children&&T(r,r.x0,n*(r.depth+1)/e,r.x1,n*(r.depth+2)/e);var t=r.x0,u=r.y0,o=r.x1-i,a=r.y1-i;t>o&&(t=o=(t+o)/2),u>a&&(u=a=(u+a)/2),r.x0=t,r.y0=u,r.x1=o,r.y1=a}}var r=1,t=1,i=0,u=!1;return n.round=function(e){return arguments.length?(u=!!e,n):u},n.size=function(e){return arguments.length?(r=+e[0],t=+e[1],n):[r,t]},n.padding=function(e){return arguments.length?(i=+e,n):i},n}function O(n){return n.id}function R(n){return n.parentId}function j(){function n(n){var t,i,u,o,a,f,c,h=n.length,d=new Array(h),p={};for(i=0;h>i;++i)if(t=n[i],a=d[i]=new l(t),null!=(f=e(t,i,n))&&(f+="")){if(c=Q+(a.id=f),c in p)throw new Error("duplicate: "+f);p[c]=a}for(i=0;h>i;++i)if(a=d[i],f=r(n[i],i,n),null!=f&&(f+="")){if(o=p[Q+f],!o)throw new Error("missing: "+f);o.children?o.children.push(a):o.children=[a],a.parent=o}else{if(u)throw new Error("multiple roots");u=a}if(!u)throw new Error("no root");if(u.parent=U,u.eachBefore(function(n){n.depth=n.parent.depth+1,--h}),u.parent=null,h>0)throw new Error("cycle");return u}var e=O,r=R;return n.id=function(r){return arguments.length?(e=q(r),n):e},n.parentId=function(e){return arguments.length?(r=q(e),n):r},n}function $(n,e,r,t,i){for(var u,o=n.children,a=-1,f=o.length,c=(i-r)/n.value;++a<f;)u=o[a],u.x0=e,u.x1=t,u.y0=r,u.y1=r+=u.value*c}function C(n,e,r,t,i){for(var u,o,a,f,c=n._squarify,h=-1,l=c.length,d=n.value;++h<l;){for(u=c[h],o=u.children,a=u.value=0,f=o.length;f>a;++a)u.value+=o[a].value;u.dice?T(u,e,r,t,r+=(i-r)*u.value/d):$(u,e,r,e+=(t-e)*u.value/d,i),d-=u.value}}function F(){return 0}function G(n){return function(){return n}}function H(){function n(n){var r=o(n)/2;return n.x0=-r,n.y0=-r,n.x1=i+r,n.y1=u+r,n.eachBefore(e),t&&n.eachBefore(S),n}function e(n){var e=o(n)/2,t=n.x0+e,i=n.y0+e,u=n.x1-e,l=n.y1-e;t>u&&(t=u=(t+u)/2),i>l&&(i=l=(i+l)/2),n.x0=t,n.y0=i,n.x1=u,n.y1=l,n.children&&(i+=a(n)-e,u-=f(n)-e,l-=c(n)-e,t+=h(n)-e,t>u&&(t=u=(t+u)/2),i>l&&(i=l=(i+l)/2),r(n,t,i,u,l))}var r=V,t=!1,i=1,u=1,o=F,a=F,f=F,c=F,h=F;return n.round=function(e){return arguments.length?(t=!!e,n):t},n.size=function(e){return arguments.length?(i=+e[0],u=+e[1],n):[i,u]},n.tile=function(e){return arguments.length?(r=q(e),n):r},n.padding=function(e){return arguments.length?n.paddingInner(e).paddingOuter(e):n.paddingInner()},n.paddingInner=function(e){return arguments.length?(o="function"==typeof e?e:G(+e),n):o},n.paddingOuter=function(e){return arguments.length?n.paddingTop(e).paddingRight(e).paddingBottom(e).paddingLeft(e):n.paddingTop()},n.paddingTop=function(e){return arguments.length?(a="function"==typeof e?e:G(+e),n):a},n.paddingRight=function(e){return arguments.length?(f="function"==typeof e?e:G(+e),n):f},n.paddingBottom=function(e){return arguments.length?(c="function"==typeof e?e:G(+e),n):c},n.paddingLeft=function(e){return arguments.length?(h="function"==typeof e?e:G(+e),n):h},n}function J(n,e,r,t,i){var u=n.children;K(u,0,u.length,n.value,e,r,t,i)}function K(n,e,r,t,i,u,o,a){if(e>=r-1)return n=n[e],n.x0=i,n.y0=u,n.x1=o,n.y1=a,void 0;var f=e,c=t/2,h=0;do h+=n[f].value;while(++f<r-1&&c>h);var l=t-h;if(a-u>o-i){var d=(u*l+a*h)/t;K(n,e,f,h,i,u,o,d),K(n,f,r,l,i,d,o,a)}else{var p=(i*l+o*h)/t;K(n,e,f,h,i,u,p,a),K(n,f,r,l,p,u,o,a)}}function N(n,e,r,t,i){(1&n.depth?$:T)(n,e,r,t,i)}var P="0.0.2";l.prototype=c.prototype={constructor:l,each:e,eachAfter:t,eachBefore:r,sum:i,sort:u,ancestors:o,descendants:a,leaves:f,copy:h};var Q="$",U={depth:-1},V=function W(n){function e(e,r,t,i,u){if(e._squarify)return C(e,r,t,i,u);for(var o,a,f,c,h,l,d,p,s,v,x,y,g=e._squarify=[],w=e.children,m=0,_=w.length,B=e.value;_>m;){for(c=i-r,h=u-t,d=p=l=w[m].value,x=Math.max(h/c,c/h)/(B*n),y=l*l*x,v=Math.max(p/y,y/d),f=m+1;_>f;++f){if(l+=a=w[f].value,d>a&&(d=a),a>p&&(p=a),y=l*l*x,s=Math.max(p/y,y/d),s>v){l-=a;break}v=s}g.push(o={value:l,dice:h>c,children:w.slice(m,f)}),o.dice?T(o,r,t,i,t+=h*l/B):$(o,r,t,r+=c*l/B,u),B-=l,m=f}}return e.ratio=function(n){return W((n=+n)>1?n:1)},e}((1+Math.sqrt(5))/2,!1);n.version=P,n.hierarchy=c,n.pack=E,n.partition=L,n.stratify=j,n.treemap=H,n.treemapBinary=J,n.treemapDice=T,n.treemapSlice=$,n.treemapSliceDice=N,n.treemapSquarify=V});
    7 changes: 3 additions & 4 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -27,14 +27,13 @@
    .map(d3.randomUniform(8, 26))
    .map(function(r) { return {r: Math.max(1, r)}; });

    var root = d3_hierarchy.pack()
    var pack = d3_hierarchy.pack()
    .size([size, size])
    .radius(function(d) { return d.data.r; })
    ({children: circles});
    .radius(function(d) { return d.data.r; });

    svg
    .selectAll("circle")
    .data(root
    .data(pack(d3_hierarchy.hierarchy({children: circles}))
    .leaves()
    .filter(function(d) { return -30 < d.x && d.x < size + 30 && -30 < d.y && d.y < size + 30; }))
    .enter().append("circle")
  10. mbostock revised this gist Mar 25, 2016. 2 changed files with 16 additions and 11 deletions.
    2 changes: 1 addition & 1 deletion d3-hierarchy.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    !function(n,r){"object"==typeof exports&&"undefined"!=typeof module?r(exports):"function"==typeof define&&define.amd?define(["exports"],r):r(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function r(){for(var n=this,r=[this];n=n.parent;)r.push(n);return r}function e(){var n=[];return this.each(function(r){n.push(r)}),n}function t(n){var r,e,t,u,i=this,o=[i];do for(r=o.reverse(),o=[];null!=(i=r.pop());)if(n(i),e=i.children)for(t=0,u=e.length;u>t;++t)o.push(e[t]);while(o.length);return this}function u(n){for(var r,e,t=this,u=[t],i=[];null!=(t=u.pop());)if(i.push(t),r=t.children)for(e=r.length-1;e>=0;--e)u.push(r[e]);for(;null!=(t=i.pop());)n(t);return this}function i(n){for(var r,e,t=this,u=[t];null!=(t=u.pop());)if(n(t),r=t.children)for(e=r.length-1;e>=0;--e)u.push(r[e]);return this}function o(n){return this.eachBefore(function(r){r.children&&r.children.sort(n)})}function a(n,r){this.data=n,this.index=r}function c(n){return n.id}function f(n){return n.parent}function l(n){return n.value}function h(n,r){return r.value-n.value}function v(n){var r=new Array(n);return function(n){var e=n.index;if(r[e])throw new Error("cycle");n.depth=n.parent?n.parent.depth+1:0,r[e]=1}}function s(){function n(n){var t=r(n),u=t[0],i=-1;return u.eachBefore(v(n.length)),u.eachAfter(e(n)),null!=o&&u.sort(o),u.each(function(n){t[++i]=n}),t.data=n,t}function r(n){var r,e,i,o,c,f,l,h=n.length,v={},s=new Array(h);for(r=0;h>r;++r)if(s[r]=c=new a(e=n[r],r),null!=(i=t(e,r,n))){if(o=J+(c.id=i+=""),o in v)throw new Error("duplicate: "+i);v[o]=c}for(r=0;h>r;++r)if(c=s[r],i=u(e=n[r],r,n),null==i){if(l)throw new Error("multiple roots");l=s[0],s[0]=c,s[r]=l}else{if(f=v[J+i],!f)throw new Error("missing: "+i);c.parent=f,f.children?f.children.push(c):f.children=[c]}if(!l)throw new Error("cycle");return s}function e(n){return function(r){for(var e=+i(r.data,r.index,n)||0,t=r.children,u=t&&t.length;--u>=0;)e+=t[u].value;r.value=e}}var t=c,u=f,i=l,o=h;return n.revalue=function(n){return n[0].eachAfter(e(n.data)),n},n.id=function(r){return arguments.length?(t=r,n):t},n.parentId=function(r){return arguments.length?(u=r,n):u},n.value=function(r){return arguments.length?(i=r,n):i},n.sort=function(r){return arguments.length?(o=r,n):o},n}function d(n,r){return n.revalue=r.revalue,n.id=function(){var e=r.id.apply(r,arguments);return e===r?n:e},n.parentId=function(){var e=r.parentId.apply(r,arguments);return e===r?n:e},n.value=function(){var e=r.value.apply(r,arguments);return e===r?n:e},n.sort=function(){var e=r.sort.apply(r,arguments);return e===r?n:e},n}function x(n){return g(p(n),[])}function p(n){for(var r,e=(n=n.slice()).length,t=null,u=t;e;){var i={circle:n[e-1],next:null};u=u?u.next=i:t=i,n[r]=n[--e]}return{head:t,tail:u}}function y(n,r){var e=r.x-n.x,t=r.y-n.y,u=n.r-r.r;return u*u+1e-6>e*e+t*t}function g(n,r){var e,t,u,i=null,o=n.head;switch(r.length){case 1:e=r[0];break;case 2:e=_(r[0],r[1]);break;case 3:e=m(r[0],r[1],r[2])}for(;o;)u=o.circle,t=o.next,e&&y(e,u)?i=o:(i?(n.tail=i,i.next=null):n.head=n.tail=null,r.push(u),e=g(n,r),r.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),i=n.tail,i.next=t),o=t;return n.tail=i,e}function _(n,r){var e=n.x,t=n.y,u=n.r,i=r.x,o=r.y,a=r.r,c=i-e,f=o-t,l=a-u,h=Math.sqrt(c*c+f*f);return{x:(e+i+c/h*l)/2,y:(t+o+f/h*l)/2,r:(h+u+a)/2}}function m(n,r,e){var t=n.x,u=n.y,i=n.r,o=r.x,a=r.y,c=r.r,f=e.x,l=e.y,h=e.r,v=2*(t-o),s=2*(u-a),d=2*(c-i),x=t*t+u*u-i*i-o*o-a*a+c*c,p=2*(t-f),y=2*(u-l),g=2*(h-i),_=t*t+u*u-i*i-f*f-l*l+h*h,m=p*s-v*y,w=(s*_-y*x)/m-t,M=(y*d-s*g)/m,q=(p*x-v*_)/m-u,B=(v*g-p*d)/m,E=M*M+B*B-1,A=2*(w*M+q*B+i),k=w*w+q*q-i*i,b=(-A-Math.sqrt(A*A-4*E*k))/(2*E);return{x:w+M*b+t,y:q+B*b+u,r:b}}function w(n,r,e){var t=n._,u=r._,i=e._,o=t.x,a=t.y,c=u.r+i.r,f=t.r+i.r,l=u.x-o,h=u.y-a,v=l*l+h*h;if(v){var s=.5+((f*=f)-(c*=c))/(2*v),d=Math.sqrt(Math.max(0,2*c*(f+v)-(f-=v)*f-c*c))/(2*v);i.x=o+s*l+d*h,i.y=a+s*h-d*l}else i.x=o+f,i.y=a;e.score=i.x*i.x+i.y*i.y}function M(n,r){var e=r.x-n.x,t=r.y-n.y,u=n.r+r.r;return u*u>e*e+t*t}function q(n){return{_:n,next:null,previous:null,score:NaN}}function B(n){if(f=n.length){n=n.map(q);var r,e,t,u,i,o,a,c,f;if(r=n[0],r.score=r._.r*r._.r,r._.x=r._.r,r._.y=0,f>1&&(e=n[1],e.score=e._.r*e._.r,e._.x=-e._.r,e._.y=0,f>2)){w(e,r,t=n[2]),r.next=t.previous=e,e.next=r.previous=t,t.next=e.previous=r;n:for(u=3;f>u;++u){if(w(r,e,t=n[u]),(o=r.previous)===(i=e.next)){if(M(i._,t._)){r=e,e=i,--u;continue n}}else{a=i._.r,c=o._.r;do if(c>=a){if(M(i._,t._)){e=i,r.next=e,e.previous=r,--u;continue n}i=i.next,a+=i._.r}else{if(M(o._,t._)){r=o,r.next=e,e.previous=r,--u;continue n}o=o.previous,c+=o._.r}while(i!==o.next)}for(t.previous=r,t.next=e,r.next=e.previous=e=t;(t=t.next)!==e;)t.score<r.score&&(r=t,e=r.next)}}}}function E(){function n(n){var t=e(n);return r(t[0]),t}function r(n){n.x=t/2,n.y=u/2,n.eachAfter(A),i>0&&n.eachAfter(k(i*n.r/Math.min(t,u))),n.eachBefore(I(Math.min(t,u)/(2*n.r)))}var e=s(),t=1,u=1,i=0;return d(n,e),n.revalue=function(n){return e.revalue(n),r(n[0]),n},n.size=function(r){return arguments.length?(t=+r[0],u=+r[1],n):[t,u]},n.padding=function(r){return arguments.length?(i=+r,n):i},n}function A(n){if(n.children){B(n.children);var r=x(n.children);n.children.forEach(z(-r.x,-r.y)),n.r=r.r}else n.r=Math.sqrt(n.value)}function k(n){var r=b(n),e=b(-n);return function(t){t.children&&(t.children.forEach(r),A(t),t.children.forEach(e),t.r+=n)}}function b(n){return function(r){r.r+=n}}function I(n){return function(r){var e=r.parent;r.r*=n,e&&(r.x=e.x+n*r.x,r.y=e.y+n*r.y)}}function z(n,r){return function(e){e.x+=n,e.y+=r}}function S(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function C(n,r,e,t,u){for(var i,o=n.children,a=-1,c=o.length,f=(t-r)/n.value;++a<c;)i=o[a],i.y0=e,i.y1=u,i.x0=r,i.x1=r+=i.value*f}function D(n){var r=n.depth;return n.eachBefore(function(n){n.depth>r&&(r=n.depth)}),r}function N(){function n(n){var e=t(n);return r(e[0]),e}function r(n){var r=D(n)+1;n.x0=n.y0=o,n.x1=u,n.y1=i/r,n.eachBefore(e(i,r)),a&&n.eachBefore(S)}function e(n,r){return function(e){e.children&&C(e,e.x0,n*(e.depth+1)/r,e.x1,n*(e.depth+2)/r);var t=e.x0,u=e.y0,i=e.x1-o,a=e.y1-o;t>i&&(t=i=(t+i)/2),u>a&&(u=a=(u+a)/2),e.x0=t,e.y0=u,e.x1=i,e.y1=a}}var t=s(),u=1,i=1,o=0,a=!1;return d(n,t),n.revalue=function(n){return t.revalue(n),r(n[0]),n},n.round=function(r){return arguments.length?(a=!!r,n):a},n.size=function(r){return arguments.length?(u=+r[0],i=+r[1],n):[u,i]},n.padding=function(r){return arguments.length?(o=+r,n):o},n}function j(){function n(n){var e=t(n);return r(e[0]),e}function r(n){n.x0=n.y0=-o,n.x1=u+o,n.y1=i+o,n.eachBefore(e),l&&n.eachBefore(S)}function e(n){var r=n.x0+o,e=n.y0+o,t=n.x1-o,u=n.y1-o;r>t&&(r=t=(r+t)/2),e>u&&(e=u=(e+u)/2),n.x0=r,n.y0=e,n.x1=t,n.y1=u,n.children&&(r+=c,e+=c,t-=c,u-=c,r>t&&(r=t=(r+t)/2),e>u&&(e=u=(e+u)/2),f(n,r,e,t,u))}var t=s(),u=1,i=1,o=0,a=0,c=0,f=K,l=!1;return d(n,t),n.revalue=function(n){return t.revalue(n),r(n[0]),n},n.round=function(r){return arguments.length?(l=!!r,n):l},n.size=function(r){return arguments.length?(u=+r[0],i=+r[1],n):[u,i]},n.tile=function(r){return arguments.length?(f=r,n):f},n.padding=function(r){return arguments.length?(o=(a=+r)/2,c=o,n):2*o},n.paddingInner=function(r){return arguments.length?(o=r/2,c=a-o,n):2*o},n.paddingOuter=function(r){return arguments.length?(a=+r,c=a-o,n):a},n}function O(n,r,e,t,u){var i=n.children;$(i,0,i.length,n.value,r,e,t,u)}function $(n,r,e,t,u,i,o,a){if(r>=e-1)return n=n[r],n.x0=u,n.y0=i,n.x1=o,n.y1=a,void 0;var c=r,f=t/2,l=0;do l+=n[c].value;while(++c<e-1&&f>l);var h=t-l;if(a-i>o-u){var v=(i*h+a*l)/t;$(n,r,c,l,u,i,o,v),$(n,c,e,h,u,v,o,a)}else{var s=(u*h+o*l)/t;$(n,r,c,l,u,i,s,a),$(n,c,e,h,s,i,o,a)}}function F(n,r,e,t,u){for(var i,o=n.children,a=-1,c=o.length,f=(u-e)/n.value;++a<c;)i=o[a],i.x0=r,i.x1=t,i.y0=e,i.y1=e+=i.value*f}function G(n,r,e,t,u){(1&n.depth?F:C)(n,r,e,t,u)}var H="0.0.2";a.prototype={constructor:a,each:t,eachBefore:i,eachAfter:u,ancestors:r,descendants:e,sort:o};var J="$",K=function L(n){function r(r,e,t,u,i){for(var o,a,c,f,l,h,v,s,d,x,p,y,g,_,m=r.children,w=0,M=m.length,q=r.value;M>w;){if(h=u-e,v=i-t,s=(o=m[w]).value,o._squarify)for(c=w+1;c<Math.abs(o._squarify);++c)s+=m[c].value;else{for(d=x=s,p=Math.max(v/h,h/v)/(q*n),y=s*s*p,_=Math.max(x/y,y/d),c=w+1;M>c;++c){if(s+=a=m[c].value,d>a&&(d=a),a>x&&(x=a),y=s*s*p,g=Math.max(x/y,y/d),g>_){s-=a;break}_=g}o._squarify=v>h?c:-c}if(o._squarify>0){for(f=e,l=t+v*s/q,h/=s;c>w;++w)o=m[w],o.x0=f,o.y0=t,o.y1=l,o.x1=f+=o.value*h;t=l}else{for(l=t,f=e+h*s/q,v/=s;c>w;++w)o=m[w],o.y0=l,o.x0=e,o.x1=f,o.y1=l+=o.value*v;e=f}q-=s}}return r.ratio=function(n){return L((n=+n)>1?n:1)},r}((1+Math.sqrt(5))/2);n.version=H,n.hierarchy=s,n.pack=E,n.packCircles=B,n.packEnclosingCircle=x,n.partition=N,n.treemap=j,n.treemapBinary=O,n.treemapDice=C,n.treemapSlice=F,n.treemapSliceDice=G,n.treemapSquarify=K});
    !function(n,r){"object"==typeof exports&&"undefined"!=typeof module?r(exports):"function"==typeof define&&define.amd?define(["exports"],r):r(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function r(n){return n.value}function t(n,r){return r.value-n.value}function e(n){return null==n?null:u(n)}function u(n){if("function"!=typeof n)throw new Error;return n}function i(n,r){for(var t,e,u=[n];null!=(n=u.pop());)if(r(n),t=n.children)for(e=t.length-1;e>=0;--e)u.push(t[e])}function o(n){return n.id}function a(n){return n.parentId}function f(){function n(n){var e,u,o,a,f,c,l,h,d=n.length,x=new Array(d),s={};for(o=0;d>o;++o){e=n[o],c=x[o]={};for(u in e)u in R||(c[u]=e[u]);if(null!=(l=r(e,o,n))&&(l+="")){if(h=Q+(c.id=l),h in s)throw new Error("duplicate: "+l);s[h]=c}}for(o=0;d>o;++o)if(c=x[o],l=t(n[o],o,n),null!=l&&(l+="")){if(f=s[Q+l],!f)throw new Error("missing: "+l);f.children?f.children.push(c):f.children=[c]}else{if(a)throw new Error("multiple roots");a=c}if(!a)throw new Error("no root");if(i(a,function(){--d}),d>0)throw new Error("cycle");return a}var r=o,t=a;return n.id=function(t){return arguments.length?(r=u(t),n):r},n.parentId=function(r){return arguments.length?(t=u(r),n):t},n}function c(){for(var n=this,r=[n];n=n.parent;)r.push(n);return r}function l(n,r){var t,e,u,i,o=[n];do for(t=o.reverse(),o=[];null!=(n=t.pop());)if(r(n),e=n.children)for(u=0,i=e.length;i>u;++u)o.push(e[u]);while(o.length)}function h(){var n=[];return l(this,function(r){n.push(r)}),n}function d(){var n=[];return l(this,function(r){r.children||n.push(r)}),n}function x(n){for(var r,t,e,u,i,o=new v(n),a=[o];null!=(r=a.pop());)if((e=r.data.children)&&(i=e.length))for(r.children=new Array(i),u=i-1;u>=0;--u)a.push(t=r.children[u]=new v(e[u])),t.parent=r,t.depth=r.depth+1;return o}function s(){var n=x(this);return i(n,function(n){n.data=n.data.data}),n}function v(n){this.data=n,this.depth=0,this.parent=null}function p(n){return _(y(n),[])}function y(n){for(var r,t=(n=n.slice()).length,e=null,u=e;t;){var i={circle:n[t-1],next:null};u=u?u.next=i:e=i,n[r]=n[--t]}return{head:e,tail:u}}function g(n,r){var t=r.x-n.x,e=r.y-n.y,u=n.r-r.r;return u*u+1e-6>t*t+e*e}function _(n,r){var t,e,u,i=null,o=n.head;switch(r.length){case 1:t=r[0];break;case 2:t=w(r[0],r[1]);break;case 3:t=m(r[0],r[1],r[2])}for(;o;)u=o.circle,e=o.next,t&&g(t,u)?i=o:(i?(n.tail=i,i.next=null):n.head=n.tail=null,r.push(u),t=_(n,r),r.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),i=n.tail,i.next=e),o=e;return n.tail=i,t}function w(n,r){var t=n.x,e=n.y,u=n.r,i=r.x,o=r.y,a=r.r,f=i-t,c=o-e,l=a-u,h=Math.sqrt(f*f+c*c);return{x:(t+i+f/h*l)/2,y:(e+o+c/h*l)/2,r:(h+u+a)/2}}function m(n,r,t){var e=n.x,u=n.y,i=n.r,o=r.x,a=r.y,f=r.r,c=t.x,l=t.y,h=t.r,d=2*(e-o),x=2*(u-a),s=2*(f-i),v=e*e+u*u-i*i-o*o-a*a+f*f,p=2*(e-c),y=2*(u-l),g=2*(h-i),_=e*e+u*u-i*i-c*c-l*l+h*h,w=p*x-d*y,m=(x*_-y*v)/w-e,M=(y*s-x*g)/w,q=(p*v-d*_)/w-u,E=(d*g-p*s)/w,b=M*M+E*E-1,k=2*(m*M+q*E+i),I=m*m+q*q-i*i,z=(-k-Math.sqrt(k*k-4*b*I))/(2*b);return{x:m+M*z+e,y:q+E*z+u,r:z}}function M(n,r){for(var t,e,u,i=[n],o=[];null!=(n=i.pop());)if(o.push(n),t=n.children)for(e=0,u=t.length;u>e;++e)i.push(t[e]);for(;null!=(n=o.pop());)r(n)}function q(n,r){M(n,function(n){for(var t=+r(n.data)||0,e=n.children,u=e&&e.length;--u>=0;)t+=e[u].value;n.value=t})}function E(n,r){i(n,function(n){n.children&&n.children.sort(r)})}function b(n,r,t){var e=n._,u=r._,i=t._,o=e.x,a=e.y,f=u.r+i.r,c=e.r+i.r,l=u.x-o,h=u.y-a,d=l*l+h*h;if(d){var x=.5+((c*=c)-(f*=f))/(2*d),s=Math.sqrt(Math.max(0,2*f*(c+d)-(c-=d)*c-f*f))/(2*d);i.x=o+x*l+s*h,i.y=a+x*h-s*l}else i.x=o+c,i.y=a;t.score=i.x*i.x+i.y*i.y}function k(n,r){var t=r.x-n.x,e=r.y-n.y,u=n.r+r.r;return u*u>t*t+e*e}function I(n){return{_:n,next:null,previous:null,score:NaN}}function z(n){if(c=n.length){n=n.map(I);var r,t,e,u,i,o,a,f,c;if(r=n[0],r.score=r._.r*r._.r,r._.x=r._.r,r._.y=0,c>1&&(t=n[1],t.score=t._.r*t._.r,t._.x=-t._.r,t._.y=0,c>2)){b(t,r,e=n[2]),r.next=e.previous=t,t.next=r.previous=e,e.next=t.previous=r;n:for(u=3;c>u;++u){if(b(r,t,e=n[u]),(o=r.previous)===(i=t.next)){if(k(i._,e._)){r=t,t=i,--u;continue n}}else{a=i._.r,f=o._.r;do if(f>=a){if(k(i._,e._)){t=i,r.next=t,t.previous=r,--u;continue n}i=i.next,a+=i._.r}else{if(k(o._,e._)){r=o,r.next=t,t.previous=r,--u;continue n}o=o.previous,f+=o._.r}while(i!==o.next)}for(e.previous=r,e.next=t,r.next=t.previous=t=e;(e=e.next)!==t;)e.score<r.score&&(r=e,t=r.next)}}}}function N(n){return Math.sqrt(n.value)}function S(){function n(n){var r=x(n);return o&&q(r,o),a&&E(r,a),r.x=f/2,r.y=c/2,u?(i(r,A(u)),M(r,D(l/2)),i(r,j(1))):(i(r,A(N)),M(r,B),l&&M(r,D(l*r.r/Math.min(f,c))),i(r,j(Math.min(f,c)/(2*r.r)))),r}var u=null,o=r,a=t,f=1,c=1,l=0;return n.radius=function(r){return arguments.length?(u=e(r),n):u},n.value=function(r){return arguments.length?(o=e(r),n):o},n.sort=function(r){return arguments.length?(a=e(r),n):a},n.size=function(r){return arguments.length?(f=+r[0],c=+r[1],n):[f,c]},n.padding=function(r){return arguments.length?(l=Math.max(0,+r||0),n):l},n}function A(n){return function(r){r.children||(r.r=Math.max(0,+n(r)||0))}}function B(n){if(r=n.children){z(r);var r,t,e,u=p(r),i=r.length;for(e=0;i>e;++e)t=r[e],t.x-=u.x,t.y-=u.y;n.r=u.r}}function D(n){return function(r){if(t=r.children){var t,e,u=t.length;for(e=0;u>e;++e)t[e].r+=n;for(B(r),e=0;u>e;++e)t[e].r-=n;r.r+=n}}}function j(n){return function(r){var t=r.parent;r.r*=n,t&&(r.x=t.x+n*r.x,r.y=t.y+n*r.y)}}function O(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function $(n,r,t,e,u){for(var i,o=n.children,a=-1,f=o.length,c=(e-r)/n.value;++a<f;)i=o[a],i.y0=t,i.y1=u,i.x0=r,i.x1=r+=i.value*c}function C(n){var r=n.depth;return n.eachBefore(function(n){n.depth>r&&(r=n.depth)}),r}function F(){function n(n){var r=x(n);q(r,a),f&&E(r,f);var t=C(r)+1;return r.x0=r.y0=h,r.x1=c,r.y1=l/t,i(r,o(l,t)),d&&i(r,O),r}function o(n,r){return function(t){t.children&&$(t,t.x0,n*(t.depth+1)/r,t.x1,n*(t.depth+2)/r);var e=t.x0,u=t.y0,i=t.x1-h,o=t.y1-h;e>i&&(e=i=(e+i)/2),u>o&&(u=o=(u+o)/2),t.x0=e,t.y0=u,t.x1=i,t.y1=o}}var a=r,f=t,c=1,l=1,h=0,d=!1;return n.value=function(r){return arguments.length?(a=u(r),n):a},n.sort=function(r){return arguments.length?(f=e(r),n):f},n.round=function(r){return arguments.length?(d=!!r,n):d},n.size=function(r){return arguments.length?(c=+r[0],l=+r[1],n):[c,l]},n.padding=function(r){return arguments.length?(h=+r,n):h},n}function G(){function n(n){var r=x(n);return q(r,f),c&&E(r,c),o(r)}function o(n){return n.x0=n.y0=-d,n.x1=l+d,n.y1=h+d,i(n,a),y&&i(n,O),n}function a(n){var r=n.x0+d,t=n.y0+d,e=n.x1-d,u=n.y1-d;r>e&&(r=e=(r+e)/2),t>u&&(t=u=(t+u)/2),n.x0=r,n.y0=t,n.x1=e,n.y1=u,n.children&&(r+=v,t+=v,e-=v,u-=v,r>e&&(r=e=(r+e)/2),t>u&&(t=u=(t+u)/2),p(n,r,t,e,u))}var f=r,c=t,l=1,h=1,d=0,s=0,v=0,p=T,y=!1;return n.update=function(n){return q(n,f),o(n)},n.value=function(r){return arguments.length?(f=u(r),n):f},n.sort=function(r){return arguments.length?(c=e(r),n):c},n.round=function(r){return arguments.length?(y=!!r,n):y},n.size=function(r){return arguments.length?(l=+r[0],h=+r[1],n):[l,h]},n.tile=function(r){return arguments.length?(p=u(r),n):p},n.padding=function(r){return arguments.length?(d=(s=+r)/2,v=d,n):2*d},n.paddingInner=function(r){return arguments.length?(d=r/2,v=s-d,n):2*d},n.paddingOuter=function(r){return arguments.length?(s=+r,v=s-d,n):s},n}function H(n,r,t,e,u){var i=n.children;J(i,0,i.length,n.value,r,t,e,u)}function J(n,r,t,e,u,i,o,a){if(r>=t-1)return n=n[r],n.x0=u,n.y0=i,n.x1=o,n.y1=a,void 0;var f=r,c=e/2,l=0;do l+=n[f].value;while(++f<t-1&&c>l);var h=e-l;if(a-i>o-u){var d=(i*h+a*l)/e;J(n,r,f,l,u,i,o,d),J(n,f,t,h,u,d,o,a)}else{var x=(u*h+o*l)/e;J(n,r,f,l,u,i,x,a),J(n,f,t,h,x,i,o,a)}}function K(n,r,t,e,u){for(var i,o=n.children,a=-1,f=o.length,c=(u-t)/n.value;++a<f;)i=o[a],i.x0=r,i.x1=e,i.y0=t,i.y1=t+=i.value*c}function L(n,r,t,e,u){(1&n.depth?K:$)(n,r,t,e,u)}var P="0.0.2",Q="$",R={id:1,parentId:1,children:1};v.prototype=x.prototype={constructor:v,ancestors:c,descendants:h,leaves:d,copy:s};var T=function U(n){function r(r,t,e,u,i){for(var o,a,f,c,l,h,d,x,s,v,p,y,g,_,w=r.children,m=0,M=w.length,q=r.value;M>m;){if(h=u-t,d=i-e,x=(o=w[m]).value,o._squarify)for(f=m+1;f<Math.abs(o._squarify);++f)x+=w[f].value;else{for(s=v=x,p=Math.max(d/h,h/d)/(q*n),y=x*x*p,_=Math.max(v/y,y/s),f=m+1;M>f;++f){if(x+=a=w[f].value,s>a&&(s=a),a>v&&(v=a),y=x*x*p,g=Math.max(v/y,y/s),g>_){x-=a;break}_=g}o._squarify=d>h?f:-f}if(o._squarify>0){for(c=t,l=e+d*x/q,h/=x;f>m;++m)o=w[m],o.x0=c,o.y0=e,o.y1=l,o.x1=c+=o.value*h;o.x1=u,e=l}else{for(l=e,c=t+h*x/q,d/=x;f>m;++m)o=w[m],o.y0=l,o.x0=t,o.x1=c,o.y1=l+=o.value*d;o.y1=i,t=c}q-=x}o.x1=u,o.y1=i}return r.ratio=function(n){return U((n=+n)>1?n:1)},r}((1+Math.sqrt(5))/2);n.version=P,n.hierarchy=f,n.hierarchyNode=x,n.pack=S,n.partition=F,n.treemap=G,n.treemapBinary=H,n.treemapDice=$,n.treemapSlice=K,n.treemapSliceDice=L,n.treemapSquarify=T});
    25 changes: 15 additions & 10 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -12,30 +12,35 @@
    }

    </style>
    <svg width="960" height="960">
    <g transform="translate(480,480)"></g>
    </svg>
    <svg width="960" height="960"></svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
    <script src="d3-hierarchy.min.js"></script>
    <script>

    var svg = d3.select("svg"),
    size = +svg.attr("width");

    var color = d3.scaleRainbow()
    .domain([0, 2 * Math.PI]);

    var circles = d3.range(2000)
    .map(d3.randomUniform(8, 26))
    .map(function(r) { return {r: Math.max(1, r)}; });

    d3_hierarchy.packCircles(circles);
    var root = d3_hierarchy.pack()
    .size([size, size])
    .radius(function(d) { return d.data.r; })
    ({children: circles});

    d3.select("g")
    svg
    .selectAll("circle")
    .data(circles
    .filter(function(d) { return -500 < d.x && d.x < 500 && -500 < d.y && d.y < 500; }))
    .data(root
    .leaves()
    .filter(function(d) { return -30 < d.x && d.x < size + 30 && -30 < d.y && d.y < size + 30; }))
    .enter().append("circle")
    .style("fill", function(d) { return color(Math.atan2(d.y, d.x)); })
    .attr("cx", function(d) { return d.x / Math.sqrt(d.x * d.x + d.y * d.y) * 720; })
    .attr("cy", function(d) { return d.y / Math.sqrt(d.x * d.x + d.y * d.y) * 720; })
    .style("fill", function(d) { return color(d.angle = Math.atan2(d.y - size / 2, d.x - size / 2)); })
    .attr("cx", function(d) { return size / 2 + Math.cos(d.angle) * (size / Math.SQRT2 + 30); })
    .attr("cy", function(d) { return size / 2 + Math.sin(d.angle) * (size / Math.SQRT2 + 30); })
    .attr("r", function(d) { return d.r - 0.25; })
    .transition()
    .ease(d3.easeCubicOut)
  11. mbostock revised this gist Mar 22, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion d3-hierarchy.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    !function(n,r){"object"==typeof exports&&"undefined"!=typeof module?r(exports):"function"==typeof define&&define.amd?define(["exports"],r):r(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function r(){for(var n=this,r=[this];n=n.parent;)r.push(n);return r}function e(){var n=[];return this.each(function(r){n.push(r)}),n}function t(n){var r,e,t,u,i=this,o=[i];do for(r=o.reverse(),o=[];null!=(i=r.pop());)if(n(i),e=i.children)for(t=0,u=e.length;u>t;++t)o.push(e[t]);while(o.length);return this}function u(n){for(var r,e,t=this,u=[t],i=[];null!=(t=u.pop());)if(i.push(t),r=t.children)for(e=r.length-1;e>=0;--e)u.push(r[e]);for(;null!=(t=i.pop());)n(t);return this}function i(n){for(var r,e,t=this,u=[t];null!=(t=u.pop());)if(n(t),r=t.children)for(e=r.length-1;e>=0;--e)u.push(r[e]);return this}function o(n){return this.eachBefore(function(r){r.children&&r.children.sort(n)})}function a(n,r){this.data=n,this.index=r}function c(n){return n.id}function f(n){return n.parent}function l(n){return n.value}function h(n,r){return r.value-n.value}function v(n){var r=new Array(n);return function(n){var e=n.index;if(r[e])throw new Error("cycle");n.depth=n.parent?n.parent.depth+1:0,r[e]=1}}function s(){function n(n){var t=r(n),u=t[0],i=-1;return u.eachBefore(v(n.length)),u.eachAfter(e(n)),null!=o&&u.sort(o),u.each(function(n){t[++i]=n}),t.data=n,t}function r(n){var r,e,i,o,c,f,l,h=n.length,v={},s=new Array(h);for(r=0;h>r;++r)if(s[r]=c=new a(e=n[r],r),null!=(i=t(e,r,n))){if(o=J+(c.id=i+=""),o in v)throw new Error("duplicate: "+i);v[o]=c}for(r=0;h>r;++r)if(c=s[r],i=u(e=n[r],r,n),null==i){if(l)throw new Error("multiple roots");l=s[0],s[0]=c,s[r]=l}else{if(f=v[J+i],!f)throw new Error("missing: "+i);c.parent=f,f.children?f.children.push(c):f.children=[c]}if(!l)throw new Error("cycle");return s}function e(n){return function(r){for(var e=+i(r.data,r.index,n)||0,t=r.children,u=t&&t.length;--u>=0;)e+=t[u].value;r.value=e}}var t=c,u=f,i=l,o=h;return n.revalue=function(n){return n[0].eachAfter(e(n.data)),n},n.id=function(r){return arguments.length?(t=r,n):t},n.parentId=function(r){return arguments.length?(u=r,n):u},n.value=function(r){return arguments.length?(i=r,n):i},n.sort=function(r){return arguments.length?(o=r,n):o},n}function d(n,r){var e=r.x-n.x,t=r.y-n.y,u=n.r-r.r;return u*u+1e-6>e*e+t*t}function x(n){return y(p(n),[])}function p(n){for(var r,e=(n=n.slice()).length,t=null,u=t;e;){var i={circle:n[e-1],next:null};u=u?u.next=i:t=i,n[r]=n[--e]}return{head:t,tail:u}}function y(n,r){var e,t,u,i=null,o=n.head;switch(r.length){case 1:e=r[0];break;case 2:e=g(r[0],r[1]);break;case 3:e=_(r[0],r[1],r[2])}for(;o;)u=o.circle,t=o.next,e&&d(e,u)?i=o:(i?(n.tail=i,i.next=null):n.head=n.tail=null,r.push(u),e=y(n,r),r.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),i=n.tail,i.next=t),o=t;return n.tail=i,e}function g(n,r){var e=n.x,t=n.y,u=n.r,i=r.x,o=r.y,a=r.r,c=i-e,f=o-t,l=a-u,h=Math.sqrt(c*c+f*f);return{x:(e+i+c/h*l)/2,y:(t+o+f/h*l)/2,r:(h+u+a)/2}}function _(n,r,e){var t=n.x,u=n.y,i=n.r,o=r.x,a=r.y,c=r.r,f=e.x,l=e.y,h=e.r,v=2*(t-o),s=2*(u-a),d=2*(c-i),x=t*t+u*u-i*i-o*o-a*a+c*c,p=2*(t-f),y=2*(u-l),g=2*(h-i),_=t*t+u*u-i*i-f*f-l*l+h*h,m=p*s-v*y,w=(s*_-y*x)/m-t,M=(y*d-s*g)/m,q=(p*x-v*_)/m-u,B=(v*g-p*d)/m,E=M*M+B*B-1,A=2*(w*M+q*B+i),b=w*w+q*q-i*i,k=(-A-Math.sqrt(A*A-4*E*b))/(2*E);return{x:w+M*k+t,y:q+B*k+u,r:k}}function m(n,r){var e=r.x-n.x,t=r.y-n.y,u=n.r+r.r;return u*u>e*e+t*t}function w(n,r,e){var t=n._,u=r._,i=e._,o=t.x,a=t.y,c=u.r+i.r,f=t.r+i.r,l=u.x-o,h=u.y-a,v=l*l+h*h;if(v){var s=.5+((f*=f)-(c*=c))/(2*v),d=Math.sqrt(Math.max(0,2*c*(f+v)-(f-=v)*f-c*c))/(2*v);i.x=o+s*l+d*h,i.y=a+s*h-d*l}else i.x=o+f,i.y=a;e.score=i.x*i.x+i.y*i.y}function M(n){return{_:n,next:null,previous:null,score:NaN}}function q(n){if(f=n.length){n=n.map(M);var r,e,t,u,i,o,a,c,f;if(r=n[0],r.score=r._.r*r._.r,r._.x=r._.r,r._.y=0,f>1&&(e=n[1],e.score=e._.r*e._.r,e._.x=-e._.r,e._.y=0,f>2)){w(e,r,t=n[2]),r.next=t.previous=e,e.next=r.previous=t,t.next=e.previous=r;n:for(u=3;f>u;++u){if(w(r,e,t=n[u]),(o=r.previous)===(i=e.next)){if(m(i._,t._)){r=e,e=i,--u;continue n}}else{a=i._.r,c=o._.r;do if(c>=a){if(m(i._,t._)){e=i,r.next=e,e.previous=r,--u;continue n}i=i.next,a+=i._.r}else{if(m(o._,t._)){r=o,r.next=e,e.previous=r,--u;continue n}o=o.previous,c+=o._.r}while(i!==o.next)}for(t.previous=r,t.next=e,r.next=e.previous=e=t;(t=t.next)!==e;)t.score<r.score&&(r=t,e=r.next)}}}}function B(n,r){return n.revalue=r.revalue,n.id=function(){var e=r.id.apply(r,arguments);return e===r?n:e},n.parentId=function(){var e=r.parentId.apply(r,arguments);return e===r?n:e},n.value=function(){var e=r.value.apply(r,arguments);return e===r?n:e},n.sort=function(){var e=r.sort.apply(r,arguments);return e===r?n:e},n}function E(){function n(n){var t=e(n);return r(t[0]),t}function r(n){n.x=t/2,n.y=u/2,n.eachAfter(A),i>0&&n.eachAfter(b(i*n.r/Math.min(t,u))),n.eachBefore(I(Math.min(t,u)/(2*n.r)))}var e=s(),t=1,u=1,i=0;return B(n,e),n.revalue=function(n){return e.revalue(n),r(n[0]),n},n.size=function(r){return arguments.length?(t=+r[0],u=+r[1],n):[t,u]},n.padding=function(r){return arguments.length?(i=+r,n):i},n}function A(n){if(n.children){q(n.children);var r=x(n.children);n.children.forEach(z(-r.x,-r.y)),n.r=r.r}else n.r=Math.sqrt(n.value)}function b(n){var r=k(n),e=k(-n);return function(t){t.children&&(t.children.forEach(r),A(t),t.children.forEach(e),t.r+=n)}}function k(n){return function(r){r.r+=n}}function I(n){return function(r){var e=r.parent;r.r*=n,e&&(r.x=e.x+n*r.x,r.y=e.y+n*r.y)}}function z(n,r){return function(e){e.x+=n,e.y+=r}}function S(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function C(n,r,e,t,u){for(var i,o=n.children,a=-1,c=o.length,f=(t-r)/n.value;++a<c;)i=o[a],i.y0=e,i.y1=u,i.x0=r,i.x1=r+=i.value*f}function D(n){var r=n.depth;return n.eachBefore(function(n){n.depth>r&&(r=n.depth)}),r}function N(){function n(n){var e=t(n);return r(e[0]),e}function r(n){var r=D(n)+1;n.x0=n.y0=o,n.x1=u,n.y1=i/r,n.eachBefore(e(i,r)),a&&n.eachBefore(S)}function e(n,r){return function(e){e.children&&C(e,e.x0,n*(e.depth+1)/r,e.x1,n*(e.depth+2)/r);var t=e.x0,u=e.y0,i=e.x1-o,a=e.y1-o;t>i&&(t=i=(t+i)/2),u>a&&(u=a=(u+a)/2),e.x0=t,e.y0=u,e.x1=i,e.y1=a}}var t=s(),u=1,i=1,o=0,a=!1;return B(n,t),n.revalue=function(n){return t.revalue(n),r(n[0]),n},n.round=function(r){return arguments.length?(a=!!r,n):a},n.size=function(r){return arguments.length?(u=+r[0],i=+r[1],n):[u,i]},n.padding=function(r){return arguments.length?(o=+r,n):o},n}function j(){function n(n){var e=t(n);return r(e[0]),e}function r(n){n.x0=n.y0=-o,n.x1=u+o,n.y1=i+o,n.eachBefore(e),l&&n.eachBefore(S)}function e(n){var r=n.x0+o,e=n.y0+o,t=n.x1-o,u=n.y1-o;r>t&&(r=t=(r+t)/2),e>u&&(e=u=(e+u)/2),n.x0=r,n.y0=e,n.x1=t,n.y1=u,n.children&&(r+=c,e+=c,t-=c,u-=c,r>t&&(r=t=(r+t)/2),e>u&&(e=u=(e+u)/2),f(n,r,e,t,u))}var t=s(),u=1,i=1,o=0,a=0,c=0,f=K,l=!1;return B(n,t),n.revalue=function(n){return t.revalue(n),r(n[0]),n},n.round=function(r){return arguments.length?(l=!!r,n):l},n.size=function(r){return arguments.length?(u=+r[0],i=+r[1],n):[u,i]},n.tile=function(r){return arguments.length?(f=r,n):f},n.padding=function(r){return arguments.length?(o=(a=+r)/2,c=o,n):2*o},n.paddingInner=function(r){return arguments.length?(o=r/2,c=a-o,n):2*o},n.paddingOuter=function(r){return arguments.length?(a=+r,c=a-o,n):a},n}function O(n,r,e,t,u){var i=n.children;$(i,0,i.length,n.value,r,e,t,u)}function $(n,r,e,t,u,i,o,a){if(r>=e-1)return n=n[r],n.x0=u,n.y0=i,n.x1=o,n.y1=a,void 0;var c=r,f=t/2,l=0;do l+=n[c].value;while(++c<e-1&&f>l);var h=t-l;if(a-i>o-u){var v=(i*h+a*l)/t;$(n,r,c,l,u,i,o,v),$(n,c,e,h,u,v,o,a)}else{var s=(u*h+o*l)/t;$(n,r,c,l,u,i,s,a),$(n,c,e,h,s,i,o,a)}}function F(n,r,e,t,u){for(var i,o=n.children,a=-1,c=o.length,f=(u-e)/n.value;++a<c;)i=o[a],i.x0=r,i.x1=t,i.y0=e,i.y1=e+=i.value*f}function G(n,r,e,t,u){(1&n.depth?F:C)(n,r,e,t,u)}var H="0.0.2";a.prototype={constructor:a,each:t,eachBefore:i,eachAfter:u,ancestors:r,descendants:e,sort:o};var J="$",K=function L(n){function r(r,e,t,u,i){for(var o,a,c,f,l,h,v,s,d,x,p,y,g,_,m=r.children,w=0,M=m.length,q=r.value;M>w;){if(h=u-e,v=i-t,s=(o=m[w]).value,o._squarify)for(c=w+1;c<Math.abs(o._squarify);++c)s+=m[c].value;else{for(d=x=s,p=Math.max(v/h,h/v)/(q*n),y=s*s*p,_=Math.max(x/y,y/d),c=w+1;M>c;++c){if(s+=a=m[c].value,d>a&&(d=a),a>x&&(x=a),y=s*s*p,g=Math.max(x/y,y/d),g>_){s-=a;break}_=g}o._squarify=v>h?c:-c}if(o._squarify>0){for(f=e,l=t+v*s/q,h/=s;c>w;++w)o=m[w],o.x0=f,o.y0=t,o.y1=l,o.x1=f+=o.value*h;t=l}else{for(l=t,f=e+h*s/q,v/=s;c>w;++w)o=m[w],o.y0=l,o.x0=e,o.x1=f,o.y1=l+=o.value*v;e=f}q-=s}}return r.ratio=function(n){return L((n=+n)>1?n:1)},r}((1+Math.sqrt(5))/2);n.version=H,n.hierarchy=s,n.enclosingCircle=x,n.packCircles=q,n.pack=E,n.partition=N,n.treemap=j,n.treemapBinary=O,n.treemapDice=C,n.treemapSlice=F,n.treemapSliceDice=G,n.treemapSquarify=K});
    !function(n,r){"object"==typeof exports&&"undefined"!=typeof module?r(exports):"function"==typeof define&&define.amd?define(["exports"],r):r(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function r(){for(var n=this,r=[this];n=n.parent;)r.push(n);return r}function e(){var n=[];return this.each(function(r){n.push(r)}),n}function t(n){var r,e,t,u,i=this,o=[i];do for(r=o.reverse(),o=[];null!=(i=r.pop());)if(n(i),e=i.children)for(t=0,u=e.length;u>t;++t)o.push(e[t]);while(o.length);return this}function u(n){for(var r,e,t=this,u=[t],i=[];null!=(t=u.pop());)if(i.push(t),r=t.children)for(e=r.length-1;e>=0;--e)u.push(r[e]);for(;null!=(t=i.pop());)n(t);return this}function i(n){for(var r,e,t=this,u=[t];null!=(t=u.pop());)if(n(t),r=t.children)for(e=r.length-1;e>=0;--e)u.push(r[e]);return this}function o(n){return this.eachBefore(function(r){r.children&&r.children.sort(n)})}function a(n,r){this.data=n,this.index=r}function c(n){return n.id}function f(n){return n.parent}function l(n){return n.value}function h(n,r){return r.value-n.value}function v(n){var r=new Array(n);return function(n){var e=n.index;if(r[e])throw new Error("cycle");n.depth=n.parent?n.parent.depth+1:0,r[e]=1}}function s(){function n(n){var t=r(n),u=t[0],i=-1;return u.eachBefore(v(n.length)),u.eachAfter(e(n)),null!=o&&u.sort(o),u.each(function(n){t[++i]=n}),t.data=n,t}function r(n){var r,e,i,o,c,f,l,h=n.length,v={},s=new Array(h);for(r=0;h>r;++r)if(s[r]=c=new a(e=n[r],r),null!=(i=t(e,r,n))){if(o=J+(c.id=i+=""),o in v)throw new Error("duplicate: "+i);v[o]=c}for(r=0;h>r;++r)if(c=s[r],i=u(e=n[r],r,n),null==i){if(l)throw new Error("multiple roots");l=s[0],s[0]=c,s[r]=l}else{if(f=v[J+i],!f)throw new Error("missing: "+i);c.parent=f,f.children?f.children.push(c):f.children=[c]}if(!l)throw new Error("cycle");return s}function e(n){return function(r){for(var e=+i(r.data,r.index,n)||0,t=r.children,u=t&&t.length;--u>=0;)e+=t[u].value;r.value=e}}var t=c,u=f,i=l,o=h;return n.revalue=function(n){return n[0].eachAfter(e(n.data)),n},n.id=function(r){return arguments.length?(t=r,n):t},n.parentId=function(r){return arguments.length?(u=r,n):u},n.value=function(r){return arguments.length?(i=r,n):i},n.sort=function(r){return arguments.length?(o=r,n):o},n}function d(n,r){return n.revalue=r.revalue,n.id=function(){var e=r.id.apply(r,arguments);return e===r?n:e},n.parentId=function(){var e=r.parentId.apply(r,arguments);return e===r?n:e},n.value=function(){var e=r.value.apply(r,arguments);return e===r?n:e},n.sort=function(){var e=r.sort.apply(r,arguments);return e===r?n:e},n}function x(n){return g(p(n),[])}function p(n){for(var r,e=(n=n.slice()).length,t=null,u=t;e;){var i={circle:n[e-1],next:null};u=u?u.next=i:t=i,n[r]=n[--e]}return{head:t,tail:u}}function y(n,r){var e=r.x-n.x,t=r.y-n.y,u=n.r-r.r;return u*u+1e-6>e*e+t*t}function g(n,r){var e,t,u,i=null,o=n.head;switch(r.length){case 1:e=r[0];break;case 2:e=_(r[0],r[1]);break;case 3:e=m(r[0],r[1],r[2])}for(;o;)u=o.circle,t=o.next,e&&y(e,u)?i=o:(i?(n.tail=i,i.next=null):n.head=n.tail=null,r.push(u),e=g(n,r),r.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),i=n.tail,i.next=t),o=t;return n.tail=i,e}function _(n,r){var e=n.x,t=n.y,u=n.r,i=r.x,o=r.y,a=r.r,c=i-e,f=o-t,l=a-u,h=Math.sqrt(c*c+f*f);return{x:(e+i+c/h*l)/2,y:(t+o+f/h*l)/2,r:(h+u+a)/2}}function m(n,r,e){var t=n.x,u=n.y,i=n.r,o=r.x,a=r.y,c=r.r,f=e.x,l=e.y,h=e.r,v=2*(t-o),s=2*(u-a),d=2*(c-i),x=t*t+u*u-i*i-o*o-a*a+c*c,p=2*(t-f),y=2*(u-l),g=2*(h-i),_=t*t+u*u-i*i-f*f-l*l+h*h,m=p*s-v*y,w=(s*_-y*x)/m-t,M=(y*d-s*g)/m,q=(p*x-v*_)/m-u,B=(v*g-p*d)/m,E=M*M+B*B-1,A=2*(w*M+q*B+i),k=w*w+q*q-i*i,b=(-A-Math.sqrt(A*A-4*E*k))/(2*E);return{x:w+M*b+t,y:q+B*b+u,r:b}}function w(n,r,e){var t=n._,u=r._,i=e._,o=t.x,a=t.y,c=u.r+i.r,f=t.r+i.r,l=u.x-o,h=u.y-a,v=l*l+h*h;if(v){var s=.5+((f*=f)-(c*=c))/(2*v),d=Math.sqrt(Math.max(0,2*c*(f+v)-(f-=v)*f-c*c))/(2*v);i.x=o+s*l+d*h,i.y=a+s*h-d*l}else i.x=o+f,i.y=a;e.score=i.x*i.x+i.y*i.y}function M(n,r){var e=r.x-n.x,t=r.y-n.y,u=n.r+r.r;return u*u>e*e+t*t}function q(n){return{_:n,next:null,previous:null,score:NaN}}function B(n){if(f=n.length){n=n.map(q);var r,e,t,u,i,o,a,c,f;if(r=n[0],r.score=r._.r*r._.r,r._.x=r._.r,r._.y=0,f>1&&(e=n[1],e.score=e._.r*e._.r,e._.x=-e._.r,e._.y=0,f>2)){w(e,r,t=n[2]),r.next=t.previous=e,e.next=r.previous=t,t.next=e.previous=r;n:for(u=3;f>u;++u){if(w(r,e,t=n[u]),(o=r.previous)===(i=e.next)){if(M(i._,t._)){r=e,e=i,--u;continue n}}else{a=i._.r,c=o._.r;do if(c>=a){if(M(i._,t._)){e=i,r.next=e,e.previous=r,--u;continue n}i=i.next,a+=i._.r}else{if(M(o._,t._)){r=o,r.next=e,e.previous=r,--u;continue n}o=o.previous,c+=o._.r}while(i!==o.next)}for(t.previous=r,t.next=e,r.next=e.previous=e=t;(t=t.next)!==e;)t.score<r.score&&(r=t,e=r.next)}}}}function E(){function n(n){var t=e(n);return r(t[0]),t}function r(n){n.x=t/2,n.y=u/2,n.eachAfter(A),i>0&&n.eachAfter(k(i*n.r/Math.min(t,u))),n.eachBefore(I(Math.min(t,u)/(2*n.r)))}var e=s(),t=1,u=1,i=0;return d(n,e),n.revalue=function(n){return e.revalue(n),r(n[0]),n},n.size=function(r){return arguments.length?(t=+r[0],u=+r[1],n):[t,u]},n.padding=function(r){return arguments.length?(i=+r,n):i},n}function A(n){if(n.children){B(n.children);var r=x(n.children);n.children.forEach(z(-r.x,-r.y)),n.r=r.r}else n.r=Math.sqrt(n.value)}function k(n){var r=b(n),e=b(-n);return function(t){t.children&&(t.children.forEach(r),A(t),t.children.forEach(e),t.r+=n)}}function b(n){return function(r){r.r+=n}}function I(n){return function(r){var e=r.parent;r.r*=n,e&&(r.x=e.x+n*r.x,r.y=e.y+n*r.y)}}function z(n,r){return function(e){e.x+=n,e.y+=r}}function S(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function C(n,r,e,t,u){for(var i,o=n.children,a=-1,c=o.length,f=(t-r)/n.value;++a<c;)i=o[a],i.y0=e,i.y1=u,i.x0=r,i.x1=r+=i.value*f}function D(n){var r=n.depth;return n.eachBefore(function(n){n.depth>r&&(r=n.depth)}),r}function N(){function n(n){var e=t(n);return r(e[0]),e}function r(n){var r=D(n)+1;n.x0=n.y0=o,n.x1=u,n.y1=i/r,n.eachBefore(e(i,r)),a&&n.eachBefore(S)}function e(n,r){return function(e){e.children&&C(e,e.x0,n*(e.depth+1)/r,e.x1,n*(e.depth+2)/r);var t=e.x0,u=e.y0,i=e.x1-o,a=e.y1-o;t>i&&(t=i=(t+i)/2),u>a&&(u=a=(u+a)/2),e.x0=t,e.y0=u,e.x1=i,e.y1=a}}var t=s(),u=1,i=1,o=0,a=!1;return d(n,t),n.revalue=function(n){return t.revalue(n),r(n[0]),n},n.round=function(r){return arguments.length?(a=!!r,n):a},n.size=function(r){return arguments.length?(u=+r[0],i=+r[1],n):[u,i]},n.padding=function(r){return arguments.length?(o=+r,n):o},n}function j(){function n(n){var e=t(n);return r(e[0]),e}function r(n){n.x0=n.y0=-o,n.x1=u+o,n.y1=i+o,n.eachBefore(e),l&&n.eachBefore(S)}function e(n){var r=n.x0+o,e=n.y0+o,t=n.x1-o,u=n.y1-o;r>t&&(r=t=(r+t)/2),e>u&&(e=u=(e+u)/2),n.x0=r,n.y0=e,n.x1=t,n.y1=u,n.children&&(r+=c,e+=c,t-=c,u-=c,r>t&&(r=t=(r+t)/2),e>u&&(e=u=(e+u)/2),f(n,r,e,t,u))}var t=s(),u=1,i=1,o=0,a=0,c=0,f=K,l=!1;return d(n,t),n.revalue=function(n){return t.revalue(n),r(n[0]),n},n.round=function(r){return arguments.length?(l=!!r,n):l},n.size=function(r){return arguments.length?(u=+r[0],i=+r[1],n):[u,i]},n.tile=function(r){return arguments.length?(f=r,n):f},n.padding=function(r){return arguments.length?(o=(a=+r)/2,c=o,n):2*o},n.paddingInner=function(r){return arguments.length?(o=r/2,c=a-o,n):2*o},n.paddingOuter=function(r){return arguments.length?(a=+r,c=a-o,n):a},n}function O(n,r,e,t,u){var i=n.children;$(i,0,i.length,n.value,r,e,t,u)}function $(n,r,e,t,u,i,o,a){if(r>=e-1)return n=n[r],n.x0=u,n.y0=i,n.x1=o,n.y1=a,void 0;var c=r,f=t/2,l=0;do l+=n[c].value;while(++c<e-1&&f>l);var h=t-l;if(a-i>o-u){var v=(i*h+a*l)/t;$(n,r,c,l,u,i,o,v),$(n,c,e,h,u,v,o,a)}else{var s=(u*h+o*l)/t;$(n,r,c,l,u,i,s,a),$(n,c,e,h,s,i,o,a)}}function F(n,r,e,t,u){for(var i,o=n.children,a=-1,c=o.length,f=(u-e)/n.value;++a<c;)i=o[a],i.x0=r,i.x1=t,i.y0=e,i.y1=e+=i.value*f}function G(n,r,e,t,u){(1&n.depth?F:C)(n,r,e,t,u)}var H="0.0.2";a.prototype={constructor:a,each:t,eachBefore:i,eachAfter:u,ancestors:r,descendants:e,sort:o};var J="$",K=function L(n){function r(r,e,t,u,i){for(var o,a,c,f,l,h,v,s,d,x,p,y,g,_,m=r.children,w=0,M=m.length,q=r.value;M>w;){if(h=u-e,v=i-t,s=(o=m[w]).value,o._squarify)for(c=w+1;c<Math.abs(o._squarify);++c)s+=m[c].value;else{for(d=x=s,p=Math.max(v/h,h/v)/(q*n),y=s*s*p,_=Math.max(x/y,y/d),c=w+1;M>c;++c){if(s+=a=m[c].value,d>a&&(d=a),a>x&&(x=a),y=s*s*p,g=Math.max(x/y,y/d),g>_){s-=a;break}_=g}o._squarify=v>h?c:-c}if(o._squarify>0){for(f=e,l=t+v*s/q,h/=s;c>w;++w)o=m[w],o.x0=f,o.y0=t,o.y1=l,o.x1=f+=o.value*h;t=l}else{for(l=t,f=e+h*s/q,v/=s;c>w;++w)o=m[w],o.y0=l,o.x0=e,o.x1=f,o.y1=l+=o.value*v;e=f}q-=s}}return r.ratio=function(n){return L((n=+n)>1?n:1)},r}((1+Math.sqrt(5))/2);n.version=H,n.hierarchy=s,n.pack=E,n.packCircles=B,n.packEnclosingCircle=x,n.partition=N,n.treemap=j,n.treemapBinary=O,n.treemapDice=C,n.treemapSlice=F,n.treemapSliceDice=G,n.treemapSquarify=K});
  12. mbostock revised this gist Mar 22, 2016. 3 changed files with 3 additions and 3 deletions.
    1 change: 1 addition & 0 deletions d3-hierarchy.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    !function(n,r){"object"==typeof exports&&"undefined"!=typeof module?r(exports):"function"==typeof define&&define.amd?define(["exports"],r):r(n.d3_hierarchy=n.d3_hierarchy||{})}(this,function(n){"use strict";function r(){for(var n=this,r=[this];n=n.parent;)r.push(n);return r}function e(){var n=[];return this.each(function(r){n.push(r)}),n}function t(n){var r,e,t,u,i=this,o=[i];do for(r=o.reverse(),o=[];null!=(i=r.pop());)if(n(i),e=i.children)for(t=0,u=e.length;u>t;++t)o.push(e[t]);while(o.length);return this}function u(n){for(var r,e,t=this,u=[t],i=[];null!=(t=u.pop());)if(i.push(t),r=t.children)for(e=r.length-1;e>=0;--e)u.push(r[e]);for(;null!=(t=i.pop());)n(t);return this}function i(n){for(var r,e,t=this,u=[t];null!=(t=u.pop());)if(n(t),r=t.children)for(e=r.length-1;e>=0;--e)u.push(r[e]);return this}function o(n){return this.eachBefore(function(r){r.children&&r.children.sort(n)})}function a(n,r){this.data=n,this.index=r}function c(n){return n.id}function f(n){return n.parent}function l(n){return n.value}function h(n,r){return r.value-n.value}function v(n){var r=new Array(n);return function(n){var e=n.index;if(r[e])throw new Error("cycle");n.depth=n.parent?n.parent.depth+1:0,r[e]=1}}function s(){function n(n){var t=r(n),u=t[0],i=-1;return u.eachBefore(v(n.length)),u.eachAfter(e(n)),null!=o&&u.sort(o),u.each(function(n){t[++i]=n}),t.data=n,t}function r(n){var r,e,i,o,c,f,l,h=n.length,v={},s=new Array(h);for(r=0;h>r;++r)if(s[r]=c=new a(e=n[r],r),null!=(i=t(e,r,n))){if(o=J+(c.id=i+=""),o in v)throw new Error("duplicate: "+i);v[o]=c}for(r=0;h>r;++r)if(c=s[r],i=u(e=n[r],r,n),null==i){if(l)throw new Error("multiple roots");l=s[0],s[0]=c,s[r]=l}else{if(f=v[J+i],!f)throw new Error("missing: "+i);c.parent=f,f.children?f.children.push(c):f.children=[c]}if(!l)throw new Error("cycle");return s}function e(n){return function(r){for(var e=+i(r.data,r.index,n)||0,t=r.children,u=t&&t.length;--u>=0;)e+=t[u].value;r.value=e}}var t=c,u=f,i=l,o=h;return n.revalue=function(n){return n[0].eachAfter(e(n.data)),n},n.id=function(r){return arguments.length?(t=r,n):t},n.parentId=function(r){return arguments.length?(u=r,n):u},n.value=function(r){return arguments.length?(i=r,n):i},n.sort=function(r){return arguments.length?(o=r,n):o},n}function d(n,r){var e=r.x-n.x,t=r.y-n.y,u=n.r-r.r;return u*u+1e-6>e*e+t*t}function x(n){return y(p(n),[])}function p(n){for(var r,e=(n=n.slice()).length,t=null,u=t;e;){var i={circle:n[e-1],next:null};u=u?u.next=i:t=i,n[r]=n[--e]}return{head:t,tail:u}}function y(n,r){var e,t,u,i=null,o=n.head;switch(r.length){case 1:e=r[0];break;case 2:e=g(r[0],r[1]);break;case 3:e=_(r[0],r[1],r[2])}for(;o;)u=o.circle,t=o.next,e&&d(e,u)?i=o:(i?(n.tail=i,i.next=null):n.head=n.tail=null,r.push(u),e=y(n,r),r.pop(),n.head?(o.next=n.head,n.head=o):(o.next=null,n.head=n.tail=o),i=n.tail,i.next=t),o=t;return n.tail=i,e}function g(n,r){var e=n.x,t=n.y,u=n.r,i=r.x,o=r.y,a=r.r,c=i-e,f=o-t,l=a-u,h=Math.sqrt(c*c+f*f);return{x:(e+i+c/h*l)/2,y:(t+o+f/h*l)/2,r:(h+u+a)/2}}function _(n,r,e){var t=n.x,u=n.y,i=n.r,o=r.x,a=r.y,c=r.r,f=e.x,l=e.y,h=e.r,v=2*(t-o),s=2*(u-a),d=2*(c-i),x=t*t+u*u-i*i-o*o-a*a+c*c,p=2*(t-f),y=2*(u-l),g=2*(h-i),_=t*t+u*u-i*i-f*f-l*l+h*h,m=p*s-v*y,w=(s*_-y*x)/m-t,M=(y*d-s*g)/m,q=(p*x-v*_)/m-u,B=(v*g-p*d)/m,E=M*M+B*B-1,A=2*(w*M+q*B+i),b=w*w+q*q-i*i,k=(-A-Math.sqrt(A*A-4*E*b))/(2*E);return{x:w+M*k+t,y:q+B*k+u,r:k}}function m(n,r){var e=r.x-n.x,t=r.y-n.y,u=n.r+r.r;return u*u>e*e+t*t}function w(n,r,e){var t=n._,u=r._,i=e._,o=t.x,a=t.y,c=u.r+i.r,f=t.r+i.r,l=u.x-o,h=u.y-a,v=l*l+h*h;if(v){var s=.5+((f*=f)-(c*=c))/(2*v),d=Math.sqrt(Math.max(0,2*c*(f+v)-(f-=v)*f-c*c))/(2*v);i.x=o+s*l+d*h,i.y=a+s*h-d*l}else i.x=o+f,i.y=a;e.score=i.x*i.x+i.y*i.y}function M(n){return{_:n,next:null,previous:null,score:NaN}}function q(n){if(f=n.length){n=n.map(M);var r,e,t,u,i,o,a,c,f;if(r=n[0],r.score=r._.r*r._.r,r._.x=r._.r,r._.y=0,f>1&&(e=n[1],e.score=e._.r*e._.r,e._.x=-e._.r,e._.y=0,f>2)){w(e,r,t=n[2]),r.next=t.previous=e,e.next=r.previous=t,t.next=e.previous=r;n:for(u=3;f>u;++u){if(w(r,e,t=n[u]),(o=r.previous)===(i=e.next)){if(m(i._,t._)){r=e,e=i,--u;continue n}}else{a=i._.r,c=o._.r;do if(c>=a){if(m(i._,t._)){e=i,r.next=e,e.previous=r,--u;continue n}i=i.next,a+=i._.r}else{if(m(o._,t._)){r=o,r.next=e,e.previous=r,--u;continue n}o=o.previous,c+=o._.r}while(i!==o.next)}for(t.previous=r,t.next=e,r.next=e.previous=e=t;(t=t.next)!==e;)t.score<r.score&&(r=t,e=r.next)}}}}function B(n,r){return n.revalue=r.revalue,n.id=function(){var e=r.id.apply(r,arguments);return e===r?n:e},n.parentId=function(){var e=r.parentId.apply(r,arguments);return e===r?n:e},n.value=function(){var e=r.value.apply(r,arguments);return e===r?n:e},n.sort=function(){var e=r.sort.apply(r,arguments);return e===r?n:e},n}function E(){function n(n){var t=e(n);return r(t[0]),t}function r(n){n.x=t/2,n.y=u/2,n.eachAfter(A),i>0&&n.eachAfter(b(i*n.r/Math.min(t,u))),n.eachBefore(I(Math.min(t,u)/(2*n.r)))}var e=s(),t=1,u=1,i=0;return B(n,e),n.revalue=function(n){return e.revalue(n),r(n[0]),n},n.size=function(r){return arguments.length?(t=+r[0],u=+r[1],n):[t,u]},n.padding=function(r){return arguments.length?(i=+r,n):i},n}function A(n){if(n.children){q(n.children);var r=x(n.children);n.children.forEach(z(-r.x,-r.y)),n.r=r.r}else n.r=Math.sqrt(n.value)}function b(n){var r=k(n),e=k(-n);return function(t){t.children&&(t.children.forEach(r),A(t),t.children.forEach(e),t.r+=n)}}function k(n){return function(r){r.r+=n}}function I(n){return function(r){var e=r.parent;r.r*=n,e&&(r.x=e.x+n*r.x,r.y=e.y+n*r.y)}}function z(n,r){return function(e){e.x+=n,e.y+=r}}function S(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function C(n,r,e,t,u){for(var i,o=n.children,a=-1,c=o.length,f=(t-r)/n.value;++a<c;)i=o[a],i.y0=e,i.y1=u,i.x0=r,i.x1=r+=i.value*f}function D(n){var r=n.depth;return n.eachBefore(function(n){n.depth>r&&(r=n.depth)}),r}function N(){function n(n){var e=t(n);return r(e[0]),e}function r(n){var r=D(n)+1;n.x0=n.y0=o,n.x1=u,n.y1=i/r,n.eachBefore(e(i,r)),a&&n.eachBefore(S)}function e(n,r){return function(e){e.children&&C(e,e.x0,n*(e.depth+1)/r,e.x1,n*(e.depth+2)/r);var t=e.x0,u=e.y0,i=e.x1-o,a=e.y1-o;t>i&&(t=i=(t+i)/2),u>a&&(u=a=(u+a)/2),e.x0=t,e.y0=u,e.x1=i,e.y1=a}}var t=s(),u=1,i=1,o=0,a=!1;return B(n,t),n.revalue=function(n){return t.revalue(n),r(n[0]),n},n.round=function(r){return arguments.length?(a=!!r,n):a},n.size=function(r){return arguments.length?(u=+r[0],i=+r[1],n):[u,i]},n.padding=function(r){return arguments.length?(o=+r,n):o},n}function j(){function n(n){var e=t(n);return r(e[0]),e}function r(n){n.x0=n.y0=-o,n.x1=u+o,n.y1=i+o,n.eachBefore(e),l&&n.eachBefore(S)}function e(n){var r=n.x0+o,e=n.y0+o,t=n.x1-o,u=n.y1-o;r>t&&(r=t=(r+t)/2),e>u&&(e=u=(e+u)/2),n.x0=r,n.y0=e,n.x1=t,n.y1=u,n.children&&(r+=c,e+=c,t-=c,u-=c,r>t&&(r=t=(r+t)/2),e>u&&(e=u=(e+u)/2),f(n,r,e,t,u))}var t=s(),u=1,i=1,o=0,a=0,c=0,f=K,l=!1;return B(n,t),n.revalue=function(n){return t.revalue(n),r(n[0]),n},n.round=function(r){return arguments.length?(l=!!r,n):l},n.size=function(r){return arguments.length?(u=+r[0],i=+r[1],n):[u,i]},n.tile=function(r){return arguments.length?(f=r,n):f},n.padding=function(r){return arguments.length?(o=(a=+r)/2,c=o,n):2*o},n.paddingInner=function(r){return arguments.length?(o=r/2,c=a-o,n):2*o},n.paddingOuter=function(r){return arguments.length?(a=+r,c=a-o,n):a},n}function O(n,r,e,t,u){var i=n.children;$(i,0,i.length,n.value,r,e,t,u)}function $(n,r,e,t,u,i,o,a){if(r>=e-1)return n=n[r],n.x0=u,n.y0=i,n.x1=o,n.y1=a,void 0;var c=r,f=t/2,l=0;do l+=n[c].value;while(++c<e-1&&f>l);var h=t-l;if(a-i>o-u){var v=(i*h+a*l)/t;$(n,r,c,l,u,i,o,v),$(n,c,e,h,u,v,o,a)}else{var s=(u*h+o*l)/t;$(n,r,c,l,u,i,s,a),$(n,c,e,h,s,i,o,a)}}function F(n,r,e,t,u){for(var i,o=n.children,a=-1,c=o.length,f=(u-e)/n.value;++a<c;)i=o[a],i.x0=r,i.x1=t,i.y0=e,i.y1=e+=i.value*f}function G(n,r,e,t,u){(1&n.depth?F:C)(n,r,e,t,u)}var H="0.0.2";a.prototype={constructor:a,each:t,eachBefore:i,eachAfter:u,ancestors:r,descendants:e,sort:o};var J="$",K=function L(n){function r(r,e,t,u,i){for(var o,a,c,f,l,h,v,s,d,x,p,y,g,_,m=r.children,w=0,M=m.length,q=r.value;M>w;){if(h=u-e,v=i-t,s=(o=m[w]).value,o._squarify)for(c=w+1;c<Math.abs(o._squarify);++c)s+=m[c].value;else{for(d=x=s,p=Math.max(v/h,h/v)/(q*n),y=s*s*p,_=Math.max(x/y,y/d),c=w+1;M>c;++c){if(s+=a=m[c].value,d>a&&(d=a),a>x&&(x=a),y=s*s*p,g=Math.max(x/y,y/d),g>_){s-=a;break}_=g}o._squarify=v>h?c:-c}if(o._squarify>0){for(f=e,l=t+v*s/q,h/=s;c>w;++w)o=m[w],o.x0=f,o.y0=t,o.y1=l,o.x1=f+=o.value*h;t=l}else{for(l=t,f=e+h*s/q,v/=s;c>w;++w)o=m[w],o.y0=l,o.x0=e,o.x1=f,o.y1=l+=o.value*v;e=f}q-=s}}return r.ratio=function(n){return L((n=+n)>1?n:1)},r}((1+Math.sqrt(5))/2);n.version=H,n.hierarchy=s,n.enclosingCircle=x,n.packCircles=q,n.pack=E,n.partition=N,n.treemap=j,n.treemapBinary=O,n.treemapDice=C,n.treemapSlice=F,n.treemapSliceDice=G,n.treemapSquarify=K});
    4 changes: 2 additions & 2 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -16,7 +16,7 @@
    <g transform="translate(480,480)"></g>
    </svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
    <script src="pack.min.js"></script>
    <script src="d3-hierarchy.min.js"></script>
    <script>

    var color = d3.scaleRainbow()
    @@ -26,7 +26,7 @@
    .map(d3.randomUniform(8, 26))
    .map(function(r) { return {r: Math.max(1, r)}; });

    pack(circles);
    d3_hierarchy.packCircles(circles);

    d3.select("g")
    .selectAll("circle")
    1 change: 0 additions & 1 deletion pack.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +0,0 @@
    function place(e,r,n){var t=e._,i=r._,o=n._,s=t.x,x=t.y,_=i.r+o.r,c=t.r+o.r,u=i.x-s,p=i.y-x,f=u*u+p*p;if(f){var v=.5+((c*=c)-(_*=_))/(2*f),a=Math.sqrt(Math.max(0,2*_*(c+f)-(c-=f)*c-_*_))/(2*f);o.x=s+v*u+a*p,o.y=x+v*p-a*u}else o.x=s+c,o.y=x;n.score=o.x*o.x+o.y*o.y}function intersects(e,r){var n=r.x-e.x,t=r.y-e.y,i=e.r+r.r;return i*i>n*n+t*t}function newNode(e){return{_:e,next:null,previous:null,score:NaN}}function pack(e){if(c=e.length){e=e.map(newNode);var r,n,t,i,o,s,x,_,c;if(r=e[0],r.score=r._.r*r._.r,r._.x=r._.r,r._.y=0,c>1&&(n=e[1],n.score=n._.r*n._.r,n._.x=-n._.r,n._.y=0,c>2)){place(n,r,t=e[2]),r.next=t.previous=n,n.next=r.previous=t,t.next=n.previous=r;e:for(i=3;c>i;++i){if(place(r,n,t=e[i]),(s=r.previous)===(o=n.next)){if(intersects(o._,t._)){r=n,n=o,--i;continue e}}else{x=o._.r,_=s._.r;do if(_>=x){if(intersects(o._,t._)){n=o,r.next=n,n.previous=r,--i;continue e}o=o.next,x+=o._.r}else{if(intersects(s._,t._)){r=s,r.next=n,n.previous=r,--i;continue e}s=s.previous,_+=s._.r}while(o!==s.next)}for(t.previous=r,t.next=n,r.next=n.previous=n=t;(t=t.next)!==n;)t.score<r.score&&(r=t,n=r.next)}}}}
  13. mbostock revised this gist Mar 22, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -39,7 +39,7 @@
    .attr("r", function(d) { return d.r - 0.25; })
    .transition()
    .ease(d3.easeCubicOut)
    .delay(function(d, i) { return Math.sqrt(i) * 250 + Math.random() * 500; })
    .delay(function(d, i) { return Math.sqrt(i) * 250; })
    .duration(1000)
    .attr("cx", function(d) { return d.x; })
    .attr("cy", function(d) { return d.y; });
  14. mbostock revised this gist Mar 22, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion pack.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    function tangent(e,n,t){var r=n.r+t.r,i=e.r+t.r,o=n.x-e.x,x=n.y-e.y,s=o*o+x*x;if(s){var u=.5+((i*=i)-(r*=r))/(2*s),v=Math.sqrt(Math.max(0,2*r*(i+s)-(i-=s)*i-r*r))/(2*s);t.x=e.x+u*o+v*x,t.y=e.y+u*x-v*o}else t.x=e.x+i,t.y=e.y}function intersects(e,n){var t=n.x-e.x,r=n.y-e.y,i=e.r+n.r;return.999*i*i>t*t+r*r}function Node(e){this._=e}function pack(e){if(v=e.length){var n,t,r,i,o,x,s,u,v;if(n=e[0],n.x=-n.r,n.y=0,v>1&&(t=e[1],t.x=t.r,t.y=0,v>2)){tangent(n,t,r=e[2]),n=new Node(n),t=new Node(t),r=new Node(r),t.next=r.previous=n,r.next=n.previous=t,t=n.next=t.previous=r;e:for(i=3;v>i;++i){for(tangent(n._,t._,(r=new Node(e[i]))._),o=t.next,s=1;o!==n;o=o.next,++s)if(intersects(o._,r._)){if(n.previous===t.next){n=n.next,t=t.next,--i;continue e}for(x=n.previous,u=0;x!==o&&!intersects(x._,r._);x=x.previous,++u);u>s||s===u&&t._.r<n._.r?t=o:n=x,n.next=t,t.previous=n,--i;continue e}r.previous=n,r.next=t,t=n.next=t.previous=r}}}}
    function place(e,r,n){var t=e._,i=r._,o=n._,s=t.x,x=t.y,_=i.r+o.r,c=t.r+o.r,u=i.x-s,p=i.y-x,f=u*u+p*p;if(f){var v=.5+((c*=c)-(_*=_))/(2*f),a=Math.sqrt(Math.max(0,2*_*(c+f)-(c-=f)*c-_*_))/(2*f);o.x=s+v*u+a*p,o.y=x+v*p-a*u}else o.x=s+c,o.y=x;n.score=o.x*o.x+o.y*o.y}function intersects(e,r){var n=r.x-e.x,t=r.y-e.y,i=e.r+r.r;return i*i>n*n+t*t}function newNode(e){return{_:e,next:null,previous:null,score:NaN}}function pack(e){if(c=e.length){e=e.map(newNode);var r,n,t,i,o,s,x,_,c;if(r=e[0],r.score=r._.r*r._.r,r._.x=r._.r,r._.y=0,c>1&&(n=e[1],n.score=n._.r*n._.r,n._.x=-n._.r,n._.y=0,c>2)){place(n,r,t=e[2]),r.next=t.previous=n,n.next=r.previous=t,t.next=n.previous=r;e:for(i=3;c>i;++i){if(place(r,n,t=e[i]),(s=r.previous)===(o=n.next)){if(intersects(o._,t._)){r=n,n=o,--i;continue e}}else{x=o._.r,_=s._.r;do if(_>=x){if(intersects(o._,t._)){n=o,r.next=n,n.previous=r,--i;continue e}o=o.next,x+=o._.r}else{if(intersects(s._,t._)){r=s,r.next=n,n.previous=r,--i;continue e}s=s.previous,_+=s._.r}while(o!==s.next)}for(t.previous=r,t.next=n,r.next=n.previous=n=t;(t=t.next)!==n;)t.score<r.score&&(r=t,n=r.next)}}}}
  15. mbostock revised this gist Mar 18, 2016. 1 changed file with 8 additions and 7 deletions.
    15 changes: 8 additions & 7 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -8,12 +8,12 @@

    circle {
    stroke: #000;
    stroke-width: 0.5px;
    stroke-width: 1.5px;
    }

    </style>
    <svg width="960" height="960" viewBox="0 0 250 250">
    <g transform="translate(125,125)"></g>
    <svg width="960" height="960">
    <g transform="translate(480,480)"></g>
    </svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
    <script src="pack.min.js"></script>
    @@ -23,21 +23,22 @@
    .domain([0, 2 * Math.PI]);

    var circles = d3.range(2000)
    .map(d3.randomUniform(3, 8))
    .map(d3.randomUniform(8, 26))
    .map(function(r) { return {r: Math.max(1, r)}; });

    pack(circles);

    d3.select("g")
    .selectAll("circle")
    .data(circles
    .filter(function(d) { return -135 < d.x && d.x < 135 && -135 < d.y && d.y < 135; }))
    .filter(function(d) { return -500 < d.x && d.x < 500 && -500 < d.y && d.y < 500; }))
    .enter().append("circle")
    .style("fill", function(d) { return color(Math.atan2(d.y, d.x)); })
    .attr("cx", function(d) { return d.x / Math.sqrt(d.x * d.x + d.y * d.y) * 190; })
    .attr("cy", function(d) { return d.y / Math.sqrt(d.x * d.x + d.y * d.y) * 190; })
    .attr("cx", function(d) { return d.x / Math.sqrt(d.x * d.x + d.y * d.y) * 720; })
    .attr("cy", function(d) { return d.y / Math.sqrt(d.x * d.x + d.y * d.y) * 720; })
    .attr("r", function(d) { return d.r - 0.25; })
    .transition()
    .ease(d3.easeCubicOut)
    .delay(function(d, i) { return Math.sqrt(i) * 250 + Math.random() * 500; })
    .duration(1000)
    .attr("cx", function(d) { return d.x; })
  16. mbostock revised this gist Mar 18, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    A quick test of [d3-hierarchy](https://github.com/d3/d3-hierarchy) new circle-packing layout.
    A quick test of [d3-hierarchy](https://github.com/d3/d3-hierarchy)’s new circle-packing layout.
  17. mbostock created this gist Mar 18, 2016.
    2 changes: 2 additions & 0 deletions .block
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,2 @@
    license: gpl-3.0
    height: 960
    1 change: 1 addition & 0 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    A quick test of [d3-hierarchy](https://github.com/d3/d3-hierarchy) new circle-packing layout.
    46 changes: 46 additions & 0 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,46 @@
    <!DOCTYPE html>
    <meta charset="utf-8">
    <style>

    body {
    background: #333;
    }

    circle {
    stroke: #000;
    stroke-width: 0.5px;
    }

    </style>
    <svg width="960" height="960" viewBox="0 0 250 250">
    <g transform="translate(125,125)"></g>
    </svg>
    <script src="//d3js.org/d3.v4.0.0-alpha.28.min.js"></script>
    <script src="pack.min.js"></script>
    <script>

    var color = d3.scaleRainbow()
    .domain([0, 2 * Math.PI]);

    var circles = d3.range(2000)
    .map(d3.randomUniform(3, 8))
    .map(function(r) { return {r: Math.max(1, r)}; });

    pack(circles);

    d3.select("g")
    .selectAll("circle")
    .data(circles
    .filter(function(d) { return -135 < d.x && d.x < 135 && -135 < d.y && d.y < 135; }))
    .enter().append("circle")
    .style("fill", function(d) { return color(Math.atan2(d.y, d.x)); })
    .attr("cx", function(d) { return d.x / Math.sqrt(d.x * d.x + d.y * d.y) * 190; })
    .attr("cy", function(d) { return d.y / Math.sqrt(d.x * d.x + d.y * d.y) * 190; })
    .attr("r", function(d) { return d.r - 0.25; })
    .transition()
    .delay(function(d, i) { return Math.sqrt(i) * 250 + Math.random() * 500; })
    .duration(1000)
    .attr("cx", function(d) { return d.x; })
    .attr("cy", function(d) { return d.y; });

    </script>
    1 change: 1 addition & 0 deletions pack.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    function tangent(e,n,t){var r=n.r+t.r,i=e.r+t.r,o=n.x-e.x,x=n.y-e.y,s=o*o+x*x;if(s){var u=.5+((i*=i)-(r*=r))/(2*s),v=Math.sqrt(Math.max(0,2*r*(i+s)-(i-=s)*i-r*r))/(2*s);t.x=e.x+u*o+v*x,t.y=e.y+u*x-v*o}else t.x=e.x+i,t.y=e.y}function intersects(e,n){var t=n.x-e.x,r=n.y-e.y,i=e.r+n.r;return.999*i*i>t*t+r*r}function Node(e){this._=e}function pack(e){if(v=e.length){var n,t,r,i,o,x,s,u,v;if(n=e[0],n.x=-n.r,n.y=0,v>1&&(t=e[1],t.x=t.r,t.y=0,v>2)){tangent(n,t,r=e[2]),n=new Node(n),t=new Node(t),r=new Node(r),t.next=r.previous=n,r.next=n.previous=t,t=n.next=t.previous=r;e:for(i=3;v>i;++i){for(tangent(n._,t._,(r=new Node(e[i]))._),o=t.next,s=1;o!==n;o=o.next,++s)if(intersects(o._,r._)){if(n.previous===t.next){n=n.next,t=t.next,--i;continue e}for(x=n.previous,u=0;x!==o&&!intersects(x._,r._);x=x.previous,++u);u>s||s===u&&t._.r<n._.r?t=o:n=x,n.next=t,t.previous=n,--i;continue e}r.previous=n,r.next=t,t=n.next=t.previous=r}}}}
    Binary file added preview.png
    View file
    Loading
    Sorry, something went wrong. Reload?
    Sorry, we cannot display this file.
    Sorry, this file is invalid so it cannot be displayed.
    Binary file added thumbnail.png
    View file
    Loading
    Sorry, something went wrong. Reload?
    Sorry, we cannot display this file.
    Sorry, this file is invalid so it cannot be displayed.