Point data structure for a sketching application

Question

I am currently developing a little sketching application based on HTML5 Canvas element. There is one particular problem I haven't yet managed to find a proper solution for.

The idea is that the user will be able to manipulate existing stroke data (points) quite freely. This includes pushing point data around (ie. magnet tool) and manipulating it at whim otherwise (ie. altering color).

Note that the current brush engine is able to shade by taking existing stroke data in count. It's a quick and dirty solution as it just iterates the points in the current stroke and checks them against a distance rule.

Now the problem is how to do this in a nice manner. It is extremely important to be able to perform efficient queries that return all points within given canvas coordinate and radius. Other features, such as space usage, should be secondary to this. I don't mind doing some extra processing between strokes while the user is not painting.

Any pointers are welcome. :)

Answer 1

I would go with simple matrix int pixels[][] where for given pixel at x,y the value of the matrix is its color.

I do not see any clear advantage of using more sophisticated data structures, matrix is very fast and easy to use. As for operations, for instance getting points for given coordinate and radius you just perform the math on matrix indices and only retrieve only matchings pixels etc. Bleeding fast.

Answer 2

I'd basically just wrap an array in an object with some special functions for moving the pixels' data around - or sampling them. I did something fairly similar in a weather-erosion project...just used a Gaussian function to both sample and push data down based on some sort of circumference / weighting principle.

You'd have to have a list of pixels mapping to each 'brushstroke' if you wanted to have undo / brushstroke interactions, but that seems like a different object - you'd just have all your brushstrokes pointing at that central matrix (for the actual contents of the points they influenced - they'd maybe have 'weights' concerning how much color they contributed to the point, or something).

Answer 3

the standard solution for working with arbitrary points lists in 2d is a quadtree space partitioning: http://en.wikipedia.org/wiki/Quadtree

Answer 4

You want to have a look at spatial indexing in general. Johan has a good suggestion with the quadtree. Other data structures that might work:

• kd-tree
• vp tree
• simple grid index