1 | import enclose from "./enclose.js";
|
2 |
|
3 | function place(b, a, c) {
|
4 | var dx = b.x - a.x, x, a2,
|
5 | dy = b.y - a.y, y, b2,
|
6 | d2 = dx * dx + dy * dy;
|
7 | if (d2) {
|
8 | a2 = a.r + c.r, a2 *= a2;
|
9 | b2 = b.r + c.r, b2 *= b2;
|
10 | if (a2 > b2) {
|
11 | x = (d2 + b2 - a2) / (2 * d2);
|
12 | y = Math.sqrt(Math.max(0, b2 / d2 - x * x));
|
13 | c.x = b.x - x * dx - y * dy;
|
14 | c.y = b.y - x * dy + y * dx;
|
15 | } else {
|
16 | x = (d2 + a2 - b2) / (2 * d2);
|
17 | y = Math.sqrt(Math.max(0, a2 / d2 - x * x));
|
18 | c.x = a.x + x * dx - y * dy;
|
19 | c.y = a.y + x * dy + y * dx;
|
20 | }
|
21 | } else {
|
22 | c.x = a.x + c.r;
|
23 | c.y = a.y;
|
24 | }
|
25 | }
|
26 |
|
27 | function intersects(a, b) {
|
28 | var dr = a.r + b.r - 1e-6, dx = b.x - a.x, dy = b.y - a.y;
|
29 | return dr > 0 && dr * dr > dx * dx + dy * dy;
|
30 | }
|
31 |
|
32 | function score(node) {
|
33 | var a = node._,
|
34 | b = node.next._,
|
35 | ab = a.r + b.r,
|
36 | dx = (a.x * b.r + b.x * a.r) / ab,
|
37 | dy = (a.y * b.r + b.y * a.r) / ab;
|
38 | return dx * dx + dy * dy;
|
39 | }
|
40 |
|
41 | function Node(circle) {
|
42 | this._ = circle;
|
43 | this.next = null;
|
44 | this.previous = null;
|
45 | }
|
46 |
|
47 | export function packEnclose(circles) {
|
48 | if (!(n = circles.length)) return 0;
|
49 |
|
50 | var a, b, c, n, aa, ca, i, j, k, sj, sk;
|
51 |
|
52 |
|
53 | a = circles[0], a.x = 0, a.y = 0;
|
54 | if (!(n > 1)) return a.r;
|
55 |
|
56 |
|
57 | b = circles[1], a.x = -b.r, b.x = a.r, b.y = 0;
|
58 | if (!(n > 2)) return a.r + b.r;
|
59 |
|
60 |
|
61 | place(b, a, c = circles[2]);
|
62 |
|
63 |
|
64 | a = new Node(a), b = new Node(b), c = new Node(c);
|
65 | a.next = c.previous = b;
|
66 | b.next = a.previous = c;
|
67 | c.next = b.previous = a;
|
68 |
|
69 |
|
70 | pack: for (i = 3; i < n; ++i) {
|
71 | place(a._, b._, c = circles[i]), c = new Node(c);
|
72 |
|
73 |
|
74 |
|
75 |
|
76 | j = b.next, k = a.previous, sj = b._.r, sk = a._.r;
|
77 | do {
|
78 | if (sj <= sk) {
|
79 | if (intersects(j._, c._)) {
|
80 | b = j, a.next = b, b.previous = a, --i;
|
81 | continue pack;
|
82 | }
|
83 | sj += j._.r, j = j.next;
|
84 | } else {
|
85 | if (intersects(k._, c._)) {
|
86 | a = k, a.next = b, b.previous = a, --i;
|
87 | continue pack;
|
88 | }
|
89 | sk += k._.r, k = k.previous;
|
90 | }
|
91 | } while (j !== k.next);
|
92 |
|
93 |
|
94 | c.previous = a, c.next = b, a.next = b.previous = b = c;
|
95 |
|
96 |
|
97 | aa = score(a);
|
98 | while ((c = c.next) !== b) {
|
99 | if ((ca = score(c)) < aa) {
|
100 | a = c, aa = ca;
|
101 | }
|
102 | }
|
103 | b = a.next;
|
104 | }
|
105 |
|
106 |
|
107 | a = [b._], c = b; while ((c = c.next) !== b) a.push(c._); c = enclose(a);
|
108 |
|
109 |
|
110 | for (i = 0; i < n; ++i) a = circles[i], a.x -= c.x, a.y -= c.y;
|
111 |
|
112 | return c.r;
|
113 | }
|
114 |
|
115 | export default function(circles) {
|
116 | packEnclose(circles);
|
117 | return circles;
|
118 | }
|