'use strict';

var Potrace = (function () {

    function Point(x, y) {
        this.x = x;
        this.y = y;
    }

    Point.prototype.copy = function () {
        return new Point(this.x, this.y);
    };

    function fixed(number) {
        return number.toFixed(3).replace('.000', '');
    }

    function luminance(r, g, b) {
        return Math.round(0.2126 * r + 0.7153 * g + 0.0721 * b);
    }

    function between(val, min, max) {
        return val >= min && val <= max;
    }

    function clamp(val, min, max) {
        return Math.min(max, Math.max(min, val));
    }

    function isNumber(val) {
        return typeof val === 'number';
    }

    function mod(a, n) {
        return a >= n ? a % n : a >= 0 ? a : n - 1 - (-1 - a) % n;
    }

    function xprod(p1, p2) {
        return p1.x * p2.y - p1.y * p2.x;
    }

    function cyclic(a, b, c) {
        if (a <= c) {
            return (a <= b && b < c);
        } else {
            return (a <= b || b < c);
        }
    }

    function sign(i) {
        return i > 0 ? 1 : i < 0 ? -1 : 0;
    }

    function quadform(Q, w) {
        var v = new Array(3), i, j, sum;

        v[0] = w.x;
        v[1] = w.y;
        v[2] = 1;
        sum = 0.0;

        for (i = 0; i < 3; i++) {
            for (j = 0; j < 3; j++) {
                sum += v[i] * Q.at(i, j) * v[j];
            }
        }
        return sum;
    }

    function interval(lambda, a, b) {
        var res = new Point();

        res.x = a.x + lambda * (b.x - a.x);
        res.y = a.y + lambda * (b.y - a.y);
        return res;
    }

    function dorth_infty(p0, p2) {
        var r = new Point();

        r.y = sign(p2.x - p0.x);
        r.x = -sign(p2.y - p0.y);

        return r;
    }

    function ddenom(p0, p2) {
        var r = dorth_infty(p0, p2);

        return r.y * (p2.x - p0.x) - r.x * (p2.y - p0.y);
    }

    function dpara(p0, p1, p2) {
        var x1, y1, x2, y2;

        x1 = p1.x - p0.x;
        y1 = p1.y - p0.y;
        x2 = p2.x - p0.x;
        y2 = p2.y - p0.y;

        return x1 * y2 - x2 * y1;
    }

    function cprod(p0, p1, p2, p3) {
        var x1, y1, x2, y2;

        x1 = p1.x - p0.x;
        y1 = p1.y - p0.y;
        x2 = p3.x - p2.x;
        y2 = p3.y - p2.y;

        return x1 * y2 - x2 * y1;
    }

    function iprod(p0, p1, p2) {
        var x1, y1, x2, y2;

        x1 = p1.x - p0.x;
        y1 = p1.y - p0.y;
        x2 = p2.x - p0.x;
        y2 = p2.y - p0.y;

        return x1 * x2 + y1 * y2;
    }

    function iprod1(p0, p1, p2, p3) {
        var x1, y1, x2, y2;

        x1 = p1.x - p0.x;
        y1 = p1.y - p0.y;
        x2 = p3.x - p2.x;
        y2 = p3.y - p2.y;

        return x1 * x2 + y1 * y2;
    }

    function ddist(p, q) {
        return Math.sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
    }

    function bezier(t, p0, p1, p2, p3) {
        var s = 1 - t, res = new Point();

        res.x = s * s * s * p0.x + 3 * (s * s * t) * p1.x + 3 * (t * t * s) * p2.x + t * t * t * p3.x;
        res.y = s * s * s * p0.y + 3 * (s * s * t) * p1.y + 3 * (t * t * s) * p2.y + t * t * t * p3.y;

        return res;
    }

    function tangent(p0, p1, p2, p3, q0, q1) {
        var A, B, C, a, b, c, d, s, r1, r2;

        A = cprod(p0, p1, q0, q1);
        B = cprod(p1, p2, q0, q1);
        C = cprod(p2, p3, q0, q1);

        a = A - 2 * B + C;
        b = -2 * A + 2 * B;
        c = A;

        d = b * b - 4 * a * c;

        if (a === 0 || d < 0) {
            return -1.0;
        }

        s = Math.sqrt(d);

        r1 = (-b + s) / (2 * a);
        r2 = (-b - s) / (2 * a);

        if (r1 >= 0 && r1 <= 1) {
            return r1;
        } else if (r2 >= 0 && r2 <= 1) {
            return r2;
        } else {
            return -1.0;
        }
    }

    var utils = {
        luminance: function (r, g, b) {
            return Math.round(0.2126 * r + 0.7153 * g + 0.0721 * b);
        },

        between: function (val, min, max) {
            return val >= min && val <= max;
        },

        clamp: function (val, min, max) {
            return Math.min(max, Math.max(min, val));
        },

        isNumber: function (val) {
            return typeof val === 'number';
        },

        /**
         * Generates path instructions for given curve
         *
         * @param {Curve} curve
         * @param {Number} [scale]
         * @returns {string}
         */
        renderCurve: function (curve, scale) {
            scale = scale || 1;

            var startingPoint = curve.c[(curve.n - 1) * 3 + 2];

            var path = 'M '
                + fixed(startingPoint.x * scale) + ' '
                + fixed(startingPoint.y * scale) + ' ';

            curve.tag.forEach(function (tag, i) {
                var i3 = i * 3;
                var p0 = curve.c[i3];
                var p1 = curve.c[i3 + 1];
                var p2 = curve.c[i3 + 2];

                if (tag === "CURVE") {
                    path += 'C ';
                    path += fixed(p0.x * scale) + ' ' + fixed(p0.y * scale) + ', ';
                    path += fixed(p1.x * scale) + ' ' + fixed(p1.y * scale) + ', ';
                    path += fixed(p2.x * scale) + ' ' + fixed(p2.y * scale) + ' ';
                } else if (tag === "CORNER") {
                    path += 'L ';
                    path += fixed(p1.x * scale) + ' ' + fixed(p1.y * scale) + ' ';
                    path += fixed(p2.x * scale) + ' ' + fixed(p2.y * scale) + ' ';
                }
            });

            return path;
        },

        bezier: bezier,

        tangent: tangent,

        mod: mod,
        xprod: xprod,
        cyclic: cyclic,
        sign: sign,
        quadform: quadform,
        interval: interval,
        dorth_infty: dorth_infty,
        ddenom: ddenom,
        dpara: dpara,
        cprod: cprod,
        iprod: iprod,
        iprod1: iprod1,
        ddist: ddist
    };

    function Bitmap(w, h) {
        this.w = w;
        this.h = h;
        this.size = w * h;
        //this.arraybuffer = new ArrayBuffer(this.size);
        //this.data = new Uint16Array(this.arraybuffer);

        this.data = [];
        for (let i = 0; i < this.size; i++) {
            this.data[i] = 0;
        }
    }

    Bitmap.prototype.at = function (x, y) {
        //return (x >= 0 && x < this.w && y >=0 && y < this.h) &&  this.data[this.w * y + x] === 1;
        var index = (typeof x === 'number' && typeof y !== 'number') ? x : this.pointToIndex(x, y);
        return this.data[index];
    };

    Bitmap.prototype.pointToIndex = function (pointOrX, y) {
        var _x = pointOrX,
            _y = y;

        if (pointOrX instanceof Point) {
            _x = pointOrX.x;
            _y = pointOrX.y;
        }

        if (!utils.between(_x, 0, this.w) || !utils.between(_y, 0, this.h)) {
            return -1;
        }

        return this.w * _y + _x;
    };

    Bitmap.prototype.index = function (i) {
        var point = new Point();
        if (utils.between(i, 0, this.size)) {
            point.y = Math.floor(i / this.w);
            point.x = i - point.y * this.w;
        } else {
            point.x = -1;
            point.y = -1;
        }
        return point;
    };

    Bitmap.prototype.flip = function (x, y) {
        if (this.at(x, y)) {
            this.data[this.w * y + x] = 0;
        } else {
            this.data[this.w * y + x] = 1;
        }
    };

    Bitmap.prototype.copy = function (iterator) {
        var _bm = new Bitmap(this.w, this.h),
            iteratorPresent = typeof iterator === 'function',
            i;
        for (i = 0; i < this.size; i++) {
            _bm.data[i] = iteratorPresent ? iterator(this.data[i], i) : this.data[i];
        }
        return _bm;
    };

    function Path() {
        this.area = 0;
        this.len = 0;
        this.curve = {};
        this.pt = [];
        this.minX = 100000;
        this.minY = 100000;
        this.maxX = -1;
        this.maxY = -1;
    }

    function Curve(n) {
        this.n = n;
        this.tag = new Array(n);
        this.c = new Array(n * 3);
        this.alphaCurve = 0;
        this.vertex = new Array(n);
        this.alpha = new Array(n);
        this.alpha0 = new Array(n);
        this.beta = new Array(n);
    }

    var imgCanvas = document.createElement("canvas"),
        bm = null,
        pathlist = [],
        callback,
        info = {
            isReady: false,
            turnpolicy: "minority",
            turdsize: 2,
            optcurve: true,
            alphamax: 1,
            opttolerance: 0.2,
            threshold: 128,
            blackOnWhite: true,
            color: 'none',
            background: 'transparent',
            outline: 'blue',
            margin: 0,
            offset: 0,
            needResize: false
        };

    function setParameter(obj) {
        var key;
        for (key in obj) {
            if (obj.hasOwnProperty(key)) {
                info[key] = obj[key];
            }
        }
    }

    function loadData(imgData, width, height) {
        loadCanvas(imgData, width, height);
        setTimeout(function () {
            createShade();
        }, 100);
        setTimeout(function () {
            loadBm();
        }, 500);
    }

    function loadCanvas(imgdataObj, width, height) {
        imgCanvas.width = width;
        imgCanvas.height = height;
        var ctx = imgCanvas.getContext('2d');
        ctx.putImageData(imgdataObj, info.margin, info.margin);
    }

    function loadBm() {
        var ctx = imgCanvas.getContext('2d');
        bm = new Bitmap(imgCanvas.width, imgCanvas.height);
        var imgdataobj = ctx.getImageData(0, 0, bm.w, bm.h);
        var l = imgdataobj.data.length, i, j, color;
        for (i = 0, j = 0; i < l; i += 4, j++) {

            var opacity = imgdataobj.data[i + 3] / 255,
                r = 255 + (imgdataobj.data[i + 0] - 255) * opacity,
                g = 255 + (imgdataobj.data[i + 1] - 255) * opacity,
                b = 255 + (imgdataobj.data[i + 2] - 255) * opacity;
            bm.data[j] = utils.luminance(r, g, b);
        }

        info.isReady = true;
    }

    function createShade() {
        var shade = [],
            contour = [],
            threshold = 0,
            ctx = imgCanvas.getContext('2d'),
            width = imgCanvas.width,
            height = imgCanvas.height,
            imgdataobj = ctx.getImageData(0, 0, width, height),
            imgDataCopy = imgdataobj;

        function setColorAtIndex(index, r, g, b, a) {
            imgDataCopy.data[index] = r;
            imgDataCopy.data[index + 1] = g;
            imgDataCopy.data[index + 2] = b;
            imgDataCopy.data[index + 3] = a;
        }

        var l = imgdataobj.data.length, i, j;
        for (i = 0, j = 0; i < l; i += 4, j++) {
            if (imgDataCopy.data[i + 3] > threshold) {
                setColorAtIndex(i, 0, 0, 0, 255);
            } else {
                setColorAtIndex(i, 0, 0, 0, 0);
            }
        }

        var pixelsToCheck = [0, 0];

        function getPixelColor(x, y) {
            if (x < 0 || y < 0 || x >= width || y >= height) {
                return -1;
            } else {
                var index = (width * y + x) * 4;
                return [imgDataCopy.data[index], imgDataCopy.data[index + 1], imgDataCopy.data[index + 2], imgDataCopy.data[index + 3]];
            }
        }

        function compareTwoColos(color1, color2) {
            if (color1 == -1 || color2 == -1) return false;

            var check = true;
            for (var i = 0; i < 4; i++) {
                if (color1[i] != color2[i]) {
                    check = false;
                    break;
                }
            }
            return check;
        }

        var targetColor = getPixelColor(0, 0);

        while (pixelsToCheck.length > 0) {
            var y = pixelsToCheck.pop(),
                x = pixelsToCheck.pop(),
                index = (width * y + x) * 4,
                currentColor = getPixelColor(x, y);

            if (compareTwoColos(currentColor, targetColor)) {
                setColorAtIndex(index, 255, 0, 0, 255);
                pixelsToCheck.push(x + 1, y);
                pixelsToCheck.push(x - 1, y);
                pixelsToCheck.push(x, y + 1);
                pixelsToCheck.push(x, y - 1);
            }
        }
        
        for (i = 0, j = 0; i < l; i += 4, j++) {
            var currentColor = [imgDataCopy.data[i], imgDataCopy.data[i + 1], imgDataCopy.data[i + 2], imgDataCopy.data[i + 3]],
                floodColor = [255, 0, 0, 255];
            if (!compareTwoColos(currentColor, floodColor)) {
                setColorAtIndex(i, 0, 0, 0, 255);
            } else {
                setColorAtIndex(i, 0, 0, 0, 0);
            }
        }

        for (i = 0, j = 0; i < l; i += 4, j++) {
            if (imgDataCopy.data[i + 3] > threshold) {
                shade.push(i);
            }
        }

        function indexToPixel(index) {
            var y = Math.floor(index / 4 / width);
            x = index / 4 - y * width;
            return [x, y];
        }

        shade.forEach(function (index) {
            var __point = indexToPixel(index);
            var x = __point[0],
                y = __point[1],
                isContour = false, nIndex;

            for (let i = x - 1; i <= x + 1; i++) {
                if (isContour) {
                    break;
                }

                for (let j = y - 1; j <= y + 1; j++) {
                    nIndex = (width * j + i) * 4;

                    if (imgDataCopy.data[nIndex + 3] <= threshold) {
                        contour.push(index);
                        isContour = true;
                        break;
                    }
                }
            }
        });

        contour.forEach(function (index) {
            var margin = info.margin,
                __point = indexToPixel(index),
                x = __point[0],
                y = __point[1];

            var nIndex;
            for (let i = x - margin; i <= x + margin; i++) {
                for (let j = y - margin; j <= y + margin; j++) {
                    if (margin * margin >= ((x - i) * (x - i) + (y - j) * (y - j))) {
                        nIndex = (width * j + i) * 4;
                        imgDataCopy.data[nIndex] = 0;
                        imgDataCopy.data[nIndex + 1] = 0;
                        imgDataCopy.data[nIndex + 2] = 0;
                        imgDataCopy.data[nIndex + 3] = 255;
                    }
                }
            }
        });

        ctx.putImageData(imgDataCopy, 0, 0);
    }

    function getImg() {
        return imgCanvas.toDataURL();
    }
    
    function bmToPathlist() {

        var bm1,
            threshold = info.threshold,
            blackOnWhite = info.blackOnWhite,
            currentPoint = new Point(0, 0),
            path;

        threshold = 128;
        bm1 = bm.copy(function (lum) {
            var pastTheThreshold = blackOnWhite ? lum > threshold : lum < threshold;
            return pastTheThreshold ? 0 : 1;
        });

        function findNext(point) {
            var i = bm1.w * point.y + point.x;
            while (i < bm1.size && bm1.data[i] !== 1) {
                i++;
            }
            return i < bm1.size && bm1.index(i);
        }

        function majority(x, y) {
            var i, a, ct;
            for (i = 2; i < 5; i++) {
                ct = 0;
                for (a = -i + 1; a <= i - 1; a++) {
                    ct += bm1.at(x + a, y + i - 1) ? 1 : -1;
                    ct += bm1.at(x + i - 1, y + a - 1) ? 1 : -1;
                    ct += bm1.at(x + a - 1, y - i) ? 1 : -1;
                    ct += bm1.at(x - i, y + a) ? 1 : -1;
                }
                if (ct > 0) {
                    return 1;
                } else if (ct < 0) {
                    return 0;
                }
            }
            return 0;
        }

        function findPath(point) {
            var path = new Path(),
                x = point.x, y = point.y,
                dirx = 0, diry = 1, tmp;

            path.sign = bm.at(point.x, point.y) ? "+" : "-";

            while (1) {
                path.pt.push(new Point(x, y));
                if (x > path.maxX)
                    path.maxX = x;
                if (x < path.minX)
                    path.minX = x;
                if (y > path.maxY)
                    path.maxY = y;
                if (y < path.minY)
                    path.minY = y;
                path.len++;

                x += dirx;
                y += diry;
                path.area -= x * diry;

                if (x === point.x && y === point.y)
                    break;

                var l = bm1.at(x + (dirx + diry - 1) / 2, y + (diry - dirx - 1) / 2);
                var r = bm1.at(x + (dirx - diry - 1) / 2, y + (diry + dirx - 1) / 2);

                if (r && !l) {
                    if (info.turnpolicy === "right" ||
                        (info.turnpolicy === "black" && path.sign === '+') ||
                        (info.turnpolicy === "white" && path.sign === '-') ||
                        (info.turnpolicy === "majority" && majority(x, y)) ||
                        (info.turnpolicy === "minority" && !majority(x, y))) {
                        tmp = dirx;
                        dirx = -diry;
                        diry = tmp;
                    } else {
                        tmp = dirx;
                        dirx = diry;
                        diry = -tmp;
                    }
                } else if (r) {
                    tmp = dirx;
                    dirx = -diry;
                    diry = tmp;
                } else if (!l) {
                    tmp = dirx;
                    dirx = diry;
                    diry = -tmp;
                }
            }
            return path;
        }

        function xorPath(path) {
            var y1 = path.pt[0].y,
                len = path.len,
                x, y, maxX, minY, i, j;
            for (i = 1; i < len; i++) {
                x = path.pt[i].x;
                y = path.pt[i].y;

                if (y !== y1) {
                    minY = y1 < y ? y1 : y;
                    maxX = path.maxX;
                    for (j = x; j < maxX; j++) {
                        bm1.flip(j, minY);
                    }
                    y1 = y;
                }
            }

        }

        while (currentPoint = findNext(currentPoint)) {

            path = findPath(currentPoint);

            xorPath(path);

            if (path.area > info.turdsize) {
                pathlist.push(path);
            }
        }

    }

    function processPath() {

        function Quad() {
            this.data = [0, 0, 0, 0, 0, 0, 0, 0, 0];
        }

        Quad.prototype.at = function (x, y) {
            return this.data[x * 3 + y];
        };

        function Sum(x, y, xy, x2, y2) {
            this.x = x;
            this.y = y;
            this.xy = xy;
            this.x2 = x2;
            this.y2 = y2;
        }

        function calcSums(path) {
            var i, x, y;
            path.x0 = path.pt[0].x;
            path.y0 = path.pt[0].y;

            path.sums = [];
            var s = path.sums;
            s.push(new Sum(0, 0, 0, 0, 0));
            for (i = 0; i < path.len; i++) {
                x = path.pt[i].x - path.x0;
                y = path.pt[i].y - path.y0;
                s.push(new Sum(s[i].x + x, s[i].y + y, s[i].xy + x * y,
                    s[i].x2 + x * x, s[i].y2 + y * y));
            }
        }

        function calcLon(path) {

            var n = path.len, pt = path.pt, dir,
                pivk = new Array(n),
                nc = new Array(n),
                ct = new Array(4);
            path.lon = new Array(n);

            var constraint = [new Point(), new Point()],
                cur = new Point(),
                off = new Point(),
                dk = new Point(),
                foundk;

            var i, j, k1, a, b, c, d, k = 0;
            for (i = n - 1; i >= 0; i--) {
                if (pt[i].x != pt[k].x && pt[i].y != pt[k].y) {
                    k = i + 1;
                }
                nc[i] = k;
            }

            for (i = n - 1; i >= 0; i--) {
                ct[0] = ct[1] = ct[2] = ct[3] = 0;
                dir = (3 + 3 * (pt[mod(i + 1, n)].x - pt[i].x) +
                    (pt[mod(i + 1, n)].y - pt[i].y)) / 2;
                ct[dir]++;

                constraint[0].x = 0;
                constraint[0].y = 0;
                constraint[1].x = 0;
                constraint[1].y = 0;

                k = nc[i];
                k1 = i;
                while (1) {
                    foundk = 0;
                    dir = (3 + 3 * sign(pt[k].x - pt[k1].x) +
                        sign(pt[k].y - pt[k1].y)) / 2;
                    ct[dir]++;

                    if (ct[0] && ct[1] && ct[2] && ct[3]) {
                        pivk[i] = k1;
                        foundk = 1;
                        break;
                    }

                    cur.x = pt[k].x - pt[i].x;
                    cur.y = pt[k].y - pt[i].y;

                    if (xprod(constraint[0], cur) < 0 || xprod(constraint[1], cur) > 0) {
                        break;
                    }

                    if (Math.abs(cur.x) <= 1 && Math.abs(cur.y) <= 1) {

                    } else {
                        off.x = cur.x + ((cur.y >= 0 && (cur.y > 0 || cur.x < 0)) ? 1 : -1);
                        off.y = cur.y + ((cur.x <= 0 && (cur.x < 0 || cur.y < 0)) ? 1 : -1);
                        if (xprod(constraint[0], off) >= 0) {
                            constraint[0].x = off.x;
                            constraint[0].y = off.y;
                        }
                        off.x = cur.x + ((cur.y <= 0 && (cur.y < 0 || cur.x < 0)) ? 1 : -1);
                        off.y = cur.y + ((cur.x >= 0 && (cur.x > 0 || cur.y < 0)) ? 1 : -1);
                        if (xprod(constraint[1], off) <= 0) {
                            constraint[1].x = off.x;
                            constraint[1].y = off.y;
                        }
                    }
                    k1 = k;
                    k = nc[k1];
                    if (!cyclic(k, i, k1)) {
                        break;
                    }
                }
                if (foundk === 0) {
                    dk.x = sign(pt[k].x - pt[k1].x);
                    dk.y = sign(pt[k].y - pt[k1].y);
                    cur.x = pt[k1].x - pt[i].x;
                    cur.y = pt[k1].y - pt[i].y;

                    a = xprod(constraint[0], cur);
                    b = xprod(constraint[0], dk);
                    c = xprod(constraint[1], cur);
                    d = xprod(constraint[1], dk);

                    j = 10000000;
                    if (b < 0) {
                        j = Math.floor(a / -b);
                    }
                    if (d > 0) {
                        j = Math.min(j, Math.floor(-c / d));
                    }
                    pivk[i] = mod(k1 + j, n);
                }
            }

            j = pivk[n - 1];
            path.lon[n - 1] = j;
            for (i = n - 2; i >= 0; i--) {
                if (cyclic(i + 1, pivk[i], j)) {
                    j = pivk[i];
                }
                path.lon[i] = j;
            }

            for (i = n - 1; cyclic(mod(i + 1, n), j, path.lon[i]); i--) {
                path.lon[i] = j;
            }
        }

        function bestPolygon(path) {

            function penalty3(path, i, j) {

                var n = path.len, pt = path.pt, sums = path.sums;
                var x, y, xy, x2, y2,
                    k, a, b, c, s,
                    px, py, ex, ey,
                    r = 0;
                if (j >= n) {
                    j -= n;
                    r = 1;
                }

                if (r === 0) {
                    x = sums[j + 1].x - sums[i].x;
                    y = sums[j + 1].y - sums[i].y;
                    x2 = sums[j + 1].x2 - sums[i].x2;
                    xy = sums[j + 1].xy - sums[i].xy;
                    y2 = sums[j + 1].y2 - sums[i].y2;
                    k = j + 1 - i;
                } else {
                    x = sums[j + 1].x - sums[i].x + sums[n].x;
                    y = sums[j + 1].y - sums[i].y + sums[n].y;
                    x2 = sums[j + 1].x2 - sums[i].x2 + sums[n].x2;
                    xy = sums[j + 1].xy - sums[i].xy + sums[n].xy;
                    y2 = sums[j + 1].y2 - sums[i].y2 + sums[n].y2;
                    k = j + 1 - i + n;
                }

                px = (pt[i].x + pt[j].x) / 2.0 - pt[0].x;
                py = (pt[i].y + pt[j].y) / 2.0 - pt[0].y;
                ey = (pt[j].x - pt[i].x);
                ex = -(pt[j].y - pt[i].y);

                a = ((x2 - 2 * x * px) / k + px * px);
                b = ((xy - x * py - y * px) / k + px * py);
                c = ((y2 - 2 * y * py) / k + py * py);

                s = ex * ex * a + 2 * ex * ey * b + ey * ey * c;

                return Math.sqrt(s);
            }

            var i, j, m, k,
                n = path.len,
                pen = new Array(n + 1),
                prev = new Array(n + 1),
                clip0 = new Array(n),
                clip1 = new Array(n + 1),
                seg0 = new Array(n + 1),
                seg1 = new Array(n + 1),
                thispen, best, c;

            for (i = 0; i < n; i++) {
                c = mod(path.lon[mod(i - 1, n)] - 1, n);
                if (c == i) {
                    c = mod(i + 1, n);
                }
                if (c < i) {
                    clip0[i] = n;
                } else {
                    clip0[i] = c;
                }
            }

            j = 1;
            for (i = 0; i < n; i++) {
                while (j <= clip0[i]) {
                    clip1[j] = i;
                    j++;
                }
            }

            i = 0;
            for (j = 0; i < n; j++) {
                seg0[j] = i;
                i = clip0[i];
            }
            seg0[j] = n;
            m = j;

            i = n;
            for (j = m; j > 0; j--) {
                seg1[j] = i;
                i = clip1[i];
            }
            seg1[0] = 0;

            pen[0] = 0;
            for (j = 1; j <= m; j++) {
                for (i = seg1[j]; i <= seg0[j]; i++) {
                    best = -1;
                    for (k = seg0[j - 1]; k >= clip1[i]; k--) {
                        thispen = penalty3(path, k, i) + pen[k];
                        if (best < 0 || thispen < best) {
                            prev[i] = k;
                            best = thispen;
                        }
                    }
                    pen[i] = best;
                }
            }
            path.m = m;
            path.po = new Array(m);

            for (i = n, j = m - 1; i > 0; j--) {
                i = prev[i];
                path.po[j] = i;
            }
        }

        function adjustVertices(path) {

            function pointslope(path, i, j, ctr, dir) {

                var n = path.len, sums = path.sums,
                    x, y, x2, xy, y2,
                    k, a, b, c, lambda2, l, r = 0;

                while (j >= n) {
                    j -= n;
                    r += 1;
                }
                while (i >= n) {
                    i -= n;
                    r -= 1;
                }
                while (j < 0) {
                    j += n;
                    r -= 1;
                }
                while (i < 0) {
                    i += n;
                    r += 1;
                }

                x = sums[j + 1].x - sums[i].x + r * sums[n].x;
                y = sums[j + 1].y - sums[i].y + r * sums[n].y;
                x2 = sums[j + 1].x2 - sums[i].x2 + r * sums[n].x2;
                xy = sums[j + 1].xy - sums[i].xy + r * sums[n].xy;
                y2 = sums[j + 1].y2 - sums[i].y2 + r * sums[n].y2;
                k = j + 1 - i + r * n;

                ctr.x = x / k;
                ctr.y = y / k;

                a = (x2 - x * x / k) / k;
                b = (xy - x * y / k) / k;
                c = (y2 - y * y / k) / k;

                lambda2 = (a + c + Math.sqrt((a - c) * (a - c) + 4 * b * b)) / 2;

                a -= lambda2;
                c -= lambda2;

                if (Math.abs(a) >= Math.abs(c)) {
                    l = Math.sqrt(a * a + b * b);
                    if (l !== 0) {
                        dir.x = -b / l;
                        dir.y = a / l;
                    }
                } else {
                    l = Math.sqrt(c * c + b * b);
                    if (l !== 0) {
                        dir.x = -c / l;
                        dir.y = b / l;
                    }
                }
                if (l === 0) {
                    dir.x = dir.y = 0;
                }
            }

            var m = path.m, po = path.po, n = path.len, pt = path.pt,
                x0 = path.x0, y0 = path.y0,
                ctr = new Array(m), dir = new Array(m),
                q = new Array(m),
                v = new Array(3), d, i, j, k, l,
                s = new Point();

            path.curve = new Curve(m);

            for (i = 0; i < m; i++) {
                j = po[mod(i + 1, m)];
                j = mod(j - po[i], n) + po[i];
                ctr[i] = new Point();
                dir[i] = new Point();
                pointslope(path, po[i], j, ctr[i], dir[i]);
            }

            for (i = 0; i < m; i++) {
                q[i] = new Quad();
                d = dir[i].x * dir[i].x + dir[i].y * dir[i].y;
                if (d === 0.0) {
                    for (j = 0; j < 3; j++) {
                        for (k = 0; k < 3; k++) {
                            q[i].data[j * 3 + k] = 0;
                        }
                    }
                } else {
                    v[0] = dir[i].y;
                    v[1] = -dir[i].x;
                    v[2] = - v[1] * ctr[i].y - v[0] * ctr[i].x;
                    for (l = 0; l < 3; l++) {
                        for (k = 0; k < 3; k++) {
                            q[i].data[l * 3 + k] = v[l] * v[k] / d;
                        }
                    }
                }
            }

            var Q, w, dx, dy, det, min, cand, xmin, ymin, z;
            for (i = 0; i < m; i++) {
                Q = new Quad();
                w = new Point();

                s.x = pt[po[i]].x - x0;
                s.y = pt[po[i]].y - y0;

                j = mod(i - 1, m);

                for (l = 0; l < 3; l++) {
                    for (k = 0; k < 3; k++) {
                        Q.data[l * 3 + k] = q[j].at(l, k) + q[i].at(l, k);
                    }
                }

                while (1) {

                    det = Q.at(0, 0) * Q.at(1, 1) - Q.at(0, 1) * Q.at(1, 0);
                    if (det !== 0.0) {
                        w.x = (-Q.at(0, 2) * Q.at(1, 1) + Q.at(1, 2) * Q.at(0, 1)) / det;
                        w.y = (Q.at(0, 2) * Q.at(1, 0) - Q.at(1, 2) * Q.at(0, 0)) / det;
                        break;
                    }

                    if (Q.at(0, 0) > Q.at(1, 1)) {
                        v[0] = -Q.at(0, 1);
                        v[1] = Q.at(0, 0);
                    } else if (Q.at(1, 1)) {
                        v[0] = -Q.at(1, 1);
                        v[1] = Q.at(1, 0);
                    } else {
                        v[0] = 1;
                        v[1] = 0;
                    }
                    d = v[0] * v[0] + v[1] * v[1];
                    v[2] = - v[1] * s.y - v[0] * s.x;
                    for (l = 0; l < 3; l++) {
                        for (k = 0; k < 3; k++) {
                            Q.data[l * 3 + k] += v[l] * v[k] / d;
                        }
                    }
                }
                dx = Math.abs(w.x - s.x);
                dy = Math.abs(w.y - s.y);
                if (dx <= 0.5 && dy <= 0.5) {
                    path.curve.vertex[i] = new Point(w.x + x0, w.y + y0);
                    continue;
                }

                min = quadform(Q, s);
                xmin = s.x;
                ymin = s.y;

                if (Q.at(0, 0) !== 0.0) {
                    for (z = 0; z < 2; z++) {
                        w.y = s.y - 0.5 + z;
                        w.x = - (Q.at(0, 1) * w.y + Q.at(0, 2)) / Q.at(0, 0);
                        dx = Math.abs(w.x - s.x);
                        cand = quadform(Q, w);
                        if (dx <= 0.5 && cand < min) {
                            min = cand;
                            xmin = w.x;
                            ymin = w.y;
                        }
                    }
                }

                if (Q.at(1, 1) !== 0.0) {
                    for (z = 0; z < 2; z++) {
                        w.x = s.x - 0.5 + z;
                        w.y = - (Q.at(1, 0) * w.x + Q.at(1, 2)) / Q.at(1, 1);
                        dy = Math.abs(w.y - s.y);
                        cand = quadform(Q, w);
                        if (dy <= 0.5 && cand < min) {
                            min = cand;
                            xmin = w.x;
                            ymin = w.y;
                        }
                    }
                }

                for (l = 0; l < 2; l++) {
                    for (k = 0; k < 2; k++) {
                        w.x = s.x - 0.5 + l;
                        w.y = s.y - 0.5 + k;
                        cand = quadform(Q, w);
                        if (cand < min) {
                            min = cand;
                            xmin = w.x;
                            ymin = w.y;
                        }
                    }
                }

                path.curve.vertex[i] = new Point(xmin + x0, ymin + y0);
            }
        }

        function reverse(path) {
            var curve = path.curve, m = curve.n, v = curve.vertex, i, j, tmp;

            for (i = 0, j = m - 1; i < j; i++ , j--) {
                tmp = v[i];
                v[i] = v[j];
                v[j] = tmp;
            }
        }

        function smooth(path) {
            var m = path.curve.n, curve = path.curve;

            var i, j, k, dd, denom, alpha,
                p2, p3, p4;

            for (i = 0; i < m; i++) {
                j = mod(i + 1, m);
                k = mod(i + 2, m);
                p4 = interval(1 / 2.0, curve.vertex[k], curve.vertex[j]);

                denom = ddenom(curve.vertex[i], curve.vertex[k]);
                if (denom !== 0.0) {
                    dd = dpara(curve.vertex[i], curve.vertex[j], curve.vertex[k]) / denom;
                    dd = Math.abs(dd);
                    alpha = dd > 1 ? (1 - 1.0 / dd) : 0;
                    alpha = alpha / 0.75;
                } else {
                    alpha = 4 / 3.0;
                }
                curve.alpha0[j] = alpha;

                if (alpha >= info.alphamax) {
                    curve.tag[j] = "CORNER";
                    curve.c[3 * j + 1] = curve.vertex[j];
                    curve.c[3 * j + 2] = p4;
                } else {
                    if (alpha < 0.55) {
                        alpha = 0.55;
                    } else if (alpha > 1) {
                        alpha = 1;
                    }
                    p2 = interval(0.5 + 0.5 * alpha, curve.vertex[i], curve.vertex[j]);
                    p3 = interval(0.5 + 0.5 * alpha, curve.vertex[k], curve.vertex[j]);
                    curve.tag[j] = "CURVE";
                    curve.c[3 * j + 0] = p2;
                    curve.c[3 * j + 1] = p3;
                    curve.c[3 * j + 2] = p4;
                }
                curve.alpha[j] = alpha;
                curve.beta[j] = 0.5;
            }
            curve.alphacurve = 1;
        }

        function optiCurve(path) {
            function Opti() {
                this.pen = 0;
                this.c = [new Point(), new Point()];
                this.t = 0;
                this.s = 0;
                this.alpha = 0;
            }

            function opti_penalty(path, i, j, res, opttolerance, convc, areac) {
                var m = path.curve.n, curve = path.curve, vertex = curve.vertex,
                    k, k1, k2, conv, i1,
                    area, alpha, d, d1, d2,
                    p0, p1, p2, p3, pt,
                    A, R, A1, A2, A3, A4,
                    s, t;

                if (i == j) {
                    return 1;
                }

                k = i;
                i1 = mod(i + 1, m);
                k1 = mod(k + 1, m);
                conv = convc[k1];
                if (conv === 0) {
                    return 1;
                }
                d = ddist(vertex[i], vertex[i1]);
                for (k = k1; k != j; k = k1) {
                    k1 = mod(k + 1, m);
                    k2 = mod(k + 2, m);
                    if (convc[k1] != conv) {
                        return 1;
                    }
                    if (sign(cprod(vertex[i], vertex[i1], vertex[k1], vertex[k2])) !=
                        conv) {
                        return 1;
                    }
                    if (iprod1(vertex[i], vertex[i1], vertex[k1], vertex[k2]) <
                        d * ddist(vertex[k1], vertex[k2]) * -0.999847695156) {
                        return 1;
                    }
                }

                p0 = curve.c[mod(i, m) * 3 + 2].copy();
                p1 = vertex[mod(i + 1, m)].copy();
                p2 = vertex[mod(j, m)].copy();
                p3 = curve.c[mod(j, m) * 3 + 2].copy();

                area = areac[j] - areac[i];
                area -= dpara(vertex[0], curve.c[i * 3 + 2], curve.c[j * 3 + 2]) / 2;
                if (i >= j) {
                    area += areac[m];
                }

                A1 = dpara(p0, p1, p2);
                A2 = dpara(p0, p1, p3);
                A3 = dpara(p0, p2, p3);

                A4 = A1 + A3 - A2;

                if (A2 == A1) {
                    return 1;
                }

                t = A3 / (A3 - A4);
                s = A2 / (A2 - A1);
                A = A2 * t / 2.0;

                if (A === 0.0) {
                    return 1;
                }

                R = area / A;
                alpha = 2 - Math.sqrt(4 - R / 0.3);

                res.c[0] = interval(t * alpha, p0, p1);
                res.c[1] = interval(s * alpha, p3, p2);
                res.alpha = alpha;
                res.t = t;
                res.s = s;

                p1 = res.c[0].copy();
                p2 = res.c[1].copy();

                res.pen = 0;

                for (k = mod(i + 1, m); k != j; k = k1) {
                    k1 = mod(k + 1, m);
                    t = tangent(p0, p1, p2, p3, vertex[k], vertex[k1]);
                    if (t < -0.5) {
                        return 1;
                    }
                    pt = bezier(t, p0, p1, p2, p3);
                    d = ddist(vertex[k], vertex[k1]);
                    if (d === 0.0) {
                        return 1;
                    }
                    d1 = dpara(vertex[k], vertex[k1], pt) / d;
                    if (Math.abs(d1) > opttolerance) {
                        return 1;
                    }
                    if (iprod(vertex[k], vertex[k1], pt) < 0 ||
                        iprod(vertex[k1], vertex[k], pt) < 0) {
                        return 1;
                    }
                    res.pen += d1 * d1;
                }

                for (k = i; k != j; k = k1) {
                    k1 = mod(k + 1, m);
                    t = tangent(p0, p1, p2, p3, curve.c[k * 3 + 2], curve.c[k1 * 3 + 2]);
                    if (t < -0.5) {
                        return 1;
                    }
                    pt = bezier(t, p0, p1, p2, p3);
                    d = ddist(curve.c[k * 3 + 2], curve.c[k1 * 3 + 2]);
                    if (d === 0.0) {
                        return 1;
                    }
                    d1 = dpara(curve.c[k * 3 + 2], curve.c[k1 * 3 + 2], pt) / d;
                    d2 = dpara(curve.c[k * 3 + 2], curve.c[k1 * 3 + 2], vertex[k1]) / d;
                    d2 *= 0.75 * curve.alpha[k1];
                    if (d2 < 0) {
                        d1 = -d1;
                        d2 = -d2;
                    }
                    if (d1 < d2 - opttolerance) {
                        return 1;
                    }
                    if (d1 < d2) {
                        res.pen += (d1 - d2) * (d1 - d2);
                    }
                }

                return 0;
            }

            var curve = path.curve, m = curve.n, vert = curve.vertex,
                pt = new Array(m + 1),
                pen = new Array(m + 1),
                len = new Array(m + 1),
                opt = new Array(m + 1),
                om, i, j, r,
                o = new Opti(), p0,
                i1, area, alpha, ocurve,
                s, t;

            var convc = new Array(m), areac = new Array(m + 1);

            for (i = 0; i < m; i++) {
                if (curve.tag[i] == "CURVE") {
                    convc[i] = sign(dpara(vert[mod(i - 1, m)], vert[i], vert[mod(i + 1, m)]));
                } else {
                    convc[i] = 0;
                }
            }

            area = 0.0;
            areac[0] = 0.0;
            p0 = curve.vertex[0];
            for (i = 0; i < m; i++) {
                i1 = mod(i + 1, m);
                if (curve.tag[i1] == "CURVE") {
                    alpha = curve.alpha[i1];
                    area += 0.3 * alpha * (4 - alpha) *
                        dpara(curve.c[i * 3 + 2], vert[i1], curve.c[i1 * 3 + 2]) / 2;
                    area += dpara(p0, curve.c[i * 3 + 2], curve.c[i1 * 3 + 2]) / 2;
                }
                areac[i + 1] = area;
            }

            pt[0] = -1;
            pen[0] = 0;
            len[0] = 0;


            for (j = 1; j <= m; j++) {
                pt[j] = j - 1;
                pen[j] = pen[j - 1];
                len[j] = len[j - 1] + 1;

                for (i = j - 2; i >= 0; i--) {
                    r = opti_penalty(path, i, mod(j, m), o, info.opttolerance, convc,
                        areac);
                    if (r) {
                        break;
                    }
                    if (len[j] > len[i] + 1 ||
                        (len[j] == len[i] + 1 && pen[j] > pen[i] + o.pen)) {
                        pt[j] = i;
                        pen[j] = pen[i] + o.pen;
                        len[j] = len[i] + 1;
                        opt[j] = o;
                        o = new Opti();
                    }
                }
            }
            om = len[m];
            ocurve = new Curve(om);
            s = new Array(om);
            t = new Array(om);

            j = m;
            for (i = om - 1; i >= 0; i--) {
                if (pt[j] == j - 1) {
                    ocurve.tag[i] = curve.tag[mod(j, m)];
                    ocurve.c[i * 3 + 0] = curve.c[mod(j, m) * 3 + 0];
                    ocurve.c[i * 3 + 1] = curve.c[mod(j, m) * 3 + 1];
                    ocurve.c[i * 3 + 2] = curve.c[mod(j, m) * 3 + 2];
                    ocurve.vertex[i] = curve.vertex[mod(j, m)];
                    ocurve.alpha[i] = curve.alpha[mod(j, m)];
                    ocurve.alpha0[i] = curve.alpha0[mod(j, m)];
                    ocurve.beta[i] = curve.beta[mod(j, m)];
                    s[i] = t[i] = 1.0;
                } else {
                    ocurve.tag[i] = "CURVE";
                    ocurve.c[i * 3 + 0] = opt[j].c[0];
                    ocurve.c[i * 3 + 1] = opt[j].c[1];
                    ocurve.c[i * 3 + 2] = curve.c[mod(j, m) * 3 + 2];
                    ocurve.vertex[i] = interval(opt[j].s, curve.c[mod(j, m) * 3 + 2],
                        vert[mod(j, m)]);
                    ocurve.alpha[i] = opt[j].alpha;
                    ocurve.alpha0[i] = opt[j].alpha;
                    s[i] = opt[j].s;
                    t[i] = opt[j].t;
                }
                j = pt[j];
            }

            for (i = 0; i < om; i++) {
                i1 = mod(i + 1, om);
                ocurve.beta[i] = s[i] / (s[i] + t[i1]);
            }
            ocurve.alphacurve = 1;
            path.curve = ocurve;
        }

        for (var i = 0; i < pathlist.length; i++) {
            var path = pathlist[i];
            calcSums(path);
            calcLon(path);
            bestPolygon(path);
            adjustVertices(path);

            if (path.sign === "-") {
                reverse(path);
            }

            smooth(path);

            if (info.optcurve) {
                optiCurve(path);
            }
        }

    }

    function process(c) {
        if (c) {
            callback = c;
        }
        if (!info.isReady) {
            setTimeout(process, 100);
            return;
        }
        bmToPathlist();
        processPath();
        callback();
        setTimeout(function () {
            callback = null;
        });
    }

    function clear() {
        bm = null;
        pathlist = [];
        callback = null;
        info.isReady = false;
    }

    function getSVG(size, opt_type, onlyPath) {

        function path(curve) {

            function bezier(i) {
                var b = 'C ' + (curve.c[i * 3 + 0].x * size).toFixed(3) + ' ' +
                    (curve.c[i * 3 + 0].y * size).toFixed(3) + ',';
                b += (curve.c[i * 3 + 1].x * size).toFixed(3) + ' ' +
                    (curve.c[i * 3 + 1].y * size).toFixed(3) + ',';
                b += (curve.c[i * 3 + 2].x * size).toFixed(3) + ' ' +
                    (curve.c[i * 3 + 2].y * size).toFixed(3) + ' ';
                return b;
            }

            function segment(i) {
                var s = 'L ' + (curve.c[i * 3 + 1].x * size).toFixed(3) + ' ' +
                    (curve.c[i * 3 + 1].y * size).toFixed(3) + ' ';
                s += (curve.c[i * 3 + 2].x * size).toFixed(3) + ' ' +
                    (curve.c[i * 3 + 2].y * size).toFixed(3) + ' ';
                return s;
            }

            var n = curve.n, i;
            var p = 'M' + (curve.c[(n - 1) * 3 + 2].x * size).toFixed(3) +
                ' ' + (curve.c[(n - 1) * 3 + 2].y * size).toFixed(3) + ' ';
            for (i = 0; i < n; i++) {
                if (curve.tag[i] === "CURVE") {
                    p += bezier(i);
                } else if (curve.tag[i] === "CORNER") {
                    p += segment(i);
                }
            }
            //p += 
            return p;
        }

        var w = bm.w * size, h = bm.h * size,
            len = pathlist.length, c, i, strokec, fillc, fillrule;
        var pathcmd = '';
        for (i = 0; i < len; i++) {
            c = pathlist[i].curve;
            //svg += path(c);
            pathcmd += utils.renderCurve(c, 1);
        }

        if( onlyPath ) return {
            pathcmd: pathcmd,
            needResize: info.needResize
        };

        var svg = '<svg version="1.1" width="' + w + '" height="' + h + '"' + ' viewBox="0 0 ' + w + ' ' + h + '" ' + ' xmlns="http://www.w3.org/2000/svg">';
        if (opt_type === "curve") {
            strokec = info.outline;
            fillc = "none";
            fillrule = '';
        } else {
            strokec = "none";
            fillc = info.color;
            fillrule = ' fill-rule="evenodd"';
        }
        svg += '<defs><clipPath id="stiker_contour"><path d="' + pathcmd + '" /></clipPath></defs>';
        svg += '<path d="';
        svg += pathcmd;
        svg += '" stroke="' + strokec + '" fill="' + fillc + '"' + fillrule + '/></svg>';
        return svg;
    }

    return {
        loadData: loadData,
        setParameter: setParameter,
        process: process,
        getSVG: getSVG,
        getImg: getImg,
        clear: clear
    };
})();