Вычисление подобия между нарисованными линиями

Question

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

К примеру, в соответствии со следующей схемой:

Линии А и В, очевидно, похожи, но В и С не являются. Алгоритм должен отражать это. Кроме того, имеет значение «направление» линии, обозначенное начальным и конечным точками. Существует ли такой алгоритм?

Answer 1

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

Answer 2

Взгляните на Hough transform. Это может быть излишним, возможно, у кого-то есть лучшее решение.