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

Discussion in 'C++' started by Simon L, Mar 31, 2006.

  1. Simon L

    Simon L Guest

    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?

    Simon L, Mar 31, 2006
    1. Advertisements

  2. Simon L

    mlimber Guest

    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
    mlimber, Mar 31, 2006
    1. Advertisements

  3. Simon L

    Ben Pope Guest

    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
    Ben Pope, Mar 31, 2006
  4. Simon L

    Jeff Flinn Guest

    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).
    Jeff Flinn, Mar 31, 2006
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.