关于.net：非重叠矩形中的点击测试算法

Algorithm for hit test in non-overlapping rectangles

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

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

您可以将矩形组织成四叉树或kd树。那给你O(log n)。那是主流方法。

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

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

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

1
2
3
4
5
6
7
8
9

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

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

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

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

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

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

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

使用BSP树存储矩形。

将它们推成四叉树。