how to efficiently find a rect @ some x,y point with iphone sdk

Question

Hi, I am looking for an efficient way to handle the image/frame detection from touch methods. Let's say i am building a keyboard or similar to this. I have 'n' number of images placed on the UI. When someone touches an alphabet (which is an image), i can do the following to detect the corresponding letter

1) CGRectIntersectsRect(..,..) : if i use this, then i need to check each & every letter to find out what letter exists at that touch point (let's say 100,100). This becomes O(n). If i move my finger accross the screen, then i will get m points & all corresponding image detection becomes O(n*m) which is not good.

2) Other way is building a hash for each & every x,y position so that the look up will be simply O(1). But again this will be a memory constraint as i need to store 300*300 ( assuming i am using 300*300 screen size). if i reshuffle my letters, then everything needs to calculated again. So this is not good

In other words, i need some thing like , given a point (x,y), i need some way of finding which rectangle is covering that point efficiently.

Sorry for long post & any help would be grateful.

Thanks

Answer 1

If there are in a regular grid, then integer division by the grid size. Assuming you've a small, fixed screen size, a bucket array gives as similar gain ( a 2D grid, where each entry is a list of the rectangles which intersect that part of the grid ) is very fast if tuned correctly so the lists only have a few members. For unbounded or large spaces, KD trees can be used.

Answer 2

It's useful to have the rects you want as final targets set up as subviews as a larger UIView (or subclass) where you expect all these related hits to occur. For example, if you're building your own keyboard, you could add a bunch of UIButton objects as subviews and hit test those.

So, the easy and traditional way of hit testing a bunch of subviews is to simply have code triggered by someone hitting those buttons. For example, you could add the subviews as UIControl objects (which is a subclass of UIView that adds some useful methods for catching user touch events), and call addTarget:action:forControlEvents: to specify some method to be triggered when the user does something in the rect of that UIControl. For example, you can catch things like UIControlEventTouchDown or UIControlEventTouchDragEnter. You can read the complete list in the UIControl class reference.

Now, it sounds like you might be going for something even more customized. If you really want to start with a random (x,y) coordinate and know which rect it's in, you can also use the hitTest:withEvent: method of UIView. This method takes a point in a view, and finds the most detailed (lowest in the hierarchy) subview which contains that point.

If you want to use these subviews purely for hit testing and not for displaying, then you can set their background color to [UIColor clearColor], but don't hide them (i.e. set the hidden property to YES), disable user interaction with them (via the userInteractionEnabled BOOL property), or set the alpha below 0.1, since any of those things will cause the hitTest:withEvent: method to skip over that subview. But you can still use an invisible subview with this method call, as long as it meets these criteria.

Answer 3

Thanks Pete Kirkham & Tyler for your answers which are really helpful. Lets say i dont wanna use buttons as i am mainly displaying images as a small rectangles. To check for the rect @ (x,y) , i can trigger that easily by making my grid as a square & finding

gridcolumn = Math.floor(pos.x / cellwidth); gridrow = Math.floor(pos.y / cellheight);

But my problem is with touchesMoved. Lets say i started @ grid-1 & dragged till grid-9 (in a 3*3 matrix), in this case, i am assuming i will get 100-300 (x,y) positions, so everytime i need to run above formula to determine corresponding grid. This results in 300 calculations which might effect the performance.

So when i display an image as a rect, can i associate some id for that image? so that i can simply just save the ids in a list (from grid-1 to grid-9) so that i can avoid the above calculation.

Thanks for your help

Answer 4

Look at UIView's tag property. If your images are in UIViews or subviews of UIView, then you can set each tag and use the tag to look up in an array.

If not, then you can improve the speed by dividing your array of rectangles into sets that fit into larger rectangles. Test the outer rectangles first, then the inner rectangles. 25 rectangles would need only 10 tests worst case as 5 sets of 5.