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.