I need a container to hold grid positions and the objects on the grid?

[Simon L]

I'm creating a GUI which is a bitmap with active areas, so when I paint
the dialog I calculate the rectangles containing objects.

When I get a click event, I want to know which (if any) rectangle
encompasses the click (so I know which object is clicked).

In the past I've created a vector of rectangles and gone though them
one by one testing for PointInRect or whatever but I reckon this is a
bit clunky, and I'm up to 100 or so objects on a screen.

So RECT is my reference to an object
POINT is what I need to test to get an object.

Any thoughts on what sort of collection could do this neatly for me?

Thanks.

[mlimber]

Simon L wrote:

I'm creating a GUI which is a bitmap with active areas, so when I paint
the dialog I calculate the rectangles containing objects.

When I get a click event, I want to know which (if any) rectangle
encompasses the click (so I know which object is clicked).

In the past I've created a vector of rectangles and gone though them
one by one testing for PointInRect or whatever but I reckon this is a
bit clunky, and I'm up to 100 or so objects on a screen.

So RECT is my reference to an object
POINT is what I need to test to get an object.

Any thoughts on what sort of collection could do this neatly for me?

Thanks.

You might have to build your own depending on how you use it, but you
might be able to get by with a std::set<RECT> if you create a dummy
point-sized RECT for the lookup and a custom comparison functor for
RECTs. Search time should be O(log N).

Cheers! --M

[Ben Pope]

Simon L wrote:

I'm creating a GUI which is a bitmap with active areas, so when I paint
the dialog I calculate the rectangles containing objects.

When I get a click event, I want to know which (if any) rectangle
encompasses the click (so I know which object is clicked).

In the past I've created a vector of rectangles and gone though them
one by one testing for PointInRect or whatever but I reckon this is a
bit clunky, and I'm up to 100 or so objects on a screen.

So RECT is my reference to an object
POINT is what I need to test to get an object.

Any thoughts on what sort of collection could do this neatly for me?

Sounds to me like you require some kind of hierarchical representation,
which is probably implicit in the structure of the GUI.

You ask the parent if the point is inside of it's RECT, if not, nothing
has been clicked, if so, you ask the first child, if so, you ask it's
children, if not you ask the next child etc.

Sounds like a simple tree traversal to me, and it sounds like your RECTs
are implicitly defined by each window object.

If you create a vector of RECTs, you lose the hierarchical nature (Z
dimension), many rectangles may match a point, you want the "closest"
one. You also have to manage the vector whenever a window is added or
removed, sounds like a good source of trouble.

I suggest most of this information is already available in the structure
of the GUI elements, and a simple traversal is required.

Correct me if I'm wrong.

Ben Pope
--
I'm not just a number. To many, I'm known as a string...

[Jeff Flinn]

Simon L wrote:

I'm creating a GUI which is a bitmap with active areas, so when I
paint the dialog I calculate the rectangles containing objects.

When I get a click event, I want to know which (if any) rectangle
encompasses the click (so I know which object is clicked).

In the past I've created a vector of rectangles and gone though them
one by one testing for PointInRect or whatever but I reckon this is a
bit clunky, and I'm up to 100 or so objects on a screen.

100 is not that many items to deal with. If this is purely a performance
concern have you measured to see if this is a bottleneck?

Your subject line specifies "grid" while your description here makes no
mention that your "rectangles" are layed out in a grid. If in fact you do
have a grid layout, you could achieve O(rows) + O(cols) by maintaining
sorted vectors of row heights and of col widths, and use upper/lower_bound
to determine row/col indices. Of course if all heights/widths are equal, you
could achieve O(1) complexity by simply calculating the row/col indices. If
you're dealing with 'dense' data use a std::vector< std::vector< ... > >, if
the data is 'sparse' you can use a std::map< key, ... > where key encodes
the indices and provides the necessary strict weak ordering requirments(
possibly use a std::vector<int> of size 2).