Adaptive Sampling of Function Values for Plotting

Situations to Handle

• Regions near singularities where the value changes sharply (e.g. singularities of the Gamma function).

• Edges of the domain (e.g. the edges of asin, acos).

• Regions of rapid oscillation (e.g. functions like sin(1/x)).

• Regions with a jump discontinuity (e.g. the floor function).

The basic approach is to sample at a fixed resolution in x first, then insert additional points between samples as needed to satisfy the required accuracy.

Criteria for Adding a Point Between Two Samples

• The change in coordinates between two adjacent points is large.

  • A threshold is set on the change in the y coordinate.

    • The threshold is a value relative to the range of y shown in the plot.

• The change across three consecutive points is large.

  • The slope between each pair of adjacent points is computed, and a threshold is set on the change in slope.

    • The threshold is specified relative to the plot area: the slope is computed as the ratio of the change in y to the change in x, each normalized by the plot area.

• A point inside the plot range is adjacent to a point that is inf or nan.

  • Without an inserted point, the line would be cut off instead of connecting to the edge of the plot.

Criteria for Not Adding a Point

• Both of two adjacent points are outside the plot range, or are inf or nan.

  • If only one of the two is inside the range, a point is still added (see above).

• The x distance between two adjacent points is already too small.

  • This prevents an infinite loop of repeatedly subdividing around a singularity.

    • This threshold is set relative to the range of x.

  • A lower bound is set on this threshold to limit the number of recursions (roughly 1/1000 of the size of the domain).

  • Whether to connect the two points with a line when this threshold is reached needs further consideration:

    • When the change in y is large, the function is likely piecewise, so the points should not be connected with a line (this is handled in the plotting step). However, this resulted in discontinuities of the line in many cases where the function is actually continuous, so not implemented for now.

• The total number of points becomes too large.

  • Even after applying the criteria above, a maximum point count is set as a last resort to give up further subdivision.

    • A feature to warn the user when this limit is reached would be useful.

Constraints

• A spike within an extremely narrow range cannot be handled reliably.

  • Handling this in general would require prior knowledge of the function, so instead the number of initial samples is made tunable, leaving the trade-off to the user.

Requirements for the Algorithm

• Keep processing time low.

  • Repeatedly inserting points into the middle of a vector that already holds many elements is slow. Therefore, the initial sampling is kept in a separate vector from the final vector that includes the inserted points, to reduce the amount of copying within a vector.