Matt Legend Gemmell – Hit test algorithm

Favorites for iPhone
Speed-dial with style.

Other Pages

Hit test algorithm

I need to write a simple 2D hit-detection algorithm to decide which “layer” (if any) of a composite graphic to select when the user clicks in the graphic, just like Photoshop’s “move” tool with automatic layer selection enabled.

The layers will all be filled paths, so we already have NSBezierPath’s -containsPoint: method to use for checking the click-coordinates against each path. The issue is narrowing down the set of paths we’re checking, for efficiency and performance. The obvious solution is to break the canvas up into a grid, and for each grid rectangle, noting which shape(s) at least partially overlap that rectangle, as shown below.

When the user clicks on the canvas, it’s a simple calculation to determine which grid-rect the click occurred in. You then just look up which shapes overlap that rect, and ask each of them if they contain the click point; for example if the user clicked in the canvas shown above and the click was in grid rectangle 7, we’d only have to ask shape B if it contained the click point. Not stunningly brilliant, but it would work. The list of which shapes overlap each rect can be updated upon creation, deletion, movement or resizing of a shape, at very little cost. Simple enough.

It makes sense that the grid rectangles should be slightly larger than the average likely size of a shape, in order to minimise the number of grid rectangles which a given shape can simultaneously be in. Smaller grid rectangles would obviously yield a reduced number of candidate shapes for a given click, but would require more entries per shape, so obviously the likely usage model for the app is a key factor is making that tradeoff. It also probably makes sense to check the candidate shapes in depth-order, topmost first.

Since the total canvas size is relatively small in my case, I don’t want to get into recursive subdivision of grid rectangles (using a tree structure). With that in mind, are there any obvious optimisations or refinements anyone can see for this? I’ve thought about taking the physical size of the shape into account, to test larger shapes first given the presumably increased statistical likelihood that they’ll contain an arbitrary click point.

General thoughts are always welcome too.

4 Comments

Byron
7 November 2005 @ 9pm

An R-tree maybe?

Kevin Ballard
8 November 2005 @ 9am

Distance is a pretty trivial calculation, so you could always test the shapes whose center point (or some other known location in the shape) is closer to the click point than the other shapes.

Of course, ordering the detection like this is kind of trivial, given that if two shapes overlap, just because one contains the point doesn’t mean it’s the correct shape. Maybe you should just start at layer 1 and work down from there?

Uli Kusterer
8 November 2005 @ 12pm

If you have each shape as a different object already (and it’s not just a set of NSImages for each layer or so) I’d just get the bezier path’s frame rect and hit-test against those. That’s basically four comparisons per rect, and was lightning-fast even back in the System 7 days on a 16MHz LC.

As additional optimisation, you could union together all rects in each layer to have the “bounding rect” for the layer, and ignore all layers whose bounds don’t even intersect the click loc. In the end, you’ll immediately know which shapes *can’t* have been clicked. Then all you gotta do is do a containsPoint: on those few paths whose rects intersect the click loc to root out false positives.

You’ll still have to go layer by layer, though, because of overlapping shapes.

Uli Kusterer
8 November 2005 @ 12pm

Another option would be to do like openGL does. If you only care about the layer and not the particular shape, pick a different color for each layer and draw all layers into an NSImage, with all shapes of one layer in that layer’s color. Then you can query the clicked pixel and immediately tell what layer it was by the color.

It’s a little wasteful for an image editor, but if your shapes don’t change a lot, you can cache that NSImage and get the fastest hit-testing you could ever get (just an constant-time array look-up).