Привет всем!
Мне очень нужна ваша помощь в задачи оптимизации ломаной графика. Т.е. построить новую ломаную с меньшим количеством точек до определенного уровня погрешности. Чтобы точки оставались преимущественно в явных вершинах.

Ломаная представляет собой график с большим количеством точек потому выглядит как кривая.

на картинке ниже:
черная линия — график
красная линия — то как необходимо оптимизировать ее
синяя линия — на нее можете не обращать внимания. это построение зигзага по экстремумам. т.е. то как мне не нужно.

http://files.rsdn.ru/81648/g.JPG

интересует алгоритм решения, примерный хотя бы. также приветствуются ссылки на литературу

заранее спасибо!

Здравствуйте, Airaleais, Вы писали:

A>Привет всем!
A>Мне очень нужна ваша помощь в задачи оптимизации ломаной графика. Т.е. построить новую ломаную с меньшим количеством точек до определенного уровня погрешности. Чтобы точки оставались преимущественно в явных вершинах.

Так как есть "определённый уровень погрешности", то можно взять левый край и провести из него отрезок как можно дальше, пока всё укладывается в погрешность. Потом из получившейся точки повторить операцию и т.д. Если реализовать правильно, то алгоритм линеен по количеству точек.

Здравствуйте, RomikT, Вы писали:
RT>Так как есть "определённый уровень погрешности", то можно взять левый край и провести из него отрезок как можно дальше, пока всё укладывается в погрешность. Потом из получившейся точки повторить операцию и т.д. Если реализовать правильно, то алгоритм линеен по количеству точек.

"пока всё укладывается в погрешность."
Так вот вопрос как рассчитывать погрешность?

"Потом из получившейся точки повторить операцию"
когда погрешность будет высока это будет не та точка которая от которой следует считать ранее. Эта точка будет уже дальше вершины находится. Надо находить именно точку на вершинах кривой(ломаной с высоким разрешением).

Если не отвечать на эти вопросы.. может есть другой алгоритм оптимизации ломаной?

Здравствуйте, Airaleais, Вы писали:

A>интересует алгоритм решения, примерный хотя бы. также приветствуются ссылки на литературу

На первый взгляд подойдёт построение прямой методом наименьших квадратов. Строим, например, по 5-ти первым точкам. Получившаяся погрешность меньше допустимой — добавляем 6-ю точку; опять меньше — 7-ю... При превышении останавливаемся, строим следующий отрезок.
Для ускорения, можно добавлять не по одной точке, а по 2 (3, 4, 5,...), а после превышения уже корректировать.

Здравствуйте, Nuzhny, Вы писали:
N>На первый взгляд подойдёт построение прямой методом наименьших квадратов. Строим, например, по 5-ти первым точкам. Получившаяся погрешность меньше допустимой — добавляем 6-ю точку; опять меньше — 7-ю... При превышении останавливаемся, строим следующий отрезок.
N>Для ускорения, можно добавлять не по одной точке, а по 2 (3, 4, 5,...), а после превышения уже корректировать.

>"Строим, например, по 5-ти первым точкам."
а почему именно по 5.. эти 5 точек тоже могут быть оптимизированы двумя отрезками а не одним

>"Получившаяся погрешность меньше допустимой"
Так вот вопрос как рассчитывать погрешность?

>"При превышении останавливаемся, строим следующий отрезок."
когда погрешность будет высока это будет не та точка которая от которой следует считать новый отрезок. Эта точка будет уже дальше вершины. Надо находить именно точку на вершинах кривой(ломаной с высоким разрешением).

Если не отвечать на эти вопросы.. может есть другой алгоритм оптимизации ломаной?

Здравствуйте, Airaleais, Вы писали:

A>Если не отвечать на эти вопросы.. может есть другой алгоритм оптимизации ломаной?

Можешь дать не картинку, а в текстовике набор чисел (x и y)? И максимальную погрешность.

Здравствуйте, Nuzhny, Вы писали:
N>Можешь дать не картинку, а в текстовике набор чисел (x и y)? И максимальную погрешность.

ну.. акей конечно)
[3,5,8,10,11,12,12,12,13,13,14,15,16,17,17,15,7,5,4,6,11,12,14,14,14,14,11,8,2,4,16,15,8,22,24,24,24,20,24,24,20,10,3,1,1,1,1,1,1,1,10,20,20,20,20,20]
вот массив значений Y графика
по X например с 5 с интервалом 1
в графике есть острые и тупые вершины.


N> максимальную погрешность.
ммм.. в чем погрешность? в процентах? ну пусть будет 35%

Здравствуйте, Airaleais, Вы писали:

A>Здравствуйте, RomikT, Вы писали:
RT>>Так как есть "определённый уровень погрешности", то можно взять левый край и провести из него отрезок как можно дальше, пока всё укладывается в погрешность. Потом из получившейся точки повторить операцию и т.д. Если реализовать правильно, то алгоритм линеен по количеству точек.

