Algorithm to implement a lasso selection tool?

Question

I am developing a Mac OS X application which, as part of it's UI, will display many visual elements in it's main view which can be selected. These elements can be positioned really anywhere within the view. The UI will support various ways of selecting the elements: rectangular marquee selection, elliptical marquee selection, and 'free' lasso selection.

I already have rectangular and elliptical marquee selection working. The algorithm is pretty simple; an element is deemed 'selected' if the element's area intersects with the area of the rectangle/ellipse.

The lasso selection will work just as it does in modern image manipulation applications like Photoshop; the user can click-and-drag a path which will close itself, and the elements contained within the path drawn will be selected.

This algorithm will likely be much more complex than the rectangular/elliptical selection, since the form of the selection is unrestricted. I am wondering if anyone has experience writing something like this, or if you can point me in the right direction as to what kind of programming techniques are necessary, and what is the most efficient way this algorithm can work.

Thanks in advance.

Answer 1

The only way I can think of is to treat the lasso outline as a polygon. Then you can use any standard point-inside-polygon test to check which elements to select.

You'll have to make a decision what to do when the polygon intersects itself (e.g. figure-8).

When constructing the polygon, to prevent it from getting too many points, maybe you can skip points that are too close to the previous point (maybe 3 pixels or so, depending on your application).

Answer 2

You're looking at a point in polygon problem: http://en.wikipedia.org/wiki/Point_in_polygon If you can guarantee that the polygon is convex (not likely), the algorithm becomes simpler.