Hit test rectangles

Question

I'm working on a project where I have several rectangles and I want to have a hover effect for each one. Now I know I could just capture the WM_MOUSEMOVE message and iterate through each rectangle. But what if I have a lot of rectangles (if 50 is alot).
I might be wrong but wouldn't iterating through that many and hit testing each one every time the mouse moves slow the application down a little?

Then I started wondering how a operating system (such as windows) does this, there's like 100+ things on my screen right now that all have some sort of animation when I hover over them. And I don't think windows iterates through all of them each time the mouse moves a pixel.

Basically:
1. How can I figure out which rectangle my mouse is over if I have around 50 rectangles, with performance in mind.
2. How does windows do this? (I'm more curious then anything, but if it's not to complex, maybe I could implement something similar in my own program?)

Oh and they're all rectangles, they won't be rotated or anything.

Answer 1

I wouldn't be bothered much about performance until it becomes clear that a piece of code creates a real bottleneck. Let's assume that you've got such a bottleneck, and measure the performance of the following code (it's in C#, but I'm pretty sure that C++ will not be slower):

public class Rectangle
{
    public int X { get; set; }
    public int Y { get; set; }
    public int W { get; set; }
    public int H { get; set; }

    public bool HitTest(int x, int y)
    {
        return x >= X && x < X + W && y >= Y && y < Y + H ? true : false;
    }
}

We're interested in performance of the HitTest() method, so let's measure it!

void PerformanceTest()
{
    const int Iterations = 1000000;
    Random rnd = new Random();
    var rectangles = Enumerable.Range(1, 50).Select(
            r => new Rectangle {
                X = rnd.Next(1000),
                Y = rnd.Next(1000),
                W = rnd.Next(1000),
                H = rnd.Next(1000)}).ToList();

    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < Iterations; i++)
    {
        rectangles.ForEach(r => r.HitTest(500, 500));
    }
    sw.Stop();

    Console.WriteLine("Elapsed time: {0}ms. ({1}us per one iteration)",
        sw.ElapsedMilliseconds,
        (float)sw.ElapsedMilliseconds * 1000 / Iterations);
}

On my PC the above code prints:

Elapsed time: 701ms. (0.701us per one iteration)

As you can see, it takes less than one microsecond to hit test 50 rectangles. Do you really think that this is too long compared to the time it takes to create fancy hover effects and whatever else your program does? Only you can answer this question, of course.

But the moral of my story is: don't try to pre-optimize and don't spend time trying to solve a problem which might not exist at all.

Answer 2

Don't think about performance. If you do, then measure it!

The mouse events are very low level events, it's fast, really. Windows puts mouse messages in a queue and your application either reads or ignores them. In your mouse event handler, checking in which rectangle is the mouse is a fast operation.

If your "rectangles" are windows controls (and they should) then you could set a mouse listener for each control so that the right handler will be called by windows automatically.

Answer 3

I agree that for a small number of rectangles (e.g. fifty) the obvious approach of testing each one in turn is likely to be quickest.

I would guess that Windows does much the same. Obviously it doesn't have to test child windows unless the mouse pointer is in the parent, and even the most badly designed dialogs rarely have more than a hundred controls visible at once. Controls that do have lots of hit-test regions (e.g. ListViews, grids) optimize their own hit-testing.

If you had tens of thousands of rectangles then performance might be an issue and you could use one of the methods described here.

Answer 4

The other questions here didn't answer your part 2, so I'll give that a shot:

2. How does windows do this? (I'm more curious then anything, but if it's not to complex, maybe I could implement something similar in my own program?)

The thing to realize is that even if you have tens of windows open, each with many toolbars, each with many items in it, and so on, every time you move the mouse, windows doesn't need to check everything.

Windows is basically structured in two layers: there's HWNDs, which is how Windows itself manages the subdivision of space on the desktop; and typically within each HWND is a control that manages its own space within that HWND: a listbox managing its own list items, a tab control managing its own tabs, a HTML control managing its own HTML page layout, and so on. (Or, in your case, code managing 50 or so rectangles.)

When the mouse moves, Windows first determines the correct HWND to send that WM_MOUSEMOVE to. And it does so by traversing the HWNDs. The HWNDs are stored as a tree, representing containment, and the order among siblings representing Z-Order, so Windows can do a simple depth-first descent into this tree to find out the bottom-most HWND at any given point. If you start the Spy++ app, you can see for yourself what this HWND tree looks like. Note that Windows is not doing a full exhaustive traversal: while traversing the top-level application windows, for example, to find out which app the point is in, as soon as windows finds the first top-level HWND that contains the point, it will drill into that, outright ignoring all other apps that are beneath/after it - and all the controls within them. This is the key that means windows only has to traverse relatively few HWNDs even if there are many many visible on the screen at once.

Once Windows determines the correct HWND, it sends the appropriate message to that (WM_NCHITTEST, WM_MOUSEMOVE, and so on), and it's then up to that control to do likewise for its own content. For a listbox, containing fixed-size items, determining the item at a particular point may be as simple as a division operation; or for a HTML control, the control may have its own equivalent to a "layout tree" that it can use to traverse an quickly determine the element at that point. In your case, looping through the list of rectangles may be perfectly fine.

That's the somewhat simplified version: it's a bit more complex than above - eg. windows doesn't just to a point-in-rect check, there's other checks to allow for odd-shaped and transparent windows (and invisible and disabled windows); but the basic tree descent idea applies.

The other important issue to remember is that all this is pretty quick: moving a mouse takes place in "human time", and a modern CPU can to a lot of operations in the time it takes the mouse to move a couple of pixels on the screen. And finally, note that when you move the mouse from point A to point B on the screen, the mouse doesn't always traverse every single pixel in between - especially if you move the mouse rapidly.

Answer 5

I believe you have one completely unnecessary 'branch' in the answer (which in your test results in an extra million operations). In your 'HitTest' you end with:

return ... ? true : false;

The "? true : false" is redundant, since the expression is already 'true' or 'false'. When trying to make ultra-efficient code, I always think of 'operations' performed...

PS: also things like ++var, versus var++ can have a worthy impact on performance depending on how it's used in the code (as optimizers catch some of them and fix it for you...

PPS: while I'm at it... also never put an expression or method call in your loops unless the loop changes the expression results eg: for(int i=0; i < getWidth(); ++i)... if this looped a million times, your method would be called a million times :)