How to reduce the number of points in (x,y) data

I have a set of data points:

(x1, y1) (x2, y2) (x3, y3) ... (xn, yn)

The number of sample points can be thousands. I want to represent the same curve as accurately as possible with minimal (lets suppose 30) set of points. I want to capture as many inflection points as possible. However, I have a hard limit on the number of allowed points to represent the data.

What is the best algorithm to achieve the same? Is there any free software library that can help?

PS: I have tried to implement relative slope difference based point elimination, but this开发者_JS百科 does not always result in the best possible data representation.

---

You are searching for an interpolation algorithm. Is your set of points a function in a mathematical sense (all x values are disjunct from each other) then you can go for a polynomial interpolation, or are they distributed over the 2d plane, then you could use bezier curves.

---

Late answer after years:
Have a look at the Douglas-Peucker algorithm:

function DouglasPeucker(PointList[], epsilon)
    // Find the point with the maximum distance
    dmax = 0
    index = 0
    end = length(PointList)
    for i = 2 to ( end - 1) {
        d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) 
        if ( d > dmax ) {
            index = i
            dmax = d
        }
    }
    // If max distance is greater than epsilon, recursively simplify
    if ( dmax > epsilon ) {
        // Recursive call
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

        // Build the result list
        ResultList[] = {recResults1[1...length(recResults1)-1], recResults2[1...length(recResults2)]}
    } else {
        ResultList[] = {PointList[1], PointList[end]}
    }
    // Return the result
    return ResultList[]
end

It is frequently used to simplify GPS tracks and reduce the number of waypoints. As a preparation, you may have to sort your points to store neighbour points adjacent in your list or array.

---

it depends on must your curve intersect each point or it is approximation. Try:

1. Take points
2. Apply any interpolation (http://en.wikipedia.org/wiki/Polynomial_interpolation) to get equation of curve
3. Then take sample points with specific step.