-
Notifications
You must be signed in to change notification settings - Fork 315
/
siblings.js
119 lines (101 loc) · 3.15 KB
/
siblings.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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import array from "../array.js";
import enclose from "./enclose.js";
function place(b, a, c) {
var dx = b.x - a.x, x, a2,
dy = b.y - a.y, y, b2,
d2 = dx * dx + dy * dy;
if (d2) {
a2 = a.r + c.r, a2 *= a2;
b2 = b.r + c.r, b2 *= b2;
if (a2 > b2) {
x = (d2 + b2 - a2) / (2 * d2);
y = Math.sqrt(Math.max(0, b2 / d2 - x * x));
c.x = b.x - x * dx - y * dy;
c.y = b.y - x * dy + y * dx;
} else {
x = (d2 + a2 - b2) / (2 * d2);
y = Math.sqrt(Math.max(0, a2 / d2 - x * x));
c.x = a.x + x * dx - y * dy;
c.y = a.y + x * dy + y * dx;
}
} else {
c.x = a.x + c.r;
c.y = a.y;
}
}
function intersects(a, b) {
var dr = a.r + b.r - 1e-6, dx = b.x - a.x, dy = b.y - a.y;
return dr > 0 && dr * dr > dx * dx + dy * dy;
}
function score(node) {
var a = node._,
b = node.next._,
ab = a.r + b.r,
dx = (a.x * b.r + b.x * a.r) / ab,
dy = (a.y * b.r + b.y * a.r) / ab;
return dx * dx + dy * dy;
}
function Node(circle) {
this._ = circle;
this.next = null;
this.previous = null;
}
export function packEnclose(circles) {
if (!(n = (circles = array(circles)).length)) return 0;
var a, b, c, n, aa, ca, i, j, k, sj, sk;
// Place the first circle.
a = circles[0], a.x = 0, a.y = 0;
if (!(n > 1)) return a.r;
// Place the second circle.
b = circles[1], a.x = -b.r, b.x = a.r, b.y = 0;
if (!(n > 2)) return a.r + b.r;
// Place the third circle.
place(b, a, c = circles[2]);
// Initialize the front-chain using the first three circles a, b and c.
a = new Node(a), b = new Node(b), c = new Node(c);
a.next = c.previous = b;
b.next = a.previous = c;
c.next = b.previous = a;
// Attempt to place each remaining circle…
pack: for (i = 3; i < n; ++i) {
place(a._, b._, c = circles[i]), c = new Node(c);
// Find the closest intersecting circle on the front-chain, if any.
// “Closeness” is determined by linear distance along the front-chain.
// “Ahead” or “behind” is likewise determined by linear distance.
j = b.next, k = a.previous, sj = b._.r, sk = a._.r;
do {
if (sj <= sk) {
if (intersects(j._, c._)) {
b = j, a.next = b, b.previous = a, --i;
continue pack;
}
sj += j._.r, j = j.next;
} else {
if (intersects(k._, c._)) {
a = k, a.next = b, b.previous = a, --i;
continue pack;
}
sk += k._.r, k = k.previous;
}
} while (j !== k.next);
// Success! Insert the new circle c between a and b.
c.previous = a, c.next = b, a.next = b.previous = b = c;
// Compute the new closest circle pair to the centroid.
aa = score(a);
while ((c = c.next) !== b) {
if ((ca = score(c)) < aa) {
a = c, aa = ca;
}
}
b = a.next;
}
// Compute the enclosing circle of the front chain.
a = [b._], c = b; while ((c = c.next) !== b) a.push(c._); c = enclose(a);
// Translate the circles to put the enclosing circle around the origin.
for (i = 0; i < n; ++i) a = circles[i], a.x -= c.x, a.y -= c.y;
return c.r;
}
export default function(circles) {
packEnclose(circles);
return circles;
}