4

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?

Sonny Saluja
  • 7,193
  • 2
  • 25
  • 39

4 Answers4

6

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.

enter image description here

Shannon Matthews
  • 9,649
  • 7
  • 44
  • 75
  • I've seen some painting apps that use a similar approach while it reduces points I feel that it sometimes moves lines from where I actually draw them. – Jonny Jan 30 '12 at 07:14
1

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.

idz
  • 12,825
  • 1
  • 29
  • 40
  • I did something very similar to this approach (only finding it described now), although I was constructing something else - finger writing recognition. It worked pretty well - play around with the tolerance number. – Jonny Jan 30 '12 at 07:11
1

You want to subdivide the surface into a grid with a quadtree or a space-filling-curve. A sfc reduce the 2d complexity to a 1d complexity. You want to look for Nick's hilbert curve quadtree spatial index blog.

Micromega
  • 12,486
  • 7
  • 35
  • 72
0

I was going to do something this in an app, but was intending on generating a path from the points on-the-fly. I was going to use a technique mentioned in this Point Sequence Interpolation thread

Community
  • 1
  • 1
Pierre Houston
  • 1,631
  • 20
  • 33