查找矩形包含矩形数组中的点

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

对于大型数组，您可以使用枚举循环，它将在后台线程上运行而不会妨碍主线程。