SVG Paths parser

gistfile1.js

// === PATHS ===================================================================

// M<X> <Y> - move to
// L<X> <Y> - line to
// C<X1> <Y1> <X2> <Y2> <X3> <Y3> - curve to
// Z - close path
// lowercase marker means relative coord
// Example: "M0 10 L20 20 C10 20 15 30 10 9 Z"

// all commands:
// V = vertical lineto
// C = curveto
// S = smooth curveto
// Q = quadratic Bézier curve
// T = smooth quadratic Bézier curveto
// A = elliptical Arc
// Z = closepath

// Currently our format differs in a number format:
// "M0.0 10.0 L20.0 20.0 C10.0 20.0 15.0 30.0 10.0 9.0 Z"
// ======================================================

// > Path % (str: String) 
function Path(str) {
    this.str = str;
    this.segs = [];
    this.parse(str); 
}
// visits every chunk of path in array-form and calls
// visitor function, so visitor function gets 
// chunk marker and positions sequentially
// data argument will be also passed to visitor if specified
// > Path.visit % (visitor: Function[Segment, Any], data: Any)
Path.prototype.visit = function(visitor, data) {
    var segments = this.segs;
    for (var i = 0; i < segments.length; i++) {
        visitor(segments[i], data);
    }
}
// path length, in points
// > Path.length % () => Double
Path.prototype.length = function() {
    var sum = 0;
    var p = [ this.segs[0].pts[0], // start-x
              this.segs[0].pts[1] ]; // start-y
    this.visit(function(segment) {
        sum += segment.length(p);
        var pts = segment.pts;
        p = [ pts[pts.length - 2],
              pts[pts.length - 1] ];
    });
    return sum;
}
// > Path.add % (seg: Segment)
Path.prototype.add = function(seg) {
    this.segs.push(seg);
}
// > Path.apply % (ctx: Context)
Path.prototype.apply = function(ctx) {
    this.visit(this.__apply_visitor,ctx);
}
Path.prototype.__apply_visitor = function(segment, ctx) {
    var marker = segment.type;
    var positions = segment.pts;
    if (marker === Path.P_MOVETO) {
        ctx.moveTo(positions[0], positions[1]);
    } else if (marker === Path.P_LINETO) {
        ctx.lineTo(positions[0], positions[1]);
    } else if (marker === Path.P_CURVETO) {
        ctx.bezierCurveTo(positions[0], positions[1],
                          positions[2], positions[3],
                          positions[4], positions[5]);
    }
}
// > Path.parse % (str: String) => Path
Path.prototype.parse = function(str) {
    if (str) __parse_path(str, this);
    return this;
}
// find a segment data in a path that corresponds to specified distance (t) 
// of the path (0..1), 
// > Path.hit_at % (t: [0..1]) => Array[Int, 2]
Path.prototype.hit_at = function(t, func) {
    var startp = this.start();
    if (t === 0) return {
          'seg': this.segs[0], 'start': startp, 'slen': 0.0, 'segt': 0.0 
        };
    var endp = this.end();
    /*if (t == 1) return func ? func(startp, endp) : endp;*/

    var plen = this.length(); // path length in pixels
    var nsegs = this.segs.length; // number of segments
    var distance = t * plen;
    var p = startp;
    var length = 0; // checked length in pixels
    for (var si = 0; si < nsegs; si++) {
        var seg = this.segs[si];
        var slen = seg.length(p); // segment length
        if (distance <= (length + slen)) {
            // inside current segment
            var segdist = distance - length;
            return {
              'seg': seg, 'start': p, 'slen': slen, 'segt': (segdist / slen) 
            };
        }
        length += slen;
        // end point of segment
        p = seg.last();
    };
    var lseg = this.segs[this.segs.length - 1];
    return {
      'seg': lseg, 'start': p, 'slen': lseg.length(p), 'segt': 1.0
    };
}
// find a point on a path at specified distance (t) of the path (0..1), 
// a function that transforms the result point (using given start point of
// segment and a point on a segment) may be passed
// > Path.point_at % (t: [0..1]) => Array[Int, 2]
Path.prototype.point_at = function(t) {
    var hit = this.hit_at(t);
    return hit.seg.at_t(hit.start, hit.segt);
}
// find a tangent on a path at specified distance (t) of the path (0..1)
// > Path.tangent_at % (t: [0..1]) => Double
Path.prototype.tangent_at = function(t) { 
    var hit = this.hit_at(t);
    return hit.seg.tangent_at(hit.start, hit.segt);
}
Path.prototype.start = function() {
    return [ this.segs[0].pts[0],   // first-x
             this.segs[0].pts[1] ]; // first-y
}
Path.prototype.end = function() {
    var lastidx = this.segs.length - 1;
    var s = this.segs[lastidx].count; // size of the last segment
    return [ this.segs[lastidx].pts[s-2],   // last-x
             this.segs[lastidx].pts[s-1] ]; // last-y
}

