Подскажите, пожалуйста, как можно векторизовать сплайновую кривую (NURB), превратив её в ломаную (набор отрезков) с минимальным количеством отрезков.
Сплайн задан численно. Точность оговаривается.
Интересует готовый алгоритм, если он есть, разумеется.
Спасибо.

Здравствуйте, Аноним, Вы писали:

А>Подскажите, пожалуйста, как можно векторизовать сплайновую кривую (NURB), превратив её в ломаную (набор отрезков) с минимальным количеством отрезков.
А>Сплайн задан численно. Точность оговаривается.
А>Интересует готовый алгоритм, если он есть, разумеется.

Вот, товарищ Tony Juricic подрудился, за что ему гигантский респект.
http://article.gmane.org/gmane.comp.graphics.agg/1262
http://article.gmane.org/gmane.comp.graphics.agg/1263

Для компиляции примера надо скачать AGG: http://antigrain.com/agg23.zip и положить RationalCurves куда-нибудь типа agg23/research/win32/RationalCurves/*

Пользоваться его классами тоже просто, можно и безо всяких AGG, если "отчистить" от зависимости от "agg_basics.h"
Вызываем nurbs.rewind(0);
Затем nurbs.vertex(&x, &y); до тех пор, пока он не вернет 0. В x,y будут координаты очередной точки для кусочно-линейной аппроксимации.

Процедура вычисления точек сплайна с фиксированным шагом параметра мне никак не подходит.

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

На сплайнах встречаются и пологие участки, и острые. В случае постоянного шага, при
большом шаге разбиения имеем проблемы с передачей формы на острых участках, при малом
имеем избыточное количество векторов на пологих участках.

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

Потому, собственно, интересуюсь: может быть, кто-то уже решал подобную задачу....

Здравствуйте, Аноним, Вы писали:

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

Тогда больше подойдет рекурсивный метод деления пополам:

void Bezier(Path* p,
            double x1, double y1, 
            double x2, double y2, 
            double x3, double y3, 
            double x4, double y4)
{

    double x12,y12,x23,y23,x34,y34,x123,y123,x234,y234,x1234,y1234;

    // if the manhattan distance between points (x1,y1) and (x4,y4) < 5.0
    // plot the line (x1,y1,x4,y4)
    if(fabs(x4-x1)+fabs(y4-y1) < 5.0)
    {
        p->AddVertex(x4, y4);
        return;                 // Return up recursion tree
    }

    // Calculate all the mid-points of the lines //
    x12 = (x1+x2)/2;                
    y12 = (y1+y2)/2;
    x23 = (x2+x3)/2;
    y23 = (y2+y3)/2;
    x34 = (x3+x4)/2;
    y34 = (y3+y4)/2;
    x123 = (x12+x23)/2;
    y123 = (y12+y23)/2;
    x234 = (x23+x34)/2;
    y234 = (y23+y34)/2;
    x1234 = (x123+x234)/2;
    y1234 = (y123+y234)/2;
    Bezier(p, x1,y1,x12,y12,x123,y123,x1234,y1234);
    Bezier(p, x1234,y1234,x234,y234,x34,y34,x4,y4);
}

При этом можно очень гибко управлять условием:

    if(fabs(x4-x1)+fabs(y4-y1) < 5.0)
    {
        p->AddVertex(x4, y4);
        return;                 // Return up recursion tree
    }

Здесь оно примитивное, но вполне несложно вычислить "курватуру" по 4-м точкам. Берем atan2 между первым и вторым отрезком и между вторым и третьим. Нормализуем, складываем по модулю, и если значение не превышает некий tolerance, заканчиваем. Можно взять другой критерий — суммарное расстояние по модулю точек 1 и 4 от прямой, определяемой точками 2 и 3.

Здравствуйте, Аноним, Вы писали:

А>Подскажите, пожалуйста, как можно векторизовать сплайновую кривую (NURB), превратив её в ломаную (набор отрезков) с минимальным количеством отрезков.
А>Сплайн задан численно. Точность оговаривается.
А>Интересует готовый алгоритм, если он есть, разумеется.
А>Спасибо.

Посмотрите алгоритм Douglas-Peucker -а. Может быть это оно и есть.

Есть програмная реализация алгоритма для 2D на http://www.codeproject.com/cpp/dphull.asp

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

P>Посмотрите алгоритм Douglas-Peucker -а. Может быть это оно и есть.
P>Есть програмная реализация алгоритма для 2D на http://www.codeproject.com/cpp/dphull.asp

В принципе можно и так, но при этом мы получим что-то типа "вылить воду из чайника и таким образом свести задачу к предыдущей". То есть, считаем Безье инкрементальным способом, после чего фильтруем. Но у нас набор точек не является исходными данными, следовательно, можно объединить.

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

