Most efficient way to find min and max of a sin/cos curve in C#

Answer 1

If you have a quadratic equation then the maximum or minimum will always be at the point when the differential of the equation is 0. If your quadratic equation has a formula of ax^2 + bx + c = 0 then this point will be when x = -b/2a.

Whether it is a maximum opr minimum can be determined by looking at a. If a > 0 then its a minimum and if a < 0 then its a maximum (if a = 0 then its not a quadratic).

I hope that helps. If you haven't got the equation of the curve in this sort of form could you say what you have got to work from?

Edit: question has changed so that the curve is a section of a sine curve and not a quadratic any more. This answer is therefore no longer appropriate.

Edit2:

With a sine curve the general equation will be y = a sin(mx+t) + c. You will never be able to exactly determine the original equation because for any solution there will be a higher frequency solution that also matches. I'm unsure currently how many points are needed to precisely calculate what a would be (which would give the min and max of the curve).

Answer 2

Is all you have available the set of points? And are there no restrictions on the "shape" of the function these points represent? If so, then you're probably stuck, iterating through the points will be your best bet...
Although if you have any other work to do on this set, you might want to sort it by the Y-coord for use by future processing.

(Keep both arrays around - the one you were fed as input (it's probably sorted by x-corrd ?) and the one sorted by function value(y-coord) ) ...

Edit: if you know that the curve will always be shaped "like" a portion of Sin/Cos curve, then if you know the smallest period that might be represented, you can do some optimizations by using binary search algorithm to "look" for the inflection points (where the slope (Change in Y to the left and to the right ) are of different signs. For each point examined on the left, move to the right by chunks = half the allowable period until you find the point of inflection, or the slope changes sign... Then move back by half the last change in x, until you find the point of inflection. [Do the opposite for the points on the right]

A recursive routine that examines/finds the first and last inflection point, compares them to determine which is greatest, and then recursively examines and finds, the inlfection point halfway between them, until the two points involved are less than the smallest allowable period aprt from one another, will produce some performance gains...

2nd EDIT: Since I read in yr other comment that set will never contain more than one inflection point... If this so, then just do binary search to find it.

PsuedoCode:

  Check Leftmost point to see slope (Up Down or Zero)
       If Zero, done
  Check RightMost Slope 
       If Zero - Done
  If two Slopes are same sign - Done 
        - pick Bigger of two points ( - or smaller if looking for min)
  Check point in the Middle slope
     If Zero, Done
     If slope has same sign as left pt, Change Left to this Point and repeat
     If slope has same sign as right pt, Change Right to this Point and repeat

Answer 3

Since the curve is always quadratic (and thus always convex), there should be a lot of methods available (though since I don't program in c#, I don't know if source is available). Newton's method comes to mind first but there are others (like interior point methods). For a mathematical background of these algorithms (but not their implementations, unfortunately), see this textbook (pdf). If you do use any of these methods, they'll work for other convex curves as well.

Answer 4

The algorithm you should use (and the parameters you give it) depends on what your data set looks like. It sounds like you are evaluating a waveform of some physical measurement that is acquired continuously.

If so, then you need to decide whether you want to ignore local minima and maxima (eg spikes from noise in the signal). Also, you'll want some way to handle the edges of your data set. In other words, does the beginning of your data count as a maxima if it is the highest point in the current dataset but is merely coming down from a big peak in the previous one?

Canned peak detection algorithms will typically have some way to specify a threshold and also a width (to control sensitivity to spikes) and a buffer size (to handle really gradual peaks).

There are plenty of algorithms out there, just pick one or two and tweak parameters until it gives the results you expect.

Answer 5

After you collected a few points (>=4) you could use a form of local search to match your points to a sine curve y = A cos(Bx+C)+D then use a simple formula based on the derivative to find the minimum. While searching, you should keep B as little as possible to avoid redundant hi-frequency solutions. Just an idea, may be very inefficient.

Answer 6

From the comment the input X and the output Y are arrays

"@Mike:I generate the values and put them in an array"

I suggest to use this approach. All what you need from my code is {getMaxIndex}

    private void Test()
    {
        double[] X = SetLinearRange(0, Math.PI * 2, 1000);
        double[] Y = GetOutput(X);
        int MaxIndex = getMaxIndex(Y);
        double MaxX = X[MaxIndex];
        double MaxY = Y[MaxIndex];
    }
    private double[] SetLinearRange(double Start, double End, int Sample)
    {
        double Step = (End - Start) / Sample;
        double CurrentVaue = Start;
        double[] Array = new double[Sample];
        for (int Index = 0; Index < Sample; Index++)
        {
            Array[Index] = CurrentVaue;
            CurrentVaue += Step;
        }
        return Array;
    }
    private double[] GetOutput(double[] X)
    {
        double[] Array;
        Array = (from double Item in X select myFunction(Item)).ToArray();
        return Array;
    }
    private double myFunction(double x)
    {
        double y;
        //put any function
        y = 3 * Math.Sin(5 * x + 2);
        return y;
    }
    private int getMaxIndex(double[] Y)
    {
        double YM = Y.Max();
        int Index = Y.ToList().IndexOf(YM);
        return Index;
    }

I hope that will be fast.

Answer 7

I'm a little confused.

If you yourself are generating the points, why not just keep track of the largest/smallest points when doing the generating?

If you have a function, like I'm sure others have pointed out, just get the derivative and solve for 0. This will give you the point(s) of min/max.