text: /**
   * @private
   * Singleton that provides methods used by the Ext.draw.Path
   * for hit testing and finding path intersection points.
   */
  Ext.define('Ext.draw.PathUtil', function () {
      var abs = Math.abs,
          pow = Math.pow,
          cos = Math.cos,
          acos = Math.acos,
          sqrt = Math.sqrt,
          PI = Math.PI;
  
      // For extra info see: http://pomax.github.io/bezierinfo/
  
      return {
          singleton: true,
  
          requires: [
              'Ext.draw.overrides.hittest.Path',
              'Ext.draw.overrides.hittest.sprite.Path'
          ],
  
          /**
           * @private
           * Finds roots of a cubic equation in t, where t lies in the interval of [0,1].
           * Based on http://www.particleincell.com/blog/2013/cubic-line-intersection/
           * @param P {Number[]} Cubic equation coefficients.
           * @return {Number[]} Returns an array of parametric intersection locations along the cubic,
           *                  with -1 indicating an out-of-bounds intersection
           *                  (before or after the end point or in the imaginary plane).
           */
          cubicRoots: function (P) {
              var a = P[0],
                  b = P[1],
                  c = P[2],
                  d = P[3];
  
              if (a === 0) {
                  return this.quadraticRoots(b, c, d);
              }
  
              var A = b / a,
                  B = c / a,
                  C = d / a,
  
                  Q = (3*B - pow(A, 2)) / 9,
                  R = (9*A*B - 27*C - 2*pow(A, 3)) / 54,
                  D = pow(Q, 3) + pow(R, 2), // Polynomial discriminant.
                  t = [],
                  S, T, Im, th, i,
  
                  sign = Ext.Number.sign;
  
              if (D >= 0) { // Complex or duplicate roots.
                  S = sign(R + sqrt(D)) * pow(abs(R + sqrt(D)), 1/3);
                  T = sign(R - sqrt(D)) * pow(abs(R - sqrt(D)), 1/3);
  
                  t[0] = -A/3 + (S + T);          // Real root.
                  t[1] = -A/3 - (S + T)/2;        // Real part of complex root.
                  t[2] = t[1];                    // Real part of complex root.
                  Im = abs(sqrt(3) * (S - T)/2);  // Complex part of root pair.
  
                  // Discard complex roots.
                  if (Im !== 0) {
                      t[1] =- 1;
                      t[2] =- 1;
                  }
  
              } else { // Distinct real roots.
                  th = acos(R / sqrt(-pow(Q, 3)));
  
                  t[0] = 2*sqrt(-Q)*cos(th/3) - A/3;
                  t[1] = 2*sqrt(-Q)*cos((th + 2*PI)/3) - A/3;
                  t[2] = 2*sqrt(-Q)*cos((th + 4*PI)/3) - A/3;
              }
  
              // Discard out of spec roots.
              for (i = 0; i < 3; i++) {
                  if (t[i] < 0 || t[i] > 1) {
                      t[i] = -1;
                  }
              }
  
              return t;
          },
  
          /**
           * @private
           * Finds roots of a quadratic equation in t, where t lies in the interval of [0,1].
           * Takes three quadratic equation coefficients as parameters.
           * @param a {Number}
           * @param b {Number}
           * @param c {Number}
           * @return {Array}
           */
          quadraticRoots: function (a, b, c) {
              var D, rD, t, i;
              if (a === 0) {
                  return this.linearRoot(b, c);
              }
              D = b*b - 4*a*c;
              if (D === 0) { // One real root.
                  t = [-b/(2*a)];
              } else if (D > 0) { // Distinct real roots.
                  rD = sqrt(D);
                  t = [(-b - rD) / (2*a), (-b + rD) / (2*a)];
              } else { // Complex roots.
                  return [];
              }
              for (i = 0; i < t.length; i++) {
                  if (t[i] < 0 || t[i] > 1) {
                      t[i] = -1;
                  }
              }
              return t;
          },
  
          /**
           * @private
           * Finds roots of a linear equation in t, where t lies in the interval of [0,1].
           * Takes two linear equation coefficients as parameters.
           * @param a {Number}
           * @param b {Number}
           * @return {Array}
           */
          linearRoot: function (a, b) {
              var t = -b/a;
              if (a === 0 || t < 0 || t > 1) {
                  return [];
              }
              return [t];
          },
  
          /**
           * @private
           * Calculates the coefficients of a cubic function for the given coordinates.
           * @param P0 {Number}
           * @param P1 {Number}
           * @param P2 {Number}
           * @param P3 {Number}
           * @return {Array}
           */
          bezierCoeffs: function (P0, P1, P2, P3) {
              var Z = [];
              Z[0] = -P0 + 3*P1 - 3*P2 + P3;
              Z[1] = 3*P0 - 6*P1 + 3*P2;
              Z[2] = -3*P0 + 3*P1;
              Z[3] = P0;
              return Z;
          },
  
          /**
           * @private
           * Computes intersection points between a cubic spline and a line segment.
           * Takes in x/y components of cubic control points and line segment start/end points
           * as parameters.
           * @param px1 {Number}
           * @param px2 {Number}
           * @param px3 {Number}
           * @param px4 {Number}
           * @param py1 {Number}
           * @param py2 {Number}
           * @param py3 {Number}
           * @param py4 {Number}
           * @param x1 {Number}
           * @param y1 {Number}
           * @param x2 {Number}
           * @param y2 {Number}
           * @return {Array} Array of intersection points, where each intersection point
           *                  is itself a two-item array [x,y].
           */
          cubicLineIntersections: function (px1, px2, px3, px4, py1, py2, py3, py4,
                                            x1, y1, x2, y2) {
              var P = [],
                  intersections = [],
  
                  // Finding line equation coefficients.
                  A = y1 - y2,
                  B = x2 - x1,
                  C = x1 * (y2 - y1) - y1 * (x2 - x1),
  
                  // Finding cubic Bezier curve equation coefficients.
                  bx = this.bezierCoeffs(px1, px2, px3, px4),
                  by = this.bezierCoeffs(py1, py2, py3, py4),
  
                  i, r, s,
                  t, tt, ttt,
                  cx, cy;
  
              P[0] = A*bx[0] + B*by[0];		// t^3
              P[1] = A*bx[1] + B*by[1];		// t^2
              P[2] = A*bx[2] + B*by[2];		// t
              P[3] = A*bx[3] + B*by[3] + C;	// 1
  
              r = this.cubicRoots(P);
  
              // Verify the roots are in bounds of the linear segment.
              for (i = 0; i < r.length; i++) {
                  t = r[i];
  
                  if (t < 0 || t > 1) {
                      continue;
                  }
  
                  tt = t*t;
                  ttt = tt*t;
  
                  cx = bx[0]*ttt + bx[1]*tt + bx[2]*t + bx[3];
                  cy = by[0]*ttt + by[1]*tt + by[2]*t + by[3];
  
                  // Above is intersection point assuming infinitely long line segment,
                  // make sure we are also in bounds of the line.
                  if ((x2 - x1) !== 0) { // If not vertical line
                      s = (cx - x1) / (x2 - x1);
                  } else {
                      s = (cy - y1) / (y2 - y1);
                  }
                  // In bounds?
                  if (!(s < 0 || s > 1)) {
                      intersections.push([cx, cy]);
                  }
              }
              return intersections;
          },
  
          /**
           * @private
           * Splits cubic Bezier curve into two cubic Bezier curves at point z,
           * where z belongs to a range of [0, 1].
           * Accepts cubic coefficients and point z as parameters.
           * @param P1 {Number}
           * @param P2 {Number}
           * @param P3 {Number}
           * @param P4 {Number}
           * @param z Point to split the given curve at.
           * @return {Array} Two-item array, where each item is itself an array
           *                  of cubic coefficients.
           */
          splitCubic: function (P1, P2, P3, P4, z) {
              var zz = z * z,
                  zzz = z * zz,
                  iz = z - 1,
                  izz = iz * iz,
                  izzz = iz * izz,
                  // Common point for both curves.
                  P = zzz * P4 - 3 * zz * iz * P3 + 3 * z * izz * P2 - izzz * P1;
  
              return [
                  [
                      P1,
                      z * P2 - iz * P1,
                      zz * P3 - 2 * z * iz * P2 + izz * P1,
                      P
                  ],
                  [
                      P,
                      zz * P4 - 2 * z * iz * P3 + izz * P2,
                      z * P4 - iz * P3,
                      P4
                  ]
              ]
          },
  
          /**
           * @private
           * Returns the dimension of a cubic Bezier curve in a single direction.
           * @param a {Number}
           * @param b {Number}
           * @param c {Number}
           * @param d {Number}
           * @return {Array} Two-item array representing cubic's range in the given direction.
           */
          cubicDimension: function (a, b, c, d) {
              var qa = 3 * (-a + 3 * (b - c) + d),
                  qb = 6 * (a - 2 * b + c),
                  qc = -3 * (a - b), x, y,
                  min = Math.min(a, d),
                  max = Math.max(a, d), delta;
  
              if (qa === 0) {
                  if (qb === 0) {
                      return [min, max];
                  } else {
                      x = -qc / qb;
                      if (0 < x && x < 1) {
                          y = this.interpolateCubic(a, b, c, d, x);
                          min = Math.min(min, y);
                          max = Math.max(max, y);
                      }
                  }
              } else {
                  delta = qb * qb - 4 * qa * qc;
                  if (delta >= 0) {
                      delta = sqrt(delta);
                      x = (delta - qb) / 2 / qa;
                      if (0 < x && x < 1) {
                          y = this.interpolateCubic(a, b, c, d, x);
                          min = Math.min(min, y);
                          max = Math.max(max, y);
                      }
                      if (delta > 0) {
                          x -= delta / qa;
                          if (0 < x && x < 1) {
                              y = this.interpolateCubic(a, b, c, d, x);
                              min = Math.min(min, y);
                              max = Math.max(max, y);
                          }
                      }
                  }
              }
              return [min, max];
          },
  
          /**
           * @private
           * Calculates a value of a cubic function at the given point t. In other words
           * returns a * (1 - t) ^ 3 + 3 * b (1 - t) ^ 2 * t + 3 * c (1 - t) * t ^ 3 + d * t ^ 3
           * for given a, b, c, d and t, where t belongs to an interval of [0, 1].
           * @param a {Number}
           * @param b {Number}
           * @param c {Number}
           * @param d {Number}
           * @param t {Number}
           * @return {Number}
           */
          interpolateCubic: function (a, b, c, d, t) {
              if (t === 0) {
                  return a;
              }
              if (t === 1) {
                  return d;
              }
              var rate = (1 - t) / t;
              return t * t * t * (d + rate * (3 * c + rate * (3 * b + rate * a)));
          },
  
          /**
           * @private
           * Computes intersection points between two cubic Bezier curve segments.
           * Takes x/y components of control points for two Bezier curve segments.
           * @param ax1 {Number}
           * @param ax2 {Number}
           * @param ax3 {Number}
           * @param ax4 {Number}
           * @param ay1 {Number}
           * @param ay2 {Number}
           * @param ay3 {Number}
           * @param ay4 {Number}
           * @param bx1 {Number}
           * @param bx2 {Number}
           * @param bx3 {Number}
           * @param bx4 {Number}
           * @param by1 {Number}
           * @param by2 {Number}
           * @param by3 {Number}
           * @param by4 {Number}
           * @return {Array} Array of intersection points, where each intersection point
           *                  is itself a two-item array [x,y].
           */
          cubicsIntersections: function (ax1, ax2, ax3, ax4, ay1, ay2, ay3, ay4,
                                         bx1, bx2, bx3, bx4, by1, by2, by3, by4) {
              var me = this,
                  axDim = me.cubicDimension(ax1, ax2, ax3, ax4),
                  ayDim = me.cubicDimension(ay1, ay2, ay3, ay4),
                  bxDim = me.cubicDimension(bx1, bx2, bx3, bx4),
                  byDim = me.cubicDimension(by1, by2, by3, by4),
                  splitAx, splitAy, splitBx, splitBy,
                  points = [];
  
              // Curves' bounding boxes don't intersect.
              if (axDim[0] > bxDim[1] || axDim[1] < bxDim[0] || ayDim[0] > byDim[1] || ayDim[1] < byDim[0]) {
                  return [];
              }
              // Both curves occupy sub-pixel areas which is effectively their intersection point.
              if (abs(ay1 - ay2) < 1 && abs(ay3 - ay4) < 1 && abs(ax1 - ax4) < 1 && abs(ax2 - ax3) < 1 &&
                  abs(by1 - by2) < 1 && abs(by3 - by4) < 1 && abs(bx1 - bx4) < 1 && abs(bx2 - bx3) < 1) {
                  return [[ (ax1 + ax4) * 0.5, (ay1 + ay2) * 0.5 ]];
              }
  
              splitAx = me.splitCubic(ax1, ax2, ax3, ax4, 0.5);
              splitAy = me.splitCubic(ay1, ay2, ay3, ay4, 0.5);
              splitBx = me.splitCubic(bx1, bx2, bx3, bx4, 0.5);
              splitBy = me.splitCubic(by1, by2, by3, by4, 0.5);
  
              points.push.apply(points, me.cubicsIntersections.apply(me, splitAx[0].concat(splitAy[0], splitBx[0], splitBy[0])));
              points.push.apply(points, me.cubicsIntersections.apply(me, splitAx[0].concat(splitAy[0], splitBx[1], splitBy[1])));
              points.push.apply(points, me.cubicsIntersections.apply(me, splitAx[1].concat(splitAy[1], splitBx[0], splitBy[0])));
              points.push.apply(points, me.cubicsIntersections.apply(me, splitAx[1].concat(splitAy[1], splitBx[1], splitBy[1])));
  
              return points;
          },
  
          /**
           * @private
           * Returns the point [x,y] where two line segments intersect or null.
           * Takes x/y components of the start and end point of the segments as parameters.
           * Based on Paul Bourke's explanation:
           * http://paulbourke.net/geometry/pointlineplane/
           * @param x1 {Number}
           * @param y1 {Number}
           * @param x2 {Number}
           * @param y2 {Number}
           * @param x3 {Number}
           * @param y3 {Number}
           * @param x4 {Number}
           * @param y4 {Number}
           * @return {Number[]|null}
           */
          linesIntersection: function (x1, y1, x2, y2, x3, y3, x4, y4) {
              var d = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3),
                  ua, ub;
              if (d === 0) { // Lines are parallel.
                  return null;
              }
              ua = ( (x4 - x3) * (y1 - y3) - (x1 - x3) * (y4 - y3) ) / d;
              ub = ( (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3) ) / d;
              if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {
                  return [
                      x1 + ua * (x2 - x1), // x
                      y1 + ua * (y2 - y1)  // y
                  ];
              }
              return null; // The intersection point is outside one or both segments.
          },
  
          /**
           * @private
           * Checks if a point belongs to a line segment.
           * Takes x/y components of the start and end points of the segment and the point's
           * coordinates as parameters.
           * @param x1 {Number}
           * @param y1 {Number}
           * @param x2 {Number}
           * @param y2 {Number}
           * @param x {Number}
           * @param y {Number}
           * @return {Boolean}
           */
          pointOnLine: function (x1, y1, x2, y2, x, y) {
              var t, _;
              if (abs(x2 - x1) < abs(y2 - y1)) {
                  _ = x1;
                  x1 = y1;
                  y1 = _;
                  _ = x2;
                  x2 = y2;
                  y2 = _;
                  _ = x;
                  x = y;
                  y = _;
              }
              t = (x - x1) / (x2 - x1);
              if (t < 0 || t > 1) {
                  return false;
              }
              return abs(y1 + t * (y2 - y1) - y) < 4;
          },
  
          /**
           * @private
           * Checks if a point belongs to a cubic Bezier curve segment.
           * Takes x/y components of the control points of the segment and the point's
           * coordinates as parameters.
           * @param px1 {Number}
           * @param px2 {Number}
           * @param px3 {Number}
           * @param px4 {Number}
           * @param py1 {Number}
           * @param py2 {Number}
           * @param py3 {Number}
           * @param py4 {Number}
           * @param x {Number}
           * @param y {Number}
           * @return {Boolean}
           */
          pointOnCubic: function (px1, px2, px3, px4, py1, py2, py3, py4, x, y) {
              // Finding cubic Bezier curve equation coefficients.
              var me = this,
                  bx = me.bezierCoeffs(px1, px2, px3, px4),
                  by = me.bezierCoeffs(py1, py2, py3, py4),
                  i, j, rx, ry, t;
  
              bx[3] -= x;
              by[3] -= y;
  
              rx = me.cubicRoots(bx);
              ry = me.cubicRoots(by);
  
              for (i = 0; i < rx.length; i++) {
                  t = rx[i];
                  for (j = 0; j < ry.length; j++) {
                      // TODO: for more accurate results tolerance should be dynamic
                      // TODO: based on the length and shape of the segment.
                      if (t >= 0 && t <= 1 && abs(t - ry[j]) < 0.05) {
                          return true;
                      }
                  }
              }
  
              return false;
          }
  
      };
  });
  