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?

    Thanks.
    Simon L, Mar 31, 2006
    #1
    1. Advertising

  2. Simon L

    mlimber Guest

    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
    mlimber, Mar 31, 2006
    #2
    1. Advertising

  3. Simon L

    Ben Pope Guest

    Re: I need a container to hold grid positions and the objects onthe grid?

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

    Jeff Flinn Guest

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

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. don
    Replies:
    2
    Views:
    1,068
    Mike Wahler
    Feb 8, 2004
  2. Piaoger Gong
    Replies:
    2
    Views:
    357
    Sumit Rajan
    Oct 10, 2006
  3. Knut Krueger
    Replies:
    2
    Views:
    430
    Knut Krueger
    May 21, 2007
  4. mrstephengross
    Replies:
    5
    Views:
    361
    mrstephengross
    May 23, 2008
  5. J Krugman

    RDBMS to hold Perl objects?

    J Krugman, Feb 5, 2004, in forum: Perl Misc
    Replies:
    9
    Views:
    114
    Chris
    Feb 17, 2004
Loading...

Share This Page