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

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();
  }

显然，只有当您的矩形不经常更改并且您可以为位图腾出内存时，该方法才有效。

Answer 2

创建区间树。查询区间树。请参阅麻省理工学院出版社的“算法”。

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

请记住，通常只有当您单击矩形的次数多于更改其位置时，才建议对矩形进行排序。

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

此外，大多数库存或“教科书”间隔树仅检查单个间隔，并且仅返回单个间隔（但您说“非重叠”不是吗？）

Answer 3

把它们塞进一个 四叉树.

Answer 4

用一个 中央银行 树来存储矩形。