Friday, 25 November 2011

Defining selection regions

I wanted to be able to define a subset of regions within a layer as an interactively-edited selection. This turned out to provide a nice example of the tension between formalised algorithms and "intuitive" user intention.

The basic idea was that the user should be able to draw a line around the items of interest, or that a previously defined image layer could act as a region selection mask. In either case, an enclosed region is clearly intent to select something.

The enclosure could be defined computationally using either a flood fill, or a convex hull. However, neither of those corresponds very well to informal graphical conventions. A partially closed boundary still indicates containment, but couldn't be flood-filled, while a concavity should certainly be respected, if specifically drawn to exclude something.

As a result, I spent nearly a day inventing a more informal alternative to the well-known formal algorithms. It seems to work as expected in most cases, and while less efficient than a good flood fill, is faster than a naive convex hull. I doubt there is much future to the field of informal algorithm design, but hopefully this will be good enough to suffice for the rest of my project.

No comments:

Post a Comment