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

Question

我有一组矩形。试图找出包含给定点的矩形。我可以迭代这个数组并使用 CGRectContainsPoint 找到包含这个点的矩形。伪代码如下

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

我觉得如果我的数组太大以至于我必须迭代大数组，就性能而言这可能不是一个优雅的解决方案。如果有任何最佳解决方案或算法以乐观的方式找到它，有人可以帮助我吗？

Answer 1

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

Answer 2

I feel this may not be elegant solution in terms of performance if my array is so large where I have to iterate large array. Can someone help me if there is any best solution or algorithm to find this in optimistic way.

首先你真的有性能问题吗？在考虑如何改进算法之前确定这一点。一旦您确信需要做某事，然后继续...

您当前的解决方案是通过一组矩形进行线性搜索，这是一个复杂度为 O(N) 的解决方案。要对此进行改进，您需要一种搜索方法来减少您需要进行的测试数量，例如有序集合中的二分搜索具有 O(log N) 的行为，这要好得多。

要使用有序集合，您不想为每次搜索都对无序集合进行排序，完整排序的时间复杂度为 O(NlogN)。相反，你需要考虑保持你的集合排序添加项目以保持排序，每次插入的性能可以是 O(log N)，与二进制搜索相同。

这就留下了一个大问题，你能为你的矩形设计一个合适的顺序以便它们可以排序吗？按原点的 x 坐标排序是可能的，在测试是否包含时，如果点的 x 坐标小于原点的 x 坐标，则该点不能在排序后的任何矩形中。您可能希望研究基于两个原点坐标等的排序。

长话短说：

对矩形列表进行排序并保持排序（每次插入 O(log N)）
以某种方式对矩形进行排序，考虑为此使用原点坐标
使用二进制搜索 (O(log N)) 之类的方法搜索点的包含

这可能会使一切变得更快。

如果您在研究排序和搜索并编写一些代码后遇到问题，请提出一个新问题，展示您的代码，详细说明您的算法（特别是您选择的顺序），并描述您遇到的问题。到时候肯定会有人帮你的。

HTH

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

Find Rectangle contains Point from array of rectangles

ios

objective-c

cgrect