Вы правы, отчасти.
Я не знаю какая задача стоит у автора топика, но она у меня подобна. Я думал о другой задаче — каким образом можно отобразить скажем числовую серию из 1 миллиарда -10e9-100e9 итд точек на экране — флейм на эту тему почему-то спарадически появляется на MFC-форуме.
Если точки графика не представляют из хаотичного перемещения по всей плоскости, то любой участок можно представить грубой ломаной или плоскостью без искажения общей картины. "Вылить воду из чайника"- то бишь построить сплайн и посчитать ломаную для меня не самое критичное, простим криворукому задержку в 3-5 секунд при первом выводе данных — дальше все будет летать со страшной скоростью, критичность возникает, естественно, если "работать" в лоб. К сожалению, большинство 2D коммерческих чартов (если не все) работают по этому принципы (пожалуй, естественное исключение составляют программы отображения фракталов ), о 3D умолчу, — я не видел ни одной программы или компонента который бы не сдохнул на миллионе узлов с обрушением всей систем win9x — ...и дальше по линейке ... Думаю "Векторизация сплайновой кривой" спасает положение, хотя, как вы и говорите криво спасает.
Где возможен выйгрыш сплайнового подхода, так это в задачах "зум с лету", опять же не проверял, я так полагаю.

Спасибо за наводящие ответы, я буду проверять.

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

P>Вы правы, отчасти.
P>Я не знаю какая задача стоит у автора топика, но она у меня подобна. Я думал о другой задаче — каким образом можно отобразить скажем числовую серию из 1 миллиарда -10e9-100e9 итд точек на экране — флейм на эту тему почему-то спарадически появляется на MFC-форуме.

Интересно... Если взять область 1000x1000 пикселов, то это получается по 1000 точек на каждый пиксел. А если это некая "вменяемая" кривая, то ее результирующая длина гораздо меньше миллиона пикселов, скажем, 4000 пикселов, что будет в среднем 250000 точек на пиксел. И конечно же, WinGDI в принципе не способен это сделать, поскольку, например, Polyline требует массива точек в памяти, который в принципе невозможно аллокировать. Можно только читать файл и по ходу дела вызывать LineTo.

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

P>Если точки графика не представляют из хаотичного перемещения по всей плоскости, то любой участок можно представить грубой ломаной или плоскостью без искажения общей картины. "Вылить воду из чайника"- то бишь построить сплайн и посчитать ломаную для меня не самое критичное, простим криворукому задержку в 3-5 секунд при первом выводе данных — дальше все будет летать со страшной скоростью, критичность возникает, естественно, если "работать" в лоб.

По-моему, за 3-5 секунд четыре гига данных не прочитаешь...

P>К сожалению, большинство 2D коммерческих чартов (если не все) работают по этому принципы (пожалуй, естественное исключение составляют программы отображения фракталов ), о 3D умолчу, — я не видел ни одной программы или компонента который бы не сдохнул на миллионе узлов с обрушением всей систем win9x — ...и дальше по линейке ... Думаю "Векторизация сплайновой кривой" спасает положение, хотя, как вы и говорите криво спасает.

Ну если массив точек существует как данность, то конечно же надо как-то упрощать и аппроксимировать. Если же точки генерируются чем-то нам подконтрольным, то нужно позаботиться о разумном их количестве еще на этапе генерации.

P>Где возможен выйгрыш сплайнового подхода, так это в задачах "зум с лету", опять же не проверял, я так полагаю.

Вообще-то, вопрос о точности аппроксимации Безье — крайне непростой. Я пока что делаю примитивно, но буду думать как улучшить.

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


MS>Вообще-то, вопрос о точности аппроксимации Безье — крайне непростой. Я пока что делаю примитивно, но буду думать как улучшить.

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

Вот результат некоторых исследований:
http://www.rsdn.ru/Forum/Message.aspx?mid=1226416&only=1

Автор: McSeem2
Дата: 16.06.05

Здравствуйте, <Аноним>, Вы писали:

А>Подскажите, пожалуйста, как можно векторизовать сплайновую кривую (NURB), превратив её в ломаную (набор отрезков) с минимальным количеством отрезков.
А>Сплайн задан численно. Точность оговаривается.
А>Интересует готовый алгоритм, если он есть, разумеется.
А>Спасибо.

Могу предложить алгоритм для кубических сплайнов (не рациональных). Он хорош, когда нужна заданная точность интерполяции маленьким количеством отрезком. ИМХО, для задачи отрисовки лучше воспользоваться делением пополам.
Сплайн представим в виде
X(t) = Ax*t^3 + Bx*t^2 + Cx*t + Dx
Y(t) = Ay*t^3 + By*t^2 + Cy*t + Dy
Сначала добавим в интерполяцию точки при t = 0, при t = 1 и точку перегиба (её легко посчитать).
Таким образом получаем одну (0->1) или две (0 -> точка перегиба, точка перегиба -> 1) хорды, в зависимости от того, есть ли точка перегиба.
После этого считаем максимальное отклонение сплайна от текушей хорды и в точке максимального отклонения хорду разделяем на две. Точку максимального отклонения легко посчитать, если учесть что в ней касательная к сплайну параллельна хорде, то есть достаточно решить квадратное уравнение
A*X'(t) + B*Y'(t) = 0, где A = -sin(alpha), B = cos(alpha), где alpha — угол наклона хорды.