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

Question

Я пытаюсь написать какое-то программное обеспечение для обнаружения точек / линий на основе того, что пользователь рисует на холсте (я делал все это через Интернет и HTML 5 canvas). Когда пользователь выполняет событие 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)], потому что я буду использовать первую точку последовательности, постараюсь найти четкое изменение направления и получить эту точку, и используйте последнюю точку в последовательности.

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

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

РЕДАКТИРОВАТЬ: опечатка

Answer 1

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

Answer 2

Скажите ваши точки, в следующем порядке: ((x1, y1), (x2, y2),..., (xn, yn)]. Вычислить приблизительные производные между каждым последовательным набором точек: 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 3

Скажем, у вас есть точки P(i), где i=0 ~ (N-1), для каждой точки вы можете вычислить обратный наклон как P(i)-P(im) и прямой наклон как P(i+m)-P(i), где m

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