Click Testing 1

[Dreadson]

Hello, I have a question on click testing objects on the screen. The way I have been doing it is to have an entry in a RECT array for every object, then on WM_LBUTTONDOWN I use a loop of PtInRect to see if the user clicked on an object. I was just wondering if there is a more clever way of doing this, because I imagine with hundreds or possibly thousands of objects on the screen this method might slow down performance.

 

[Salem]

> I was just wondering if there is a more clever way of doing this,
Probably, but is this really your main performance bottleneck, or just a speculative guess?

[URL unfurl="true"]http://en.wikipedia.org/wiki/Optimization_(computer_science)[/URL]

Say your processor is 1GHz (probably more) and your monitor refresh rate is 100Hz (probably less). That gives you 10M instructions (at least) before your user has any chance at all of noticing what went on. Useful mouse clicking rate is more like 10Hz. You can do a lot of tests in that time.
What else are you planning to do in response to a click - redraw a bit of the screen (say a selection rectangle)?

A simple linear search may seem to be a problem on paper, but each test is only a few machine instructions. The code is obvious and easy to write.

A "better" approach (see below) is harder to write, maintain, debug etc, and has a higher overhead (like keeping the list sorted).



You could sort your list into position and size order, which would allow you to quickly reject whole sets of rectangles with a single test.

Also, since any given rectangle has a lot more outside than inside, it might be more efficient to complement the test by checking outsides rather than insides.

// rect contains left, right, bottom, top
// point contains x and y
bool pointInsideRect ( rect r, point p ) {
  return r->l <= p.x &&
         r->r >= p.x &&
         r->b <= p.y &&
         r->t >= p.y;
}
bool pointOutsideRect ( rect r, point p ) {
  return r->l > p.x ||
         r->r < p.x ||
         r->b > p.y ||
         r->t < p.y;
}

--

 

[Dreadson]

You're right, simplicity is probably best. I'll just stay with what I have. If it comes down to it I can probably just split the screen into large blocks and check only the objects in the block where the mouse clicked. Anyway, thanks for your helpful advice.

 

[lionelhill]

Another plus-point is that if you have things that can be drawn on top of each other, partially overlapping, and you want to select only the one the user could see when they clicked, you just have to check all the rectangles in the same order as they're drawn.