Efficient way to find key points on spline to approximate it with line strip

Question

Given a spline, what is an efficient way to find (approximately) the least amount (and position) of key-points to approximate the spline with a line strip, so that the largest distance between the line strip and the spline at any given point is <= d.

Here is a visual example. I'm looking to find a computationally efficient way to find the points in the green circles that I use as beginnings and endings for the lines.

What I thought about is walking along the spline, summing up the traveled distance. As I walk the spline, I test the last position as a key-point candidate. Once the distance traveled on the spline and the length of the line through the key-point candidate deviate by a certain percentage, I use the last key point candidate that was still below that percentage. What I'm uncertain about is first, if there is a more efficient way, and second, deviation in length as a percentage is not really the same as distance (e.g. in cm). If there is a relatively long, relatively straight part of the spline, the length deviation that I might accept, could lead to quite a large distance between the spline and the line somewhere on the way, couldn't it?

[Discussion / Comments]

What's a "line strip"?

For the purpose of this question a line strip is a bunch of connected line segments, like the red strip in the image above.

Do you require that each endpoint of each line segment in the line strip must be on the spline?

No. I just require that the maximum distance between the line segment and the spline segment is <= d. And I want to end up with a small number of line segments. It doesn't need to be the smallest number possible, but it should be reasonably small. The smaller the better. If allowing for a few extra segments prevents me from having to iterate over my solutions for optimization, I'd take that.

Given the difference between the lengths of the curved and straight segments, you can give an upper bound for maximal distance between them

That is not a bad idea! As I stated above, I tried this by giving the deviation in percent of the line-segment's length. But using the absolute deviation in length instead (without converting to percent), does give me an upper bound for the maximum distance. So this would be better than what I used before.

Answer 1

A simple approach would be to take a dense sample of points on the spline (i.e., more than you need), and then apply the Ramer-Douglas-Peucker polyline simplification algorithm to get rid of as many of them as possible. Note: Unless you generate the point sample in some clever way (e.g., with density proportional to the local curvature), this isn't guaranteed to recover sharp bends perfectly.

According to that Wikipedia page, the straightforward implementation takes $O(n^2)$ time in the worst case for $n$ points, though there is also a more complicated version due to Hershberger and Snoeyink that takes just $O(n \log n)$ time in the worst case.

Answer 2

One approach would be to use dynamic programming. Pick 100 points $P_1,\dots,P_{100}$ along the spline. For each point $P_i$ on the spline, pick 5 points $Q_{i,-1},Q_{i,-1/2},Q_{i,0},Q_{i,1/2},Q_{i,1}$, where $Q_{i,0}=P_i$, $Q_{i,1}$ is $d$ away from $P_i$ in the direction perpendicular to the spline, $Q_{i,1}$ is $d$ away in the opposite direction, $Q_{i,1/2}$ is halfway between $Q_{i,0}$ and $Q_{i,1}$, and so on.

Now use dynamic programming to pick a subset of the $Q_{i,j}$ that give the best fit to the spline. In particular, let $A[i,j]$ denote the smallest number of line segments that suffice to approximate the part of the spline that starts at the beginning and continue on to $P_i$, if the line strip ends at $Q_{i,j}$. Then

$$A[i,j] = \min\{1+A[i',j']\}$$

where the $\min$ is taken over all $i',j'$ such that $i'<i$ and such that the line segment from $Q_{i',j'}$ to $Q_{i,j}$ is never more than $d$ away from the spline. This gives a recursive relation for $A[i,j]$, so you can fill in the $A[i,j]$ entries using dynamic programming. The running time will be $O(n^2)$, where $n$ is the number of points $P_1,\dots,P_n$ chosen (e.g., $n=100$).

This won't give the exact optimum, but the larger $n$ is, the better an approximation you get. This lets you control the tradeoff between running time and quality of the solution.

A simple way to pick the points $P_1,\dots,P_{100}$ is to choose them to be evenly spaced along the spline. Heuristically, a better solution might be to sample points with a density proportional to the curvature of the spline (so the $P_i$ are closer together in regions where the spline curves sharply, and are farther apart in regions where the spline is nearly a straight line).