Remove interpolated points from graph data using c#

Question

Given two columns of graph data from a file, I'm reading the file contents & storing the values in an ArrayList,How to "un-interpolate",

i.e. compress down to the least number of rows that would produce the same line graph.

For a simple example:

Would become:

since this would produce the same line graph with the "in between" points on the two straight lines removed.

Can someone guide me how to achieve this using c#?

Have a look at the [Ramer–Douglas–Peucker algorithm](https://en.m.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm). A clever way to remove points in a 2D route. — Axel Kemper, Oct 19 '15 at 05:38
If you need help with the math part of this, see http://math.stackexchange.com/questions/255120/determining-if-a-point-lies-on-a-particular-slope-between-two-points You can just apply that to each set of three consecutive points and remove the middle one if it does. — Ian Mercer, Oct 19 '15 at 05:43
This is high school geometry question. To define a line you need only two points, not 4 if you have a straight line. You need to get the slope and b of the line and get equation y = mx + b. Then get the x,y pair of the minimum x and maximum x. — jdweng, Oct 19 '15 at 07:02
I wrote a hittest method last week straight from wikipaedia. See [this post ](http://stackoverflow.com/questions/32919918/how-to-draw-line-and-select-it-in-panel/32920894#32920894) - But in this case a simple comparison of the slopes would be more efficient.. — TaW, Oct 19 '15 at 11:14
I'm trying to compare the first 3 elements, and add the greater values to Arraylist and at last i will be plotting the graph based on the values in arraylist. I am trying below way int[] arr = new int[] { 2, 5, 8, 6, -1, -2, 4 }; ArrayList addArr = new ArrayList();int first = arr[0]; int second = arr[1]; int third = arr[2]; if (second > first && second < third) { addArr.Add(first); addArr.Add(third); } I want to implement the above condition for all array elements. Tried using for loop but no luck — Rao, Oct 19 '15 at 11:35
For each pair of points, remove any point which is on the line segment defined by those two points. It's probably not the most time efficient, but it's easy to code and understand. — apokryfos, Oct 19 '15 at 14:46

score 0 · Answer 1 · answered Oct 19 '15 at 14:38

There should be some much more elegant solution, but here we go:

List<Point> reducePlotLines(List<Point> points)
{
    float limit = 0.1f;

    List<Point> newPoints = new List<Point>();
    Dictionary<int, float> slopes = new Dictionary<int, float>();
    List<int> toRemove = new List<int>();

    for (int i = 1; i < points.Count; i++)
    {
        if ( points[i-1].Y - points[i].Y == 0)  slopes.Add(i, float.MaxValue);
        else slopes.Add(i, 
             1f * (points[i-1].X - points[i].X) / (points[i-1].Y - points[i].Y));
    }

    newPoints.Add(points[0]);
    for (int i = slopes.Count - 2; i > 0; i--)
    {
        if (Math.Abs(slopes[i] - slopes[i + 1]) < limit)
            toRemove.Add(i);   
    }

    foreach (int i in toRemove) slopes.Remove(i);

    newPoints.Add(points[points.Count-1]);
    foreach (KeyValuePair<int, float> kv in slopes) newPoints.Add(points[kv.Key]);

    return newPoints;
}

The above chart was created like this:

private void button7_Click(object sender, EventArgs e)
{
    chart1.Series.Clear();        chart1.Series.Add("S1");
    chart1.Series.Add("S2");      chart1.Series.Add("S3");
    List<Point> points = new List<Point>();
    points.Add(new Point(1,2));   points.Add(new Point(2,5));
    points.Add(new Point(3,8));   points.Add(new Point(4,6));
    points.Add(new Point(5,4));   points.Add(new Point(6,2));
    points.Add(new Point(7,4));
    chart1.Series[0].ChartType = SeriesChartType.Line;
    chart1.Series[1].ChartType = SeriesChartType.Point;
    chart1.Series[2].ChartType = SeriesChartType.Point;
    chart1.Series[0].Points.Clear();
    foreach (Point pt in points)
    {
        chart1.Series[0].Points.AddXY(pt.X, pt.Y);
        chart1.Series[1].Points.AddXY(pt.X, pt.Y);
    }

    List<Point> reducedPoints = reducePlotLines(points);
    foreach (Point pt in reducedPoints)
    {
        chart1.Series[2].Points.AddXY(pt.X, pt.Y);
    }

}

Note that I had to change your data as it contained only one interpolated point.

Remove interpolated points from graph data using c#

1 Answers1