Longueur d'arc de courbe de Bézier

23

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.)

Mateen Ulhaq
la source
1
Vous devriez reformuler la question pour faire référence à la longueur de la courbe, qui est un terme beaucoup plus simple (et consultable).
Sparr
je suggère de poster ceci sur les mathématiques, je suis sûr qu'un visage intelligent là-bas vous donnera la réponse dans l'une de ces polices Web intelligentes: p
Tor Valamo
2
@Je l'ai fait (hier), mais on m'a dit que c'était très compliqué, et donc peu pratique. [ math.stackexchange.com/q/12186/2736 ]
Mateen Ulhaq
Les courbes / splines censément clothoïdes sont une alternative aux béziers et ont des expressions de longueur d'arc de forme fermée, mais je ne sais pas encore grand-chose à ce sujet. (Vous essayez de générer des points à distance égale le long d'une courbe.) Les caténaires ont également des expressions de longueur d'arc de forme fermée?
endolith

Réponses:

9

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.

Ivo Wetzel
la source
Je fais cela pour le LEGO Mindstorms NXT, qui a un processeur vraiment faible (48Mhz), j'ai donc besoin d'autant de vitesse que possible. Je vais adopter l'approche de division pour conserver une certaine vitesse et la rendre suffisamment précise (pour un rendu "non en temps réel"). J'ai également une option dans laquelle vous pouvez définir la valeur de 1.0/t(appelé resolution), c'est donc pour "en temps réel" (qui est au mieux 10fps sur le NXT lent). Chaque itération, t += resolutionet un nouveau point / ligne est tracé. Quoi qu'il en soit, merci pour l'idée.
Mateen Ulhaq
4

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]);
}
Matthias
la source
Bien que ce soit une bonne approche, j'ai entendu parler de l'instabilité numérique aux courbes de Bézier d'ordre élevé, qui nécessitent une autre idée: diviser les courbes d'ordre supérieur en courbes cubiques plus petites.
Mateen Ulhaq
De plus, si l'objectif final est une estimation précise, il peut être judicieux d'approximer avec des quadratiques au lieu de lignes pour garantir que nous ne sous-estimons pas notre estimation aux endroits à forte courbure.
Mateen Ulhaq
2

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.

Robert
la source
2

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)));
Pixel
la source