查找包含点的矩形

Question

在Java SE 7中，我试图解决我有一系列矩形的问题。通过一些用户互动，我得到了一个点。我需要做的是找到包含点（如果有的话）的（第一个）矩形。

目前，我是通过非常幼稚的解决方案来做到这一点的，该解决方案只是将矩形存储在 ArrayList 中，并通过迭代列表并使用 contains() 来搜索包含的矩形。问题是，因为这需要对用户进行交互，所以即使对于相对较少的矩形（例如，200），这种技术也开始太慢了。

我当前的代码如下所示：

// Given rects is an ArrayList<Rectangle>, and p is a Point:
for(Rectangle r : rects)
{
    if(r.contains(p))
    {
        return r;
    }
}
return null;

有没有更聪明的方法来解决这个问题（即，用 O（log n） 代替 O（n），和/或通过尽早消除明显不好的候选者来减少对contains()的调用）？

Answer 1

是的，有。构建 2 个区间树，它会告诉您 x1 到 x2 之间以及 y1 和 y2 之间是否有一个矩形。然后，当您拥有该点的坐标时，在两棵树中执行 O（log n） 搜索。

这会告诉您兴趣点周围是否有矩形。您仍然需要检查两棵树是否给出了一个公共矩形。