Сравнение кривых Безье

Строить и по какой-нибудь метрике сравнивать? Например, по среднеквадратичной или чебышевской.

Можно пытаться строить не попиксельно, а по сетке с большим шагом.

не понимаю, что ты вкладываешь в понятие «сравнивать» в данном контексте.

В смысле строить? Находить следующие от начальной точки?

если да, то

а по сетке с большим шагом.

имеется в виду длинна отрезка кривой или проекции на оси?

сам пока не понимаю, это как два яблока - вроде похожи, а вроде совершенно разные

Да, находить следующие точки. Имел в виду проекции, но это не столь важно.

интуитивный вариант - совместить начала и соединить прямой - концы, площадь образовавшейся фигуры будет некоей «разницей»

Но зачем?

А какой именно результат требуется от сравнения?

Некий коэффициент

Некий функционал, уж тогда.

Некий коэффициент

ну посчитай инеграл от разницы в квдарате.

Удивись:

https://dl.dropboxusercontent.com/u/31471800/p2p/Без имени.png

я сказал от _разницы_. [latex]\int_a^b (f_1(x)-f_2(x))^2 dx[/latex]

Только кривая Безье - параметрическая. По чему интегрировать?

http://www.wolframalpha.com/input/?i=integrate (x^2 - 2x^2)^2 from 0 to 5
http://www.wolframalpha.com/input/?i=integrate (x^2 - 2x*3.75%29%5E2+from+0+to+5

Они таааак похожи между собой, эти 2x^2 и 2x*3.75

по данному критерию - похожи. Мсье что-то имеет против?

Только кривая Безье - параметрическая. По чему интегрировать?

по параметру. В аппроксимируемой на интервале [a,b] функции сделай замену переменной [latex]x=(1-t)a+tb[/latex]

А если тебе просто две кривых Безье [latex]C_1,C_2[/latex] надо сравнить, то тогда

[latex]\int_0^1 \Vert C_1(t)-C_2(t)\Vert^2 dt[/latex].

Я бы считал, что две кривые Безье одинаковы, если есть линейное преобразование координат, переводящее одну в другую. Для начала тогда хорошей идеей было бы найти это преобразование - оно переводит отрезки между первой и последней опорными точками кривых друг в друга.

После применения этого преобразования получим две кривых, начинающихся и заканчивающихся в одинаковых точках. Далее, кривая безье как и разность между ними это на самом деле система уравнений x(t)=... y(t)=...

Тогда dx=...dt, dy=...dt и возможно имеет смысл проинтегрировать по параметру форму sqrt(dx^2+dy^2).

Интересен физический смысл получаемого интеграла.

как вариант тоже. Еще можно поднять вопрос о том, чтобы сделать «разницу» инвариантной относительно скорости пробегания кривой. Ну то есть для каждой точки кривой C_1 искать ближайшую точку кривой C_2. В общем, зависит о того, что хочет получить ТС. Поэтому я предлагаю подождать.

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

Интересен физический смысл получаемого интеграла.

хм. мне не интересен :)

Кстати, получить инвариантность относительно аффинного преобразования можно проще:

пусть есть n точек P_i. К ним существуют коэффициенты в виде полиномов B_i(t). Кривая C(t) получается в виде [latex]\sum_{i=1}^n B_i(t)P_i[/latex]. Пусть теперь B(t) - это вектор образованный из B_i(t). Разницу считаем в виде

[latex]\int_0^1 \Vert B^{(1)}(t)-B^{(2)}(t)\Vert^2 dt[/latex]

Единственная проблема - в нумерации точек. В лоб можно решить подсчетом всех возможных интегралов при разных перестановках точек. Получается посчитать n! интегралов для сравнения. Можно наверное и лучше, но и так для начала пойдет.

Инвариантность будет в виду того, что вектор B(t) представляет собой барицентрические координаты.

cast pseudo-cat. Чтобы увидеть latex-формулы в читаемом виде, поставь скрипт из профиля Эдички.

Для меня визуальная похожесть пропорциональна площади между кривыми. Поэтому мне и интересно, нервами, о интеграл соответствует этой площади.

Про скорости движения по кривым ты очень верно подметил.

Пусть в момент времени t мы находимся на первой кривой в точке x1(t),y1(t) а на второй кривой в точке x2(t),y2(t). Тогда расстояние между ними это sqrt(x^2+y^2), где x=x1-x2, y=y1-y2.

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

нужно сравнивать сложные кривые, образованные несколькими кривыми Безье, последовательно соединённых через опорные точки

Я бы попробовал:
1. Построить кусочно-линейную аппроксимацию кривых. Recursive subdivision, до тех пор, пока максимальное отклонение аппроксимирующей ломаной от исходной кривой не окажется в пределах некого малого epsilon.
2. Затем сравнить получившиеся ломаные.

