Point / Line Detection Based on a Set of Consecutive / Semi-Consecutive Points

Question

I am trying to write some point / line detection software based on what a user is drawing on a canvas (I have been doing this all via the web and html 5 canvas). When a user performs a MouseDown event we create an array that will hold all of the points of his / her drawing. Each MouseMove event after that pushes a point (x, y) onto the array. The MouseUp event signals the end of the user's drawing. What I want to do with those points is determine where the user has distinctly changed directions. Take the following example:

The above methodology has generated the following ordered set of points:

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

So based on these points I can tell the user has distinctly changed directions at point (5, 5) onward. The outcome of the program would give me three points [(1, 1), (5, 5), (8, 2)] because I will use the first point of the sequence, try to find a distinct change in direction and get that point, and use the final point in the sequence.

The above example is extremely simplified because of the number of points and the fact that they are in a completely straight line. When a user is actually drawing on a canvas the line will not be completely straight. For my purposes you can assume the user is drawing straight-ish lines and not blatantly curved ones.

So based on the above information what algorithms, methodologies, etc would you suggest I use?

EDIT: typo

Answer 1

Say your points, in order are [(x1, y1), (x2, y2),..., (xn, yn)]. Compute approx derivatives between each consecutive set of points: D1 = (y2-y1)/(x2-x1), D2=(y3-y2)/(x3-x2), etc. Then watch for significant (lasting) changes in the derivative. In your case, D1=1, D2=1, D3=1, D4=1, D5=-1, D6=-1, D7=-1. Note that you have to be careful if they draw a vertical line because the division will be by zero in that case.

Answer 2

There is Douglas–Peucker algorithm, intended to simplify polylines and curves. If finds similar polyline with fewer points.

Answer 3

Say you have points P(i), where i=0 ~ (N-1), for each point, you can compute the backward slope as P(i)-P(i-m) and forward slope as P(i+m)-P(i), where m < N. Then you can compute the slope's turning angle at Pi as the angle between backward slope and the forward slope. When the turning angle is greater than a threshold value (say 60 degree), then you have a sharp turn in your path.

The choice of the value of m is a bit tricky and requires a little bit experiment with your actual data point. It is in fact somehow dependent on how dense your data points are. If m is very small (such as 1), then you will identify many unwanted sharp turns from data noise. When m is too big, then it is likely that you will miss some sharp turns. Of course, by going with this approach we do not identify any sharp turns in the first and last (m-1) points.