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?
Search algorithm with co-ordinate (x,y) hints?
algorithms;data structures;search;storage
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:On initialization build the tree and the hash. 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. 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)