Regarding object managers

Question

I am designing a class that manages a collection of rectangles. Each rectangle represents a button, so contains the following properties:

• x position
• y position
• width
• height
• a callback function for what happens when it is pressed.

The concept itself is fairly straightforward and is managed through a command line interface. In particular.

If I type "100, 125" it looks up whether there is a rectangle that contains this point (or multiple) and performs their callback functions.

My proposal is to iterate over all rectangles in this collection and perform the callback of each individual rectangle which contains this point, or stop upon the first rectangle that matches (simulating z order).

I fear however that this solution is sloppy, as this iteration becomes longer the more rectangles I have. This is fine for the console application, since it can easily go over 10,000 rectangles and find which ones match, expensive computation, but time wise it is not particularly an issue.

The issue is that if I were to implement this algorithm in a GUI application which needs to perform this check every time a mouse is moved (to simulate mouse over effect), moving your mouse 10 pixels over a panel with 10,000 object would require checking of 100,000 objects, that's not even 1000 pixels or over people tend to move mouse over at.

Is there a more elegant solution to this issue, or will such programs always need to be so expensive?

Note: I understand that most GUIs do not have to deal with 10,000 active objects at once, but that is not my objective. The reason I choose to explain this issue in terms of buttons is because they are simpler. Ideally, I would like a solution which would be able to work in GUIs as well as particle systems which interact with the mouse, and other demanding systems.

In a GUI, I can easily use indirection to reduce amount of checks drastically, but this does not alleviate the issue of needing to perform checks every single time a mouse is moved, which can be quite demanding even if there are 25 buttons, as moving over 400 pixels with 25 objects(in ideal conditions) would be as bad as moving 1 pixel with 10,000 objects.

In a nutshell, this issue is twofold:

1. What can I do to reduce the amount of checks from 10,000 (granted there are 10,000 objects).
2. Is it possible to reduce amount of checks required in such a GUI application from every mouse move, to something more reasonable.

Any help is appreciated!

Answer 1

Is there a more elegant solution to this issue, or will such programs always need to be so expensive?

Instead of doing a linear search through all the objects you could use a data structure like a quad tree that lets you efficiently find the nearest object.

Or, you could come up with a more realistic set of requirements based on the intended use for your algorithm. A GUI with 10,000 buttons visible at once is a poor design for many reasons, the main one being that the poor user will have a very hard time finding the right button. A linear search through a number of rectangles more typical of a UI, say somewhere between 2 and 100, will be no problem from a performance point of view.

Answer 2

There are any number of 2D-intersection acceleration structures you could apply. For example, you could use a Quadtree (http://en.wikipedia.org/wiki/Quadtree) to recursively divide the viewport into quadrants. Subdivide each quadrant that doesn't fall entirely within or entirely outside every rectangle and place a pointer to either the top or the list of rectangles at each leaf (or NULL if no rectangles land there). The structure isn't trivial, but it's fairly straightforward conceptually.