algorithm - 有效检测与给定点对应的矩形区域（地图）

Question

我们有一个（w 乘以 h）画布（宽度 w 和高度 h），用作绘图区域。我们可以在绘图区域中定义“地图”或区域，用户可以在其上单击以执行一些预定义的任务。每个区域由一个边界矩形定义。当用户在其中单击时，将激活图像映射。两个区域可能有重叠的矩形。每当用户点击画布上的一个点时，我们需要找到该点所属的图像地图并开始执行相应的任务。我们总是可以使用线性列表来查找图像映射。但是有没有更好的方法，一种可用于存储图像映射的数据结构，以便我们可以有效地（在少于 O(n) 时间）确定哪些图像映射在用户点击时被激活？

Answer 1

是 - 使用任何类型的 2D 空间索引。最常见的是四叉树，它的查找复杂度为 O(log(n))，而且构建起来也很快。所有主要语言的实现都可用；它广泛用于所有类型的映射应用程序。

Answer 2

您可以创建某种优化以使这项工作的平均时间减少，但效率仍然是O(n)，因为用户单击可能会执行所有N个可能的任务。