A>"пока всё укладывается в погрешность."
A>Так вот вопрос как рассчитывать погрешность?
А как рассчитывать погрешность это уже вы сами должны ответить — вы же сказали "до определенного уровня погрешности"

A>"Потом из получившейся точки повторить операцию"
A>когда погрешность будет высока это будет не та точка которая от которой следует считать ранее. Эта точка будет уже дальше вершины находится. Надо находить именно точку на вершинах кривой(ломаной с высоким разрешением).
Под "провести отрезок как можно дальше" я подразумевал "соединить начальную точку с как можно более удалённой точкой кривой".

A>Если не отвечать на эти вопросы.. может есть другой алгоритм оптимизации ломаной?
Возможно. Если вы определитесь с тем, что хотите от него получить.

Здравствуйте, RomikT, Вы писали:
A>>"пока всё укладывается в погрешность."
A>>Так вот вопрос как рассчитывать погрешность?
RT>А как рассчитывать погрешность это уже вы сами должны ответить — вы же сказали "до определенного уровня погрешности"
Ну образно я понимаю.. алгоритмически нет. иначе я бы тут сейчас не дискутировал)

A>>"Потом из получившейся точки повторить операцию"
A>>когда погрешность будет высока это будет не та точка которая от которой следует считать ранее. Эта точка будет уже дальше вершины находится. Надо находить именно точку на вершинах кривой(ломаной с высоким разрешением).
RT>Под "провести отрезок как можно дальше" я подразумевал "соединить начальную точку с как можно более удалённой точкой кривой".
Я правильно тебя понял и повторюсь. вторая точка отрезка, когда погрешность уже высока будет находится дальше то до которой стоит рисовать отрезок. т.е. мы проскочим ВЕРШИНУ графика.. вот)

A>>Если не отвечать на эти вопросы.. может есть другой алгоритм оптимизации ломаной?
RT>Возможно. Если вы определитесь с тем, что хотите от него получить.

ну по рисунке понятно ведь) уменьшить количество точек ломаной оставив их преимущественно на вершинах его или ОСТРЫХ ПОВОРОТАХ графика.
например:
[1,2,1,2,1,2,6,7,6,7,6,6,1,0,1,1,2,1]
вот график. это значния по Y. по Х значения от 0 с интервалом 1.
вот оптимизированый график[x,y]:

[0,1],[5,1],[6,6],[11,6],[12,1]]

мы тут опредили начало и конец [0,1] .. [12,1]
и углы графика. указали их координаты

*[0,1],[5,1],[6,6],[11,6],[12,1],[17,1]]

Здравствуйте, Airaleais, Вы писали:

A>Здравствуйте, Nuzhny, Вы писали:
N>>На первый взгляд подойдёт построение прямой методом наименьших квадратов. Строим, например, по 5-ти первым точкам. Получившаяся погрешность меньше допустимой — добавляем 6-ю точку; опять меньше — 7-ю... При превышении останавливаемся, строим следующий отрезок.
N>>Для ускорения, можно добавлять не по одной точке, а по 2 (3, 4, 5,...), а после превышения уже корректировать.

>>"Строим, например, по 5-ти первым точкам."
A>а почему именно по 5.. эти 5 точек тоже могут быть оптимизированы двумя отрезками а не одним

Это параметр алгоритма, который стоит подобрать экспериментально, на некотором количестве примеров. В крайнем случае начитать с 3 точек.

>>"Получившаяся погрешность меньше допустимой"
A>Так вот вопрос как рассчитывать погрешность?
Если использовать метод наименьших квадратов, то естественно и брать в качестве погрешности сумму квадратов отклонений по всем точкам.

>>"При превышении останавливаемся, строим следующий отрезок."
A>когда погрешность будет высока это будет не та точка которая от которой следует считать новый отрезок. Эта точка будет уже дальше вершины. Надо находить именно точку на вершинах кривой(ломаной с высоким разрешением).
Можете пояснить это утверждение.

A>Если не отвечать на эти вопросы.. может есть другой алгоритм оптимизации ломаной?

Есть ещё идея. Найти вторую производную, возможно сгладить её (чтоб убрать мелкие локальные экстремумы), и после этого вершинами ломаной считать экстремумы второй производной.

Здравствуйте, KRA, Вы писали:
>>>"Строим, например, по 5-ти первым точкам."
A>>а почему именно по 5.. эти 5 точек тоже могут быть оптимизированы двумя отрезками а не одним
KRA>Это параметр алгоритма, который стоит подобрать экспериментально, на некотором количестве примеров. В крайнем случае начитать с 3 точек.
А если точки такие.. [100,0,100] тут явный угол и он будет описан двумя отрезками обязательно. выходит с двух надо начинать.

