javascript - 在 JavaScript 中绘制路径点简化/减少

Question

我们正在为 iOS 和 android 开发绘图应用程序。我正在使用三次二次曲线绘制平滑曲线，因为三次贝塞尔曲线在移动设备(主要是平板电脑)上绘制速度很慢。

在 pad 中绘制带有很多点的长二次曲线仍然很慢，所以我试图减少我必须在 Canvas 上绘制的点以加快绘制速度。

我试过了，

1. Catmull-Rom 样条
2. 拉默-道格拉斯-普克

但它们适用于三次曲线而不是四线曲线。

四边形曲线是否也有任何算法或技术？可以做任何其他优化来加速路径绘制吗？

Answer 1

您可以递归地分割样条线段，直到它们几乎是一条直线。

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

在哪里
Polyline-Length 计算由控制点形成的折线的长度。
StraightLineMeasure 对直线返回零，对几乎是直线返回一个小数。
Split 返回两组控制点，每组代表原始曲线的一半。

B 样条曲线是 easy to subdivide (pdf) .

---

(click here for demo)

这是 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);
        }
    }
};​