123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422 |
- (function() {
-
- if(typeof Math.sgn == "undefined") {
- Math.sgn = function(x) { return x == 0 ? 0 : x > 0 ? 1 :-1; };
- }
-
- var Vectors = {
- subtract : function(v1, v2) { return {x:v1.x - v2.x, y:v1.y - v2.y }; },
- dotProduct : function(v1, v2) { return (v1.x * v2.x) + (v1.y * v2.y); },
- square : function(v) { return Math.sqrt((v.x * v.x) + (v.y * v.y)); },
- scale : function(v, s) { return {x:v.x * s, y:v.y * s }; }
- },
-
- maxRecursion = 64,
- flatnessTolerance = Math.pow(2.0,-maxRecursion-1);
-
- var _distanceFromCurve = function(point, curve) {
- var candidates = [],
- w = _convertToBezier(point, curve),
- degree = curve.length - 1, higherDegree = (2 * degree) - 1,
- numSolutions = _findRoots(w, higherDegree, candidates, 0),
- v = Vectors.subtract(point, curve[0]), dist = Vectors.square(v), t = 0.0;
- for (var i = 0; i < numSolutions; i++) {
- v = Vectors.subtract(point, _bezier(curve, degree, candidates[i], null, null));
- var newDist = Vectors.square(v);
- if (newDist < dist) {
- dist = newDist;
- t = candidates[i];
- }
- }
- v = Vectors.subtract(point, curve[degree]);
- newDist = Vectors.square(v);
- if (newDist < dist) {
- dist = newDist;
- t = 1.0;
- }
- return {location:t, distance:dist};
- };
-
- var _nearestPointOnCurve = function(point, curve) {
- var td = _distanceFromCurve(point, curve);
- return {point:_bezier(curve, curve.length - 1, td.location, null, null), location:td.location};
- };
- var _convertToBezier = function(point, curve) {
- var degree = curve.length - 1, higherDegree = (2 * degree) - 1,
- c = [], d = [], cdTable = [], w = [],
- z = [ [1.0, 0.6, 0.3, 0.1], [0.4, 0.6, 0.6, 0.4], [0.1, 0.3, 0.6, 1.0] ];
-
- for (var i = 0; i <= degree; i++) c[i] = Vectors.subtract(curve[i], point);
- for (var i = 0; i <= degree - 1; i++) {
- d[i] = Vectors.subtract(curve[i+1], curve[i]);
- d[i] = Vectors.scale(d[i], 3.0);
- }
- for (var row = 0; row <= degree - 1; row++) {
- for (var column = 0; column <= degree; column++) {
- if (!cdTable[row]) cdTable[row] = [];
- cdTable[row][column] = Vectors.dotProduct(d[row], c[column]);
- }
- }
- for (i = 0; i <= higherDegree; i++) {
- if (!w[i]) w[i] = [];
- w[i].y = 0.0;
- w[i].x = parseFloat(i) / higherDegree;
- }
- var n = degree, m = degree-1;
- for (var k = 0; k <= n + m; k++) {
- var lb = Math.max(0, k - m),
- ub = Math.min(k, n);
- for (i = lb; i <= ub; i++) {
- j = k - i;
- w[i+j].y += cdTable[j][i] * z[j][i];
- }
- }
- return w;
- };
-
- var _findRoots = function(w, degree, t, depth) {
- var left = [], right = [],
- left_count, right_count,
- left_t = [], right_t = [];
-
- switch (_getCrossingCount(w, degree)) {
- case 0 : {
- return 0;
- }
- case 1 : {
- if (depth >= maxRecursion) {
- t[0] = (w[0].x + w[degree].x) / 2.0;
- return 1;
- }
- if (_isFlatEnough(w, degree)) {
- t[0] = _computeXIntercept(w, degree);
- return 1;
- }
- break;
- }
- }
- _bezier(w, degree, 0.5, left, right);
- left_count = _findRoots(left, degree, left_t, depth+1);
- right_count = _findRoots(right, degree, right_t, depth+1);
- for (var i = 0; i < left_count; i++) t[i] = left_t[i];
- for (var i = 0; i < right_count; i++) t[i+left_count] = right_t[i];
- return (left_count+right_count);
- };
- var _getCrossingCount = function(curve, degree) {
- var n_crossings = 0, sign, old_sign;
- sign = old_sign = Math.sgn(curve[0].y);
- for (var i = 1; i <= degree; i++) {
- sign = Math.sgn(curve[i].y);
- if (sign != old_sign) n_crossings++;
- old_sign = sign;
- }
- return n_crossings;
- };
- var _isFlatEnough = function(curve, degree) {
- var error,
- intercept_1, intercept_2, left_intercept, right_intercept,
- a, b, c, det, dInv, a1, b1, c1, a2, b2, c2;
- a = curve[0].y - curve[degree].y;
- b = curve[degree].x - curve[0].x;
- c = curve[0].x * curve[degree].y - curve[degree].x * curve[0].y;
-
- var max_distance_above = max_distance_below = 0.0;
-
- for (var i = 1; i < degree; i++) {
- var value = a * curve[i].x + b * curve[i].y + c;
- if (value > max_distance_above)
- max_distance_above = value;
- else if (value < max_distance_below)
- max_distance_below = value;
- }
-
- a1 = 0.0; b1 = 1.0; c1 = 0.0; a2 = a; b2 = b;
- c2 = c - max_distance_above;
- det = a1 * b2 - a2 * b1;
- dInv = 1.0/det;
- intercept_1 = (b1 * c2 - b2 * c1) * dInv;
- a2 = a; b2 = b; c2 = c - max_distance_below;
- det = a1 * b2 - a2 * b1;
- dInv = 1.0/det;
- intercept_2 = (b1 * c2 - b2 * c1) * dInv;
- left_intercept = Math.min(intercept_1, intercept_2);
- right_intercept = Math.max(intercept_1, intercept_2);
- error = right_intercept - left_intercept;
- return (error < flatnessTolerance)? 1 : 0;
- };
- var _computeXIntercept = function(curve, degree) {
- var XLK = 1.0, YLK = 0.0,
- XNM = curve[degree].x - curve[0].x, YNM = curve[degree].y - curve[0].y,
- XMK = curve[0].x - 0.0, YMK = curve[0].y - 0.0,
- det = XNM*YLK - YNM*XLK, detInv = 1.0/det,
- S = (XNM*YMK - YNM*XMK) * detInv;
- return 0.0 + XLK * S;
- };
- var _bezier = function(curve, degree, t, left, right) {
- var temp = [[]];
- for (var j =0; j <= degree; j++) temp[0][j] = curve[j];
- for (var i = 1; i <= degree; i++) {
- for (var j =0 ; j <= degree - i; j++) {
- if (!temp[i]) temp[i] = [];
- if (!temp[i][j]) temp[i][j] = {};
- temp[i][j].x = (1.0 - t) * temp[i-1][j].x + t * temp[i-1][j+1].x;
- temp[i][j].y = (1.0 - t) * temp[i-1][j].y + t * temp[i-1][j+1].y;
- }
- }
- if (left != null)
- for (j = 0; j <= degree; j++) left[j] = temp[j][0];
- if (right != null)
- for (j = 0; j <= degree; j++) right[j] = temp[degree-j][j];
-
- return (temp[degree][0]);
- };
-
- var _curveFunctionCache = {};
- var _getCurveFunctions = function(order) {
- var fns = _curveFunctionCache[order];
- if (!fns) {
- fns = [];
- var f_term = function() { return function(t) { return Math.pow(t, order); }; },
- l_term = function() { return function(t) { return Math.pow((1-t), order); }; },
- c_term = function(c) { return function(t) { return c; }; },
- t_term = function() { return function(t) { return t; }; },
- one_minus_t_term = function() { return function(t) { return 1-t; }; },
- _termFunc = function(terms) {
- return function(t) {
- var p = 1;
- for (var i = 0; i < terms.length; i++) p = p * terms[i](t);
- return p;
- };
- };
-
- fns.push(new f_term());
- for (var i = 1; i < order; i++) {
- var terms = [new c_term(order)];
- for (var j = 0 ; j < (order - i); j++) terms.push(new t_term());
- for (var j = 0 ; j < i; j++) terms.push(new one_minus_t_term());
- fns.push(new _termFunc(terms));
- }
- fns.push(new l_term());
-
- _curveFunctionCache[order] = fns;
- }
-
- return fns;
- };
-
-
-
- var _pointOnPath = function(curve, location) {
- var cc = _getCurveFunctions(curve.length - 1),
- _x = 0, _y = 0;
- for (var i = 0; i < curve.length ; i++) {
- _x = _x + (curve[i].x * cc[i](location));
- _y = _y + (curve[i].y * cc[i](location));
- }
-
- return {x:_x, y:_y};
- };
-
- var _dist = function(p1,p2) {
- return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
- };
- var _isPoint = function(curve) {
- return curve[0].x == curve[1].x && curve[0].y == curve[1].y;
- };
-
-
- var _pointAlongPath = function(curve, location, distance) {
- if (_isPoint(curve)) {
- return {
- point:curve[0],
- location:location
- };
- }
- var prev = _pointOnPath(curve, location),
- tally = 0,
- curLoc = location,
- direction = distance > 0 ? 1 : -1,
- cur = null;
-
- while (tally < Math.abs(distance)) {
- curLoc += (0.005 * direction);
- cur = _pointOnPath(curve, curLoc);
- tally += _dist(cur, prev);
- prev = cur;
- }
- return {point:cur, location:curLoc};
- };
-
- var _length = function(curve) {
- if (_isPoint(curve)) return 0;
- var prev = _pointOnPath(curve, 0),
- tally = 0,
- curLoc = 0,
- direction = 1,
- cur = null;
-
- while (curLoc < 1) {
- curLoc += (0.005 * direction);
- cur = _pointOnPath(curve, curLoc);
- tally += _dist(cur, prev);
- prev = cur;
- }
- return tally;
- };
-
-
- var _pointAlongPathFrom = function(curve, location, distance) {
- return _pointAlongPath(curve, location, distance).point;
- };
-
- var _locationAlongPathFrom = function(curve, location, distance) {
- return _pointAlongPath(curve, location, distance).location;
- };
-
-
- var _gradientAtPoint = function(curve, location) {
- var p1 = _pointOnPath(curve, location),
- p2 = _pointOnPath(curve.slice(0, curve.length - 1), location),
- dy = p2.y - p1.y, dx = p2.x - p1.x;
- return dy == 0 ? Infinity : Math.atan(dy / dx);
- };
-
-
- var _gradientAtPointAlongPathFrom = function(curve, location, distance) {
- var p = _pointAlongPath(curve, location, distance);
- if (p.location > 1) p.location = 1;
- if (p.location < 0) p.location = 0;
- return _gradientAtPoint(curve, p.location);
- };
-
- var _perpendicularToPathAt = function(curve, location, length, distance) {
- distance = distance == null ? 0 : distance;
- var p = _pointAlongPath(curve, location, distance),
- m = _gradientAtPoint(curve, p.location),
- _theta2 = Math.atan(-1 / m),
- y = length / 2 * Math.sin(_theta2),
- x = length / 2 * Math.cos(_theta2);
- return [{x:p.point.x + x, y:p.point.y + y}, {x:p.point.x - x, y:p.point.y - y}];
- };
-
- var jsBezier = window.jsBezier = {
- distanceFromCurve : _distanceFromCurve,
- gradientAtPoint : _gradientAtPoint,
- gradientAtPointAlongCurveFrom : _gradientAtPointAlongPathFrom,
- nearestPointOnCurve : _nearestPointOnCurve,
- pointOnCurve : _pointOnPath,
- pointAlongCurveFrom : _pointAlongPathFrom,
- perpendicularToCurveAt : _perpendicularToPathAt,
- locationAlongCurveFrom:_locationAlongPathFrom,
- getLength:_length
- };
- })();
|