// path constants
Path.P_MOVETO = 0;
Path.P_LINETO = 1;
Path.P_CURVETO = 2;

function MSeg(pts) {
    this.type = Path.P_MOVETO;
    this.pts = pts;
    this.count = pts.length;
}
// > MSeg.length(start: Array[Int,2]) => Double
MSeg.prototype.length = function(start) {
    return 0;
}
// distance is specified in points
MSeg.prototype.at_dist = function(start, dist) {
    return [ this.pts[0], this.pts[1] ];
}
MSeg.prototype.at_t = function(start, t) {
    return this.at_dist(start, null);
}
MSeg.prototype.tangent_at = function(start, t) {
    return [0, 0];
}
MSeg.prototype.last = function() {
    return [ this.pts[0], this.pts[1] ];
}

function LSeg(pts) {
    this.type = Path.P_LINETO;
    this.pts = pts;
    this.count = pts.length;    
}
LSeg.prototype.length = function(start) {
    var dx = this.pts[0] - start[0];
    var dy = this.pts[1] - start[1];
    return Math.sqrt(dx*dx + dy*dy);
}
LSeg.prototype.at_dist = function(start, dist) {
    return this.at_t(start, dist / this.length(start));
}
LSeg.prototype.at_t = function(start, t) {
    var p0x = start[0];
    var p0y = start[1]; 
    var p1x = this.pts[0];
    var p1y = this.pts[1];
    return [
        p0x + (p1x - p0x) * t,
        p0y + (p1y - p0y) * t
    ];
}
LSeg.prototype.tangent_at = function(start, t) {
    return Math.atan2(this.pts[1] - start[1],
                      this.pts[0] - start[0]);
}
LSeg.prototype.last = function() {
    return [ this.pts[0], this.pts[1] ];
}

function CSeg(pts) {
    this.type = Path.P_CURVETO;
    this.pts = pts;
    this.count = pts.length;
}
CSeg.prototype.length = function(start) {
    // FIXME: cache length data and points somewhere
    var positions = this.pts;
    var p0x = start[0];
    var p0y = start[1];
    var p1x = positions[0];
    var p1y = positions[1];
    var p2x = positions[2];
    var p2y = positions[3];
    var p3x = positions[4];
    var p3y = positions[5];

    var p0to1 = Math.sqrt(Math.pow(p1x-p0x, 2) + Math.pow(p1y-p0y, 2));
    var p1to2 = Math.sqrt(Math.pow(p2x-p1x, 2) + Math.pow(p2y-p1y, 2));
    var p2to3 = Math.sqrt(Math.pow(p3x-p2x, 2) + Math.pow(p3y-p2y, 2));

    var len = p0to1 + p1to2 + p2to3 + 1;
    
    var count = len * 3;
    
    // choose the step as 1/len
    var dt = 1.0 / len;

    var q1 = 3 * dt;
    var q2 = q1 * dt;
    var q3 = dt * dt * dt;
    var q4 = 2 * q2;
    var q5 = 6 * q3;

    var q6x = p0x - 2 * p1x + p2x;
    var q6y = p0y - 2 * p1y + p2y;

    var q7x = 3 * (p1x - p2x) - p0x + p3x;
    var q7y = 3 * (p1y - p2y) - p0y + p3y;

    var bx = p0x;
    var by = p0y;

    var dbx = (p1x - p0x) * q1 + q6x * q2 + q3 * q7x;
    var dby = (p1y - p0y) * q1 + q6y * q2 + q3 * q7y;

    var ddbx = q6x * q4 + q7x * q5;
    var ddby = q6y * q4 + q7y * q5;

    var dddbx = q7x * q5;
    var dddby = q7y * q5;

    var length = 0;
    for (var idx = 0; idx < count; idx += 3) {
        var px = bx;
        var py = by;

        bx += dbx;
        by += dby;

        dbx += ddbx;
        dby += ddby;

        ddbx += dddbx;
        ddby += dddby;

        length += Math.sqrt((bx - px) * (bx - px) + (by - py) * (by - py));
    } 
    return length; 
}
CSeg.prototype.at_dist = function(start, dist) {
    return this.at_t(start, dist / this.length(start));
}
CSeg.prototype.at_t = function(start, t) {
    this._ensure_params(start);
    var par = this._params;
    var tt = t * t; // t^2
    var ttt = tt * t; // t^3

    return [ par[0] * ttt + par[1] * tt + par[2] * t + par[3],
             par[4] * ttt + par[5] * tt + par[6] * t + par[7] ];
}
CSeg.prototype.last = function() {
    return [ this.pts[4], this.pts[5] ];
}
CSeg.prototype.tangent_at = function(start, t) {
    this._ensure_params(start);
    var par = this._params;
    var tt = t * t; // t^2
    var p = [ 3 * par[0] * tt + 2 * par[1] * t + par[2],
              3 * par[4] * tt + 2 * par[5] * t + par[6] ];
    return Math.atan2(p[1], p[0]);
}
CSeg.prototype._ensure_params = function(start) {
    if (this._lstart && 
        (this._lstart[0] === start[0]) &&
        (this._lstart[1] === start[1])) return;
    this._lstart = start;
    this._params = this._calc_params(start);
}
CSeg.prototype._calc_params = function(start) {
    var pts = this.pts;
    var params = [];
    var p0x = start[0];
    var p0y = start[1];
    var p1x = pts[0];
    var p1y = pts[1];
    var p2x = pts[2];
    var p2y = pts[3];
    var p3x = pts[4];
    var p3y = pts[5];
    
    params[0] = p3x - 3*p2x + 3*p1x - p0x;  // A = x3 - 3 * x2 + 3 * x1 - x0
    params[1] = 3*p2x - 6*p1x + 3*p0x;      // B = 3 * x2 - 6 * x1 + 3 * x0
    params[2] = 3*p1x - 3*p0x;              // C = 3 * x1 - 3 * x0
    params[3] = p0x;                        // D = x0

    params[4] = p3y - 3*p2y + 3*p1y - p0y;  // E = y3 - 3 * y2 + 3 * y1 - y0
    params[5] = 3*p2y - 6*p1y + 3*p0y;      // F = 3 * y2 - 6 * y1 + 3 * y0
    params[6] = 3*p1y - 3*p0y;              // G = 3 * y1 - 3 * y0
    params[7] = p0y;                        // H = y0

    return params;
}

