如何快速判斷用戶是否觸碰了許多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查找。

兩者都不如基於樹的方法好，但樹可能會產生痛苦。