portal/static/unbound_reservation_static/lib/jsBezier-0.6.js

   1 /**
   2 * jsBezier-0.6
   3 *
   4 * Copyright (c) 2010 - 2013 Simon Porritt (simon.porritt@gmail.com)
   5 *
   6 * licensed under the MIT license.
   7 *
   8 * a set of Bezier curve functions that deal with Beziers, used by jsPlumb, and perhaps useful for other people.  These functions work with Bezier
   9 * curves of arbitrary degree.
  10 *
  11 * - functions are all in the 'jsBezier' namespace.
  12 *
  13 * - all input points should be in the format {x:.., y:..}. all output points are in this format too.
  14 *
  15 * - all input curves should be in the format [ {x:.., y:..}, {x:.., y:..}, {x:.., y:..}, {x:.., y:..} ]
  16 *
  17 * - 'location' as used as an input here refers to a decimal in the range 0-1 inclusive, which indicates a point some proportion along the length
  18 * of the curve.  location as output has the same format and meaning.
  19 *
  20 *
  21 * Function List:
  22 * --------------
  23 *
  24 * distanceFromCurve(point, curve)
  25 *
  26 *       Calculates the distance that the given point lies from the given Bezier.  Note that it is computed relative to the center of the Bezier,
  27 * so if you have stroked the curve with a wide pen you may wish to take that into account!  The distance returned is relative to the values
  28 * of the curve and the point - it will most likely be pixels.
  29 *
  30 * gradientAtPoint(curve, location)
  31 *
  32 *       Calculates the gradient to the curve at the given location, as a decimal between 0 and 1 inclusive.
  33 *
  34 * gradientAtPointAlongCurveFrom (curve, location)
  35 *
  36 *       Calculates the gradient at the point on the given curve that is 'distance' units from location.
  37 *
  38 * nearestPointOnCurve(point, curve)
  39 *
  40 *       Calculates the nearest point to the given point on the given curve.  The return value of this is a JS object literal, containing both the
  41 *point's coordinates and also the 'location' of the point (see above), for example:  { point:{x:551,y:150}, location:0.263365 }.
  42 *
  43 * pointOnCurve(curve, location)
  44 *
  45 *       Calculates the coordinates of the point on the given Bezier curve at the given location.
  46 *
  47 * pointAlongCurveFrom(curve, location, distance)
  48 *
  49 *       Calculates the coordinates of the point on the given curve that is 'distance' units from location.  'distance' should be in the same coordinate
  50 * space as that used to construct the Bezier curve.  For an HTML Canvas usage, for example, distance would be a measure of pixels.
  51 *
  52 * locationAlongCurveFrom(curve, location, distance)
  53 *
  54 *       Calculates the location on the given curve that is 'distance' units from location.  'distance' should be in the same coordinate
  55 * space as that used to construct the Bezier curve.  For an HTML Canvas usage, for example, distance would be a measure of pixels.
  56 *
  57 * perpendicularToCurveAt(curve, location, length, distance)
  58 *
  59 *       Calculates the perpendicular to the given curve at the given location.  length is the length of the line you wish for (it will be centered
  60 * on the point at 'location'). distance is optional, and allows you to specify a point along the path from the given location as the center of
  61 * the perpendicular returned.  The return value of this is an array of two points: [ {x:...,y:...}, {x:...,y:...} ].
  62 *
  63 *
  64 */
  65
  66 (function() {
  67
  68         if(typeof Math.sgn == "undefined") {
  69                 Math.sgn = function(x) { return x == 0 ? 0 : x > 0 ? 1 :-1; };
  70         }
  71
  72         var Vectors = {
  73                         subtract        :       function(v1, v2) { return {x:v1.x - v2.x, y:v1.y - v2.y }; },
  74                         dotProduct      :       function(v1, v2) { return (v1.x * v2.x)  + (v1.y * v2.y); },
  75                         square          :       function(v) { return Math.sqrt((v.x * v.x) + (v.y * v.y)); },
  76                         scale           :       function(v, s) { return {x:v.x * s, y:v.y * s }; }
  77                 },
  78
  79                 maxRecursion = 64,
  80                 flatnessTolerance = Math.pow(2.0,-maxRecursion-1);
  81
  82         /**
  83          * Calculates the distance that the point lies from the curve.
  84          *
  85          * @param point a point in the form {x:567, y:3342}
  86          * @param curve a Bezier curve in the form [{x:..., y:...}, {x:..., y:...}, {x:..., y:...}, {x:..., y:...}].  note that this is currently
  87          * hardcoded to assume cubiz beziers, but would be better off supporting any degree.
  88          * @return a JS object literal containing location and distance, for example: {location:0.35, distance:10}.  Location is analogous to the location
  89          * argument you pass to the pointOnPath function: it is a ratio of distance travelled along the curve.  Distance is the distance in pixels from
  90          * the point to the curve.
  91          */
  92         var _distanceFromCurve = function(point, curve) {
  93                 var candidates = [],
  94                 w = _convertToBezier(point, curve),
  95                 degree = curve.length - 1, higherDegree = (2 * degree) - 1,
  96                 numSolutions = _findRoots(w, higherDegree, candidates, 0),
  97                         v = Vectors.subtract(point, curve[0]), dist = Vectors.square(v), t = 0.0;
  98
  99             for (var i = 0; i < numSolutions; i++) {
 100                         v = Vectors.subtract(point, _bezier(curve, degree, candidates[i], null, null));
 101                 var newDist = Vectors.square(v);
 102                 if (newDist < dist) {
 103                     dist = newDist;
 104                         t = candidates[i];
 105                     }
 106             }
 107             v = Vectors.subtract(point, curve[degree]);
 108                 newDist = Vectors.square(v);
 109             if (newDist < dist) {
 110                 dist = newDist;
 111                 t = 1.0;
 112             }
 113                 return {location:t, distance:dist};
 114         };
 115         /**
 116          * finds the nearest point on the curve to the given point.
 117          */
 118         var _nearestPointOnCurve = function(point, curve) {
 119                 var td = _distanceFromCurve(point, curve);
 120             return {point:_bezier(curve, curve.length - 1, td.location, null, null), location:td.location};
 121         };
 122         var _convertToBezier = function(point, curve) {
 123                 var degree = curve.length - 1, higherDegree = (2 * degree) - 1,
 124                 c = [], d = [], cdTable = [], w = [],
 125                 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] ];
 126
 127             for (var i = 0; i <= degree; i++) c[i] = Vectors.subtract(curve[i], point);
 128             for (var i = 0; i <= degree - 1; i++) {
 129                         d[i] = Vectors.subtract(curve[i+1], curve[i]);
 130                         d[i] = Vectors.scale(d[i], 3.0);
 131             }
 132             for (var row = 0; row <= degree - 1; row++) {
 133                         for (var column = 0; column <= degree; column++) {
 134                                 if (!cdTable[row]) cdTable[row] = [];
 135                         cdTable[row][column] = Vectors.dotProduct(d[row], c[column]);
 136                         }
 137             }
 138             for (i = 0; i <= higherDegree; i++) {
 139                         if (!w[i]) w[i] = [];
 140                         w[i].y = 0.0;
 141                         w[i].x = parseFloat(i) / higherDegree;
 142             }
 143             var n = degree, m = degree-1;
 144             for (var k = 0; k <= n + m; k++) {
 145                         var lb = Math.max(0, k - m),
 146                                 ub = Math.min(k, n);
 147                         for (i = lb; i <= ub; i++) {
 148                         j = k - i;
 149                         w[i+j].y += cdTable[j][i] * z[j][i];
 150                         }
 151             }
 152             return w;
 153         };
 154         /**
 155          * counts how many roots there are.
 156          */
 157         var _findRoots = function(w, degree, t, depth) {
 158             var left = [], right = [],
 159                 left_count, right_count,
 160                 left_t = [], right_t = [];
 161
 162             switch (_getCrossingCount(w, degree)) {
 163                 case 0 : {
 164                         return 0;
 165                 }
 166                 case 1 : {
 167                         if (depth >= maxRecursion) {
 168                                 t[0] = (w[0].x + w[degree].x) / 2.0;
 169                                 return 1;
 170                         }
 171                         if (_isFlatEnough(w, degree)) {
 172                                 t[0] = _computeXIntercept(w, degree);
 173                                 return 1;
 174                         }
 175                         break;
 176                 }
 177             }
 178             _bezier(w, degree, 0.5, left, right);
 179             left_count  = _findRoots(left,  degree, left_t, depth+1);
 180             right_count = _findRoots(right, degree, right_t, depth+1);
 181             for (var i = 0; i < left_count; i++) t[i] = left_t[i];
 182             for (var i = 0; i < right_count; i++) t[i+left_count] = right_t[i];
 183                 return (left_count+right_count);
 184         };
 185         var _getCrossingCount = function(curve, degree) {
 186             var n_crossings = 0, sign, old_sign;
 187             sign = old_sign = Math.sgn(curve[0].y);
 188             for (var i = 1; i <= degree; i++) {
 189                         sign = Math.sgn(curve[i].y);
 190                         if (sign != old_sign) n_crossings++;
 191                         old_sign = sign;
 192             }
 193             return n_crossings;
 194         };
 195         var _isFlatEnough = function(curve, degree) {
 196             var  error,
 197                 intercept_1, intercept_2, left_intercept, right_intercept,
 198                 a, b, c, det, dInv, a1, b1, c1, a2, b2, c2;
 199             a = curve[0].y - curve[degree].y;
 200             b = curve[degree].x - curve[0].x;
 201             c = curve[0].x * curve[degree].y - curve[degree].x * curve[0].y;
 202
 203             var max_distance_above = max_distance_below = 0.0;
 204
 205             for (var i = 1; i < degree; i++) {
 206                 var value = a * curve[i].x + b * curve[i].y + c;
 207                 if (value > max_distance_above)
 208                     max_distance_above = value;
 209                 else if (value < max_distance_below)
 210                         max_distance_below = value;
 211             }
 212
 213             a1 = 0.0; b1 = 1.0; c1 = 0.0; a2 = a; b2 = b;
 214             c2 = c - max_distance_above;
 215             det = a1 * b2 - a2 * b1;
 216             dInv = 1.0/det;
 217             intercept_1 = (b1 * c2 - b2 * c1) * dInv;
 218             a2 = a; b2 = b; c2 = c - max_distance_below;
 219             det = a1 * b2 - a2 * b1;
 220             dInv = 1.0/det;
 221             intercept_2 = (b1 * c2 - b2 * c1) * dInv;
 222             left_intercept = Math.min(intercept_1, intercept_2);
 223             right_intercept = Math.max(intercept_1, intercept_2);
 224             error = right_intercept - left_intercept;
 225             return (error < flatnessTolerance)? 1 : 0;
 226         };
 227         var _computeXIntercept = function(curve, degree) {
 228             var XLK = 1.0, YLK = 0.0,
 229                 XNM = curve[degree].x - curve[0].x, YNM = curve[degree].y - curve[0].y,
 230                 XMK = curve[0].x - 0.0, YMK = curve[0].y - 0.0,
 231                 det = XNM*YLK - YNM*XLK, detInv = 1.0/det,
 232                 S = (XNM*YMK - YNM*XMK) * detInv;
 233             return 0.0 + XLK * S;
 234         };
 235         var _bezier = function(curve, degree, t, left, right) {
 236             var temp = [[]];
 237             for (var j =0; j <= degree; j++) temp[0][j] = curve[j];
 238             for (var i = 1; i <= degree; i++) {
 239                         for (var j =0 ; j <= degree - i; j++) {
 240                                 if (!temp[i]) temp[i] = [];
 241                                 if (!temp[i][j]) temp[i][j] = {};
 242                         temp[i][j].x = (1.0 - t) * temp[i-1][j].x + t * temp[i-1][j+1].x;
 243                         temp[i][j].y = (1.0 - t) * temp[i-1][j].y + t * temp[i-1][j+1].y;
 244                         }
 245             }
 246             if (left != null)
 247                 for (j = 0; j <= degree; j++) left[j]  = temp[j][0];
 248             if (right != null)
 249                         for (j = 0; j <= degree; j++) right[j] = temp[degree-j][j];
 250
 251             return (temp[degree][0]);
 252         };
 253
 254         var _curveFunctionCache = {};
 255         var _getCurveFunctions = function(order) {
 256                 var fns = _curveFunctionCache[order];
 257                 if (!fns) {
 258                         fns = [];
 259                         var f_term = function() { return function(t) { return Math.pow(t, order); }; },
 260                                 l_term = function() { return function(t) { return Math.pow((1-t), order); }; },
 261                                 c_term = function(c) { return function(t) { return c; }; },
 262                                 t_term = function() { return function(t) { return t; }; },
 263                                 one_minus_t_term = function() { return function(t) { return 1-t; }; },
 264                                 _termFunc = function(terms) {
 265                                         return function(t) {
 266                                                 var p = 1;
 267                                                 for (var i = 0; i < terms.length; i++) p = p * terms[i](t);
 268                                                 return p;
 269                                         };
 270                                 };
 271
 272                         fns.push(new f_term());  // first is t to the power of the curve order
 273                         for (var i = 1; i < order; i++) {
 274                                 var terms = [new c_term(order)];
 275                                 for (var j = 0 ; j < (order - i); j++) terms.push(new t_term());
 276                                 for (var j = 0 ; j < i; j++) terms.push(new one_minus_t_term());
 277                                 fns.push(new _termFunc(terms));
 278                         }
 279                         fns.push(new l_term());  // last is (1-t) to the power of the curve order
 280
 281                         _curveFunctionCache[order] = fns;
 282                 }
 283
 284                 return fns;
 285         };
 286
 287
 288         /**
 289          * calculates a point on the curve, for a Bezier of arbitrary order.
 290          * @param curve an array of control points, eg [{x:10,y:20}, {x:50,y:50}, {x:100,y:100}, {x:120,y:100}].  For a cubic bezier this should have four points.
 291          * @param location a decimal indicating the distance along the curve the point should be located at.  this is the distance along the curve as it travels, taking the way it bends into account.  should be a number from 0 to 1, inclusive.
 292          */
 293         var _pointOnPath = function(curve, location) {
 294                 var cc = _getCurveFunctions(curve.length - 1),
 295                         _x = 0, _y = 0;
 296                 for (var i = 0; i < curve.length ; i++) {
 297                         _x = _x + (curve[i].x * cc[i](location));
 298                         _y = _y + (curve[i].y * cc[i](location));
 299                 }
 300
 301                 return {x:_x, y:_y};
 302         };
 303
 304         var _dist = function(p1,p2) {
 305                 return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
 306         };
 307
 308         var _isPoint = function(curve) {
 309                 return curve[0].x == curve[1].x && curve[0].y == curve[1].y;
 310         };
 311
 312         /**
 313          * finds the point that is 'distance' along the path from 'location'.  this method returns both the x,y location of the point and also
 314          * its 'location' (proportion of travel along the path); the method below - _pointAlongPathFrom - calls this method and just returns the
 315          * point.
 316          */
 317         var _pointAlongPath = function(curve, location, distance) {
 318
 319                 if (_isPoint(curve)) {
 320                         return {
 321                                 point:curve[0],
 322                                 location:location
 323                         };
 324                 }
 325
 326                 var prev = _pointOnPath(curve, location),
 327                         tally = 0,
 328                         curLoc = location,
 329                         direction = distance > 0 ? 1 : -1,
 330                         cur = null;
 331
 332                 while (tally < Math.abs(distance)) {
 333                         curLoc += (0.005 * direction);
 334                         cur = _pointOnPath(curve, curLoc);
 335                         tally += _dist(cur, prev);
 336                         prev = cur;
 337                 }
 338                 return {point:cur, location:curLoc};
 339         };
 340
 341         var _length = function(curve) {
 342                 if (_isPoint(curve)) return 0;
 343
 344                 var prev = _pointOnPath(curve, 0),
 345                         tally = 0,
 346                         curLoc = 0,
 347                         direction = 1,
 348                         cur = null;
 349
 350                 while (curLoc < 1) {
 351                         curLoc += (0.005 * direction);
 352                         cur = _pointOnPath(curve, curLoc);
 353                         tally += _dist(cur, prev);
 354                         prev = cur;
 355                 }
 356                 return tally;
 357         };
 358
 359         /**
 360          * finds the point that is 'distance' along the path from 'location'.
 361          */
 362         var _pointAlongPathFrom = function(curve, location, distance) {
 363                 return _pointAlongPath(curve, location, distance).point;
 364         };
 365
 366         /**
 367          * finds the location that is 'distance' along the path from 'location'.
 368          */
 369         var _locationAlongPathFrom = function(curve, location, distance) {
 370                 return _pointAlongPath(curve, location, distance).location;
 371         };
 372
 373         /**
 374          * returns the gradient of the curve at the given location, which is a decimal between 0 and 1 inclusive.
 375          *
 376          * thanks // http://bimixual.org/AnimationLibrary/beziertangents.html
 377          */
 378         var _gradientAtPoint = function(curve, location) {
 379                 var p1 = _pointOnPath(curve, location),
 380                         p2 = _pointOnPath(curve.slice(0, curve.length - 1), location),
 381                         dy = p2.y - p1.y, dx = p2.x - p1.x;
 382                 return dy == 0 ? Infinity : Math.atan(dy / dx);
 383         };
 384
 385         /**
 386         returns the gradient of the curve at the point which is 'distance' from the given location.
 387         if this point is greater than location 1, the gradient at location 1 is returned.
 388         if this point is less than location 0, the gradient at location 0 is returned.
 389         */
 390         var _gradientAtPointAlongPathFrom = function(curve, location, distance) {
 391                 var p = _pointAlongPath(curve, location, distance);
 392                 if (p.location > 1) p.location = 1;
 393                 if (p.location < 0) p.location = 0;
 394                 return _gradientAtPoint(curve, p.location);
 395         };
 396
 397         /**
 398          * calculates a line that is 'length' pixels long, perpendicular to, and centered on, the path at 'distance' pixels from the given location.
 399          * if distance is not supplied, the perpendicular for the given location is computed (ie. we set distance to zero).
 400          */
 401         var _perpendicularToPathAt = function(curve, location, length, distance) {
 402                 distance = distance == null ? 0 : distance;
 403                 var p = _pointAlongPath(curve, location, distance),
 404                         m = _gradientAtPoint(curve, p.location),
 405                         _theta2 = Math.atan(-1 / m),
 406                         y =  length / 2 * Math.sin(_theta2),
 407                         x =  length / 2 * Math.cos(_theta2);
 408                 return [{x:p.point.x + x, y:p.point.y + y}, {x:p.point.x - x, y:p.point.y - y}];
 409         };
 410
 411         var jsBezier = window.jsBezier = {
 412                 distanceFromCurve : _distanceFromCurve,
 413                 gradientAtPoint : _gradientAtPoint,
 414                 gradientAtPointAlongCurveFrom : _gradientAtPointAlongPathFrom,
 415                 nearestPointOnCurve : _nearestPointOnCurve,
 416                 pointOnCurve : _pointOnPath,
 417                 pointAlongCurveFrom : _pointAlongPathFrom,
 418                 perpendicularToCurveAt : _perpendicularToPathAt,
 419                 locationAlongCurveFrom:_locationAlongPathFrom,
 420                 getLength:_length
 421         };
 422 })();