KRA>Если использовать метод наименьших квадратов, то естественно и брать в качестве погрешности сумму квадратов отклонений по всем точкам.
прямо сейчас начну гуглить "сумма наименьших квадратов"

>>>"При превышении останавливаемся, строим следующий отрезок."
A>>когда погрешность будет высока это будет не та точка которая от которой следует считать новый отрезок. Эта точка будет уже дальше вершины. Надо находить именно точку на вершинах кривой(ломаной с высоким разрешением).
KRA>Можете пояснить это утверждение.
Наверно нет смысла пояснять. дело в том что это актуально в случае когда мы строим отрезок последовательно проходя по Х по одному и проверяя погрешность получившегося отрезка. у меня сначала был такой алгоритм. ставил первую точку. вторую вычислял как СРЕДНЮЮ ТОЧКУ из всех последующих. в случае когда точки сильно отклоняются от прямой (начало: [X1,Y1], конец: [(X2_1+X2_2+..+X2_n)/n , (Y2_1+Y2_2+..+Y2_n)/n])), то на этом месте или на приблизительно Xn-2 позиции считать концом отрезка и началом первого.
но это схема на рабочая..может рабочая но очень не точно.

A>>Если не отвечать на эти вопросы.. может есть другой алгоритм оптимизации ломаной?

KRA>Есть ещё идея. Найти вторую производную, возможно сгладить её (чтоб убрать мелкие локальные экстремумы), и после этого вершинами ломаной считать экстремумы второй производной.

что-то непонятно написал.. тоже погуглю спасибо

Здравствуйте, Airaleais, Вы писали:

KRA>>Это параметр алгоритма, который стоит подобрать экспериментально, на некотором количестве примеров. В крайнем случае начитать с 3 точек.
A>А если точки такие.. [100,0,100] тут явный угол и он будет описан двумя отрезками обязательно. выходит с двух надо начинать.
Это не факт, зависит от масштаба. Если точки такие [100, 0, 100, 1000000000, 12000000000], то скорее одним отрезком.
Какова природа функции? Т.е. откуда данные берутся? Если извесно что функция непрерывная, то в случае [100, 0, 100, 110, 130] 0 нужно считать ошибкой измерения.

>>>>"При превышении останавливаемся, строим следующий отрезок."
A>>>когда погрешность будет высока это будет не та точка которая от которой следует считать новый отрезок. Эта точка будет уже дальше вершины. Надо находить именно точку на вершинах кривой(ломаной с высоким разрешением).
KRA>>Можете пояснить это утверждение.
A>Наверно нет смысла пояснять. дело в том что это актуально в случае когда мы строим отрезок последовательно проходя по Х по одному и проверяя погрешность получившегося отрезка. у меня сначала был такой алгоритм. ставил первую точку. вторую вычислял как СРЕДНЮЮ ТОЧКУ из всех последующих. в случае когда точки сильно отклоняются от прямой (начало: [X1,Y1], конец: [(X2_1+X2_2+..+X2_n)/n , (Y2_1+Y2_2+..+Y2_n)/n])), то на этом месте или на приблизительно Xn-2 позиции считать концом отрезка и началом первого.
A>но это схема на рабочая..может рабочая но очень не точно.
Этот метод (если я его правильно понял) интуитивно не будет давать хороших результатов. Гораздо лучше пробовать в качестве конца отрезка точку кривой и для отрезка считать отклонение. Пока отклонение в пределах заданой погрешности — продолжаем. Вышло за пределы — начинаем новый отрезок.

KRA>>Есть ещё идея. Найти вторую производную, возможно сгладить её (чтоб убрать мелкие локальные экстремумы), и после этого вершинами ломаной считать экстремумы второй производной.

A>что-то непонятно написал.. тоже погуглю спасибо

Глядя на пример на глаз видно, что точки результирующей ломаной находятся в точках в которых третья производная равна нулю, отсюда и идея. Построить для имеющихся примеров третьи производные и посмотреть насколько их нули корелируются с вручную построенными ломаными.

Здравствуйте, Airaleais, Вы писали:

A>ну.. акей конечно)

Мой метод не работает как надо из-за того, что концы отрезков не соединены друг с другом + они могут не совпадать с точками самой кривой.
Увы

Здравствуйте, Airaleais, Вы писали:

A>Привет всем!
A>Мне очень нужна ваша помощь в задачи оптимизации ломаной графика. Т.е. построить новую ломаную с меньшим количеством точек до определенного уровня погрешности. Чтобы точки оставались преимущественно в явных вершинах.

Алгоритм Дугласа-Пекера (Douglas Peucker)

Здравствуйте, MBo, Вы писали:
MBo>Алгоритм Дугласа-Пекера (Douglas Peucker)

