Как уменьшить количество точек в (x, y) данных

Question

У меня есть набор точек данных:

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

Количество точек выборки может быть тысяч. Я хочу представить ту же самую кривую как можно точнее с минимальным (предположим, 30) набором точек. Я хочу захватить как можно больше точек перегиба. Однако у меня есть жесткое ограничение на количество разрешенных точек для представления данных.

Какой лучший алгоритм для достижения того же? Есть ли какая-нибудь библиотека бесплатного программного обеспечения, которая может помочь?

PS: я пытался реализовать устранение точек на основе относительной разности наклона, но это не всегда приводит к наилучшему из возможных представлений данных.

Answer 1

Вы ищете алгоритм интерполяции. Если ваш набор точек является функцией в математическом смысле (все значения x не расходятся друг с другом), то вы можете пойти на полиномиальную интерполяцию или они распределены по 2-мерной плоскости, тогда вы можете использовать кривые Безье.

Answer 2

Поздний ответ после года:
Взгляните на алгоритм Дугласа-Пекера :

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

Он часто используется для упрощения GPS-треков и уменьшения количества путевых точек. В качестве подготовки вам, возможно, придется отсортировать ваши точки, чтобы сохранить соседние точки в вашем списке или массиве.

Answer 3

это зависит от того, должна ли ваша кривая пересекать каждую точку, или она является приблизительной. Попробуйте:

1. Взять очки
2. Применить любую интерполяцию (http://en.wikipedia.org/wiki/Polynomial_interpolation), чтобы получить уравнение кривой
3. Затем возьмите точки выборки с определенным шагом.