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

Background: I have a function in my program that takes a set of points and finds the minimum and maximum on the curve generated by those points. The thing is it is incredibly slow as it uses a while loop to figure out the min/max based on approximated error. Not completely sure what formal method this is because I did not write it myself, but I know we need a new and more efficient one.

Question: My question is what is the best and most efficient method/algo开发者_开发问答rithm to finding the min max points on a curve, using C#, that is also very accurate?

About the curve: I have my Numerical Analysis book from college near me, so all I need is a method name and a nudge in the right direction. I can generate as many points as I choose to approximate the curve, but I want to keep the number of points to an efficient minimum. The curve is always in the shape of one segment of a Sin/Cos curve, but not always the same curve and will always be less that one period. The range of Theta is 0° to 359.999...° It has some phase and amplitude shift and Y will never be negative. This function/algorithm will have to run fast as it will be run every several hundred milliseconds as the curve changes.

Any suggestions are appreciated.

EDIT

More info on the curve: The points are generated on mouse move. The points are a set of points based on the length of a rubber belt in a drive design with an idler, such as one like the serpentine belt in a car. The position of the idler determines the length of the belt and I get the curve [belt length(y) vs idler position(x)]. The idler in this case is a pivoting idler and will have constant circular motion. If the drive design changes the curve will change, either because the length points change, or because the range of motion of the idler has been constrained. The range of motion in the idler is potentially 0° to 359.999...° and is theta as stated above. For a slotted idler the maximum range is 1/2 of the period of the curve (easier problem).

I guess what I need is a general solver for both types of idlers, but the real issue is with the pivoting idler.

---

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).

---

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.

---

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.

---

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

---

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.

---

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.

---

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.