спасибо большое!

выкладываю код, чтобы завершить тему:

/// <summary>
/// Uses the Douglas Peucker algorithm to reduce the number of points.
/// </summary>
/// <param name="Points">The points.</param>
/// <param name="Tolerance">The tolerance.</param>
/// <returns></returns>
public static List<Point> DouglasPeuckerReduction
    (List<Point> Points, Double Tolerance)
{
    if (Points == null || Points.Count < 3)
    return Points;

    Int32 firstPoint = 0;
    Int32 lastPoint = Points.Count - 1;
    List<Int32> pointIndexsToKeep = new List<Int32>();

    //Add the first and last index to the keepers
    pointIndexsToKeep.Add(firstPoint);
    pointIndexsToKeep.Add(lastPoint);

    //The first and the last point cannot be the same
    while (Points[firstPoint].Equals(Points[lastPoint]))
    {
        lastPoint--;
    }

    DouglasPeuckerReduction(Points, firstPoint, lastPoint, 
    Tolerance, ref pointIndexsToKeep);

    List<Point> returnPoints = new List<Point>();
    pointIndexsToKeep.Sort();
    foreach (Int32 index in pointIndexsToKeep)
    {
        returnPoints.Add(Points[index]);
    }

    return returnPoints;
}
    
/// <summary>
/// Douglases the peucker reduction.
/// </summary>
/// <param name="points">The points.</param>
/// <param name="firstPoint">The first point.</param>
/// <param name="lastPoint">The last point.</param>
/// <param name="tolerance">The tolerance.</param>
/// <param name="pointIndexsToKeep">The point index to keep.</param>
private static void DouglasPeuckerReduction(List<Point> 
    points, Int32 firstPoint, Int32 lastPoint, Double tolerance, 
    ref List<Int32> pointIndexsToKeep)
{
    Double maxDistance = 0;
    Int32 indexFarthest = 0;
    
    for (Int32 index = firstPoint; index < lastPoint; index++)
    {
        Double distance = PerpendicularDistance
            (points[firstPoint], points[lastPoint], points[index]);
        if (distance > maxDistance)
        {
            maxDistance = distance;
            indexFarthest = index;
        }
    }

    if (maxDistance > tolerance && indexFarthest != 0)
    {
        //Add the largest point that exceeds the tolerance
        pointIndexsToKeep.Add(indexFarthest);
    
        DouglasPeuckerReduction(points, firstPoint, 
        indexFarthest, tolerance, ref pointIndexsToKeep);
        DouglasPeuckerReduction(points, indexFarthest, 
        lastPoint, tolerance, ref pointIndexsToKeep);
    }
}

/// <summary>
/// The distance of a point from a line made from point1 and point2.
/// </summary>
/// <param name="pt1">The PT1.</param>
/// <param name="pt2">The PT2.</param>
/// <param name="p">The p.</param>
/// <returns></returns>
public static Double PerpendicularDistance
    (Point Point1, Point Point2, Point Point)
{
    //Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|   *Area of triangle
    //Base = v((x1-x2)²+(x1-x2)²)                               *Base of Triangle*
    //Area = .5*Base*H                                          *Solve for height
    //Height = Area/.5/Base

    Double area = Math.Abs(.5 * (Point1.X * Point2.Y + Point2.X * 
    Point.Y + Point.X * Point1.Y - Point2.X * Point1.Y - Point.X * 
    Point2.Y - Point1.X * Point.Y));
    Double bottom = Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) + 
    Math.Pow(Point1.Y - Point2.Y, 2));
    Double height = area / bottom * 2;

    return height;
    
    //Another option
    //Double A = Point.X - Point1.X;
    //Double B = Point.Y - Point1.Y;
    //Double C = Point2.X - Point1.X;
    //Double D = Point2.Y - Point1.Y;
    
    //Double dot = A * C + B * D;
    //Double len_sq = C * C + D * D;
    //Double param = dot / len_sq;
    
    //Double xx, yy;
    
    //if (param < 0)
    //{
    //    xx = Point1.X;
    //    yy = Point1.Y;
    //}
    //else if (param > 1)
    //{
    //    xx = Point2.X;
    //    yy = Point2.Y;
    //}
    //else
    //{
    //    xx = Point1.X + param * C;
    //    yy = Point1.Y + param * D;
    //}
    
    //Double d = DistanceBetweenOn2DPlane(Point, new Point(xx, yy));
}

Здравствуйте, MBo, Вы писали:

MBo>Алгоритм Дугласа-Пекера (Douglas Peucker)

Начал читать, нашёл ещё алгоритмы Rosenfeld-Johnson и Teh-Chin.

N>Начал читать, нашёл ещё алгоритмы Rosenfeld-Johnson и Teh-Chin.

линк? сходу не нашлось