patternMinor
Efficient way to calculate the maximum curvature of a cubic spline
Viewed 0 times
themaximumcubiccurvaturesplineefficientwaycalculate
Problem
I've got a 2D cubic spline (Bézier) and I have the polygon-line that's a discretization of that spline.
Is there an efficient and simple to implement a way to calculate the maximum curvature of the spline either by using its smooth representation or the discrete poly-line? It doesn't have to be exact since it's for a game, an error around 10% would be totally acceptable.
Different wording: I would like to know: if I'd drive a car driving at constant speed along the spline, what would be the maximum degree I had to turn the steering wheel to stay on it?
Is there an efficient and simple to implement a way to calculate the maximum curvature of the spline either by using its smooth representation or the discrete poly-line? It doesn't have to be exact since it's for a game, an error around 10% would be totally acceptable.
Different wording: I would like to know: if I'd drive a car driving at constant speed along the spline, what would be the maximum degree I had to turn the steering wheel to stay on it?
Solution
Step 1: Express the points on the spline parametrically, so the spline is the set of points of the form $(x(t),y(t))$, where $t$ is a parameter. Here $x(t)$ represents the $x$-coordinate (as a function of the parameter $t$) and $y(t)$ represents the $y$-coordinate. Since this is a cubic spline, you can find functions $x(t),y(t)$ that are cubic polynomials with known coefficients that provide this parametric expression.
Step 2: Use the formula on Wikipedia for computing the curvature, given a parametric representation of the curve. This gives you a formula for the curvature as a function of $t$, namely, $\kappa(t)$. Note that since $x(t)$ and $y(t)$ are cubic polynomials, you can explicitly compute their first and second derivatives, so you can analytically compute an explicit expression for $\kappa(t)$, i.e., for the curvature as a function of $t$.
Step 3: Find the value of $t$ that maximizes $\kappa(t)$. Note that we are now dealing with a function $\kappa : \mathbb{R} \to \mathbb{R}$, i.e., we are in the one-dimensional case. Thus, we can find the maximum numerically using any of a number of methods: gradient descent, Newton's method, or a number of other methods.
Alternatively, you can analytically compute the derivative of $\kappa(t)$, and then solve the equation $\kappa'(t)=0$ for $t$. This might allow an analytic solution that identifies a list of candidate maxima of $\kappa(t)$. Make sure to also check the endpoints (the lower and upper bounds for $t$). Evaluate $\kappa$ at each candidate and pick the one that makes the value of $\kappa(t)$ as large as possible.
Step 2: Use the formula on Wikipedia for computing the curvature, given a parametric representation of the curve. This gives you a formula for the curvature as a function of $t$, namely, $\kappa(t)$. Note that since $x(t)$ and $y(t)$ are cubic polynomials, you can explicitly compute their first and second derivatives, so you can analytically compute an explicit expression for $\kappa(t)$, i.e., for the curvature as a function of $t$.
Step 3: Find the value of $t$ that maximizes $\kappa(t)$. Note that we are now dealing with a function $\kappa : \mathbb{R} \to \mathbb{R}$, i.e., we are in the one-dimensional case. Thus, we can find the maximum numerically using any of a number of methods: gradient descent, Newton's method, or a number of other methods.
Alternatively, you can analytically compute the derivative of $\kappa(t)$, and then solve the equation $\kappa'(t)=0$ for $t$. This might allow an analytic solution that identifies a list of candidate maxima of $\kappa(t)$. Make sure to also check the endpoints (the lower and upper bounds for $t$). Evaluate $\kappa$ at each candidate and pick the one that makes the value of $\kappa(t)$ as large as possible.
Context
StackExchange Computer Science Q#51827, answer score: 2
Revisions (0)
No revisions yet.