Algorithm to predict pen/mouse input

Question

I'm looking for an appropriate algorithm that reliably predicts input coordinates given by a digital stylus (e.g. Surface Pen). In my application, I'm given the coordinates of the input as x and y coordinates on the screen (together with their timestamps). Given a list of events ordered chronologically, my aim is to find the coordinate of the "next" events.

The simple algorithm I came up with is using weighted average. Here is some code that illustrates it (in real code I use more than just 4 points):

class Point{
    double x;
    double y;
    double timestamp;
}

// this contains 4 points
// in chronological order
vector<Point> points;

// predict using simple weighted average
// the subtraction operation is simply subtraction on x and y coordinates
Point diff1 = points[1]-points[0];
Point diff2 = points[2]-points[1];
Point diff3 = points[3]-points[2];

// add a weighted difference to the last point we have
Point predictedPoint = points[3] + diff1 * 0.2 + diff2 * 0.3 + diff3 * 0.5;

This doesn't work as well as I would like to as often the predicted input is not very accurate. So I would like to find something better that estimates the next input based on previous points (it'd be nice if this accounted for the velocity of inputs as well).

Answer 1

Unfortunately not a go to answer but merely some solution directions to consider.

One option is to plot the coordinates as a function of time and calculate the trendline (see e.g. https://math.stackexchange.com/questions/204020/what-is-the-equation-used-to-calculate-a-linear-trendline)

In your case the X axis would be the time component and the Y axis either the X or Y coordinate, so you'll end up with 2 functions. Take T=0 for the first timespan and the rest of the X axis in seconds.

This solution will only work with somewhat linear movements (maybe a zigzag) only. The issue with this approach however is that when let's say you draw half a circle the next predicted point will try to make an S curve because you average only known points.

Another option would be to differentiate the slope. Lets say you want to draw a hexagon, then the slope of your first line will be 0deg, second line 60deg, 3rd line 120deg, 4th 180deg, 5th 270deg, 6th=1St 360=0deg. In this case your X,Y coordinates go all over the place but the difference in slope is every time 60deg. Same applies to drawing a circle but the steps are infinitely smaller (this is actually one of the methods to calculate pi)

Now if you would just calculate the slope over the actual X,Y coordinates you'll basically end up with the same kind of algorithm as in your initial code. Basically you want to calculate the acceleration (using same method as described in the beginning of this answer), see e.g. https://blog.prepscholar.com/acceleration-formula-equation, and then calculate the trendline over the acceleration.

But also this solution is not fool proof. If your pencil trace is a zigzag then both your direction and acceleration will go nuts on every corner and your prediction will make no sense.

My advice would be to record a number of strokes, plot the result in a number of graphs and try some different formula's and methods to see which gives the best result.