Question: deviation estimation

[kimstik]

What is recipe to numerically estimate the maximum deviation of the extrapolated curve from the original piecewise linear one?

[carlos-adir]

I don't think there's already an algorithm that do it. So, I would do it by myself:

1. Find a region where you know the deviation is. Like, at u between two scalars ui and uj.
2. Get the tangent vector from the linear piecewise, the D vector.
3. Get the tangent vector V(u) from the extrapoled curve.
4. Your point at extrapoled curve is the one such V(u) = D. You can search it by binary search
5. Once gotten the u, compute the minimal distance of P(u) (extrapoled) from the linear one. It's what you need.

[portnov]

I can suggest a method which allows you to estimate this deviation, not exactly, but it can be enough:

• for each segment of your piecewise line, cut a corresponding segment from interpolated curve — i.e. find control points of the curve which is identical to your interpolation curve, but starts and ends at the end points of linear segment (there are methods for this in geomdl).
• now, you have a set of pairs: a linear segment and corresponding piece of the curve. Now you can apply the property of nurbs curves known as "strong convex hull property": all points of the curve lie inside the convex hull built on it's control points. So, if you calculate the distance from each control point of curve's segment to linear segment (there are obvious enough formulas), and find the maximum of such distances, you will know that your curve segment derives from linear segment not more than for this maximum.
• then you just find the maximum of such maximum distances across all segments.

Nurbs maths will guarantee that the curve never derives from your piecewise linear line more than for the value you find that way, but the deviation obviously can be less than it.