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

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；博士：

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

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

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

HTH

Answer 2

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