如何快速判断用户是否触碰了许多CGRects

Question

我有一款iPhone游戏，其中可能有30（或更多）CGRects，我需要一种快速确定用户是否触摸了它的方法。我之前一直在考虑使用下面的设置来检测用户是否触摸了Cocos2d中的CGRect，触发内部。所以我有一个向量（我用的OBJ-C++）CGRects的：

for (int i = 0; i < (int) vec_of_cgrects; i++) { 
    if (CGRectContainsPoint(vec_of_cgrects[i], location) { 
     //Do what I need to do if user touches one of the rectangles 
    } 
} 

但是这不是有效的，我想如果这最好的方式来检测用户触摸的一个特定的矩形矩形矢量或者如果有更好的方法。

Answer 1

你想让用户触摸的每个矩形发生什么事情，或者用户触摸任何一个老的矩形时发生一个事件？

在这两种情况下你可以做出的一个改进就是通过它们的x坐标（或者y坐标，如果这更适合你的情况）对CGRects进行排序，所以只要CGRect的x坐标大于触摸的x坐标。

如果是后者，您还可以事先检查CGRect是否完全被其他CGRect包含，如果是，请将它们从数组中删除。

Answer 2

你可以考虑使用空间散列：

http://www.gamedev.net/index.php?app=core&module=search&do=search&fromMainBar=1

下面是对cocos2d的论坛上一个帖子看：

http://www.cocos2d-iphone.org/forum/topic/11323#post-64132

花栗鼠和Box2D的使用它（物理库）我我很确定他们的碰撞检测...

Answer 3

替代性的低效率认可ch：存储宽度*高度列表的数组。使用覆盖该像素的矩形列表填充每个列表（如果您执行某种重叠处理，则使用“顶部”矩形）。 O（1）查找！

“黑客”的方法：将屏幕分割成大小为h * h的平方，其中h〜=（宽度+高度）/ sqrt（n）。像上面那样填充每个方块。 O（sqrt（n）） - ish查找。

两者都不如基于树的方法好，但树可能会产生痛苦。