Search code examples
algorithmsamplingcurve

Algorithm to adaptively sample a function

I am looking for some algorithm that could sample a function based on its curvature. E.g. for some interval [a,b] and a given number of samples n the algorithm would sample the function in such a way that more samples will be placed where the functions bends, and less samples where the function is more "linear".

The graphical representation of what I have in mind is presented in the picture below:

adaptive sampling example

Solution

  • A common operation in computer graphics is "flattening" a curved path, i.e., approximating a curve by line segments.

    There is usually a constraint on how far the approximation is allowed to deviate from the original curve and so the result looks a lot like what you're asking for, with samples more concentrated in the areas of highest curvature.

    So you could try one of the algorithms that is used for this purpose, like the RDP algorithm described here: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm