groupbasedpolicy-old-ui/module/src/main/resources/gbp-old/js/geometry.js

   1 /*! JointJS v0.9.3 - JavaScript diagramming library  2015-05-22
   2
   3
   4 This Source Code Form is subject to the terms of the Mozilla Public
   5 License, v. 2.0. If a copy of the MPL was not distributed with this
   6 file, You can obtain one at http://mozilla.org/MPL/2.0/.
   7  */
   8 //      Geometry library.
   9 //      (c) 2011-2013 client IO
  10
  11 (function(root, factory) {
  12
  13     if (typeof define === 'function' && define.amd) {
  14
  15         // AMD. Register as an anonymous module.
  16         define([], factory);
  17
  18     } else if (typeof exports === 'object') {
  19
  20         // Node. Does not work with strict CommonJS, but
  21         // only CommonJS-like environments that support module.exports,
  22         // like Node.
  23         module.exports = factory();
  24
  25     } else {
  26
  27         // Browser globals.
  28         root.g = factory();
  29
  30     }
  31
  32 }(this, function() {
  33
  34     // Declare shorthands to the most used math functions.
  35     var math = Math;
  36     var abs = math.abs;
  37     var cos = math.cos;
  38     var sin = math.sin;
  39     var sqrt = math.sqrt;
  40     var mmin = math.min;
  41     var mmax = math.max;
  42     var atan = math.atan;
  43     var atan2 = math.atan2;
  44     var acos = math.acos;
  45     var round = math.round;
  46     var floor = math.floor;
  47     var PI = math.PI;
  48     var random = math.random;
  49     var toDeg = function(rad) { return (180 * rad / PI) % 360; };
  50     var toRad = function(deg, over360) {
  51         over360 = over360 || false;
  52         deg = over360 ? deg : (deg % 360);
  53         return deg * PI / 180;
  54     };
  55     var snapToGrid = function(val, gridSize) { return gridSize * Math.round(val / gridSize); };
  56     var normalizeAngle = function(angle) { return (angle % 360) + (angle < 0 ? 360 : 0); };
  57
  58     // Point
  59     // -----
  60
  61     // Point is the most basic object consisting of x/y coordinate,.
  62
  63     // Possible instantiations are:
  64
  65     // * `point(10, 20)`
  66     // * `new point(10, 20)`
  67     // * `point('10 20')`
  68     // * `point(point(10, 20))`
  69     function point(x, y) {
  70         if (!(this instanceof point))
  71             return new point(x, y);
  72         var xy;
  73         if (y === undefined && Object(x) !== x) {
  74             xy = x.split(x.indexOf('@') === -1 ? ' ' : '@');
  75             this.x = parseInt(xy[0], 10);
  76             this.y = parseInt(xy[1], 10);
  77         } else if (Object(x) === x) {
  78             this.x = x.x;
  79             this.y = x.y;
  80         } else {
  81             this.x = x;
  82             this.y = y;
  83         }
  84     }
  85
  86     point.prototype = {
  87         toString: function() {
  88             return this.x + '@' + this.y;
  89         },
  90         // If point lies outside rectangle `r`, return the nearest point on the boundary of rect `r`,
  91         // otherwise return point itself.
  92         // (see Squeak Smalltalk, Point>>adhereTo:)
  93         adhereToRect: function(r) {
  94             if (r.containsPoint(this)) {
  95                 return this;
  96             }
  97             this.x = mmin(mmax(this.x, r.x), r.x + r.width);
  98             this.y = mmin(mmax(this.y, r.y), r.y + r.height);
  99             return this;
 100         },
 101         // Compute the angle between me and `p` and the x axis.
 102         // (cartesian-to-polar coordinates conversion)
 103         // Return theta angle in degrees.
 104         theta: function(p) {
 105             p = point(p);
 106             // Invert the y-axis.
 107             var y = -(p.y - this.y);
 108             var x = p.x - this.x;
 109             // Makes sure that the comparison with zero takes rounding errors into account.
 110             var PRECISION = 10;
 111             // Note that `atan2` is not defined for `x`, `y` both equal zero.
 112             var rad = (y.toFixed(PRECISION) == 0 && x.toFixed(PRECISION) == 0) ? 0 : atan2(y, x);
 113
 114             // Correction for III. and IV. quadrant.
 115             if (rad < 0) {
 116                 rad = 2 * PI + rad;
 117             }
 118             return 180 * rad / PI;
 119         },
 120         // Returns distance between me and point `p`.
 121         distance: function(p) {
 122             return line(this, p).length();
 123         },
 124         // Returns a manhattan (taxi-cab) distance between me and point `p`.
 125         manhattanDistance: function(p) {
 126             return abs(p.x - this.x) + abs(p.y - this.y);
 127         },
 128         // Offset me by the specified amount.
 129         offset: function(dx, dy) {
 130             this.x += dx || 0;
 131             this.y += dy || 0;
 132             return this;
 133         },
 134         magnitude: function() {
 135             return sqrt((this.x * this.x) + (this.y * this.y)) || 0.01;
 136         },
 137         update: function(x, y) {
 138             this.x = x || 0;
 139             this.y = y || 0;
 140             return this;
 141         },
 142         round: function(decimals) {
 143             this.x = decimals ? this.x.toFixed(decimals) : round(this.x);
 144             this.y = decimals ? this.y.toFixed(decimals) : round(this.y);
 145             return this;
 146         },
 147         // Scale the line segment between (0,0) and me to have a length of len.
 148         normalize: function(len) {
 149             var s = (len || 1) / this.magnitude();
 150             this.x = s * this.x;
 151             this.y = s * this.y;
 152             return this;
 153         },
 154         difference: function(p) {
 155             return point(this.x - p.x, this.y - p.y);
 156         },
 157         // Return the bearing between me and point `p`.
 158         bearing: function(p) {
 159             return line(this, p).bearing();
 160         },
 161         // Converts rectangular to polar coordinates.
 162         // An origin can be specified, otherwise it's 0@0.
 163         toPolar: function(o) {
 164             o = (o && point(o)) || point(0, 0);
 165             var x = this.x;
 166             var y = this.y;
 167             this.x = sqrt((x - o.x) * (x - o.x) + (y - o.y) * (y - o.y)); // r
 168             this.y = toRad(o.theta(point(x, y)));
 169             return this;
 170         },
 171         // Rotate point by angle around origin o.
 172         rotate: function(o, angle) {
 173             angle = (angle + 360) % 360;
 174             this.toPolar(o);
 175             this.y += toRad(angle);
 176             var p = point.fromPolar(this.x, this.y, o);
 177             this.x = p.x;
 178             this.y = p.y;
 179             return this;
 180         },
 181         // Move point on line starting from ref ending at me by
 182         // distance distance.
 183         move: function(ref, distance) {
 184             var theta = toRad(point(ref).theta(this));
 185             return this.offset(cos(theta) * distance, -sin(theta) * distance);
 186         },
 187         // Returns change in angle from my previous position (-dx, -dy) to my new position
 188         // relative to ref point.
 189         changeInAngle: function(dx, dy, ref) {
 190             // Revert the translation and measure the change in angle around x-axis.
 191             return point(this).offset(-dx, -dy).theta(ref) - this.theta(ref);
 192         },
 193         equals: function(p) {
 194             return this.x === p.x && this.y === p.y;
 195         },
 196         snapToGrid: function(gx, gy) {
 197             this.x = snapToGrid(this.x, gx);
 198             this.y = snapToGrid(this.y, gy || gx);
 199             return this;
 200         },
 201         // Returns a point that is the reflection of me with
 202         // the center of inversion in ref point.
 203         reflection: function(ref) {
 204             return point(ref).move(this, this.distance(ref));
 205         }
 206     };
 207     // Alternative constructor, from polar coordinates.
 208     // @param {number} r Distance.
 209     // @param {number} angle Angle in radians.
 210     // @param {point} [optional] o Origin.
 211     point.fromPolar = function(r, angle, o) {
 212         o = (o && point(o)) || point(0, 0);
 213         var x = abs(r * cos(angle));
 214         var y = abs(r * sin(angle));
 215         var deg = normalizeAngle(toDeg(angle));
 216
 217         if (deg < 90) {
 218             y = -y;
 219         } else if (deg < 180) {
 220             x = -x;
 221             y = -y;
 222         } else if (deg < 270) {
 223             x = -x;
 224         }
 225
 226         return point(o.x + x, o.y + y);
 227     };
 228
 229     // Create a point with random coordinates that fall into the range `[x1, x2]` and `[y1, y2]`.
 230     point.random = function(x1, x2, y1, y2) {
 231         return point(floor(random() * (x2 - x1 + 1) + x1), floor(random() * (y2 - y1 + 1) + y1));
 232     };
 233
 234     // Line.
 235     // -----
 236     function line(p1, p2) {
 237         if (!(this instanceof line))
 238             return new line(p1, p2);
 239         this.start = point(p1);
 240         this.end = point(p2);
 241     }
 242
 243     line.prototype = {
 244         toString: function() {
 245             return this.start.toString() + ' ' + this.end.toString();
 246         },
 247         // @return {double} length of the line
 248         length: function() {
 249             return sqrt(this.squaredLength());
 250         },
 251         // @return {integer} length without sqrt
 252         // @note for applications where the exact length is not necessary (e.g. compare only)
 253         squaredLength: function() {
 254             var x0 = this.start.x;
 255             var y0 = this.start.y;
 256             var x1 = this.end.x;
 257             var y1 = this.end.y;
 258             return (x0 -= x1) * x0 + (y0 -= y1) * y0;
 259         },
 260         // @return {point} my midpoint
 261         midpoint: function() {
 262             return point((this.start.x + this.end.x) / 2,
 263                          (this.start.y + this.end.y) / 2);
 264         },
 265         // @return {point} Point where I'm intersecting l.
 266         // @see Squeak Smalltalk, LineSegment>>intersectionWith:
 267         intersection: function(l) {
 268             var pt1Dir = point(this.end.x - this.start.x, this.end.y - this.start.y);
 269             var pt2Dir = point(l.end.x - l.start.x, l.end.y - l.start.y);
 270             var det = (pt1Dir.x * pt2Dir.y) - (pt1Dir.y * pt2Dir.x);
 271             var deltaPt = point(l.start.x - this.start.x, l.start.y - this.start.y);
 272             var alpha = (deltaPt.x * pt2Dir.y) - (deltaPt.y * pt2Dir.x);
 273             var beta = (deltaPt.x * pt1Dir.y) - (deltaPt.y * pt1Dir.x);
 274
 275             if (det === 0 ||
 276                 alpha * det < 0 ||
 277                 beta * det < 0) {
 278                 // No intersection found.
 279                 return null;
 280             }
 281             if (det > 0) {
 282                 if (alpha > det || beta > det) {
 283                     return null;
 284                 }
 285             } else {
 286                 if (alpha < det || beta < det) {
 287                     return null;
 288                 }
 289             }
 290             return point(this.start.x + (alpha * pt1Dir.x / det),
 291                          this.start.y + (alpha * pt1Dir.y / det));
 292         },
 293
 294         // @return the bearing (cardinal direction) of the line. For example N, W, or SE.
 295         // @returns {String} One of the following bearings : NE, E, SE, S, SW, W, NW, N.
 296         bearing: function() {
 297
 298             var lat1 = toRad(this.start.y);
 299             var lat2 = toRad(this.end.y);
 300             var lon1 = this.start.x;
 301             var lon2 = this.end.x;
 302             var dLon = toRad(lon2 - lon1);
 303             var y = sin(dLon) * cos(lat2);
 304             var x = cos(lat1) * sin(lat2) - sin(lat1) * cos(lat2) * cos(dLon);
 305             var brng = toDeg(atan2(y, x));
 306
 307             var bearings = ['NE', 'E', 'SE', 'S', 'SW', 'W', 'NW', 'N'];
 308
 309             var index = brng - 22.5;
 310             if (index < 0)
 311                 index += 360;
 312             index = parseInt(index / 45);
 313
 314             return bearings[index];
 315         },
 316
 317         // @return {point} my point at 't' <0,1>
 318         pointAt: function(t) {
 319             var x = (1 - t) * this.start.x + t * this.end.x;
 320             var y = (1 - t) * this.start.y + t * this.end.y;
 321             return point(x, y);
 322         },
 323
 324         // @return {number} the offset of the point `p` from the line. + if the point `p` is on the right side of the line, - if on the left and 0 if on the line.
 325         pointOffset: function(p) {
 326             // Find the sign of the determinant of vectors (start,end), where p is the query point.
 327             return ((this.end.x - this.start.x) * (p.y - this.start.y) - (this.end.y - this.start.y) * (p.x - this.start.x)) / 2;
 328         }
 329     };
 330
 331     // Rectangle.
 332     // ----------
 333     function rect(x, y, w, h) {
 334         if (!(this instanceof rect))
 335             return new rect(x, y, w, h);
 336         if (y === undefined) {
 337             y = x.y;
 338             w = x.width;
 339             h = x.height;
 340             x = x.x;
 341         }
 342         this.x = x;
 343         this.y = y;
 344         this.width = w;
 345         this.height = h;
 346     }
 347
 348     rect.prototype = {
 349         toString: function() {
 350             return this.origin().toString() + ' ' + this.corner().toString();
 351         },
 352         origin: function() {
 353             return point(this.x, this.y);
 354         },
 355         corner: function() {
 356             return point(this.x + this.width, this.y + this.height);
 357         },
 358         topRight: function() {
 359             return point(this.x + this.width, this.y);
 360         },
 361         bottomLeft: function() {
 362             return point(this.x, this.y + this.height);
 363         },
 364         center: function() {
 365             return point(this.x + this.width / 2, this.y + this.height / 2);
 366         },
 367         // @return {boolean} true if rectangles intersect
 368         intersect: function(r) {
 369             var myOrigin = this.origin();
 370             var myCorner = this.corner();
 371             var rOrigin = r.origin();
 372             var rCorner = r.corner();
 373
 374             if (rCorner.x <= myOrigin.x ||
 375                 rCorner.y <= myOrigin.y ||
 376                 rOrigin.x >= myCorner.x ||
 377                 rOrigin.y >= myCorner.y) return false;
 378             return true;
 379         },
 380         // @return {string} (left|right|top|bottom) side which is nearest to point
 381         // @see Squeak Smalltalk, Rectangle>>sideNearestTo:
 382         sideNearestToPoint: function(p) {
 383             p = point(p);
 384             var distToLeft = p.x - this.x;
 385             var distToRight = (this.x + this.width) - p.x;
 386             var distToTop = p.y - this.y;
 387             var distToBottom = (this.y + this.height) - p.y;
 388             var closest = distToLeft;
 389             var side = 'left';
 390
 391             if (distToRight < closest) {
 392                 closest = distToRight;
 393                 side = 'right';
 394             }
 395             if (distToTop < closest) {
 396                 closest = distToTop;
 397                 side = 'top';
 398             }
 399             if (distToBottom < closest) {
 400                 closest = distToBottom;
 401                 side = 'bottom';
 402             }
 403             return side;
 404         },
 405         // @return {bool} true if point p is insight me
 406         containsPoint: function(p) {
 407             p = point(p);
 408             if (p.x >= this.x && p.x <= this.x + this.width &&
 409                 p.y >= this.y && p.y <= this.y + this.height) {
 410                 return true;
 411             }
 412             return false;
 413         },
 414         // Algorithm ported from java.awt.Rectangle from OpenJDK.
 415         // @return {bool} true if rectangle `r` is inside me.
 416         containsRect: function(r) {
 417             var nr = rect(r).normalize();
 418             var W = nr.width;
 419             var H = nr.height;
 420             var X = nr.x;
 421             var Y = nr.y;
 422             var w = this.width;
 423             var h = this.height;
 424             if ((w | h | W | H) < 0) {
 425                 // At least one of the dimensions is negative...
 426                 return false;
 427             }
 428             // Note: if any dimension is zero, tests below must return false...
 429             var x = this.x;
 430             var y = this.y;
 431             if (X < x || Y < y) {
 432                 return false;
 433             }
 434             w += x;
 435             W += X;
 436             if (W <= X) {
 437                 // X+W overflowed or W was zero, return false if...
 438                 // either original w or W was zero or
 439                 // x+w did not overflow or
 440                 // the overflowed x+w is smaller than the overflowed X+W
 441                 if (w >= x || W > w) return false;
 442             } else {
 443                 // X+W did not overflow and W was not zero, return false if...
 444                 // original w was zero or
 445                 // x+w did not overflow and x+w is smaller than X+W
 446                 if (w >= x && W > w) return false;
 447             }
 448             h += y;
 449             H += Y;
 450             if (H <= Y) {
 451                 if (h >= y || H > h) return false;
 452             } else {
 453                 if (h >= y && H > h) return false;
 454             }
 455             return true;
 456         },
 457         // @return {point} a point on my boundary nearest to p
 458         // @see Squeak Smalltalk, Rectangle>>pointNearestTo:
 459         pointNearestToPoint: function(p) {
 460             p = point(p);
 461             if (this.containsPoint(p)) {
 462                 var side = this.sideNearestToPoint(p);
 463                 switch (side){
 464                     case 'right': return point(this.x + this.width, p.y);
 465                     case 'left': return point(this.x, p.y);
 466                     case 'bottom': return point(p.x, this.y + this.height);
 467                     case 'top': return point(p.x, this.y);
 468                 }
 469             }
 470             return p.adhereToRect(this);
 471         },
 472         // Find point on my boundary where line starting
 473         // from my center ending in point p intersects me.
 474         // @param {number} angle If angle is specified, intersection with rotated rectangle is computed.
 475         intersectionWithLineFromCenterToPoint: function(p, angle) {
 476             p = point(p);
 477             var center = point(this.x + this.width / 2, this.y + this.height / 2);
 478             var result;
 479             if (angle) p.rotate(center, angle);
 480
 481             // (clockwise, starting from the top side)
 482             var sides = [
 483                 line(this.origin(), this.topRight()),
 484                 line(this.topRight(), this.corner()),
 485                 line(this.corner(), this.bottomLeft()),
 486                 line(this.bottomLeft(), this.origin())
 487             ];
 488             var connector = line(center, p);
 489
 490             for (var i = sides.length - 1; i >= 0; --i) {
 491                 var intersection = sides[i].intersection(connector);
 492                 if (intersection !== null) {
 493                     result = intersection;
 494                     break;
 495                 }
 496             }
 497             if (result && angle) result.rotate(center, -angle);
 498             return result;
 499         },
 500         // Move and expand me.
 501         // @param r {rectangle} representing deltas
 502         moveAndExpand: function(r) {
 503             this.x += r.x || 0;
 504             this.y += r.y || 0;
 505             this.width += r.width || 0;
 506             this.height += r.height || 0;
 507             return this;
 508         },
 509         round: function(decimals) {
 510             this.x = decimals ? this.x.toFixed(decimals) : round(this.x);
 511             this.y = decimals ? this.y.toFixed(decimals) : round(this.y);
 512             this.width = decimals ? this.width.toFixed(decimals) : round(this.width);
 513             this.height = decimals ? this.height.toFixed(decimals) : round(this.height);
 514             return this;
 515         },
 516         // Normalize the rectangle; i.e., make it so that it has a non-negative width and height.
 517         // If width < 0 the function swaps the left and right corners,
 518         // and it swaps the top and bottom corners if height < 0
 519         // like in http://qt-project.org/doc/qt-4.8/qrectf.html#normalized
 520         normalize: function() {
 521             var newx = this.x;
 522             var newy = this.y;
 523             var newwidth = this.width;
 524             var newheight = this.height;
 525             if (this.width < 0) {
 526                 newx = this.x + this.width;
 527                 newwidth = -this.width;
 528             }
 529             if (this.height < 0) {
 530                 newy = this.y + this.height;
 531                 newheight = -this.height;
 532             }
 533             this.x = newx;
 534             this.y = newy;
 535             this.width = newwidth;
 536             this.height = newheight;
 537             return this;
 538         },
 539         // Find my bounding box when I'm rotated with the center of rotation in the center of me.
 540         // @return r {rectangle} representing a bounding box
 541         bbox: function(angle) {
 542             var theta = toRad(angle || 0);
 543             var st = abs(sin(theta));
 544             var ct = abs(cos(theta));
 545             var w = this.width * ct + this.height * st;
 546             var h = this.width * st + this.height * ct;
 547             return rect(this.x + (this.width - w) / 2, this.y + (this.height - h) / 2, w, h);
 548         }
 549     };
 550
 551     // Ellipse.
 552     // --------
 553     function ellipse(c, a, b) {
 554         if (!(this instanceof ellipse))
 555             return new ellipse(c, a, b);
 556         c = point(c);
 557         this.x = c.x;
 558         this.y = c.y;
 559         this.a = a;
 560         this.b = b;
 561     }
 562
 563     ellipse.prototype = {
 564         toString: function() {
 565             return point(this.x, this.y).toString() + ' ' + this.a + ' ' + this.b;
 566         },
 567         bbox: function() {
 568             return rect(this.x - this.a, this.y - this.b, 2 * this.a, 2 * this.b);
 569         },
 570         // Find point on me where line from my center to
 571         // point p intersects my boundary.
 572         // @param {number} angle If angle is specified, intersection with rotated ellipse is computed.
 573         intersectionWithLineFromCenterToPoint: function(p, angle) {
 574             p = point(p);
 575             if (angle) p.rotate(point(this.x, this.y), angle);
 576             var dx = p.x - this.x;
 577             var dy = p.y - this.y;
 578             var result;
 579             if (dx === 0) {
 580                 result = this.bbox().pointNearestToPoint(p);
 581                 if (angle) return result.rotate(point(this.x, this.y), -angle);
 582                 return result;
 583             }
 584             var m = dy / dx;
 585             var mSquared = m * m;
 586             var aSquared = this.a * this.a;
 587             var bSquared = this.b * this.b;
 588             var x = sqrt(1 / ((1 / aSquared) + (mSquared / bSquared)));
 589
 590             x = dx < 0 ? -x : x;
 591             var y = m * x;
 592             result = point(this.x + x, this.y + y);
 593             if (angle) return result.rotate(point(this.x, this.y), -angle);
 594             return result;
 595         }
 596     };
 597
 598     // Bezier curve.
 599     // -------------
 600     var bezier = {
 601         // Cubic Bezier curve path through points.
 602         // Ported from C# implementation by Oleg V. Polikarpotchkin and Peter Lee (http://www.codeproject.com/KB/graphics/BezierSpline.aspx).
 603         // @param {array} points Array of points through which the smooth line will go.
 604         // @return {array} SVG Path commands as an array
 605         curveThroughPoints: function(points) {
 606             var controlPoints = this.getCurveControlPoints(points);
 607             var path = ['M', points[0].x, points[0].y];
 608
 609             for (var i = 0; i < controlPoints[0].length; i++) {
 610                 path.push('C', controlPoints[0][i].x, controlPoints[0][i].y, controlPoints[1][i].x, controlPoints[1][i].y, points[i + 1].x, points[i + 1].y);
 611             }
 612             return path;
 613         },
 614
 615         // Get open-ended Bezier Spline Control Points.
 616         // @param knots Input Knot Bezier spline points (At least two points!).
 617         // @param firstControlPoints Output First Control points. Array of knots.length - 1 length.
 618         //  @param secondControlPoints Output Second Control points. Array of knots.length - 1 length.
 619         getCurveControlPoints: function(knots) {
 620             var firstControlPoints = [];
 621             var secondControlPoints = [];
 622             var n = knots.length - 1;
 623             var i;
 624
 625             // Special case: Bezier curve should be a straight line.
 626             if (n == 1) {
 627                 // 3P1 = 2P0 + P3
 628                 firstControlPoints[0] = point((2 * knots[0].x + knots[1].x) / 3,
 629                                               (2 * knots[0].y + knots[1].y) / 3);
 630                 // P2 = 2P1 – P0
 631                 secondControlPoints[0] = point(2 * firstControlPoints[0].x - knots[0].x,
 632                                                2 * firstControlPoints[0].y - knots[0].y);
 633                 return [firstControlPoints, secondControlPoints];
 634             }
 635
 636             // Calculate first Bezier control points.
 637             // Right hand side vector.
 638             var rhs = [];
 639
 640             // Set right hand side X values.
 641             for (i = 1; i < n - 1; i++) {
 642                 rhs[i] = 4 * knots[i].x + 2 * knots[i + 1].x;
 643             }
 644             rhs[0] = knots[0].x + 2 * knots[1].x;
 645             rhs[n - 1] = (8 * knots[n - 1].x + knots[n].x) / 2.0;
 646             // Get first control points X-values.
 647             var x = this.getFirstControlPoints(rhs);
 648
 649             // Set right hand side Y values.
 650             for (i = 1; i < n - 1; ++i) {
 651                 rhs[i] = 4 * knots[i].y + 2 * knots[i + 1].y;
 652             }
 653             rhs[0] = knots[0].y + 2 * knots[1].y;
 654             rhs[n - 1] = (8 * knots[n - 1].y + knots[n].y) / 2.0;
 655             // Get first control points Y-values.
 656             var y = this.getFirstControlPoints(rhs);
 657
 658             // Fill output arrays.
 659             for (i = 0; i < n; i++) {
 660                 // First control point.
 661                 firstControlPoints.push(point(x[i], y[i]));
 662                 // Second control point.
 663                 if (i < n - 1) {
 664                     secondControlPoints.push(point(2 * knots [i + 1].x - x[i + 1],
 665                                                    2 * knots[i + 1].y - y[i + 1]));
 666                 } else {
 667                     secondControlPoints.push(point((knots[n].x + x[n - 1]) / 2,
 668                                                    (knots[n].y + y[n - 1]) / 2));
 669                 }
 670             }
 671             return [firstControlPoints, secondControlPoints];
 672         },
 673
 674         // Solves a tridiagonal system for one of coordinates (x or y) of first Bezier control points.
 675         // @param rhs Right hand side vector.
 676         // @return Solution vector.
 677         getFirstControlPoints: function(rhs) {
 678             var n = rhs.length;
 679             // `x` is a solution vector.
 680             var x = [];
 681             var tmp = [];
 682             var b = 2.0;
 683
 684             x[0] = rhs[0] / b;
 685             // Decomposition and forward substitution.
 686             for (var i = 1; i < n; i++) {
 687                 tmp[i] = 1 / b;
 688                 b = (i < n - 1 ? 4.0 : 3.5) - tmp[i];
 689                 x[i] = (rhs[i] - x[i - 1]) / b;
 690             }
 691             for (i = 1; i < n; i++) {
 692                 // Backsubstitution.
 693                 x[n - i - 1] -= tmp[n - i] * x[n - i];
 694             }
 695             return x;
 696         },
 697
 698         // Solves an inversion problem -- Given the (x, y) coordinates of a point which lies on
 699         // a parametric curve x = x(t)/w(t), y = y(t)/w(t), ﬁnd the parameter value t
 700         // which corresponds to that point.
 701         // @param control points (start, control start, control end, end)
 702         // @return a function accepts a point and returns t.
 703         getInversionSolver: function(p0, p1, p2, p3) {
 704             var pts = arguments;
 705             function l(i, j) {
 706                 // calculates a determinant 3x3
 707                 // [p.x  p.y  1]
 708                 // [pi.x pi.y 1]
 709                 // [pj.x pj.y 1]
 710                 var pi = pts[i];
 711                 var pj = pts[j];
 712                 return function(p) {
 713                     var w = (i % 3 ? 3 : 1) * (j % 3 ? 3 : 1);
 714                     var lij = p.x * (pi.y - pj.y) + p.y * (pj.x - pi.x) + pi.x * pj.y - pi.y * pj.x;
 715                     return w * lij;
 716                 };
 717             }
 718             return function solveInversion(p) {
 719                 var ct = 3 * l(2, 3)(p1);
 720                 var c1 = l(1, 3)(p0) / ct;
 721                 var c2 = -l(2, 3)(p0) / ct;
 722                 var la = c1 * l(3, 1)(p) + c2 * (l(3, 0)(p) + l(2, 1)(p)) + l(2, 0)(p);
 723                 var lb = c1 * l(3, 0)(p) + c2 * l(2, 0)(p) + l(1, 0)(p);
 724                 return lb / (lb - la);
 725             };
 726         },
 727
 728         // Divide a Bezier curve into two at point defined by value 't' <0,1>.
 729         // Using deCasteljau algorithm. http://math.stackexchange.com/a/317867
 730         // @param control points (start, control start, control end, end)
 731         // @return a function accepts t and returns 2 curves each defined by 4 control points.
 732         getCurveDivider: function(p0, p1, p2, p3) {
 733             return function divideCurve(t) {
 734                 var l = line(p0, p1).pointAt(t);
 735                 var m = line(p1, p2).pointAt(t);
 736                 var n = line(p2, p3).pointAt(t);
 737                 var p = line(l, m).pointAt(t);
 738                 var q = line(m, n).pointAt(t);
 739                 var r = line(p, q).pointAt(t);
 740                 return [{ p0: p0, p1: l, p2: p, p3: r }, { p0: r, p1: q, p2: n, p3: p3 }];
 741             };
 742         }
 743     };
 744
 745     // Scale.
 746     var scale = {
 747
 748         // Return the `value` from the `domain` interval scaled to the `range` interval.
 749         linear: function(domain, range, value) {
 750
 751             var domainSpan = domain[1] - domain[0];
 752             var rangeSpan = range[1] - range[0];
 753             return (((value - domain[0]) / domainSpan) * rangeSpan + range[0]) || 0;
 754         }
 755     };
 756
 757     return {
 758         toDeg: toDeg,
 759         toRad: toRad,
 760         snapToGrid: snapToGrid,
 761         normalizeAngle: normalizeAngle,
 762         point: point,
 763         line: line,
 764         rect: rect,
 765         ellipse: ellipse,
 766         bezier: bezier,
 767         scale: scale
 768     };
 769
 770 }));