How to find the point where the slope of a line changes?

Question

I have a graph of some sensor data. At some point, the overall graph (not counting the little bumps in the data; I mean the overall line) is going to show an abrupt change in slope and get much steeper. This point is never right at the beginning of the graph, but its never as far as half way through, either. I need to find the point (or as close to it as I can) where the slope changes and the line gets steeper. This is the code I have so far. It works, but it isn't consistent --- some graphs return (0,0) as the point, which is incorrect, and other graphs return a point far past the initial up-turn of the graph, which is also incorrect. Any help would be appreciated; does anybody know if there's a check or anything I'm missing?

Point Location = new Point(0, 0);
float lastSlope = 0;
float slope = 0;

for (int i = 6; i+6 < cnt/2; i+=6)
{
    lastSlope = (display.DataSources[0].Samples[i].y - display.DataSources[0].Samples[i-6].y) / (display.DataSources[0].Samples[i].x - display.DataSources[0].Samples[i-6].x);
    slope = (display.DataSources[0].Samples[i+6].y - display.DataSources[0].Samples[i].y) / (display.DataSources[0].Samples[i+6].x - display.DataSources[0].Samples[i].x);

    //lastSlope is significantly different from slope AND (i is more than a quarter of cnt)
    if (((slope*100)-45 > lastSlope*100) && (i > cnt / 4) )
    {
        Debug.WriteLine("changing location!");
        Location.X = (int) display.DataSources[0].Samples[i].x;
        Location.Y = (int) display.DataSources[0].Samples[i].y;
    }

}

for (int i = 6; i + 6 < cnt/2; i += 6)
{
    if (Location.X == (int)display.DataSources[0].Samples[i].x && Location.Y == (int) display.DataSources[0].Samples[i].y)
    {
        display.DataSources[1].Samples[i].y = 65;  //adjust the did-we-edit-the-data line to show the location of the point
    }
}

//convert y value to inches
//Location.Y = (int)(96 - (((double)Location.Y) / 25.4));

return Location;

Answer 1

Finding a function to model portions of sensor data ought to be routine for a Math package, at least if you a) have one and b) can use it proficiently.

Since I fail on both points here is what I'd do: Calculate the derivatives not from a function I don't have but from the data points I do have.

• Decide on a grouping number n by either looking hard at the data and/or trial and error. I'd start by estimating the number of points it takes to change from the lower slope S1 to the steep slope S2 and take a small fraction of that, say 1/3rd.

• Calculate average values for each group of n points. This reduces the total number of points from N to N/n and should get rid of the bumps.

• Calculate the slopes between each of those average values, resulting in N/n - 1 slopes; this is basically the 1st derivative. Discounting the (to me unknown) start of the data series there should be two distinct slopes S1 and S2 in the list and a small number of 1-3 slopes rising from S1 to S2.

• The point we look for is somewhere in the middle of these median slopes.

• One could repeat the last step and calculate the 2nd derivative points as the slopes between the slopes. This should result in two ranges where the ('2nd order') slopes are close to 0 and one in between where they are distincly positive. The point we look for is somewhere after their maximum.

To find a good n will not be so hard, provided the data are similar in density between each batch, but the 'bumpiness' of the data is also a factor to find a good n..

Here is an example code;

Notes

• This solution takes 2 or 3 passes over the data. Sometimes preparing the data makes things easier to handle imo..

• The larger part is code to create test data.. The actual calculation is only eight lines of code!

• you will want to play with values of n and cutOff.

• I don't have any data points before or after the slopes. You'll have to exclude those parts from the calculations since there may well be more slope changes.

You'll skip most of the code until the actual calculations..:

// test data
List<PointF> oData = new List<PointF>();  // orginal data values
List<PointF> D0 = new List<PointF>();     // reduced smoothed data
List<PointF> D1 = new List<PointF>();     // 1st derivative
List<PointF> D2 = new List<PointF>();     // 2nd derivative
List<PointF> M = new List<PointF>();      // reasonably large values from D2

int N1 = 255;            // number of data points with slope S1
int N2 = 15;             // number of data points between S1 and S2
int N3 = 40;             // number of data points with slope S2

int n = N2 / 3;          // grouping number

float S1 = 0.2f;         // Slope 1
float S2 = 1.3f;         // Slope 2
float S12 = (S2 - S1) / N2; 
float P1y = N1 * S1;
float cutOff = 2f;      // cutoff value to detemine 'reasonably' large slope changes
int roughness = 10;
float smoothness = 15f;

// create the data points
for (int i = 1; i <= N1; i++) oData.Add(new PointF(
         i, i * S1 + (R.Next(roughness) - roughness/2) / smoothness));
for (int i = 1; i <= N2; i++) oData.Add(new PointF(
         i + N1, P1y + i * S12 + (R.Next(roughness) - roughness/2) / smoothness));
for (int i = 1; i <= N3; i++) oData.Add(new PointF(
         i + N1 + N2, P1y + i * S2 + (R.Next(roughness) - roughness/2) / smoothness));

// display them
chart1.ChartAreas.Add("data");
Series s = chart1.Series.Add("data");
s.ChartType = SeriesChartType.Line;
foreach (PointF p in oData) s.Points.Add(new DataPoint(p.X, p.Y));

// smoothen the data
for (int i = 1; i < oData.Count / n; i++) 
{
    float ysum = 0.0f;
    for (int j = 0;j<n; j++) ysum += oData[i*n+j].Y;
    D0.Add(new PointF(i, ysum/n));
}

// 1st derivative
for (int i = 1; i < D0.Count; i++) D1.Add(new PointF(i, D0[i - 1].Y - D0[i].Y));

// 2nd derivative
for (int i = 1; i < D1.Count; i++) D2.Add(new PointF(i, D1[i - 1].Y - D1[i].Y));

// collect 'reasonably' large values from D2
foreach (PointF p in D2) if (Math.Abs(p.Y / cutOff ) > 1) M.Add(p);

// our target is n after the last one
int targetX = (int) (M[M.Count -1 ].X * n) + n;

// display as annotation
VerticalLineAnnotation LA = new VerticalLineAnnotation();
LA.LineColor = Color.Red;
LA.AnchorDataPoint = s.Points[targetX];
LA.IsInfinitive = true;
LA.ClipToChartArea = "data";
chart1.Annotations.Add(LA);

Here is an image of the result: