非重叠矩形中的命中测试算法 [英] Algorithm for hit test in non-overlapping rectangles

问题描述

我有一组不重叠的矩形，它们覆盖了一个封闭的矩形.找到鼠标单击的包含矩形的最佳方法是什么?

I have a collection of non-overlapping rectangles that cover an enclosing rectangle. What is the best way to find the containing rectangle for a mouse click?

显而易见的答案是有一个矩形数组并按顺序搜索它们，使得搜索 O(n).有没有办法按位置对它们进行排序，使算法小于 O(n)，比如 O(log n) 或 O(sqrt(n))?

The obvious answer is to have an array of rectangles and to search them in sequence, making the search O(n). Is there some way to order them by position so that the algorithm is less than O(n), say, O(log n) or O(sqrt(n))?

推荐答案

您可以将矩形组织成四边形或 kd-tree.这给了你 O(log n).这是主流的方法.

You can organize your rectangles in a quad or kd-tree. That gives you O(log n). That's the mainstream method.

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

Another interesting data-structure for this problem are R-trees. These can be very efficient if you have to deal with lots of rectangles.

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

然后是 O(1) 方法，只需生成与屏幕大小相同的位图，用无矩形"的占位符填充它，然后将命中矩形索引绘制到该位图中.查找变得如此简单:

And then there is the O(1) method of simply generating a bitmap at the same size as your screen, fill it with a place-holder for "no rectangle" and draw the hit-rectangle indices into that bitmap. A lookup becomes as simple as:

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

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

Obviously that method only works well if your rectangles don't change that often and if you can spare the memory for the bitmap.

这篇关于非重叠矩形中的命中测试算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！