Расчет сходства между нарисованными линиями

Question

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

Например, на следующей диаграмме:

Линии A и B явно похожи, но B и C - нет. Алгоритм должен отражать это. Кроме того, имеет значение «направление» линии, обозначенное начальной и конечной точками. Такой алгоритм уже существует?

Answer 1

Наивным подходом может быть сумма расстояний между соответствующими точками на двух линиях. Итак, предположим, что обе линии имеют почти одинаковую длину, а количество точек на линиях примерно одинаково и равноудалено.
1. Переведите строку 2 так, чтобы ее начальная точка совпадала с начальной точкой строки 1.
2. вычислите сумму расстояний между соответствующими точками между линией 1 и линией 2.
3. Если среднее расстояние (т. Е. SUM / NUMBER_OF_POINTS) меньше, чем THRESHOLD, то линии аналогичны, в противном случае они различаются.
Это может быть расширено для поддержки линий с различными размерами. В этом случае просто увеличьте меньшую линию, чтобы она соответствовала более длинной линии, тогда отдых может быть аналогичен описанному выше подходу.
Помимо расчета расстояния, вы можете рассчитать разницу наклонов линий и, если она различна в уклоны в любой точке (или в нескольких точках, для этого нужно провести какой-то эксперимент) - это путь к высокому (выше некоторого ПОРОГА), тогда они не похожи.

Answer 2

Этот ответ крайне задержан, но я буду публиковать ради других, как я, которые наткнуться на него при поиске.

Я считаю, что Расстояние Фреше может быть мерой, которую вы ищете, особенно потому, что направление имеет значение.

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