/**
 * @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 (=== 0) {
                return this.quadraticRoots(b, c, d);
            }
 
            // eslint-disable-next-line vars-on-top, one-var
            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 (= 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 (=== 0) {
                return this.linearRoot(b, c);
            }
 
            D = b * b - 4 * a * c;
 
            if (D === 0) { // One real root.
                t = [-/ (2 * a)];
            }
            else if (D > 0) { // Distinct real roots.
                rD = sqrt(D);
                t = [(-- rD) / (2 * a), (-+ rD) / (2 * a)];
            }
            else { // Complex roots.
                return [];
            }
 
            for (= 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 = -/ a;
 
            if (=== 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 (= 0; i < r.length; i++) {
                t = r[i];
 
                if (< 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 (!(< 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 * (-+ 3 * (- c) + d),
                qb = 6 * (- 2 * b + c),
                qc = -3 * (- 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) {
            var rate;
 
            if (=== 0) {
                return a;
            }
 
            if (=== 1) {
                return d;
            }
 
            rate = (1 - t) / t;
 
            return t * t * t * (+ 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) {
            /* eslint-disable max-len */
            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;
        },
        /* eslint-enable max-len */
 
        /**
         * @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 (=== 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 = (- x1) / (x2 - x1);
 
            if (< 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 (= 0; i < rx.length; i++) {
                t = rx[i];
 
                for (= 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 (>= 0 && t <= 1 && abs(- ry[j]) < 0.05) {
                        return true;
                    }
                }
            }
 
            return false;
        }
 
    };
});