Обнаружение точки/линии на основе набора последовательных/полупоследовательных точек

Question

Я пытаюсь написать некоторое программное обеспечение для обнаружения точек и линий, основанное на том, что пользователь рисует на холсте (я делал все это через Интернет и html 5 холст). Когда пользователь выполняет событие MouseDown, мы создаем массив, который будет содержать все точки его/ее рисунка. Каждое событие MouseMove после этого толкает точку (x, y) в массив. Событие MouseUp сигнализирует о завершении чертежа пользователя. То, что я хочу делать с этими точками, определяет, где пользователь явно изменил направление. Рассмотрим следующий пример:

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

[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 4), (7, 3), (8, 2)]

Таким образом, исходя из этих точек, я могу сказать, что пользователь четко изменил направления в точке (5, 5) вперед , Результат программы даст мне три очка [(1, 1), (5, 5), (8, 2)], потому что я буду использовать первую точку последовательности, попытаюсь найти четкое изменение направления и получить эту точку и использовать конечную точку в последовательности.

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

Итак, основываясь на приведенной выше информации, какие алгоритмы, методологии и т. Д. Вы бы предложили использовать?

EDIT: опечатка

Answer 1

Скажите ваши очки, чтобы это [(x1, y1), (x2, y2), ..., (хп, уп)]. Вычислить приблизительно производные между каждым последовательным набором точек: D1 = (y2-y1)/(x2-x1), D2 = (y3-y2)/(x3-x2) и т. Д. Затем следите за значительными (длительными) изменениями в производное. В вашем случае D1 = 1, D2 = 1, D3 = 1, D4 = 1, D5 = -1, D6 = -1, D7 = -1. Обратите внимание, что вы должны быть осторожны, если они рисуют вертикальную линию, потому что в этом случае деление будет равным нулю.

Answer 2

Существует Douglas–Peucker algorithm, предназначенный для упрощения полилиний и кривых. Если находит аналогичную полилинию с меньшим количеством точек.

Answer 3

Допустим, вы имеете точки Р (I), где I = 0 ~ (N-1), для каждой точки, можно вычислить наклон назад, как Р (я) -P (им) и наклон вперед как P (i + m) -P (i), где m < N. Затем вы можете вычислить угол поворота склона на Pi как угол между обратным наклоном и наклоном вперед. Когда угол поворота больше порогового значения (скажем, 60 градусов), тогда у вас есть резкий поворот на вашем пути.

Выбор значения m немного сложный и требует немного эксперимента с вашей фактической точкой данных. На самом деле это зависит от того, насколько плотны ваши точки данных. Если m очень мало (например, 1), вы обнаружите много нежелательных резких поворотов от шума данных. Когда m слишком велико, то, скорее всего, вы пропустите некоторые острые повороты. Конечно, перейдя к этому подходу, мы не определяем каких-либо резких поворотов в первой и последней (m-1) точках.