5

I am about to start writing a UI view where many small text items are laid-out over the view and when the user hovers over a text item a dynamically-generated image is displayed (like a tooltip), relevant to the context of that text item. When the user clicks the text item, another view will change with a larger version of that image.

I will obviously need to hold the items in a collection along with the rect hit-area that surrounds the text, and I am wondering if anyone can suggest an storage format and search algorithm I can use to find the text item as quickly as possible using the position of the mouse as a hint to localise the search, rather than do hit-tests for every item in the collection?

Improve this question
2
  • what are you developing this UI for? many platforms have already implemented ways to make handling mouse over events more easily.
    – Ryathal
    Commented Jan 25, 2012 at 15:30
  • I am developing for Mac (Cocoa Objective-C).
    – trojanfoe
    Commented Jan 25, 2012 at 15:33

4 Answers 4

Reset to default
8

What you are looking for is called a spatial index and the problem you are trying to solve is collision detection.

More specifically I would use a quadtree data structure, which subdivides your space into four subspaces each time you descend one level in the tree. This is in 2D, if you are trying to solve the problem in 3D the appropriate structure would be an octree.

I would probably deviate from the traditional quadtree and subdivide your area to the pixel level and hash the leave nodes, so you can get the corresponding leave node for (x,y) more quickly. The algorithm would be roughly:

  1. On initialization build the tree and the hash.
  2. When inserting a new item into your collection then you calculate the hit area and you store it in the node that represents the smallest quadrant possible that still holds your entire hit box.
  3. If you receive a click on (x,y), you look up the leaf for x,y using the hash. Once you have the leaf all you need to do is work up your way to the root and compare the hitbox of every item that you encounter on your way up with your (x,y)
Improve this answer
9
  • Lovely answer - many thanks! I'll let you know how I got on with it.
    – trojanfoe
    Commented Jan 25, 2012 at 9:40
  • You're welcome. I'd be interested if this actually works :-)
    – sebastiangeiger
    Commented Jan 25, 2012 at 12:09
  • Nice answer, but the way you describe this, you don't need quadtree nodes with links. For any particular size window, the structure is fixed - with some careful integer math you can step up from single pixel to larger and larger areas in a way that mirrors the quadtree structure. A hash of the bounds can then be used to look up the list of all rectangles for that node. Simpler still, use exact quadrupling per step up the quadtree - slightly imbalanced, but you don't have to reindex for window resizing.
    – user8709
    Commented Jan 25, 2012 at 12:22
  • @Steve314 You're right, this is not really a quadtree. I abused the idea if anything, since the tree would always have a fixed number of nodes. As for the resizing problem I would imagine having a "workspace" or "canvas" that is independent from the window size or the viewport shown in the window. The (x,y) I am describing would then be already in workspace coordinates.
    – sebastiangeiger
    Commented Jan 25, 2012 at 12:32
  • I don't think "not a quadtree", just "not an explicit quadtree". Kind of like the binary heap data structure is built in an array without links rather than as a binary tree - just because you calculate the links on the fly rather than storing them doesn't mean it isn't a binary heap (or quadtree).
    – user8709
    Commented Jan 25, 2012 at 13:02
1

An alternative technique that you may want to consider (depends on your needs) is to use an off-screen bitmap to store a reference to text items. The basic approach is to draw the bounding rectangle to the off screen bitmap with a unique color for each item. The look up is constant time, just index into the bitmap with the (x,y) coordinate of interest (e.g., mouse location).

The disadvantage to this technique is the memory requirements. The bitmap needs to be as large as the display area on the screen.

Improve this answer
1
  • That's interesting, but I think the potential memory issues might prove too expensive a price.
    – trojanfoe
    Commented Jan 25, 2012 at 14:39
1

Unless you are talking many thousands of items, try it first without any special algorithms. A simple hit test for a rectangle is very cheap, processor wise. I seriously doubt you'd see any percievable improvment over more efficient schemes.

Basically, while great in theory, this is a place where there's no need to prematurely optimize.

Also, make sure you cycle backwards (top to bottom), so as to hit the top item if two are overlapped.

Improve this answer
1
  • Yeah I think you might be right; the medicine is worse than the disease
    – trojanfoe
    Commented Jan 27, 2012 at 7:40
1

As mentioned by sebastiangeiger, spatial indexes help. I've found quad trees to be simple to implement. Another alternative that may even be simpler is to just divide your space into a grid, and insert each rectangle into the series of spaces that it intersects with (this is actually similar to what each node of a quad tree does, given that each node is a 2x2 grid).

Ultimately, find the simplest approach that meets your performance requirement.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.