java - 查找包含一个点的矩形

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 interval trees它会告诉你在 x1 到 x2 之间以及 y1 和 y2 之间是否有一个矩形。然后，当您获得点的坐标时，在两棵树中执行 O(log n) 搜索。

这会告诉您兴趣点周围是否可能有矩形。您仍然需要检查是否存在两棵树给出的公共(public)矩形。