2
$\begingroup$

I have a smooth parametrized curve $r(t), t \in [0,1]$ in the plane and I want to find a sequence $r(t_1), r(t_2), ... r(t_n)$ which "best" approximates the curve. I'd like to know how to define "best".

Intuitively, I expect that the points should be more densely distributed in sections of the curve with high curvature. For example, I expect that samples of a parabola will be denser near its intersection with the line of symmetry. In the extreme case of a straight line, I expect the points to be uniformly distributed on the curve.

I suspect that there is some function F of r and the n points that is minimized/maximined at the "optimal" distribution of points. Ideally, there should be a simple algorithm for calculating these points from such a function.

Consider, for example, $F = \sum_i \kappa_i$ where $\kappa_i$ is the curvature at $r(t_i)$. It seems reasonable to want to choose $t_1, ..., t_n$ that maximize $F$, but I imagine that there is a less ad hoc choice of $F$ ... one that suggests a natural algorithm for selecting $t_1, ..., t_n$.

As a concrete example, find an algorithm for sampling n points on the parabola described parametrically by: $r(t) = (t, t^2), 0\leq t \leq 1$.

Any ideas? References?

$\endgroup$
  • $\begingroup$ For a Bézier curve, simply picking equally spaced $t$ values will work. $\endgroup$ – Parcly Taxel May 6 '17 at 1:46
  • $\begingroup$ You can check "Numerical Recipes" which have a long discussion about this topic. $\endgroup$ – Felix Marin May 9 '17 at 1:30
2
$\begingroup$

A classic method is the Douglas-Peucker algorithm. You start with a densely sampled polyline, and recursively decide whether to keep or discard vertices based on how much approximation error discarding would introduce.

$\endgroup$
1
$\begingroup$

This paper discusses the problem:

  • H. Imai and M. Iri. Polygonal approximations of a curve-formulations and algorithms. In G. T. Toussaint, editor, Computational Morphology, pages 71—86. North- Holland, 1988.

This paper seems interesting:

For a recent paper, see

  • Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, and Yusu Wang. 2002. Near-Linear Time Approximation Algorithms for Curve Simplification. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA '02), Springer-Verlag, pp. 29—41.

Adaptive arc-length computation is a good proxy for curvature-adaptive approximation. In this context, see this answer.

$\endgroup$
0
$\begingroup$

These are good comments and references, but I think that the method that most closely answers the call is http://www.cs.technion.ac.il/~tess/publications/curve_sampling.pdf.

Thanks!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.