查找矩形包含矩形數組中的點

Question

我有一個矩形數組。試圖找出包含給定點的矩形。我可以迭代這個數組，並使用CGRectContainsPoint來查找包含這個點的矩形。僞代碼如下

CGRect rectContainingPoint; 
for (CGRect rect in arrayOfRects) { 
    if(CGRectContainsPoint(rect, point)) { 
     rectContainingPoint = rect; 
     break; 
    } 
} 

我覺得這可能不是在性能方面完美的解決方案，如果我的數組是如此之大，我不得不重複大陣。如果有任何最佳的解決方案或算法以樂觀的方式找到這個問題，有人能幫助我嗎？

Answer 1

我覺得這可能不是優雅的解決方案的性能方面，如果我的數組是如此之大，我必須迭代大型數組。如果有任何最佳的解決方案或算法以樂觀的方式找到這個問題，有人能幫助我嗎？

首先你確實有性能問題？確定在考慮如何改進算法之前。一旦你確信需要做的事情，然後繼續...

您目前的解決方案是通過矩形集合的線性搜索，它是一個O（N）解決方案。爲了改善這一點，您需要一種搜索​​方法，以減少您需要進行的測試次數，例如，在有序集合中的二進制搜索具有O（log N）行爲，這是更好的。

要使用有序集合，您不希望對每個搜索的無序排序進行排序，則完整排序爲O（NlogN）。相反，你需要考慮保持你的集合排序添加項目，以保持排序，其性能可以是每個插入O（log N），與二進制搜索相同。

這只是留下了一個大問題，你能爲你的矩形設計一個合適的排序，以便它們可以排序嗎？當測試包含時，如果點的x座標值小於原點的x座標，則可能通過x座標原點排序，那麼該點不能在排序中的任何矩形中。您不妨考慮基於兩個原點座標排序等

TL; DR：

1. 排序的矩形列表，並保持它的排序（O（日誌N）的每次插入）
2. 訂購您的矩形不知何故，可以考慮使用座標原點（個），這
3. 搜索使用類似二進制搜索點的夾雜物（O（日誌N））

這可能會使一切快呃。

如果碰到一個問題，一旦你的研究排序和搜索，並寫了一些代碼，提出新問題，顯示你的代碼，詳細說明您的算法（特別是你選擇了訂購），並說明你打的問題。有人會毫無疑問地幫助你。

HTH

Answer 2

對於大型數組，您可以使用枚舉循環，它將在後臺線程上運行而不會妨礙主線程。