Drawing path point simplification / reduction in JavaScript

canvas, drawing, javascript, math

Solution

You could subdivide the spline segment recursively, until they are almost a straight line.

function Subdivide( C : Curve, maxDepth : int ) begin if maxDepth ≤ 1 or Polyline-Length( C ) ≤ 1px or StraightLineMeasure( C ) < ϵ then return List-Single( C ) end C1, C2 ← Split( C ) return List-Concat( Subdivide( C1, maxDepth - 1 ), Subdivide( C2, maxDepth - 1 ) ) end

where Polyline-Length calculates the length of the poly-line formed by the control points. StraightLineMeasure returns zero for a straight line, and a small number for almost straight lines. Split returns two sets of control points, each of which represents half of the original curve.

B-Splines are easy to subdivide (pdf).

(click here for demo)

Here is an implementation in javascript:

$(function() {
    var canvas = document.createElement('canvas');
    document.body.appendChild(canvas);

    var ctx = canvas.getContext('2d');
    ctx.fillStyle = '#f00';
    ctx.strokeStyle = '#f00';
    ctx.lineWidth = 1;

    var segments = BSplineSegment.FromBSpline([
        new Vector(10, 10),
        new Vector(110, 10),
        new Vector(110, 110),
        new Vector(10, 110),
        new Vector(10, 10),
        new Vector(110, 10),
        new Vector(110, 110)
        ]);

    for (var i = 0; i < segments.length; i++) {
        var subsegments = segments[i].subdivide(30);
        for (var j = 0; j < subsegments.length; j++) {
            var bss = subsegments[j];
            ctx.fillRect(bss.p1.x, bss.p1.y, 1, 1);
        }
    }

    var segment = new BSplineSegment(
        new Vector(110, 10), new Vector(210, 10),
        new Vector(110, 110), new Vector(210, 110));
    subsegments = segment.subdivide(50);
    for (var j = 0; j < subsegments.length; j++) {
        var bss = subsegments[j];
        ctx.fillRect(bss.p1.x, bss.p1.y, 1, 1);
    }
});

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

Vector.prototype = {
    lengthSquared: function() {
        return this.x * this.x + this.y * this.y;
    },
    length: function() {
        return Math.sqrt(this.lengthSquared());
    },
    add: function(other) {
        return new Vector(this.x + other.x, this.y + other.y);
    },
    sub: function(other) {
        return new Vector(this.x - other.x, this.y - other.y);
    },
    mul: function(scale) {
        return new Vector(this.x * scale, this.y * scale);
    },
    div: function(scale) {
        return new Vector(this.x / scale, this.y / scale);
    },
    cross: function(other) {
        return this.x * other.y - this.y * other.x;
    },
};


function BSplineSegment(p0, p1, p2, p3) {
    this.p0 = p0;
    this.p1 = p1;
    this.p2 = p2;
    this.p3 = p3;
};

BSplineSegment.FromBSpline = function(pts) {
    var n = pts.length;
    var segments = [];
    for (var i = 3; i < n; i++) {
        segments.push(new BSplineSegment(pts[i - 3], pts[i - 2], pts[i - 1], pts[i]));
    }
    return segments;
};

BSplineSegment.prototype = {
    polylineLength: function() {
        return this.p2.sub(this.p1).length();
    },
    straightLineMeasure: function() {
        var det0 = this.p1.cross(this.p2);
        var det1 = det0 + this.p2.cross(this.p0) + this.p0.cross(this.p1);
        var det2 = det0 + this.p2.cross(this.p3) + this.p3.cross(this.p1);
        return (Math.abs(det1) + Math.abs(det2)) / this.p2.sub(this.p1).length();
    },
    split: function() {
        var p0 = this.p0.add(this.p1).mul(0.5);
        var p1 = this.p0.add(this.p1.mul(6)).add(this.p2).mul(0.125);
        var p2 = this.p1.add(this.p2).mul(0.5);
        var p3 = this.p1.add(this.p2.mul(6)).add(this.p3).mul(0.125);
        var p4 = this.p2.add(this.p3).mul(0.5);
        return [new BSplineSegment(p0, p1, p2, p3), new BSplineSegment(p1, p2, p3, p4)];
    },
    subdivide: function(maxLevels) {
        if (maxLevels <= 0 || this.polylineLength() < 1.0 || this.straightLineMeasure() < 1.0) {
            return [this];
        }
        else {
            var children = this.split();
            var left = children[0].subdivide(maxLevels - 1);
            var right = children[1].subdivide(maxLevels - 1);
            return left.concat(right);
        }
    }
};​

Problem

We are developing an drawing application for iOS and android. I am using cubic quadratic curves to draw smooth curves because cubic Bézier curve is way slow to draw on mobile devices(mostly pads). Drawing long quadratic curve with lot of points is still slow in pads so I am trying to reduce points I have to plot on canvas to speed up drawing. I have tried, - Catmull-Rom splines - Ramer-Douglas-Peucker but they are for cubic curves and not has not working properly for quad-curves. Is there any algorithm or techniques for quad curves as well? can any other optimization be done to speed up path drawing?

Original source