I needed to find the extremities of a noisy curve. This is a good example where you need to translate a qualitative observation to a quantitative one. It’s easy for a human to look at a curve and say where the important peaks and troughs are while ignoring those which are not important in the context of that curve. Here’s a simple algorithm that achieves it. To see it in action, just draw any curve and click the ‘find minmax’ button to see which points along your curve the algorithm decides to be the peaks (in green) or troughs (in red)

The algorithm is very naive and has a complexity of O(n) where n are the number of points on the curve (I use the term curve loosely as it doesn’t have to be continuous). It basically does the following:

1. Determine a threshold (defined arbitrarily as 10% of the difference between the lowest and highest points on the curve).
2. Get the Y coordinate of the leftmost point on the curve
3. Set horizontal boundaries as y+threshold and y-threshold
4. Scan the points of the curve from left to right and check the Y coordinate of the point

I’ll discuss what happens when the Y coordinate crosses the y+threshold that was set (the same principle applies if the Y coordinate gets below the y-threshold point).

We know that we have found a candidate for a maximum:

1. If there was a previous minimum point, mark it as such
2. Change the state to indicate we are now looking for a minimum point
3. Reset the thresholds boundaries to be the current Y coordinate plus and minus the threshold
4. Save the X,Y coordinates of the maximum candidate

Continue scanning and:

• Update the X and Y coordinates of the maximum point candidate if the current Y coordinate is higher than the pervious maximum point candidate
• Mark the maximum point candidate as a maximum when we cross the low threshold (this basically brings us back to step 1)

Looking at the code would probably be even easier to understand:

function findMinMax()
{
    points = [];

    var minY = 10000000;
    var maxY = 0;
    for (var ix=3; ix<=w-3; ix++) {
        var height = getY(ix);
        if (height == null) {
            points.push(-1);
            continue;
        }
        points.push(height);

        if (maxY < height)
            maxY = height;
        if (minY > height)
            minY = height;
    }

    var lookingFor = -1;
    var localMaxY;
    var localMinY;
    var localMaxYx;
    var localMinYx;

    var minChange = (maxY - minY) * 0.1;
    var nextMaxY = points[0]+minChange;
    var nextMinY = points[0]-minChange;
    var npoints = points.length;
    for (var x=0; x<npoints; x++) {
        var y = points[x];
        
        if (y==-1)
            continue;

        if (y>nextMaxY) {
            if (lookingFor == 1) {
                markMinPoint(localMinYx, localMinY)
            }
            nextMinY = y - minChange;
            nextMaxY = y + minChange;
            lookingFor = 0; // look for minimum, but save highest until we find it
            localMaxY = y;  // reset the local highest
            localMaxYx = x;
        }
        if (localMaxY<=y) {
            localMaxY  = y;
            localMaxYx = x;
        }

        if (y<nextMinY) {
            if (lookingFor == 0) {
                markMaxPoint(localMaxYx, localMaxY)
            }
            nextMaxY = y + minChange;
            nextMinY = y - minChange;
            lookingFor = 1; // look for maximum, but save lowest until we find it
            localMinY = y;  // reset the local lowest
            localMinYx = x;
        }
        if (localMinY>=y) {
            localMinY = y;
            localMinYx = x;
        }
    }
}