how to efficiently find a rect @ some x,y point with iphone sdk
<p>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</p>

<p>1) CGRectIntersectsRect(..,..) : if i use this, then i need to check each &amp; 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 &amp; all corresponding image detection becomes O(n*m) which is not good.</p>

<p>2) Other way is building a hash for each &amp; 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</p>

<p>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.</p>

<p>Sorry for long post &amp; any help would be grateful.</p>

<p>Thanks</p>
