forked from d3/d3-hierarchy
-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary.js
44 lines (38 loc) · 1.13 KB
/
binary.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
export default function(parent, x0, y0, x1, y1) {
var nodes = parent.children;
var sums = [0];
for (var i = 0; i < nodes.length; i++) {
sums[i+1] = sums[i] + nodes[i].value;
}
partition(nodes, sums, 0, nodes.length, parent.value, x0, y0, x1, y1);
}
function partition(nodes, sums, i, j, value, x0, y0, x1, y1) {
if (i >= j - 1) {
nodes = nodes[i];
nodes.x0 = x0, nodes.y0 = y0;
nodes.x1 = x1, nodes.y1 = y1;
return;
}
var offset = sums[i];
var goal = (value / 2) + offset;
var k = i+1, ub = j-1, mid;
while(k < ub) {
mid = (k + ub) >>> 1;
if (sums[mid] < goal) {
k = mid+1;
} else {
ub = mid;
}
}
var valueLeft = sums[k] - offset;
var valueRight = value - valueLeft;
if ((y1 - y0) > (x1 - x0)) {
var yk = (y0 * valueRight + y1 * valueLeft) / value;
partition(nodes, sums, i, k, valueLeft, x0, y0, x1, yk);
partition(nodes, sums, k, j, valueRight, x0, yk, x1, y1);
} else {
var xk = (x0 * valueRight + x1 * valueLeft) / value;
partition(nodes, sums, i, k, valueLeft, x0, y0, xk, y1);
partition(nodes, sums, k, j, valueRight, xk, y0, x1, y1);
}
}