Kink detection in drawn polylines
Users can create sketches in my application using a very simple tool (move the mouse while holding LMB). This results in a series of mousemove events and I am recording the location of the cursor on each event. The resulting polyline curve tends to be quite dense, with nearly every other pixel recorded with points. I would like to smooth this pixelated polyline, but I do not want to smooth out the intended kinks. So how do I figure out where the kinks are?
The image shows the trail recorded (red pixels) and the "implied" shape as a human would understand it. People tend to slow down near corners, so there is usually more noise here than on straight beats.
Polyline Tracking http://www.freeimagehosting.net/uploads/c83c6b462a.png
a source to share
What you are describing may be related to gesture recognition techniques, so you might want to search for ideas.
The obvious approach is to apply a curve fit, but this will smooth out all the interesting details and kinks. Another approach is to look at speeds and accelerations, but this can get hairy (changes in direction can be very fast or very slow and deliberate)
A fairly simple but effective approach is to simplify selections directly in the polyline.
For example, work your way through the patterns (for example) from pattern 1 to pattern 4 and check if all 4 patterns are within a reasonable error of a straight line between 1 and 4. If so, then expand that to point 1..5 and repeat until the straight line from the start point to the end point no longer provides a resonant approximation to the curve defined by these samples. Create a line segment up to the previous sampling point and start accumulating a new line segment.
You have to be careful about your thresholds when the samples are too close to each other, so you can adjust the sensitivity when comparing samples less than 4-5 pixels apart.
This will give you a set of straight lines that follow the original path exactly.
If you need additional anti-aliasing or want to create scalable vector graphics, then you can bend the curve from the polyline. First, define kinks (places in your polyline where the angle between one line and the next will be sharp), for example, anything over 140 degrees is considered a smooth curve, something less than this is considered a kink) and break the polyline on these gaps, then the curve fits each of these subsections of the original gesture to smooth them out. This will have the effect of smoothing smooth materials and sharpening kinks. (You can go further and insert small smooth corner fillets in place of these sharp joints to reduce the severity of the joints)
Brute force, but it can just achieve what you want.
a source to share
Instead of trying to do it from the resulting data, have you thought about how to sync the data as it comes in? If the mouse stops or slows down noticeably, you use the trend since the last "kink" (the last time the mouse slowed down) to determine the direction of movement. If the user leaves in a new direction, you call it an inflection, otherwise you ignore the current slowing trend and start waiting for the next one.
a source to share
Ok, one way would be to use a true curve fitting algorithm. Create a Bézier curve (with exact endpoints using Catmull-Rom or something similar), then optimize and split recursively (using distance from actual line points as a measure of cost). However, this might be too complex for your use.
a source to share