Hit test rectangles

Question

I am working on a project where I have several rectangles and I want to have a freezing effect for each of them. Now I know that I can just grab the WM_MOUSEMOVE message and iterate over each rectangle. But what if I have a lot of rectangles (if 50 - a lot).
Perhaps I was mistaken, but did not try through it a lot and hit testing every time the mouse slowly moves the application a bit?

Then I began to wonder how the operating system (for example, Windows) does it, for example, on my screen now there is something like that I have some kind of animation when I hung over them. And I don’t think windows are repeated through each of them every time the mouse moves a pixel.

Basically:
1. How can I determine which rectangle my mouse is in, if I have about 50 rectangles, considering performance.
2. How do windows? (I'm more curious than anything, but if it's not difficult, maybe I could implement something like this in my own program?)

Oh, and they are all rectangles, they will not be rotated or anything else.

Answer 1

I would not worry about performance until it becomes clear that part of the code creates a real bottleneck. Suppose you have such a bottleneck and measure the performance of the following code (it is in C #, but I'm sure 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 are interested in the 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: 701 ms. (0.701us per iteration)

As you can see, less than one microsecond is required to achieve the 50 rectangle test. Do you really think that it is too long compared to the time it takes to create spectacular freezing effects and everything that your program does? Of course you can answer this question.

But the moral of my story is this: do not pre-optimize and do not waste time trying to solve a problem that may not exist at all.

Answer 2

Do not think about performance. If so, measure it!

Mouse events are very low level events, it is very fast. Windows puts queued mouse messages, and your application either reads or ignores them. In the mouse event handler, checking which rectangle is the mouse is a quick operation.

If your rectangles are Windows controls (and they should), you can set a mouse listener for each control to automatically process the right handler automatically.

Answer 3

I agree that for a small number of rectangles (for example, fifty), the obvious approach to testing each of them, in turn, is likely to be the fastest.

I would suggest that Windows does the same. Obviously, it should not check child windows if the mouse pointer is not in the parent, and even the most poorly designed dialogs rarely have more than a hundred controls immediately visible. Controls that have many areas for testing (for example, ListViews, grid) optimize their own testing.

If you had tens of thousands of rectangles, performance can be a problem, and you can use one of the methods described here .

Answer 4

Other questions here have not answered your part 2, so I will give this snapshot:

2. How do windows? (I'm more curious than anything, but if it's not difficult, maybe I could implement something like this in my own program?)

The idea is that even if you have several dozen windows open, each of which has many toolbars, each of which contains many elements, etc., every time you move the mouse, the windows do not have to check everything.

Windows is basically structured in two layers: there is HWND, how Windows itself manages the division of desktop space; and usually inside each HWND there is a control that manages its own space inside that HWND: a control list that manages its own list items, a tab control that manages its own tabs, an HTML control that manages its own layout of the HTML page, and so on . (Or, in your case, the code controls 50 or so rectangles.)

When the mouse moves, Windows first determines the correct HWND to send this WM_MOUSEMOVE to. And he does this by crossing the HWND. HWNDs are stored as a tree representing restraint and order among siblings representing Z-Order, so Windows can perform a simple descent into that tree to find the lowest HWND at any given point. If you run the Spy ++ application, you yourself will see what this HWND tree looks like. Please note that Windows does not perform a full exhaustive crawl: when passing through windows of top-level applications, for example, to find out which application the point is in, as soon as the windows detect the first top-level HWND that contains the point, this will work in this, directly ignoring all other applications that are below / after it, and all the controls inside them. This is the key, which means that only windows should go through relatively little HWND, even if there are many visible objects on the screen.

Once Windows determines the correct HWND, it will send the appropriate message (WM_NCHITTEST, WM_MOUSEMOVE, etc.), and then before that control will do the same for its own content. For a list containing items of a fixed size, defining an item at a specific point can be as simple as a division operation; or for an HTML control, the control can have its own equivalent of a "tree of layouts", which it can use to quickly cross the element at that point. In your case, scrolling through the list of rectangles can be great.

This is a slightly simplified version: it is a little more complicated than higher - for example. windows are not just direct checks, but also other checks that allow you to create odd and transparent windows (both invisible and disabled windows); but the basic idea of ​​lowering the tree applies.

Another important issue to keep in mind is that it is all pretty fast: moving the mouse occurs in “human time”, and a modern processor can perform many operations in the time it takes for 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 does not always cross each individual pixel between them - especially if you quickly move the mouse.

Answer 5

I believe that you have one completely unnecessary "branch" in the answer (which in your test leads to an additional million operations). In your "HitTest" you end:

 return ... ? true : false; 

"? true: false" is redundant because the expression is already "true" or "false". When I try to make ultra-efficient code, I always think about the operations performed ...

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

PPS: while I am ... I never put an expression or method in your loops unless the loop changes the results of the expression, for example: for (int i = 0; i <getWidth (); ++ i) ... if it's clogged million times, your method will be called a million times :)