我有一个覆盖矩形的不重叠矩形的集合。找到包含鼠标单击的矩形的最佳方法是什么？

显而易见的答案是拥有一个矩形数组并按顺序搜索它们，从而使搜索为O(n)。是否有某种方法可以按位置对它们进行排序，以使算法小于O(n)，例如O(log n)或者O(sqrt(n))？

解决方案

将它们推成四叉树。

使用BSP树存储矩形。

我们可以将矩形组织成四叉树或者kd树。这样就可以得到O(log n)。那是主流方法。

针对此问题的另一个有趣的数据结构是R树。如果我们必须处理许多矩形，这些方法会非常有效。

http://en.wikipedia.org/wiki/R-tree

然后是O(1)方法，可以简单地生成与屏幕相同大小的位图，并在其中填充"无矩形"的占位符，然后将点击矩形索引绘制到该位图中。查找变得如此简单：

int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

显然，只有在矩形不经常更改并且可以为位图保留内存的情况下，该方法才有效。

创建一个间隔树。查询间隔树。咨询麻省理工学院出版社的"算法"。

间隔树最好实现为红黑树。

请记住，通常只有在要单击矩形而不是更改矩形位置的情况下才建议对矩形进行排序。

我们必须记住，我们已经为不同的轴分别构建了索引。例如，我们必须查看是否在X和Y上重叠了一个间隔。一个明显的优化是仅检查两个X间隔上是否重叠，然后立即检查Y上是否重叠。

另外，大多数股票或者" classbook"间隔树仅检查单个间隔，并且仅返回单个间隔(但是我们说"不重叠"不是吗？)