Отличный метод.

У кривых начало и конец общие? Или что тогда «площадь между кривыми»?

кто такая эта Эдичка?

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

Или что тогда «площадь между кривыми»?

Eсть две кривых: Г1={(x(t), y(t))|0<t<1} и Г2={(u(s), v(s))|0<s<1}. В случае кривых Безье, x, y, u и v — полиномы. Паре чисел (t, s) соответствует отрезок, соединяющий точку на Г1 с точкой на Г2; обозначу этот отрезок как D(t, s) и буду дальше говорить о нем как о множестве точек на плоскости. Можно найти пару монотонных непрерывных функций { (t(r), s(r)) | t(0)=0, t(1)=1, s(0)=0, s(1)=1 } таких, чтобы площадь фигуры { D(t(r), s(r)) | 0<r<1} была минимальна. Вот это и будет «площадь между кривыми».

визуальная похожесть

Визуально большую роль играют перегибы (inflection points), а также самопересечения (loops) и изломы (cusp): см картинки на второй странице http://www.math.zju.edu.cn/cagd/Seminar/2006_SpringSummer/2006_Spring_Doctor_...

кто такая эта Эдичка?

Eddy_Em

Уточню, меня интересует визуальная похожесть при соблюдении пропорций.

Сравнение кривых Безье (комментарий)

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

Да. Линейное преобразование. Выше писал.

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

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

Пусть кривые Г1 и Г2 параметризованы одним параметром 0<r<1 имеют общие концы и пересекаются в ещё двух точках r1 и r2.

Эти точки разбивают каждую из кривых на три участка. Длины этих участков для Г1 обозначим как a1 a2 a3, для кривой Г2 соответственно b1 b2 b3. Причем выполнены неравенства:

a1 < b1, a2 > b2, a3 < b3.

Тогда фигура {D(r,r), 0<r<1} из проведённого определения не будет совпадать с «визуальной площадью» между ними, и не удастся найти монотонной перепараметризации одной из кривых r=r(v) чтоб фигура {D(r(v)), v), 0<v<1} совпадала с «визуальной площадью» между ними. А вот немонотонную, кусочно заданную, найти можно. Вот почему я против перепараметризации на кривых - искать сложно.

не удастся найти монотонной перепараметризации

Почему? Мне кажется, что как раз удастся.

Мира кривизны если я не ошибаюсь это как раз интеграл от формы sqrt(dx^2+dy^2).

Ладно, подумаю. Я так сходу не вижу.

А, все, понял😊 Отличное определение, отлично сформулировано.

Уточню, меня интересует визуальная похожесть при соблюдении пропорций.

Переходи в спектральную область, где есть инвариантность к масштабу и где разность нормированных спектров будет пропорциональна «похожести» кривых.

Я все же пока предлагаю ТС остановиться на следующем способе сравнения:

1) Линейным преобразованием добиваемся, чтоб обе кривые начинались в точке (0,0) и заканчивались в точке (1,0). Получим уравнения новых кривых x1(t),y1(t) и x2(t),y2(t).

2) [Без перепараметризации на кривых, о которой шла речь ранее, и которая надеюсь понятно зачем необходима] Рассчитываем интеграл по параметру от 0 до 1 от функции sqrt(x^2+y^2), где x(t)=x1(t)-x2(t) и y(t)=y1(t)-y2(t). Этот интеграл будет больше площади между кривыми, но на первый взгляд кажется что при уменьшении площади уменьшается и он.

3) Для расчёта интеграла пользуемся тем фактом, что имеем дело с кривыми Безье (см. посты выше).

4) Если эксперименты показывают хорошую эффективность 2) то радуемся. Иначе нужно на одной из кривых делать монотонно перепараметризацию. Готовой формулы нет, надо будет сильно думать, может быть её можно отыскать в каком-то классе функций. Лучше, чтоб 2) сработало.

Линейным преобразованием добиваемся, чтоб обе кривые начинались в точке (0,0) и заканчивались в точке (1,0).

Это ведь приведёт к изменению масштаба кривой.

как-то совсем не понятно, что за спектральная область?

Само собой, приведёт. А мы считаем кривые, различающиеся только лишь масштабом, разными?

вообще да, но масштаб можно и отдельно проверить

Так может быть и сдвигать и крутить их тоже нельзя?

Дело в том, что сравниваются группы примитивов, среди которых есть кривые Безье. Сравнение начинается с двух примитивов для которых вычисляется матрица трансформации так, чтобы они максимально совпадали. После этого эта матрица применяется ко всем примитивам. И на этом этапе крутить и сдвигать их нельзя. Но это не принципиально т.к. можно сделать дополнительные проверки, не пройдя которые кривые просто не будут сравниваться.