bezier

var _DEG2RAD = Math.PI / 180, _RAD2DEG = 180 / Math.PI, _svgPathExp = /[achlmqstvz]|(-?\d*\.?\d*(?:e[\-+]?\d+)?)[0-9]/ig, _numbersExp = /(?:(-|-=|\+=)?\d*\.?\d*(?:e[\-+]?\d+)?)[0-9]/ig, _selectorExp = /(^[#\.]|[a-y][a-z])/gi, _commands = /[achlmqstvz]/ig, _scientific = /[\+\-]?\d*\.?\d+e[\+\-]?\d+/ig, // translates an arc into a normalized array of cubic beziers excluding the starting x/y. The circle the arc follows will be centered at 0,0 and have a radius of 1 (hence normalized). Each bezier covers no more than 90 degrees; the arc will be divided evenly into a maximum of four curves. _normalizedArcToBeziers = function(angleStart, angleExtent) { var segments = Math.ceil(Math.abs(angleExtent) / 90), l = 0, a = [], angleIncrement, controlLength, angle, dx, dy, i; angleStart *= _DEG2RAD; angleExtent *= _DEG2RAD; angleIncrement = angleExtent / segments; controlLength = 4 / 3 * Math.sin(angleIncrement / 2) / (1 + Math.cos(angleIncrement / 2)); for (i = 0; i < segments; i++) { angle = angleStart + i * angleIncrement; dx = Math.cos(angle); dy = Math.sin(angle); a[l++] = dx - controlLength * dy; a[l++] = dy + controlLength * dx; angle += angleIncrement; dx = Math.cos(angle); dy = Math.sin(angle); a[l++] = dx + controlLength * dy; a[l++] = dy - controlLength * dx; a[l++] = dx; a[l++] = dy; } return a; }, // translates SVG arc data into an array of cubic beziers _arcToBeziers = function(lastX, lastY, rx, ry, angle, largeArcFlag, sweepFlag, x, y) { if (lastX === x && lastY === y) { return; } rx = Math.abs(rx); ry = Math.abs(ry); var angleRad = (angle % 360) * _DEG2RAD, cosAngle = Math.cos(angleRad), sinAngle = Math.sin(angleRad), dx2 = (lastX - x) / 2, dy2 = (lastY - y) / 2, x1 = (cosAngle * dx2 + sinAngle * dy2), y1 = (-sinAngle * dx2 + cosAngle * dy2), rx_sq = rx * rx, ry_sq = ry * ry, x1_sq = x1 * x1, y1_sq = y1 * y1, radiiCheck = x1_sq / rx_sq + y1_sq / ry_sq; if (radiiCheck > 1) { rx = Math.sqrt(radiiCheck) * rx; ry = Math.sqrt(radiiCheck) * ry; rx_sq = rx * rx; ry_sq = ry * ry; } var sign = (largeArcFlag === sweepFlag) ? -1 : 1, sq = ((rx_sq * ry_sq) - (rx_sq * y1_sq) - (ry_sq * x1_sq)) / ((rx_sq * y1_sq) + (ry_sq * x1_sq)); if (sq < 0) { sq = 0; } var coef = (sign * Math.sqrt(sq)), cx1 = coef * ((rx * y1) / ry), cy1 = coef * -((ry * x1) / rx), sx2 = (lastX + x) / 2, sy2 = (lastY + y) / 2, cx = sx2 + (cosAngle * cx1 - sinAngle * cy1), cy = sy2 + (sinAngle * cx1 + cosAngle * cy1), ux = (x1 - cx1) / rx, uy = (y1 - cy1) / ry, vx = (-x1 - cx1) / rx, vy = (-y1 - cy1) / ry, n = Math.sqrt((ux * ux) + (uy * uy)), p = ux; sign = (uy < 0) ? -1 : 1; var angleStart = (sign * Math.acos(p / n)) * _RAD2DEG; n = Math.sqrt((ux * ux + uy * uy) * (vx * vx + vy * vy)); p = ux * vx + uy * vy; sign = (ux * vy - uy * vx < 0) ? -1 : 1; var angleExtent = (sign * Math.acos(p / n)) * _RAD2DEG; if (!sweepFlag && angleExtent > 0) { angleExtent -= 360; } else if (sweepFlag && angleExtent < 0) { angleExtent += 360; } angleExtent %= 360; angleStart %= 360; var bezierPoints = _normalizedArcToBeziers(angleStart, angleExtent), a = cosAngle * rx, b = sinAngle * rx, c = sinAngle * -ry, d = cosAngle * ry, l = bezierPoints.length - 2, i, px, py; //translate all the bezier points according to the matrix... for (i = 0; i < l; i += 2) { px = bezierPoints[i]; py = bezierPoints[i+1]; bezierPoints[i] = px * a + py * c + cx; bezierPoints[i+1] = px * b + py * d + cy; } bezierPoints[bezierPoints.length-2] = x; //always set the end to exactly where it's supposed to be bezierPoints[bezierPoints.length-1] = y; return bezierPoints; }, //Spits back an array of cubic Bezier segments that use absolute coordinates. Each segment starts with a "moveTo" command (x coordinate, then y) and then 2 control points (x, y, x, y), then anchor. The goal is to minimize memory and maximize speed. _pathDataToBezier = function(d) { var a = (d + "").replace(_scientific, function(m) { var n = +m; return (n < 0.0001 && n > -0.0001) ? 0 : n; }).match(_svgPathExp) || [], //some authoring programs spit out very small numbers in scientific notation like "1e-5", so make sure we round that down to 0 first. path = [], relativeX = 0, relativeY = 0, elements = a.length, l = 2, points = 0, i, j, x, y, command, isRelative, segment, startX, startY, difX, difY, beziers, prevCommand; if (!d || !isNaN(a[0]) || isNaN(a[1])) { _log("ERROR: malformed path data: " + d); return path; } for (i = 0; i < elements; i++) { prevCommand = command; if (isNaN(a[i])) { command = a[i].toUpperCase(); isRelative = (command !== a[i]); //lower case means relative } else { //commands like "C" can be strung together without any new command characters between. i--; } x = +a[i+1]; y = +a[i+2]; if (isRelative) { x += relativeX; y += relativeY; } if (i === 0) { startX = x; startY = y; } // "M" (move) if (command === "M") { if (segment && segment.length < 8) { //if the path data was funky and just had a M with no actual drawing anywhere, skip it. path.length-=1; l = 0; } relativeX = startX = x; relativeY = startY = y; segment = [x, y]; points += l; l = 2; path.push(segment); i += 2; command = "L"; //an "M" with more than 2 values gets interpreted as "lineTo" commands ("L"). // "C" (cubic bezier) } else if (command === "C") { if (!segment) { segment = [0, 0]; } segment[l++] = x; segment[l++] = y; if (!isRelative) { relativeX = relativeY = 0; } segment[l++] = relativeX + a[i + 3] * 1; //note: "*1" is just a fast/short way to cast the value as a Number. WAAAY faster in Chrome, slightly slower in Firefox. segment[l++] = relativeY + a[i + 4] * 1; segment[l++] = relativeX = relativeX + a[i + 5] * 1; segment[l++] = relativeY = relativeY + a[i + 6] * 1; //if (y === segment[l-1] && y === segment[l-3] && x === segment[l-2] && x === segment[l-4]) { //if all the values are the same, eliminate the waste. // segment.length = l = l-6; //} i += 6; // "S" (continuation of cubic bezier) } else if (command === "S") { if (prevCommand === "C" || prevCommand === "S") { difX = relativeX - segment[l - 4]; difY = relativeY - segment[l - 3]; segment[l++] = relativeX + difX; segment[l++] = relativeY + difY; } else { segment[l++] = relativeX; segment[l++] = relativeY; } segment[l++] = x; segment[l++] = y; if (!isRelative) { relativeX = relativeY = 0; } segment[l++] = relativeX = relativeX + a[i + 3] * 1; segment[l++] = relativeY = relativeY + a[i + 4] * 1; //if (y === segment[l-1] && y === segment[l-3] && x === segment[l-2] && x === segment[l-4]) { //if all the values are the same, eliminate the waste. // segment.length = l = l-6; //} i += 4; // "Q" (quadratic bezier) } else if (command === "Q") { difX = x - relativeX; difY = y - relativeY; segment[l++] = relativeX + difX * 2 / 3; segment[l++] = relativeY + difY * 2 / 3; if (!isRelative) { relativeX = relativeY = 0; } relativeX = relativeX + a[i + 3] * 1; relativeY = relativeY + a[i + 4] * 1; difX = x - relativeX; difY = y - relativeY; segment[l++] = relativeX + difX * 2 / 3; segment[l++] = relativeY + difY * 2 / 3; segment[l++] = relativeX; segment[l++] = relativeY; i += 4; // "T" (continuation of quadratic bezier) } else if (command === "T") { difX = relativeX - segment[l-4]; difY = relativeY - segment[l-3]; segment[l++] = relativeX + difX; segment[l++] = relativeY + difY; difX = (relativeX + difX * 1.5) - x; difY = (relativeY + difY * 1.5) - y; segment[l++] = x + difX * 2 / 3; segment[l++] = y + difY * 2 / 3; segment[l++] = relativeX = x; segment[l++] = relativeY = y; i += 2; // "H" (horizontal line) } else if (command === "H") { y = relativeY; //if (x !== relativeX) { segment[l++] = relativeX + (x - relativeX) / 3; segment[l++] = relativeY + (y - relativeY) / 3; segment[l++] = relativeX + (x - relativeX) * 2 / 3; segment[l++] = relativeY + (y - relativeY) * 2 / 3; segment[l++] = relativeX = x; segment[l++] = y; //} i += 1; // "V" (horizontal line) } else if (command === "V") { y = x; //adjust values because the first (and only one) isn't x in this case, it's y. x = relativeX; if (isRelative) { y += relativeY - relativeX; } //if (y !== relativeY) { segment[l++] = x; segment[l++] = relativeY + (y - relativeY) / 3; segment[l++] = x; segment[l++] = relativeY + (y - relativeY) * 2 / 3; segment[l++] = x; segment[l++] = relativeY = y; //} i += 1; // "L" (line) or "Z" (close) } else if (command === "L" || command === "Z") { if (command === "Z") { x = startX; y = startY; segment.closed = true; } if (command === "L" || Math.abs(relativeX - x) > 0.5 || Math.abs(relativeY - y) > 0.5) { segment[l++] = relativeX + (x - relativeX) / 3; segment[l++] = relativeY + (y - relativeY) / 3; segment[l++] = relativeX + (x - relativeX) * 2 / 3; segment[l++] = relativeY + (y - relativeY) * 2 / 3; segment[l++] = x; segment[l++] = y; if (command === "L") { i += 2; } } relativeX = x; relativeY = y; // "A" (arc) } else if (command === "A") { beziers = _arcToBeziers(relativeX, relativeY, a[i+1]*1, a[i+2]*1, a[i+3]*1, a[i+4]*1, a[i+5]*1, (isRelative ? relativeX : 0) + a[i+6]*1, (isRelative ? relativeY : 0) + a[i+7]*1); if (beziers) { for (j = 0; j < beziers.length; j++) { segment[l++] = beziers[j]; } } relativeX = segment[l-2]; relativeY = segment[l-1]; i += 7; } else { _log("Error: malformed path data: " + d); } } path.totalPoints = points + l; return path; }, //adds a certain number of Beziers while maintaining the path shape (so that the start/end values can have a matching quantity of points to animate). Only pass in ONE segment of the Bezier at a time. Format: [xAnchor, yAnchor, xControlPoint1, yControlPoint1, xControlPoint2, yControlPoint2, xAnchor, yAnchor, xControlPoint1, etc...] _subdivideBezier = function(bezier, quantity) { var tally = 0, max = 0.999999, l = bezier.length, newPointsPerSegment = quantity / ((l - 2) / 6), ax, ay, cp1x, cp1y, cp2x, cp2y, bx, by, x1, y1, x2, y2, i, t; for (i = 2; i < l; i += 6) { tally += newPointsPerSegment; while (tally > max) { //compare with 0.99999 instead of 1 in order to prevent rounding errors ax = bezier[i-2]; ay = bezier[i-1]; cp1x = bezier[i]; cp1y = bezier[i+1]; cp2x = bezier[i+2]; cp2y = bezier[i+3]; bx = bezier[i+4]; by = bezier[i+5]; t = 1 / (Math.floor(tally) + 1); //progress along the bezier (value between 0 and 1) x1 = ax + (cp1x - ax) * t; x2 = cp1x + (cp2x - cp1x) * t; x1 += (x2 - x1) * t; x2 += ((cp2x + (bx - cp2x) * t) - x2) * t; y1 = ay + (cp1y - ay) * t; y2 = cp1y + (cp2y - cp1y) * t; y1 += (y2 - y1) * t; y2 += ((cp2y + (by - cp2y) * t) - y2) * t; bezier.splice(i, 4, ax + (cp1x - ax) * t, //first control point ay + (cp1y - ay) * t, x1, //second control point y1, x1 + (x2 - x1) * t, //new fabricated anchor on line y1 + (y2 - y1) * t, x2, //third control point y2, cp2x + (bx - cp2x) * t, //fourth control point cp2y + (by - cp2y) * t ); i += 6; l += 6; tally--; } } return bezier; }, _bezierToPathData = function(beziers) { var data = "", l = beziers.length, rnd = 100, sl, s, i, segment; for (s = 0; s < l; s++) { segment = beziers[s]; data += "M" + segment[0] + "," + segment[1] + " C"; sl = segment.length; for (i = 2; i < sl; i++) { data += (((segment[i++] * rnd) | 0) / rnd) + "," + (((segment[i++] * rnd) | 0) / rnd) + " " + (((segment[i++] * rnd) | 0) / rnd) + "," + (((segment[i++] * rnd) | 0) / rnd) + " " + (((segment[i++] * rnd) | 0) / rnd) + "," + (((segment[i] * rnd) | 0) / rnd) + " "; } if (segment.closed) { data += "z"; } } return data; }, _reverseBezier = function(bezier) { var a = [], i = bezier.length - 1, l = 0; while (--i > -1) { a[l++] = bezier[i]; a[l++] = bezier[i+1]; i--; } for (i = 0; i < l; i++) { bezier[i] = a[i]; } bezier.reversed = bezier.reversed ? false : true; }, _getAverageXY = function(bezier) { var l = bezier.length, x = 0, y = 0, i; for (i = 0; i < l; i++) { x += bezier[i++]; y += bezier[i]; } return [x / (l / 2), y / (l / 2)]; }, _getSize = function(bezier) { //rough estimate of the bounding box (based solely on the anchors) of a single segment. sets "size", "centerX", and "centerY" properties on the bezier array itself, and returns the size (width * height) var l = bezier.length, xMax = bezier[0], xMin = xMax, yMax = bezier[1], yMin = yMax, x, y, i; for (i = 6; i < l; i+=6) { x = bezier[i]; y = bezier[i+1]; if (x > xMax) { xMax = x; } else if (x < xMin) { xMin = x; } if (y > yMax) { yMax = y; } else if (y < yMin) { yMin = y; } } bezier.centerX = (xMax + xMin) / 2; bezier.centerY = (yMax + yMin) / 2; return (bezier.size = (xMax - xMin) * (yMax - yMin)); }, _getTotalSize = function(bezier) { //rough estimate of the bounding box of the entire list of Bezier segments (based solely on the anchors). sets "size", "centerX", and "centerY" properties on the bezier array itself, and returns the size (width * height) var segment = bezier.length, xMax = bezier[0][0], xMin = xMax, yMax = bezier[0][1], yMin = yMax, l, x, y, i, b; while (--segment > -1) { b = bezier[segment]; l = b.length; for (i = 6; i < l; i+=6) { x = b[i]; y = b[i+1]; if (x > xMax) { xMax = x; } else if (x < xMin) { xMin = x; } if (y > yMax) { yMax = y; } else if (y < yMin) { yMin = y; } } } bezier.centerX = (xMax + xMin) / 2; bezier.centerY = (yMax + yMin) / 2; return (bezier.size = (xMax - xMin) * (yMax - yMin)); }, _sortByComplexity = function(a, b) { return b.length - a.length; }, _sortBySize = function(a, b) { var sizeA = a.size || _getSize(a), sizeB = b.size || _getSize(b); return (Math.abs(sizeB - sizeA) < (sizeA + sizeB) / 20) ? (b.centerX - a.centerX) || (b.centerY - a.centerY) : sizeB - sizeA; //if the size is within 10% of each other, prioritize position from left to right, then top to bottom. };