source: frontend/node_modules/svgo/plugins/_path.js

Last change on this file was 9af201e, checked in by MBK <marija.karapandzova@…>, 11 days ago

Fix frontend appearance
  • Property mode set to 100644
File size: 31.0 KB
Line 
1/* global a2c */
2'use strict';
3
4var 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
11var 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 * Convert path string to JS representation.
27 *
28 * @param {String} pathString input string
29 * @param {Object} params plugin params
30 * @return {Array} output array
31 */
32exports.path2js = function(path) {
33 if (path.pathJS) return path.pathJS;
34
35 var paramsLength = { // Number of parameters of every path command
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 = [], // JS representation of the path data
40 instruction, // current instruction context
41 startMoveto = false;
42
43 // splitting path string into array like ['M', '10 50', 'L', '20 30']
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 // instruction item
53 if (regPathInstructions.test(data)) {
54 instruction = data;
55
56 // z - instruction w/o data
57 if (instruction == 'Z' || instruction == 'z') {
58 pathData.push({
59 instruction: 'z'
60 });
61 }
62 // data item
63 } else {
64 /* jshint boss: true */
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 // Subsequent moveto pairs of coordinates are threated as implicit lineto commands
80 // http://www.w3.org/TR/SVG/paths.html#PathDataMovetoCommands
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 // First moveto is actually absolute. Subsequent coordinates were separated above.
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 * Convert relative Path data to absolute.
109 *
110 * @param {Array} data input data
111 * @return {Array} output data
112 */
113var 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 * Apply transformation(s) to the Path data.
185 *
186 * @param {Object} elem current element
187 * @param {Array} path input path data
188 * @param {Object} params whether to apply transforms to stroked lines and transform precision (used for stroke width)
189 * @return {Array} output path data
190 */
191exports.applyTransforms = function(elem, path, params) {
192 // if there are no 'stroke' attr and references to other objects such as
193 // gradiends or clip-path which are also subjects to transform.
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 // "stroke-width" should be inside the part with ID, otherwise it can be overrided in <use>
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) { // Stroke and stroke-width can be redefined with <use>
248 return path;
249 }
250
251 path.forEach(function(pathItem) {
252
253 if (pathItem.data) {
254
255 // h -> l
256 if (pathItem.instruction === 'h') {
257
258 pathItem.instruction = 'l';
259 pathItem.data[1] = 0;
260
261 // v -> l
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 // if there is a translate() transform
271 if (pathItem.instruction === 'M' &&
272 (matrix.data[4] !== 0 ||
273 matrix.data[5] !== 0)
274 ) {
275
276 // then apply it only to the first absoluted M
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 // reduce number of digits in rotation angle
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 // remove transform attr
323 elem.removeAttr('transform');
324
325 return path;
326};
327
328/**
329 * Apply transform 3x3 matrix to x-y point.
330 *
331 * @param {Array} matrix transform 3x3 matrix
332 * @param {Array} point x-y point
333 * @return {Array} point with new coordinates
334 */
335function 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 * Compute Cubic Bézie bounding box.
346 *
347 * @see http://processingjs.nihongoresources.com/bezierinfo/
348 *
349 * @param {Float} xa
350 * @param {Float} ya
351 * @param {Float} xb
352 * @param {Float} yb
353 * @param {Float} xc
354 * @param {Float} yc
355 * @param {Float} xd
356 * @param {Float} yd
357 *
358 * @return {Object}
359 */
360exports.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 // X
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 // y = computeCubicBaseValue(t, ya, yb, yc, yd);
387
388 if (x < minx) { minx = x; }
389 if (x > maxx) { maxx = x; }
390 }
391
392 }
393
394 // Y
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 // x = computeCubicBaseValue(t, xa, xb, xc, xd);
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// compute the value for the cubic bezier function at time=t
426function 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// compute the value for the first derivative of the cubic bezier function at time=t
435function 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 * Compute Quadratic Bézier bounding box.
453 *
454 * @see http://processingjs.nihongoresources.com/bezierinfo/
455 *
456 * @param {Float} xa
457 * @param {Float} ya
458 * @param {Float} xb
459 * @param {Float} yb
460 * @param {Float} xc
461 * @param {Float} yc
462 *
463 * @return {Object}
464 */
465exports.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 // X
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 // y = computeQuadraticBaseValue(t, ya, yb, yc);
486
487 if (x < minx) { minx = x; }
488 if (x > maxx) { maxx = x; }
489 }
490
491 // Y
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 // x = computeQuadraticBaseValue(t, xa, xb, xc);
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// compute the value for the quadratic bezier function at time=t
518function 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// compute the value for the first derivative of the quadratic bezier function at time=t
527function 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 * Convert path array to string.
542 *
543 * @param {Array} path input path data
544 * @param {Object} params plugin params
545 * @return {String} output path string
546 */
547exports.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 var strData = '';
557 if (item.data) {
558 strData = cleanupOutData(item.data, params, item.instruction);
559 }
560 return pathString += item.instruction + strData;
561 }, '');
562
563};
564
565/**
566 * Collapse repeated instructions data
567 *
568 * @param {Array} path input path data
569 * @return {Array} output path data
570 */
571function collapseRepeated(data) {
572
573 var prev,
574 prevIndex;
575
576 // copy an array and modifieds item to keep original data untouched
577 data = data.reduce(function(newPath, item) {
578 if (
579 prev && item.data &&
580 item.instruction == prev.instruction
581 ) {
582 // concat previous data with current
583 if (item.instruction != 'M') {
584 prev = newPath[prevIndex] = {
585 instruction: prev.instruction,
586 data: prev.data.concat(item.data),
587 coords: item.coords,
588 base: prev.base
589 };
590 } else {
591 prev.data = item.data;
592 prev.coords = item.coords;
593 }
594 } else {
595 newPath.push(item);
596 prev = item;
597 prevIndex = newPath.length - 1;
598 }
599
600 return newPath;
601 }, []);
602
603 return data;
604
605}
606
607function set(dest, source) {
608 dest[0] = source[source.length - 2];
609 dest[1] = source[source.length - 1];
610 return dest;
611}
612
613/**
614 * Checks if two paths have an intersection by checking convex hulls
615 * collision using Gilbert-Johnson-Keerthi distance algorithm
616 * http://entropyinteractive.com/2011/04/gjk-algorithm/
617 *
618 * @param {Array} path1 JS path representation
619 * @param {Array} path2 JS path representation
620 * @return {Boolean}
621 */
622exports.intersects = function(path1, path2) {
623 if (path1.length < 3 || path2.length < 3) return false; // nothing to fill
624
625 // Collect points of every subpath.
626 var points1 = relative2absolute(path1).reduce(gatherPoints, []),
627 points2 = relative2absolute(path2).reduce(gatherPoints, []);
628
629 // Axis-aligned bounding box check.
630 if (points1.maxX <= points2.minX || points2.maxX <= points1.minX ||
631 points1.maxY <= points2.minY || points2.maxY <= points1.minY ||
632 points1.every(function (set1) {
633 return points2.every(function (set2) {
634 return set1[set1.maxX][0] <= set2[set2.minX][0] ||
635 set2[set2.maxX][0] <= set1[set1.minX][0] ||
636 set1[set1.maxY][1] <= set2[set2.minY][1] ||
637 set2[set2.maxY][1] <= set1[set1.minY][1];
638 });
639 })
640 ) return false;
641
642 // Get a convex hull from points of each subpath. Has the most complexity O(n·log n).
643 var hullNest1 = points1.map(convexHull),
644 hullNest2 = points2.map(convexHull);
645
646 // Check intersection of every subpath of the first path with every subpath of the second.
647 return hullNest1.some(function(hull1) {
648 if (hull1.length < 3) return false;
649
650 return hullNest2.some(function(hull2) {
651 if (hull2.length < 3) return false;
652
653 var simplex = [getSupport(hull1, hull2, [1, 0])], // create the initial simplex
654 direction = minus(simplex[0]); // set the direction to point towards the origin
655
656 var iterations = 1e4; // infinite loop protection, 10 000 iterations is more than enough
657 while (true) {
658 if (iterations-- == 0) {
659 console.error('Error: infinite loop while processing mergePaths plugin.');
660 return true; // true is the safe value that means “do nothing with paths”
661 }
662 // add a new point
663 simplex.push(getSupport(hull1, hull2, direction));
664 // see if the new point was on the correct side of the origin
665 if (dot(direction, simplex[simplex.length - 1]) <= 0) return false;
666 // process the simplex
667 if (processSimplex(simplex, direction)) return true;
668 }
669 });
670 });
671
672 function getSupport(a, b, direction) {
673 return sub(supportPoint(a, direction), supportPoint(b, minus(direction)));
674 }
675
676 // Computes farthest polygon point in particular direction.
677 // Thanks to knowledge of min/max x and y coordinates we can choose a quadrant to search in.
678 // Since we're working on convex hull, the dot product is increasing until we find the farthest point.
679 function supportPoint(polygon, direction) {
680 var index = direction[1] >= 0 ?
681 direction[0] < 0 ? polygon.maxY : polygon.maxX :
682 direction[0] < 0 ? polygon.minX : polygon.minY,
683 max = -Infinity,
684 value;
685 while ((value = dot(polygon[index], direction)) > max) {
686 max = value;
687 index = ++index % polygon.length;
688 }
689 return polygon[(index || polygon.length) - 1];
690 }
691};
692
693function processSimplex(simplex, direction) {
694 /* jshint -W004 */
695
696 // we only need to handle to 1-simplex and 2-simplex
697 if (simplex.length == 2) { // 1-simplex
698 var a = simplex[1],
699 b = simplex[0],
700 AO = minus(simplex[1]),
701 AB = sub(b, a);
702 // AO is in the same direction as AB
703 if (dot(AO, AB) > 0) {
704 // get the vector perpendicular to AB facing O
705 set(direction, orth(AB, a));
706 } else {
707 set(direction, AO);
708 // only A remains in the simplex
709 simplex.shift();
710 }
711 } else { // 2-simplex
712 var a = simplex[2], // [a, b, c] = simplex
713 b = simplex[1],
714 c = simplex[0],
715 AB = sub(b, a),
716 AC = sub(c, a),
717 AO = minus(a),
718 ACB = orth(AB, AC), // the vector perpendicular to AB facing away from C
719 ABC = orth(AC, AB); // the vector perpendicular to AC facing away from B
720
721 if (dot(ACB, AO) > 0) {
722 if (dot(AB, AO) > 0) { // region 4
723 set(direction, ACB);
724 simplex.shift(); // simplex = [b, a]
725 } else { // region 5
726 set(direction, AO);
727 simplex.splice(0, 2); // simplex = [a]
728 }
729 } else if (dot(ABC, AO) > 0) {
730 if (dot(AC, AO) > 0) { // region 6
731 set(direction, ABC);
732 simplex.splice(1, 1); // simplex = [c, a]
733 } else { // region 5 (again)
734 set(direction, AO);
735 simplex.splice(0, 2); // simplex = [a]
736 }
737 } else // region 7
738 return true;
739 }
740 return false;
741}
742
743function minus(v) {
744 return [-v[0], -v[1]];
745}
746
747function sub(v1, v2) {
748 return [v1[0] - v2[0], v1[1] - v2[1]];
749}
750
751function dot(v1, v2) {
752 return v1[0] * v2[0] + v1[1] * v2[1];
753}
754
755function orth(v, from) {
756 var o = [-v[1], v[0]];
757 return dot(o, minus(from)) < 0 ? minus(o) : o;
758}
759
760function gatherPoints(points, item, index, path) {
761
762 var subPath = points.length && points[points.length - 1],
763 prev = index && path[index - 1],
764 basePoint = subPath.length && subPath[subPath.length - 1],
765 data = item.data,
766 ctrlPoint = basePoint;
767
768 switch (item.instruction) {
769 case 'M':
770 points.push(subPath = []);
771 break;
772 case 'H':
773 addPoint(subPath, [data[0], basePoint[1]]);
774 break;
775 case 'V':
776 addPoint(subPath, [basePoint[0], data[0]]);
777 break;
778 case 'Q':
779 addPoint(subPath, data.slice(0, 2));
780 prevCtrlPoint = [data[2] - data[0], data[3] - data[1]]; // Save control point for shorthand
781 break;
782 case 'T':
783 if (prev.instruction == 'Q' || prev.instruction == 'T') {
784 ctrlPoint = [basePoint[0] + prevCtrlPoint[0], basePoint[1] + prevCtrlPoint[1]];
785 addPoint(subPath, ctrlPoint);
786 prevCtrlPoint = [data[0] - ctrlPoint[0], data[1] - ctrlPoint[1]];
787 }
788 break;
789 case 'C':
790 // Approximate quibic Bezier curve with middle points between control points
791 addPoint(subPath, [.5 * (basePoint[0] + data[0]), .5 * (basePoint[1] + data[1])]);
792 addPoint(subPath, [.5 * (data[0] + data[2]), .5 * (data[1] + data[3])]);
793 addPoint(subPath, [.5 * (data[2] + data[4]), .5 * (data[3] + data[5])]);
794 prevCtrlPoint = [data[4] - data[2], data[5] - data[3]]; // Save control point for shorthand
795 break;
796 case 'S':
797 if (prev.instruction == 'C' || prev.instruction == 'S') {
798 addPoint(subPath, [basePoint[0] + .5 * prevCtrlPoint[0], basePoint[1] + .5 * prevCtrlPoint[1]]);
799 ctrlPoint = [basePoint[0] + prevCtrlPoint[0], basePoint[1] + prevCtrlPoint[1]];
800 }
801 addPoint(subPath, [.5 * (ctrlPoint[0] + data[0]), .5 * (ctrlPoint[1]+ data[1])]);
802 addPoint(subPath, [.5 * (data[0] + data[2]), .5 * (data[1] + data[3])]);
803 prevCtrlPoint = [data[2] - data[0], data[3] - data[1]];
804 break;
805 case 'A':
806 // Convert the arc to bezier curves and use the same approximation
807 var curves = a2c.apply(0, basePoint.concat(data));
808 for (var cData; (cData = curves.splice(0,6).map(toAbsolute)).length;) {
809 addPoint(subPath, [.5 * (basePoint[0] + cData[0]), .5 * (basePoint[1] + cData[1])]);
810 addPoint(subPath, [.5 * (cData[0] + cData[2]), .5 * (cData[1] + cData[3])]);
811 addPoint(subPath, [.5 * (cData[2] + cData[4]), .5 * (cData[3] + cData[5])]);
812 if (curves.length) addPoint(subPath, basePoint = cData.slice(-2));
813 }
814 break;
815 }
816 // Save final command coordinates
817 if (data && data.length >= 2) addPoint(subPath, data.slice(-2));
818 return points;
819
820 function toAbsolute(n, i) { return n + basePoint[i % 2] }
821
822 // Writes data about the extreme points on each axle
823 function addPoint(path, point) {
824 if (!path.length || point[1] > path[path.maxY][1]) {
825 path.maxY = path.length;
826 points.maxY = points.length ? Math.max(point[1], points.maxY) : point[1];
827 }
828 if (!path.length || point[0] > path[path.maxX][0]) {
829 path.maxX = path.length;
830 points.maxX = points.length ? Math.max(point[0], points.maxX) : point[0];
831 }
832 if (!path.length || point[1] < path[path.minY][1]) {
833 path.minY = path.length;
834 points.minY = points.length ? Math.min(point[1], points.minY) : point[1];
835 }
836 if (!path.length || point[0] < path[path.minX][0]) {
837 path.minX = path.length;
838 points.minX = points.length ? Math.min(point[0], points.minX) : point[0];
839 }
840 path.push(point);
841 }
842}
843
844/**
845 * Forms a convex hull from set of points of every subpath using monotone chain convex hull algorithm.
846 * http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
847 *
848 * @param points An array of [X, Y] coordinates
849 */
850function convexHull(points) {
851 /* jshint -W004 */
852
853 points.sort(function(a, b) {
854 return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
855 });
856
857 var lower = [],
858 minY = 0,
859 bottom = 0;
860 for (var i = 0; i < points.length; i++) {
861 while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], points[i]) <= 0) {
862 lower.pop();
863 }
864 if (points[i][1] < points[minY][1]) {
865 minY = i;
866 bottom = lower.length;
867 }
868 lower.push(points[i]);
869 }
870
871 var upper = [],
872 maxY = points.length - 1,
873 top = 0;
874 for (var i = points.length; i--;) {
875 while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], points[i]) <= 0) {
876 upper.pop();
877 }
878 if (points[i][1] > points[maxY][1]) {
879 maxY = i;
880 top = upper.length;
881 }
882 upper.push(points[i]);
883 }
884
885 // last points are equal to starting points of the other part
886 upper.pop();
887 lower.pop();
888
889 var hull = lower.concat(upper);
890
891 hull.minX = 0; // by sorting
892 hull.maxX = lower.length;
893 hull.minY = bottom;
894 hull.maxY = (lower.length + top) % hull.length;
895
896 return hull;
897}
898
899function cross(o, a, b) {
900 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
901}
902
903/* Based on code from Snap.svg (Apache 2 license). http://snapsvg.io/
904 * Thanks to Dmitry Baranovskiy for his great work!
905 */
906
907// jshint ignore: start
908function a2c(x1, y1, rx, ry, angle, large_arc_flag, sweep_flag, x2, y2, recursive) {
909 // for more information of where this Math came from visit:
910 // http://www.w3.org/TR/SVG11/implnote.html#ArcImplementationNotes
911 var _120 = Math.PI * 120 / 180,
912 rad = Math.PI / 180 * (+angle || 0),
913 res = [],
914 rotateX = function(x, y, rad) { return x * Math.cos(rad) - y * Math.sin(rad) },
915 rotateY = function(x, y, rad) { return x * Math.sin(rad) + y * Math.cos(rad) };
916 if (!recursive) {
917 x1 = rotateX(x1, y1, -rad);
918 y1 = rotateY(x1, y1, -rad);
919 x2 = rotateX(x2, y2, -rad);
920 y2 = rotateY(x2, y2, -rad);
921 var x = (x1 - x2) / 2,
922 y = (y1 - y2) / 2;
923 var h = (x * x) / (rx * rx) + (y * y) / (ry * ry);
924 if (h > 1) {
925 h = Math.sqrt(h);
926 rx = h * rx;
927 ry = h * ry;
928 }
929 var rx2 = rx * rx,
930 ry2 = ry * ry,
931 k = (large_arc_flag == sweep_flag ? -1 : 1) *
932 Math.sqrt(Math.abs((rx2 * ry2 - rx2 * y * y - ry2 * x * x) / (rx2 * y * y + ry2 * x * x))),
933 cx = k * rx * y / ry + (x1 + x2) / 2,
934 cy = k * -ry * x / rx + (y1 + y2) / 2,
935 f1 = Math.asin(((y1 - cy) / ry).toFixed(9)),
936 f2 = Math.asin(((y2 - cy) / ry).toFixed(9));
937
938 f1 = x1 < cx ? Math.PI - f1 : f1;
939 f2 = x2 < cx ? Math.PI - f2 : f2;
940 f1 < 0 && (f1 = Math.PI * 2 + f1);
941 f2 < 0 && (f2 = Math.PI * 2 + f2);
942 if (sweep_flag && f1 > f2) {
943 f1 = f1 - Math.PI * 2;
944 }
945 if (!sweep_flag && f2 > f1) {
946 f2 = f2 - Math.PI * 2;
947 }
948 } else {
949 f1 = recursive[0];
950 f2 = recursive[1];
951 cx = recursive[2];
952 cy = recursive[3];
953 }
954 var df = f2 - f1;
955 if (Math.abs(df) > _120) {
956 var f2old = f2,
957 x2old = x2,
958 y2old = y2;
959 f2 = f1 + _120 * (sweep_flag && f2 > f1 ? 1 : -1);
960 x2 = cx + rx * Math.cos(f2);
961 y2 = cy + ry * Math.sin(f2);
962 res = a2c(x2, y2, rx, ry, angle, 0, sweep_flag, x2old, y2old, [f2, f2old, cx, cy]);
963 }
964 df = f2 - f1;
965 var c1 = Math.cos(f1),
966 s1 = Math.sin(f1),
967 c2 = Math.cos(f2),
968 s2 = Math.sin(f2),
969 t = Math.tan(df / 4),
970 hx = 4 / 3 * rx * t,
971 hy = 4 / 3 * ry * t,
972 m = [
973 - hx * s1, hy * c1,
974 x2 + hx * s2 - x1, y2 - hy * c2 - y1,
975 x2 - x1, y2 - y1
976 ];
977 if (recursive) {
978 return m.concat(res);
979 } else {
980 res = m.concat(res);
981 var newres = [];
982 for (var i = 0, n = res.length; i < n; i++) {
983 newres[i] = i % 2 ? rotateY(res[i - 1], res[i], rad) : rotateX(res[i], res[i + 1], rad);
984 }
985 return newres;
986 }
987}
988// jshint ignore: end
Note: See TracBrowser for help on using the repository browser.