Algorithms to normalize finger touch data (reduce the number of points)

Question

I'm working on an app that lets users select regions by finger painting on top of a map. The points then get converted to a latitude/longitude and get uploaded to a server.

The touch screen is delivering way too many points to be uploaded over 3G. Even small regions can accumulate up to ~500 points.

I would like to smooth this touch data (approximate it within some tolerance). The accuracy of drawing does not really matter much as long as the general area of the region is the same.

Are there any well known algorithms to do this? Is this work for a Kalman filter?

Answer 1

There is the Ramer–Douglas–Peucker algorithm (wikipedia).

The purpose of the algorithm is, given a curve composed of line segments, to find a similar curve with fewer points. The algorithm defines 'dissimilar' based on the maximum distance between the original curve and the simplified curve. The simplified curve consists of a subset of the points that defined the original curve.

Answer 2

You probably don't need anything too exotic to dramatically cut down your data. Consider something as simple as this:

Construct some sort of error metric. An easy one would be a normalized sum of the distances from the omitted points to the line that was approximating them. Decide what a tolerable error using this metric is.

Then starting from the first point construct the longest line segment that falls within the tolerable error range. Repeat this process until you have converted the entire path into a polyline.

This will not give you the globally optimal approximation but it will probably be good enough.

If you want the approximation to be more "curvey" you might consider using splines or bezier curves rather than straight line segments.