非重叠矩形中的命中测试算法

您可以在四叉树或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上的重叠。

而且,大多数股票或“分类簿”间隔树只检查单个间隔,只返回单个间隔(但您说“不重叠”不是吗?)

把他们推进去 quadtree .

使用A BSP 用于存储矩形的树。