算法在非重叠矩形命中测试 [英] 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（开方（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树。这让你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树。如果你要处理大量的矩形这些可以是非常有效的。

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屋！