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

Question

我们正在开发适用于 iOS 和 android 的绘图应用程序。我正在使用三次二次曲线来绘制平滑曲线，因为三次贝塞尔曲线在移动设备（主要是垫）上绘制速度很慢。

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

我试过了，

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

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

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

Answer 1

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

如果maxDepth ≤ 1或Polyline-Length( C ) ≤ 1px或StraightLineMeasure( C ) < ϵ则开始函数Subdivide( C : Curve, maxDepth : int )然后返回List-Single( C ) end C1 , C2 ← Split( C )返回List-Concat（细分（C1，maxDepth - 1），细分（C2，maxDepth - 1））结束

   
       
   
   
   

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

B样条线很容易细分（pdf）。

---

（点击这里查看演示）

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