1 |
|
2 | 'use strict';
|
3 |
|
4 | var rNumber = String.raw`[-+]?(?:\d*\.\d+|\d+\.?)(?:[eE][-+]?\d+)?\s*`,
|
5 | rCommaWsp = String.raw`(?:\s,?\s*|,\s*)`,
|
6 | rNumberCommaWsp = `(${rNumber})` + rCommaWsp,
|
7 | rFlagCommaWsp = `([01])${rCommaWsp}?`,
|
8 | rCoordinatePair = String.raw`(${rNumber})${rCommaWsp}?(${rNumber})`,
|
9 | rArcSeq = (rNumberCommaWsp + '?').repeat(2) + rNumberCommaWsp + rFlagCommaWsp.repeat(2) + rCoordinatePair;
|
10 |
|
11 | var regPathInstructions = /([MmLlHhVvCcSsQqTtAaZz])\s*/,
|
12 | regCoordinateSequence = new RegExp(rNumber, 'g'),
|
13 | regArcArgumentSequence = new RegExp(rArcSeq, 'g'),
|
14 | regNumericValues = /[-+]?(\d*\.\d+|\d+\.?)(?:[eE][-+]?\d+)?/,
|
15 | transform2js = require('./_transforms').transform2js,
|
16 | transformsMultiply = require('./_transforms').transformsMultiply,
|
17 | transformArc = require('./_transforms').transformArc,
|
18 | collections = require('./_collections.js'),
|
19 | referencesProps = collections.referencesProps,
|
20 | defaultStrokeWidth = collections.attrsGroupsDefaults.presentation['stroke-width'],
|
21 | cleanupOutData = require('../lib/svgo/tools').cleanupOutData,
|
22 | removeLeadingZero = require('../lib/svgo/tools').removeLeadingZero,
|
23 | prevCtrlPoint;
|
24 |
|
25 |
|
26 |
|
27 |
|
28 |
|
29 |
|
30 |
|
31 |
|
32 | exports.path2js = function(path) {
|
33 | if (path.pathJS) return path.pathJS;
|
34 |
|
35 | var paramsLength = {
|
36 | H: 1, V: 1, M: 2, L: 2, T: 2, Q: 4, S: 4, C: 6, A: 7,
|
37 | h: 1, v: 1, m: 2, l: 2, t: 2, q: 4, s: 4, c: 6, a: 7
|
38 | },
|
39 | pathData = [],
|
40 | instruction,
|
41 | startMoveto = false;
|
42 |
|
43 |
|
44 | path.attr('d').value.split(regPathInstructions).forEach(function(data) {
|
45 | if (!data) return;
|
46 | if (!startMoveto) {
|
47 | if (data == 'M' || data == 'm') {
|
48 | startMoveto = true;
|
49 | } else return;
|
50 | }
|
51 |
|
52 |
|
53 | if (regPathInstructions.test(data)) {
|
54 | instruction = data;
|
55 |
|
56 |
|
57 | if (instruction == 'Z' || instruction == 'z') {
|
58 | pathData.push({
|
59 | instruction: 'z'
|
60 | });
|
61 | }
|
62 |
|
63 | } else {
|
64 |
|
65 | if (instruction == 'A' || instruction == 'a') {
|
66 | var newData = [];
|
67 | for (var args; (args = regArcArgumentSequence.exec(data));) {
|
68 | for (var i = 1; i < args.length; i++) {
|
69 | newData.push(args[i]);
|
70 | }
|
71 | }
|
72 | data = newData;
|
73 | } else {
|
74 | data = data.match(regCoordinateSequence);
|
75 | }
|
76 | if (!data) return;
|
77 |
|
78 | data = data.map(Number);
|
79 |
|
80 |
|
81 | if (instruction == 'M' || instruction == 'm') {
|
82 | pathData.push({
|
83 | instruction: pathData.length == 0 ? 'M' : instruction,
|
84 | data: data.splice(0, 2)
|
85 | });
|
86 | instruction = instruction == 'M' ? 'L' : 'l';
|
87 | }
|
88 |
|
89 | for (var pair = paramsLength[instruction]; data.length;) {
|
90 | pathData.push({
|
91 | instruction: instruction,
|
92 | data: data.splice(0, pair)
|
93 | });
|
94 | }
|
95 | }
|
96 | });
|
97 |
|
98 |
|
99 | if (pathData.length && pathData[0].instruction == 'm') {
|
100 | pathData[0].instruction = 'M';
|
101 | }
|
102 | path.pathJS = pathData;
|
103 |
|
104 | return pathData;
|
105 | };
|
106 |
|
107 |
|
108 |
|
109 |
|
110 |
|
111 |
|
112 |
|
113 | var relative2absolute = exports.relative2absolute = function(data) {
|
114 | var currentPoint = [0, 0],
|
115 | subpathPoint = [0, 0],
|
116 | i;
|
117 |
|
118 | return data.map(function(item) {
|
119 |
|
120 | var instruction = item.instruction,
|
121 | itemData = item.data && item.data.slice();
|
122 |
|
123 | if (instruction == 'M') {
|
124 |
|
125 | set(currentPoint, itemData);
|
126 | set(subpathPoint, itemData);
|
127 |
|
128 | } else if ('mlcsqt'.indexOf(instruction) > -1) {
|
129 |
|
130 | for (i = 0; i < itemData.length; i++) {
|
131 | itemData[i] += currentPoint[i % 2];
|
132 | }
|
133 | set(currentPoint, itemData);
|
134 |
|
135 | if (instruction == 'm') {
|
136 | set(subpathPoint, itemData);
|
137 | }
|
138 |
|
139 | } else if (instruction == 'a') {
|
140 |
|
141 | itemData[5] += currentPoint[0];
|
142 | itemData[6] += currentPoint[1];
|
143 | set(currentPoint, itemData);
|
144 |
|
145 | } else if (instruction == 'h') {
|
146 |
|
147 | itemData[0] += currentPoint[0];
|
148 | currentPoint[0] = itemData[0];
|
149 |
|
150 | } else if (instruction == 'v') {
|
151 |
|
152 | itemData[0] += currentPoint[1];
|
153 | currentPoint[1] = itemData[0];
|
154 |
|
155 | } else if ('MZLCSQTA'.indexOf(instruction) > -1) {
|
156 |
|
157 | set(currentPoint, itemData);
|
158 |
|
159 | } else if (instruction == 'H') {
|
160 |
|
161 | currentPoint[0] = itemData[0];
|
162 |
|
163 | } else if (instruction == 'V') {
|
164 |
|
165 | currentPoint[1] = itemData[0];
|
166 |
|
167 | } else if (instruction == 'z') {
|
168 |
|
169 | set(currentPoint, subpathPoint);
|
170 |
|
171 | }
|
172 |
|
173 | return instruction == 'z' ?
|
174 | { instruction: 'z' } :
|
175 | {
|
176 | instruction: instruction.toUpperCase(),
|
177 | data: itemData
|
178 | };
|
179 |
|
180 | });
|
181 | };
|
182 |
|
183 |
|
184 |
|
185 |
|
186 |
|
187 |
|
188 |
|
189 |
|
190 |
|
191 | exports.applyTransforms = function(elem, path, params) {
|
192 |
|
193 |
|
194 | if (!elem.hasAttr('transform') || !elem.attr('transform').value ||
|
195 | elem.someAttr(function(attr) {
|
196 | return ~referencesProps.indexOf(attr.name) && ~attr.value.indexOf('url(');
|
197 | }))
|
198 | return path;
|
199 |
|
200 | var matrix = transformsMultiply(transform2js(elem.attr('transform').value)),
|
201 | stroke = elem.computedAttr('stroke'),
|
202 | id = elem.computedAttr('id'),
|
203 | transformPrecision = params.transformPrecision,
|
204 | newPoint, scale;
|
205 |
|
206 | if (stroke && stroke != 'none') {
|
207 | if (!params.applyTransformsStroked ||
|
208 | (matrix.data[0] != matrix.data[3] || matrix.data[1] != -matrix.data[2]) &&
|
209 | (matrix.data[0] != -matrix.data[3] || matrix.data[1] != matrix.data[2]))
|
210 | return path;
|
211 |
|
212 |
|
213 | if (id) {
|
214 | var idElem = elem,
|
215 | hasStrokeWidth = false;
|
216 |
|
217 | do {
|
218 | if (idElem.hasAttr('stroke-width')) hasStrokeWidth = true;
|
219 | } while (!idElem.hasAttr('id', id) && !hasStrokeWidth && (idElem = idElem.parentNode));
|
220 |
|
221 | if (!hasStrokeWidth) return path;
|
222 | }
|
223 |
|
224 | scale = +Math.sqrt(matrix.data[0] * matrix.data[0] + matrix.data[1] * matrix.data[1]).toFixed(transformPrecision);
|
225 |
|
226 | if (scale !== 1) {
|
227 | var strokeWidth = elem.computedAttr('stroke-width') || defaultStrokeWidth;
|
228 |
|
229 | if (!elem.hasAttr('vector-effect') || elem.attr('vector-effect').value !== 'non-scaling-stroke') {
|
230 | if (elem.hasAttr('stroke-width')) {
|
231 | elem.attrs['stroke-width'].value = elem.attrs['stroke-width'].value.trim()
|
232 | .replace(regNumericValues, function(num) {
|
233 | return removeLeadingZero(num * scale);
|
234 | });
|
235 | } else {
|
236 | elem.addAttr({
|
237 | name: 'stroke-width',
|
238 | prefix: '',
|
239 | local: 'stroke-width',
|
240 | value: strokeWidth.replace(regNumericValues, function(num) {
|
241 | return removeLeadingZero(num * scale);
|
242 | })
|
243 | });
|
244 | }
|
245 | }
|
246 | }
|
247 | } else if (id) {
|
248 | return path;
|
249 | }
|
250 |
|
251 | path.forEach(function(pathItem) {
|
252 |
|
253 | if (pathItem.data) {
|
254 |
|
255 |
|
256 | if (pathItem.instruction === 'h') {
|
257 |
|
258 | pathItem.instruction = 'l';
|
259 | pathItem.data[1] = 0;
|
260 |
|
261 |
|
262 | } else if (pathItem.instruction === 'v') {
|
263 |
|
264 | pathItem.instruction = 'l';
|
265 | pathItem.data[1] = pathItem.data[0];
|
266 | pathItem.data[0] = 0;
|
267 |
|
268 | }
|
269 |
|
270 |
|
271 | if (pathItem.instruction === 'M' &&
|
272 | (matrix.data[4] !== 0 ||
|
273 | matrix.data[5] !== 0)
|
274 | ) {
|
275 |
|
276 |
|
277 | newPoint = transformPoint(matrix.data, pathItem.data[0], pathItem.data[1]);
|
278 | set(pathItem.data, newPoint);
|
279 | set(pathItem.coords, newPoint);
|
280 |
|
281 | // clear translate() data from transform matrix
|
282 | matrix.data[4] = 0;
|
283 | matrix.data[5] = 0;
|
284 |
|
285 | } else {
|
286 |
|
287 | if (pathItem.instruction == 'a') {
|
288 |
|
289 | transformArc(pathItem.data, matrix.data);
|
290 |
|
291 |
|
292 | if (Math.abs(pathItem.data[2]) > 80) {
|
293 | var a = pathItem.data[0],
|
294 | rotation = pathItem.data[2];
|
295 | pathItem.data[0] = pathItem.data[1];
|
296 | pathItem.data[1] = a;
|
297 | pathItem.data[2] = rotation + (rotation > 0 ? -90 : 90);
|
298 | }
|
299 |
|
300 | newPoint = transformPoint(matrix.data, pathItem.data[5], pathItem.data[6]);
|
301 | pathItem.data[5] = newPoint[0];
|
302 | pathItem.data[6] = newPoint[1];
|
303 |
|
304 | } else {
|
305 |
|
306 | for (var i = 0; i < pathItem.data.length; i += 2) {
|
307 | newPoint = transformPoint(matrix.data, pathItem.data[i], pathItem.data[i + 1]);
|
308 | pathItem.data[i] = newPoint[0];
|
309 | pathItem.data[i + 1] = newPoint[1];
|
310 | }
|
311 | }
|
312 |
|
313 | pathItem.coords[0] = pathItem.base[0] + pathItem.data[pathItem.data.length - 2];
|
314 | pathItem.coords[1] = pathItem.base[1] + pathItem.data[pathItem.data.length - 1];
|
315 |
|
316 | }
|
317 |
|
318 | }
|
319 |
|
320 | });
|
321 |
|
322 |
|
323 | elem.removeAttr('transform');
|
324 |
|
325 | return path;
|
326 | };
|
327 |
|
328 |
|
329 |
|
330 |
|
331 |
|
332 |
|
333 |
|
334 |
|
335 | function transformPoint(matrix, x, y) {
|
336 |
|
337 | return [
|
338 | matrix[0] * x + matrix[2] * y + matrix[4],
|
339 | matrix[1] * x + matrix[3] * y + matrix[5]
|
340 | ];
|
341 |
|
342 | }
|
343 |
|
344 |
|
345 |
|
346 |
|
347 |
|
348 |
|
349 |
|
350 |
|
351 |
|
352 |
|
353 |
|
354 |
|
355 |
|
356 |
|
357 |
|
358 |
|
359 |
|
360 | exports.computeCubicBoundingBox = function(xa, ya, xb, yb, xc, yc, xd, yd) {
|
361 |
|
362 | var minx = Number.POSITIVE_INFINITY,
|
363 | miny = Number.POSITIVE_INFINITY,
|
364 | maxx = Number.NEGATIVE_INFINITY,
|
365 | maxy = Number.NEGATIVE_INFINITY,
|
366 | ts,
|
367 | t,
|
368 | x,
|
369 | y,
|
370 | i;
|
371 |
|
372 |
|
373 | if (xa < minx) { minx = xa; }
|
374 | if (xa > maxx) { maxx = xa; }
|
375 | if (xd < minx) { minx= xd; }
|
376 | if (xd > maxx) { maxx = xd; }
|
377 |
|
378 | ts = computeCubicFirstDerivativeRoots(xa, xb, xc, xd);
|
379 |
|
380 | for (i = 0; i < ts.length; i++) {
|
381 |
|
382 | t = ts[i];
|
383 |
|
384 | if (t >= 0 && t <= 1) {
|
385 | x = computeCubicBaseValue(t, xa, xb, xc, xd);
|
386 |
|
387 |
|
388 | if (x < minx) { minx = x; }
|
389 | if (x > maxx) { maxx = x; }
|
390 | }
|
391 |
|
392 | }
|
393 |
|
394 |
|
395 | if (ya < miny) { miny = ya; }
|
396 | if (ya > maxy) { maxy = ya; }
|
397 | if (yd < miny) { miny = yd; }
|
398 | if (yd > maxy) { maxy = yd; }
|
399 |
|
400 | ts = computeCubicFirstDerivativeRoots(ya, yb, yc, yd);
|
401 |
|
402 | for (i = 0; i < ts.length; i++) {
|
403 |
|
404 | t = ts[i];
|
405 |
|
406 | if (t >= 0 && t <= 1) {
|
407 |
|
408 | y = computeCubicBaseValue(t, ya, yb, yc, yd);
|
409 |
|
410 | if (y < miny) { miny = y; }
|
411 | if (y > maxy) { maxy = y; }
|
412 | }
|
413 |
|
414 | }
|
415 |
|
416 | return {
|
417 | minx: minx,
|
418 | miny: miny,
|
419 | maxx: maxx,
|
420 | maxy: maxy
|
421 | };
|
422 |
|
423 | };
|
424 |
|
425 |
|
426 | function computeCubicBaseValue(t, a, b, c, d) {
|
427 |
|
428 | var mt = 1 - t;
|
429 |
|
430 | return mt * mt * mt * a + 3 * mt * mt * t * b + 3 * mt * t * t * c + t * t * t * d;
|
431 |
|
432 | }
|
433 |
|
434 |
|
435 | function computeCubicFirstDerivativeRoots(a, b, c, d) {
|
436 |
|
437 | var result = [-1, -1],
|
438 | tl = -a + 2 * b - c,
|
439 | tr = -Math.sqrt(-a * (c - d) + b * b - b * (c + d) + c * c),
|
440 | dn = -a + 3 * b - 3 * c + d;
|
441 |
|
442 | if (dn !== 0) {
|
443 | result[0] = (tl + tr) / dn;
|
444 | result[1] = (tl - tr) / dn;
|
445 | }
|
446 |
|
447 | return result;
|
448 |
|
449 | }
|
450 |
|
451 |
|
452 |
|
453 |
|
454 |
|
455 |
|
456 |
|
457 |
|
458 |
|
459 |
|
460 |
|
461 |
|
462 |
|
463 |
|
464 |
|
465 | exports.computeQuadraticBoundingBox = function(xa, ya, xb, yb, xc, yc) {
|
466 |
|
467 | var minx = Number.POSITIVE_INFINITY,
|
468 | miny = Number.POSITIVE_INFINITY,
|
469 | maxx = Number.NEGATIVE_INFINITY,
|
470 | maxy = Number.NEGATIVE_INFINITY,
|
471 | t,
|
472 | x,
|
473 | y;
|
474 |
|
475 |
|
476 | if (xa < minx) { minx = xa; }
|
477 | if (xa > maxx) { maxx = xa; }
|
478 | if (xc < minx) { minx = xc; }
|
479 | if (xc > maxx) { maxx = xc; }
|
480 |
|
481 | t = computeQuadraticFirstDerivativeRoot(xa, xb, xc);
|
482 |
|
483 | if (t >= 0 && t <= 1) {
|
484 | x = computeQuadraticBaseValue(t, xa, xb, xc);
|
485 |
|
486 |
|
487 | if (x < minx) { minx = x; }
|
488 | if (x > maxx) { maxx = x; }
|
489 | }
|
490 |
|
491 |
|
492 | if (ya < miny) { miny = ya; }
|
493 | if (ya > maxy) { maxy = ya; }
|
494 | if (yc < miny) { miny = yc; }
|
495 | if (yc > maxy) { maxy = yc; }
|
496 |
|
497 | t = computeQuadraticFirstDerivativeRoot(ya, yb, yc);
|
498 |
|
499 | if (t >= 0 && t <=1 ) {
|
500 |
|
501 | y = computeQuadraticBaseValue(t, ya, yb, yc);
|
502 |
|
503 | if (y < miny) { miny = y; }
|
504 | if (y > maxy) { maxy = y ; }
|
505 |
|
506 | }
|
507 |
|
508 | return {
|
509 | minx: minx,
|
510 | miny: miny,
|
511 | maxx: maxx,
|
512 | maxy: maxy
|
513 | };
|
514 |
|
515 | };
|
516 |
|
517 |
|
518 | function computeQuadraticBaseValue(t, a, b, c) {
|
519 |
|
520 | var mt = 1 - t;
|
521 |
|
522 | return mt * mt * a + 2 * mt * t * b + t * t * c;
|
523 |
|
524 | }
|
525 |
|
526 |
|
527 | function computeQuadraticFirstDerivativeRoot(a, b, c) {
|
528 |
|
529 | var t = -1,
|
530 | denominator = a - 2 * b + c;
|
531 |
|
532 | if (denominator !== 0) {
|
533 | t = (a - b) / denominator;
|
534 | }
|
535 |
|
536 | return t;
|
537 |
|
538 | }
|
539 |
|
540 |
|
541 |
|
542 |
|
543 |
|
544 |
|
545 |
|
546 |
|
547 | exports.js2path = function(path, data, params) {
|
548 |
|
549 | path.pathJS = data;
|
550 |
|
551 | if (params.collapseRepeated) {
|
552 | data = collapseRepeated(data);
|
553 | }
|
554 |
|
555 | path.attr('d').value = data.reduce(function(pathString, item) {
|
556 | return pathString += item.instruction + (item.data ? cleanupOutData(item.data, params) : '');
|
557 | }, '');
|
558 |
|
559 | };
|
560 |
|
561 |
|
562 |
|
563 |
|
564 |
|
565 |
|
566 |
|
567 | function collapseRepeated(data) {
|
568 |
|
569 | var prev,
|
570 | prevIndex;
|
571 |
|
572 |
|
573 | data = data.reduce(function(newPath, item) {
|
574 | if (
|
575 | prev && item.data &&
|
576 | item.instruction == prev.instruction
|
577 | ) {
|
578 |
|
579 | if (item.instruction != 'M') {
|
580 | prev = newPath[prevIndex] = {
|
581 | instruction: prev.instruction,
|
582 | data: prev.data.concat(item.data),
|
583 | coords: item.coords,
|
584 | base: prev.base
|
585 | };
|
586 | } else {
|
587 | prev.data = item.data;
|
588 | prev.coords = item.coords;
|
589 | }
|
590 | } else {
|
591 | newPath.push(item);
|
592 | prev = item;
|
593 | prevIndex = newPath.length - 1;
|
594 | }
|
595 |
|
596 | return newPath;
|
597 | }, []);
|
598 |
|
599 | return data;
|
600 |
|
601 | }
|
602 |
|
603 | function set(dest, source) {
|
604 | dest[0] = source[source.length - 2];
|
605 | dest[1] = source[source.length - 1];
|
606 | return dest;
|
607 | }
|
608 |
|
609 |
|
610 |
|
611 |
|
612 |
|
613 |
|
614 |
|
615 |
|
616 |
|
617 |
|
618 | exports.intersects = function(path1, path2) {
|
619 | if (path1.length < 3 || path2.length < 3) return false;
|
620 |
|
621 |
|
622 | var points1 = relative2absolute(path1).reduce(gatherPoints, []),
|
623 | points2 = relative2absolute(path2).reduce(gatherPoints, []);
|
624 |
|
625 |
|
626 | if (points1.maxX <= points2.minX || points2.maxX <= points1.minX ||
|
627 | points1.maxY <= points2.minY || points2.maxY <= points1.minY ||
|
628 | points1.every(function (set1) {
|
629 | return points2.every(function (set2) {
|
630 | return set1[set1.maxX][0] <= set2[set2.minX][0] ||
|
631 | set2[set2.maxX][0] <= set1[set1.minX][0] ||
|
632 | set1[set1.maxY][1] <= set2[set2.minY][1] ||
|
633 | set2[set2.maxY][1] <= set1[set1.minY][1];
|
634 | });
|
635 | })
|
636 | ) return false;
|
637 |
|
638 |
|
639 | var hullNest1 = points1.map(convexHull),
|
640 | hullNest2 = points2.map(convexHull);
|
641 |
|
642 |
|
643 | return hullNest1.some(function(hull1) {
|
644 | if (hull1.length < 3) return false;
|
645 |
|
646 | return hullNest2.some(function(hull2) {
|
647 | if (hull2.length < 3) return false;
|
648 |
|
649 | var simplex = [getSupport(hull1, hull2, [1, 0])],
|
650 | direction = minus(simplex[0]);
|
651 |
|
652 | var iterations = 1e4;
|
653 | while (true) {
|
654 | if (iterations-- == 0) {
|
655 | console.error('Error: infinite loop while processing mergePaths plugin.');
|
656 | return true;
|
657 | }
|
658 |
|
659 | simplex.push(getSupport(hull1, hull2, direction));
|
660 |
|
661 | if (dot(direction, simplex[simplex.length - 1]) <= 0) return false;
|
662 |
|
663 | if (processSimplex(simplex, direction)) return true;
|
664 | }
|
665 | });
|
666 | });
|
667 |
|
668 | function getSupport(a, b, direction) {
|
669 | return sub(supportPoint(a, direction), supportPoint(b, minus(direction)));
|
670 | }
|
671 |
|
672 |
|
673 |
|
674 |
|
675 | function supportPoint(polygon, direction) {
|
676 | var index = direction[1] >= 0 ?
|
677 | direction[0] < 0 ? polygon.maxY : polygon.maxX :
|
678 | direction[0] < 0 ? polygon.minX : polygon.minY,
|
679 | max = -Infinity,
|
680 | value;
|
681 | while ((value = dot(polygon[index], direction)) > max) {
|
682 | max = value;
|
683 | index = ++index % polygon.length;
|
684 | }
|
685 | return polygon[(index || polygon.length) - 1];
|
686 | }
|
687 | };
|
688 |
|
689 | function processSimplex(simplex, direction) {
|
690 |
|
691 |
|
692 |
|
693 | if (simplex.length == 2) {
|
694 | var a = simplex[1],
|
695 | b = simplex[0],
|
696 | AO = minus(simplex[1]),
|
697 | AB = sub(b, a);
|
698 |
|
699 | if (dot(AO, AB) > 0) {
|
700 |
|
701 | set(direction, orth(AB, a));
|
702 | } else {
|
703 | set(direction, AO);
|
704 | // only A remains in the simplex
|
705 | simplex.shift();
|
706 | }
|
707 | } else {
|
708 | var a = simplex[2],
|
709 | b = simplex[1],
|
710 | c = simplex[0],
|
711 | AB = sub(b, a),
|
712 | AC = sub(c, a),
|
713 | AO = minus(a),
|
714 | ACB = orth(AB, AC),
|
715 | ABC = orth(AC, AB);
|
716 |
|
717 | if (dot(ACB, AO) > 0) {
|
718 | if (dot(AB, AO) > 0) {
|
719 | set(direction, ACB);
|
720 | simplex.shift(); // simplex = [b, a]
|
721 | } else {
|
722 | set(direction, AO);
|
723 | simplex.splice(0, 2); // simplex = [a]
|
724 | }
|
725 | } else if (dot(ABC, AO) > 0) {
|
726 | if (dot(AC, AO) > 0) {
|
727 | set(direction, ABC);
|
728 | simplex.splice(1, 1); // simplex = [c, a]
|
729 | } else {
|
730 | set(direction, AO);
|
731 | simplex.splice(0, 2); // simplex = [a]
|
732 | }
|
733 | } else // region 7
|
734 | return true;
|
735 | }
|
736 | return false;
|
737 | }
|
738 |
|
739 | function minus(v) {
|
740 | return [-v[0], -v[1]];
|
741 | }
|
742 |
|
743 | function sub(v1, v2) {
|
744 | return [v1[0] - v2[0], v1[1] - v2[1]];
|
745 | }
|
746 |
|
747 | function dot(v1, v2) {
|
748 | return v1[0] * v2[0] + v1[1] * v2[1];
|
749 | }
|
750 |
|
751 | function orth(v, from) {
|
752 | var o = [-v[1], v[0]];
|
753 | return dot(o, minus(from)) < 0 ? minus(o) : o;
|
754 | }
|
755 |
|
756 | function gatherPoints(points, item, index, path) {
|
757 |
|
758 | var subPath = points.length && points[points.length - 1],
|
759 | prev = index && path[index - 1],
|
760 | basePoint = subPath.length && subPath[subPath.length - 1],
|
761 | data = item.data,
|
762 | ctrlPoint = basePoint;
|
763 |
|
764 | switch (item.instruction) {
|
765 | case 'M':
|
766 | points.push(subPath = []);
|
767 | break;
|
768 | case 'H':
|
769 | addPoint(subPath, [data[0], basePoint[1]]);
|
770 | break;
|
771 | case 'V':
|
772 | addPoint(subPath, [basePoint[0], data[0]]);
|
773 | break;
|
774 | case 'Q':
|
775 | addPoint(subPath, data.slice(0, 2));
|
776 | prevCtrlPoint = [data[2] - data[0], data[3] - data[1]];
|
777 | break;
|
778 | case 'T':
|
779 | if (prev.instruction == 'Q' || prev.instruction == 'T') {
|
780 | ctrlPoint = [basePoint[0] + prevCtrlPoint[0], basePoint[1] + prevCtrlPoint[1]];
|
781 | addPoint(subPath, ctrlPoint);
|
782 | prevCtrlPoint = [data[0] - ctrlPoint[0], data[1] - ctrlPoint[1]];
|
783 | }
|
784 | break;
|
785 | case 'C':
|
786 |
|
787 | addPoint(subPath, [.5 * (basePoint[0] + data[0]), .5 * (basePoint[1] + data[1])]);
|
788 | addPoint(subPath, [.5 * (data[0] + data[2]), .5 * (data[1] + data[3])]);
|
789 | addPoint(subPath, [.5 * (data[2] + data[4]), .5 * (data[3] + data[5])]);
|
790 | prevCtrlPoint = [data[4] - data[2], data[5] - data[3]];
|
791 | break;
|
792 | case 'S':
|
793 | if (prev.instruction == 'C' || prev.instruction == 'S') {
|
794 | addPoint(subPath, [basePoint[0] + .5 * prevCtrlPoint[0], basePoint[1] + .5 * prevCtrlPoint[1]]);
|
795 | ctrlPoint = [basePoint[0] + prevCtrlPoint[0], basePoint[1] + prevCtrlPoint[1]];
|
796 | }
|
797 | addPoint(subPath, [.5 * (ctrlPoint[0] + data[0]), .5 * (ctrlPoint[1]+ data[1])]);
|
798 | addPoint(subPath, [.5 * (data[0] + data[2]), .5 * (data[1] + data[3])]);
|
799 | prevCtrlPoint = [data[2] - data[0], data[3] - data[1]];
|
800 | break;
|
801 | case 'A':
|
802 |
|
803 | var curves = a2c.apply(0, basePoint.concat(data));
|
804 | for (var cData; (cData = curves.splice(0,6).map(toAbsolute)).length;) {
|
805 | addPoint(subPath, [.5 * (basePoint[0] + cData[0]), .5 * (basePoint[1] + cData[1])]);
|
806 | addPoint(subPath, [.5 * (cData[0] + cData[2]), .5 * (cData[1] + cData[3])]);
|
807 | addPoint(subPath, [.5 * (cData[2] + cData[4]), .5 * (cData[3] + cData[5])]);
|
808 | if (curves.length) addPoint(subPath, basePoint = cData.slice(-2));
|
809 | }
|
810 | break;
|
811 | }
|
812 |
|
813 | if (data && data.length >= 2) addPoint(subPath, data.slice(-2));
|
814 | return points;
|
815 |
|
816 | function toAbsolute(n, i) { return n + basePoint[i % 2] }
|
817 |
|
818 |
|
819 | function addPoint(path, point) {
|
820 | if (!path.length || point[1] > path[path.maxY][1]) {
|
821 | path.maxY = path.length;
|
822 | points.maxY = points.length ? Math.max(point[1], points.maxY) : point[1];
|
823 | }
|
824 | if (!path.length || point[0] > path[path.maxX][0]) {
|
825 | path.maxX = path.length;
|
826 | points.maxX = points.length ? Math.max(point[0], points.maxX) : point[0];
|
827 | }
|
828 | if (!path.length || point[1] < path[path.minY][1]) {
|
829 | path.minY = path.length;
|
830 | points.minY = points.length ? Math.min(point[1], points.minY) : point[1];
|
831 | }
|
832 | if (!path.length || point[0] < path[path.minX][0]) {
|
833 | path.minX = path.length;
|
834 | points.minX = points.length ? Math.min(point[0], points.minX) : point[0];
|
835 | }
|
836 | path.push(point);
|
837 | }
|
838 | }
|
839 |
|
840 |
|
841 |
|
842 |
|
843 |
|
844 |
|
845 |
|
846 | function convexHull(points) {
|
847 |
|
848 |
|
849 | points.sort(function(a, b) {
|
850 | return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
|
851 | });
|
852 |
|
853 | var lower = [],
|
854 | minY = 0,
|
855 | bottom = 0;
|
856 | for (var i = 0; i < points.length; i++) {
|
857 | while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], points[i]) <= 0) {
|
858 | lower.pop();
|
859 | }
|
860 | if (points[i][1] < points[minY][1]) {
|
861 | minY = i;
|
862 | bottom = lower.length;
|
863 | }
|
864 | lower.push(points[i]);
|
865 | }
|
866 |
|
867 | var upper = [],
|
868 | maxY = points.length - 1,
|
869 | top = 0;
|
870 | for (var i = points.length; i--;) {
|
871 | while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], points[i]) <= 0) {
|
872 | upper.pop();
|
873 | }
|
874 | if (points[i][1] > points[maxY][1]) {
|
875 | maxY = i;
|
876 | top = upper.length;
|
877 | }
|
878 | upper.push(points[i]);
|
879 | }
|
880 |
|
881 |
|
882 | upper.pop();
|
883 | lower.pop();
|
884 |
|
885 | var hull = lower.concat(upper);
|
886 |
|
887 | hull.minX = 0;
|
888 | hull.maxX = lower.length;
|
889 | hull.minY = bottom;
|
890 | hull.maxY = (lower.length + top) % hull.length;
|
891 |
|
892 | return hull;
|
893 | }
|
894 |
|
895 | function cross(o, a, b) {
|
896 | return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
|
897 | }
|
898 |
|
899 |
|
900 |
|
901 |
|
902 |
|
903 |
|
904 | function a2c(x1, y1, rx, ry, angle, large_arc_flag, sweep_flag, x2, y2, recursive) {
|
905 |
|
906 |
|
907 | var _120 = Math.PI * 120 / 180,
|
908 | rad = Math.PI / 180 * (+angle || 0),
|
909 | res = [],
|
910 | rotateX = function(x, y, rad) { return x * Math.cos(rad) - y * Math.sin(rad) },
|
911 | rotateY = function(x, y, rad) { return x * Math.sin(rad) + y * Math.cos(rad) };
|
912 | if (!recursive) {
|
913 | x1 = rotateX(x1, y1, -rad);
|
914 | y1 = rotateY(x1, y1, -rad);
|
915 | x2 = rotateX(x2, y2, -rad);
|
916 | y2 = rotateY(x2, y2, -rad);
|
917 | var x = (x1 - x2) / 2,
|
918 | y = (y1 - y2) / 2;
|
919 | var h = (x * x) / (rx * rx) + (y * y) / (ry * ry);
|
920 | if (h > 1) {
|
921 | h = Math.sqrt(h);
|
922 | rx = h * rx;
|
923 | ry = h * ry;
|
924 | }
|
925 | var rx2 = rx * rx,
|
926 | ry2 = ry * ry,
|
927 | k = (large_arc_flag == sweep_flag ? -1 : 1) *
|
928 | Math.sqrt(Math.abs((rx2 * ry2 - rx2 * y * y - ry2 * x * x) / (rx2 * y * y + ry2 * x * x))),
|
929 | cx = k * rx * y / ry + (x1 + x2) / 2,
|
930 | cy = k * -ry * x / rx + (y1 + y2) / 2,
|
931 | f1 = Math.asin(((y1 - cy) / ry).toFixed(9)),
|
932 | f2 = Math.asin(((y2 - cy) / ry).toFixed(9));
|
933 |
|
934 | f1 = x1 < cx ? Math.PI - f1 : f1;
|
935 | f2 = x2 < cx ? Math.PI - f2 : f2;
|
936 | f1 < 0 && (f1 = Math.PI * 2 + f1);
|
937 | f2 < 0 && (f2 = Math.PI * 2 + f2);
|
938 | if (sweep_flag && f1 > f2) {
|
939 | f1 = f1 - Math.PI * 2;
|
940 | }
|
941 | if (!sweep_flag && f2 > f1) {
|
942 | f2 = f2 - Math.PI * 2;
|
943 | }
|
944 | } else {
|
945 | f1 = recursive[0];
|
946 | f2 = recursive[1];
|
947 | cx = recursive[2];
|
948 | cy = recursive[3];
|
949 | }
|
950 | var df = f2 - f1;
|
951 | if (Math.abs(df) > _120) {
|
952 | var f2old = f2,
|
953 | x2old = x2,
|
954 | y2old = y2;
|
955 | f2 = f1 + _120 * (sweep_flag && f2 > f1 ? 1 : -1);
|
956 | x2 = cx + rx * Math.cos(f2);
|
957 | y2 = cy + ry * Math.sin(f2);
|
958 | res = a2c(x2, y2, rx, ry, angle, 0, sweep_flag, x2old, y2old, [f2, f2old, cx, cy]);
|
959 | }
|
960 | df = f2 - f1;
|
961 | var c1 = Math.cos(f1),
|
962 | s1 = Math.sin(f1),
|
963 | c2 = Math.cos(f2),
|
964 | s2 = Math.sin(f2),
|
965 | t = Math.tan(df / 4),
|
966 | hx = 4 / 3 * rx * t,
|
967 | hy = 4 / 3 * ry * t,
|
968 | m = [
|
969 | - hx * s1, hy * c1,
|
970 | x2 + hx * s2 - x1, y2 - hy * c2 - y1,
|
971 | x2 - x1, y2 - y1
|
972 | ];
|
973 | if (recursive) {
|
974 | return m.concat(res);
|
975 | } else {
|
976 | res = m.concat(res);
|
977 | var newres = [];
|
978 | for (var i = 0, n = res.length; i < n; i++) {
|
979 | newres[i] = i % 2 ? rotateY(res[i - 1], res[i], rad) : rotateX(res[i], res[i + 1], rad);
|
980 | }
|
981 | return newres;
|
982 | }
|
983 | }
|
984 |
|