Matt Gemmell

My new book CHANGER is out now!

An action-adventure novel — book 1 in the KESTREL series.

★★★★★ — Amazon

Hit test algorithm

Development 1 min read

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.

Hit test grid

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.