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

Question

我有一组非重叠的矩形,覆盖一个封闭的矩形.找到包含鼠标单击的矩形的最佳方法是什么？

显而易见的答案是拥有一个矩形数组并按顺序搜索它们,使搜索O(n).有没有办法按位置排序,以便算法小于O(n),比如O(log n)或O(sqrt(n))？

Answer 1

您可以在四元组或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();
  }

显然,如果你的矩形不经常改变,并且你可以为位图节省内存,那么该方法才有效.