// parses `count` positions from path (string form), 
// starting at `start`, returns a length of parsed data and 
// positions array
function __collect_positions(path, start, count) {
    var pos = start + 1;
    var positions = [];
    var got = 0;
    while (got != count) {
        var posstr = __collect_to(path, pos, ' ');
        pos += posstr.length + 1; got++;
        positions.push(parseFloat(posstr));        
    }
    return [pos - start, positions];
}
MSeg.prototype.first = function() {
    return [ this.pts[0], this.pts[1] ];
}
MSeg.prototype.last = function() {
    return this.first();
}

// visits every chunk of path in string-form and calls
// visitor function, so visitor function gets 
// chunk marker and positions sequentially
// data argument will be also passed to visitor if specified
function __visit_str_path(path, visitor, data) {
    var cur_pos = 0;
    while (true) {
        var marker = path[cur_pos];
        if (marker === 'Z') {
            visitor(marker, [], data);
            return;
        }
        var pos_data = null;
        if ((marker === 'M') || (marker === 'L')) {
            pos_data = __collect_positions(path, cur_pos, 2);
        } else if (marker === 'C') {
            pos_data = __collect_positions(path, cur_pos, 6);
        }
        cur_pos += pos_data[0];
        var positions = pos_data[1];
        visitor(marker, positions, data);
    }
}

// visitor to parse a string path into Path object
function __path_parser_visitor(marker, positions, path) {
    if (marker === 'M') {
        path.add(new MSeg(positions));         
    } else if (marker === 'L') {
        path.add(new LSeg(positions));
    } else if (marker === 'C') {
        path.add(new CSeg(positions));
    }
}

// visitor to apply string path to context
function __str_path_apply_visitor(marker, positions, ctx) {
    //console.log(marker, positions);
    if (marker === 'M') {
        ctx.moveTo(positions[0], positions[1]);
    } else if (marker === 'L') {
        ctx.lineTo(positions[0], positions[1]);
    } else if (marker === 'C') {
        ctx.bezierCurveTo(positions[0], positions[1],
                          positions[2], positions[3],
                          positions[4], positions[5]);
    }
};

// converts path given in string form to array of segments
function __parse_path(path, target) {
    __visit_str_path(path, __path_parser_visitor, target);
    return target;
}

// parses a path in string form and immediately applies it to context
function __parse_and_apply(ctx, path) {
    __visit_str_path(path, __str_path_apply_visitor, ctx);
}