Как выразить численно "похожесть" Безье сплайнов

[Kalze]

Есть три кубических безье кривых с точками $A_1, A_2, A_3, A_4; B_1, B_2, B_3, B_4; C_1, C_2, C_3, C_4$ . При этом $A_4=B_1, A_1=C_1, B_4=C_4 $
Задача в том, чтобы определить некую меру похожести кривой состоящей из двух безье кривых A и B с кривой C. Конечная точка А совпадает с началом B. начало С совпадает с началом А, а конец С совпадает с концом B.
Задача интересна с компьюетрной точки зрения.
Есть идеи поиска чего-то вроде расстояния Фреше для них. Но не совсем понимаю как его применить, то есть нужно максимальное расстояние из всех минимальных расстояних для каждой точки? Как это вычислить, оформить, найти?
Ещё есть вариант поиска площади получившегося многоугольника из кривых, но что если они будут пересекаться, да и как его найти?
А может вообще решение уже есть, а я просто его не нашёл?
У кого какие идеи? Заранее спасибо

[worm2]

Расстояние Фреше — это сложно. Можно попробовать использовать тот факт, что кривые Безье уже достаточно просто параметризованы с параметром $t \in [0, 1]$. Если этот параметр как-то пересчитать для объединения кривых $A: t \in [0, \tau]$ и $B: t \in [\tau, 1]$, чтобы получить единую параметризацию $A\cup B: t \in [0, 1]$, и затем сравнить её со стандартной параметризацией $C: t \in [0, 1]$, используя сумму квадратов отклонений:

$$\int_0^1 \left((A\cup B)(t)-C(t)\right)^2 dt \to \min,$$

то получится сравнительно простой алгоритм. Вопрос, как определить оптимальный параметр $\tau$, т.е. какой точке на $C$ будет соответствовать $A_4=B_1$? Один из вариантов решения — брать минимум интеграла по всевозможным $\tau$ и объявить оптимальным лучшее $\tau$. Но могут вылезти вычислительные трудности (а могут и не вылезти, не знаю).
Можно действовать грубо, опираясь на длины исходных ломаных, но результат может оказаться сильно хуже. Экспериментировать надо.

[Kalze]

worm2 в сообщении #1442987 писал(а):

Расстояние Фреше — это сложно. Можно попробовать использовать тот факт, что кривые Безье уже достаточно просто параметризованы с параметром $t \in [0, 1]$. Если этот параметр как-то пересчитать для объединения кривых $A: t \in [0, \tau]$ и $B: t \in [\tau, 1]$, чтобы получить единую параметризацию $A\cup B: t \in [0, 1]$, и затем сравнить её со стандартной параметризацией $C: t \in [0, 1]$, используя сумму квадратов отклонений:

$$\int_0^1 \left((A\cup B)(t)-C(t)\right)^2 dt \to \min,$$

то получится сравнительно простой алгоритм. Вопрос, как определить оптимальный параметр $\tau$, т.е. какой точке на $C$ будет соответствовать $A_4=B_1$? Один из вариантов решения — брать минимум интеграла по всевозможным $\tau$ и объявить оптимальным лучшее $\tau$. Но могут вылезти вычислительные трудности (а могут и не вылезти, не знаю).
Можно действовать грубо, опираясь на длины исходных ломаных, но результат может оказаться сильно хуже. Экспериментировать надо.

Если моя задача в том, что если эти два сплайна чем ближе и "похожее" тем лучше, то можно ли тогда предполагать, что новый параметр взятый так, чтобы $t=0.5$ соответсвовал точке $A_4=B_1$ окажется достаточным для этих целей?
То есть эти сплайны в общем то очень похожи должны быть изначально. И задача как раз ввести некий критерий: "похожа ли исходная кривая на новый сплайн из двух кривых".
Или может существовать некий пример кривых при которых такая новая параметризация может дать некий минимум при их разных формах? Насколько позволяет воображение не могу таких представить.
Что думаете?

[Утундрий]

Kalze
Вы сможете сказать, похожи или не похожи две кривые, просто глядя на них? Если нет, то и говорить не о чем.

[Kalze]

Утундрий в сообщении #1442999 писал(а):

Kalze
Вы сможете сказать, похожи или не похожи две кривые, просто глядя на них? Если нет, то и говорить не о чем.

Смогу, я же описал даже примерные критерии, позволяющие представить о чём речь: площади образуемого многоугольника или расстояние Фреше, но я плохо представляю как их вычислить в программе с учетом того, что кривые могут пересечься

[worm2]

Про площадь многоугольника я пропустил, интересный критерий. Для этого нужно найти точки пересечения кривых $A\cup B$ и $C$. Мне представляется поиск этих точек таким образом: сначала выписываем уравнение $C$ в неявном виде $F(x, y) = 0$ (это сложно, но, кажется, готовый ответ есть вот здесь: https://www.istu.edu/docs/education/normativ/fgos/educ_progr/text_prog/gaer2.pdf, стр. 18–19). Затем идём по кривым $A$ и $B$, находя для них точки, где $F=0$. Например, численно, методом деления отрезка пополам. Хотя можно и аналитически выписать, получается 2 многочлена степени не выше девятой от $t$, вот у них и ищем корни. Найдя точки пересечения, находим фигуры, расположенные между кривыми и считаем для каждой площадь, что сравнительно просто (гуглить "площадь фигуры, ограниченной параметрически заданной кривой").

[arseniiv]

Очень полезная справочная страница про Безье: A Primer on Bézier Curves, в частности может быть полезен раздел про разрезание кривой на две: может быть если найти точку, ближайшую на кривой $C_1\ldots C_4$ к точке $A_4 = B_1$, разрезать $C_1\ldots C_4$ по ней и сравнивать уже кусочки с $A_1\ldots A_4$ и $B_1\ldots B_4$, можно будет выбрать способ сравнения попроще. В любом случае даже если не для этой темы, для других операций с кривыми Безье может помочь.

-- Пт мар 06, 2020 00:43:38 --

Да, ещё можно взять достаточно большое число $N$ равноотстоящих точек на $C_1\ldots C_4$ и $A_1\ldots B_4$ (по ссылке есть и про это) и сравнить попарные расстояния (взять от них всех максимум, сумму квадратов, просто сумму или ещё какую-то функцию). Мне кажется (но я ничего не считал), что для приемлемого результата будет достаточно $N\lesssim8$.

UPD: Сначала написал 8, потом сбавил до 5, но потом передумал.