Data structures for storing finger/stylus movements in drawing application?

Question

I have a general question about creating a drawing application, the language could be C++ or ObjectiveC with OpenGL. I would like to hear what are the best methods and practices for storing strokes data. Think of the many iPad apps that allow you to draw with your finger (or a stylus) or any other similar function on a desktop app.

To summarize, the data structure must:

• be highly responsive to the movement
• store precise values (close in space / time)
• usable for rendering the strokes with complex textures (textures based on the dynamic of the stroke etc)
• exportable to a text file for saving/loading

Answer 1

Regardless of the data structure you use it may be helpful to remove unneeded data points using an algorithm like the Ramer–Douglas–Peucker algorithm. It will take a linear piecewise curve and remove points that deviate less than some small amount from the curve at large. This way, if your user draws a more or less straight line, you wont store every intermediate point where their finger has been.

The problem is how to simplify and smooth piecewise linear curves. There's a free paper here Efficient Smoothing of Piecewise Linear Paths with Minimal Deviation (there's a PDF link to the right).

As World Engineer mentioned in his answer, vector graphics are an option. SVG is a popular format and it's based on XML so it's easy to manipulate with existing tools. Along with plain old "points" it can handle paths (Bézier and elliptic), text, shapes, styling info (stroke etc.) and much more. SVG gives you the tools to render your user's drawing as exactly as you'd like. SVG images also supported in most browsers. Also, since it's a well established format I'm sure there are plenty of existing libraries for manipulating the images, ex. simple-svg. Or there's always good old bitmaps.

I imagine the process would go something like:

1. Wait for user to draw a curve
2. Simplify the curve (as much or as little as you would like)
3. Render the simplified curve, path, shape, etc. to the canvas using the selected style.

Answer 2

I'd recommend storing it as a vector graphics image. There are data structures that do this kind of thing. As far as precision, Vector Graphics are very precise. Response will largely be a question of the implementation keeping overhead and locking to a minimum.