Volition

I don't suppose anyone knows of a decent (read: lightning fast) algorithm for doing 2D hit detection? I have a set of objects that are painted on a rectangular canvas as irregular, arbitrary shapes, and I need to determine which object a user has just clicked on, moused into or out-of, or is currently dragging through. This is all for my game, of course.

There are probably too many objects to just linearly iterate through, checking each to see if it contains the given point.

At the moment, I'm thinking of using a number of balanced binary trees to index either all four coordinates (x1, y1 and x2, y2) of the bounding rectangle of each object's shape, or just index the center of each shape (or bounding rectange) and go from there. This will allow me to cut down on the number of shapes that I'll need to explicitly check, but is still pretty wasteful. Also, using trees may not handle dynamic situations very well. For example, If a user is doing a drag, an object is being moved across the canvas and so the trees need to updated constantly.

Now that I think about it some more, keeping track of the last known hit object may well speed things up a bit, but there is still the issue with moving objects around.

So, all you game, err.. 2D graphics gurus out there, what the best answer? Does anyone know how existing UI systems like X, Swing, or even Windows does it? Probably the most annoying part is that I don't really know what the correct technical term is for this, so I can't even begin to ask Google.