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

Question

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

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

Answer 1

您可以将矩形组织在四边形或 kd 树中。这给了你 O(log n)。这是主流的方法。

这个问题的另一个有趣的数据结构是 R-trees。如果您必须处理大量矩形，这些可能非常有效。

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

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

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

请记住，如果您要单击矩形更多然后您通常会更改它们的位置，则建议对矩形进行排序。

You'll have to keep in mind, that you have build build your indices for different axis separately. E.g., you have to see if you overlap an interval on X and on Y. One obvious optimization is to only check for overlap on either X interval, then immediately check for overlap on Y.

Also, most stock or 'classbook' Interval Trees only check for a single interval, and only return a single Interval (but you said "non-overlapping" didn't you?)

Answer 3

将它们推入四叉树。

Answer 4

使用BSP树来存储矩形。