Longueur d'arc de courbe de Bézier

Voir aussi: même question sur Math.SE

Comment puis-je trouver la longueur d'arc d'une courbe de Bézier? Par exemple, une courbe de Bézier linéaire a la longueur:

length = sqrt(pow(x[1] - x[0], 2) + pow(y[1] - y[0], 2));

Mais qu'en est-il des courbes de Bézier quadratiques, cubiques ou à n degrés?

(Mon objectif était d'estimer une résolution d'échantillonnage à l'avance, donc je n'ai pas à perdre de temps à vérifier si le point suivant touche le point précédent.)

Une méthode simple pour les Béziers cubiques consiste à diviser la courbe en N segments et à additionner les longueurs des segments.

Cependant, dès que vous aurez besoin de la longueur d'une partie seulement de la courbe (par exemple jusqu'à un point 30% de la longueur), le paramétrage de la longueur d' arc entrera en jeu. J'ai posté une réponse assez longue à l'une de mes propres questions sur Béziers, avec un exemple de code simple.

Bien que je sois d'accord avec les réponses que vous avez déjà obtenues, je veux ajouter un mécanisme d'approximation simple mais puissant que vous pouvez utiliser pour n'importe quel degré Courbes de Bézier: Vous subdivisez continuellement la courbe en utilisant la subdivision de Casteljau jusqu'à la distance maximale des points de contrôle d'une sous-courbe à la ligne de base de la sous-courbe est inférieure à un epsilon constant . Dans ce cas, la sous-courbe peut être approximée par sa ligne de base.

En fait, je pense que c'est l'approche généralement adoptée lorsqu'un sous-système graphique doit tracer une courbe de Bézier. Mais ne me citez pas là-dessus, je n'ai pas de références pour le moment.

En pratique, cela ressemblera à ceci: (sauf que la langue n'est pas pertinente)

public static Line[] toLineStrip(BezierCurve bezierCurve, double epsilon) {
    ArrayList<Line> lines = new ArrayList<Line>();

    Stack<BezierCurve> parts = new Stack<BezierCurve>();
    parts.push(bezierCurve);

    while (!parts.isEmpty()) {
        BezierCurve curve = parts.pop();
        if (distanceToBaseline(curve) < epsilon) {
            lines.add(new Line(curve.get(0), curve.get(1)));
        } else {
            parts.addAll(curve.split(0.5));
        }
    }

    return lines.toArray(new Line[0]);
}

Les longueurs d'arc pour les courbes de Bézier ne sont fermées que pour les courbes linéaires et quadratiques. Pour les cubiques, il n'est pas garanti d'avoir une solution fermée. La raison en est que la longueur de l'arc est définie par une intégrale radicale, pour laquelle n'a un fermé que pour les polynômes du 2e degré.

Juste pour référence: La longueur d'un Bézier quadratique pour les points (a, p) (b, q) et (c, r) est

(a ^ 2 · (q ^ 2 - 2 · q · r + r ^ 2) + 2 · a · (r - q) · (b · (p - r) + c · (q - p)) + ( b · (p - r) + c · (q - p)) ^ 2) · LN ((√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · √ (a ^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) + a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) / (√ (a ^ 2 + 2 · A · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) · √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) + a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2) ^ (3/2) + (√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · (a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) - √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) · (a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2)

Où LN est le logarithme naturel, et ^ désigne la puissance et √ la racine carrée.

Par conséquent, il devrait être plus facile et moins cher d'approcher l'arc par une autre règle, comme un polygone ou un schéma d'intégration comme la règle de Simpson, car les racines carrées du LN sont des opérations coûteuses.

J'ai calculé l'expression de longueur sous forme fermée pour un Bézier à 3 points (ci-dessous). Je n'ai pas tenté d'élaborer un formulaire fermé pour plus de 4 points. Cela serait très probablement difficile ou compliqué à représenter et à gérer. Cependant, une technique d'approximation numérique telle qu'un algorithme d'intégration Runge-Kutta fonctionnerait assez bien en s'intégrant à l'aide de la formule de longueur d'arc . Mes questions et réponses sur RK45 sur MSE peuvent aider à la mise en œuvre de RK45.

Voici un code Java pour la longueur d'arc de 3 points de Bézier, avec des points a, bet c.

    v.x = 2*(b.x - a.x);
    v.y = 2*(b.y - a.y);
    w.x = c.x - 2*b.x + a.x;
    w.y = c.y - 2*b.y + a.y;

    uu = 4*(w.x*w.x + w.y*w.y);

    if(uu < 0.00001)
    {
        return (float) Math.sqrt((c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y));
    }

    vv = 4*(v.x*w.x + v.y*w.y);
    ww = v.x*v.x + v.y*v.y;

    t1 = (float) (2*Math.sqrt(uu*(uu + vv + ww)));
    t2 = 2*uu+vv;
    t3 = vv*vv - 4*uu*ww;
    t4 = (float) (2*Math.sqrt(uu*ww));

    return (float) ((t1*t2 - t3*Math.log(t2+t1) -(vv*t4 - t3*Math.log(vv+t4))) / (8*Math.pow(uu, 1.5)));