我做OpenCV中的一个项目。然而，语言不是在这一个问题。

I am doing a project in openCV. However the language is not a concern in this.

我有矩形阵列，说。我有一个点的坐标x和y的数组。 我的问题是除了用蛮力技术，检查点与每一个矩形我有一个更好，更优雅的解决方案。

I have an array of rectangles, say. And I have a an array of points with coordinates x and y. My question is apart from using the brute force technique and check a point with every rectangle I have is there a better and more elegant solution.

我看到一个类似的问题，在这个环节，但不明白的解决方案：

I saw a similar question at this link but did not understand the solution:

Check如果一个点的数组是矩形的数组里面？

背景信息（谁知道图像处理的人）

请看看这个问题：检测标记的视频序列 我要求上述一个更好的时间限制的原因是因为这个原因。我已经想为同一算法是使围绕各标记以及在下一帧中寻找一个矩形内部的标记的矩形。它是否处在一个矩形内，那么很可能这是相同的标记，其已经从previous帧移动，然后重新对齐矩形现在适合新标记位置等。有了这么多的帧的问题，很可能使加工速度慢，因此这个问题。 感谢和欢呼声。

Please have a look at this question: Detecting Markers in a video Sequence The reason I require the above in a better time limit is because of this. The algorithm that I have thought for the same is to make a rectangle around each marker and in the next frame search for a marker inside a rectangle. If it lies inside a rectangle then it is likely that it was the same marker which has moved from the previous frame, then realign the rectangle to now fit the new marker position and so on. With so many frames the problem is likely to make processing slow hence this question. Thanks and cheers.

推荐答案

要改善天真的方法来一个常见的​​方法是使用的空间索引。有一对夫妇的数据结构，专门在此。我敢打赌，OpenCV的一些数据结构提供给你了。

A common way to improve on the naive approach to this is to use Spatial Indexing. There are a couple of data structures that specialize in this. I bet OpenCV has some of these data structures available to you already.

如何索引你的场景空间是向下打破你的场景为一个网格，然后针对每个矩形，确定哪些网格单元或者包含或相交的矩形一个简单的例子。然后确定哪个单元的点在于，瞧，你现在可以做你的昂贵的点击测试矩形的名单是希望比天真的小方法上。

One simple example of how to index your scene spatially is to break your scene down into a grid, and then for each rectangle, determine which grid cells the rectangle either contains or intersects with. Then you determine which cell your point lies in, and voila, you can now do your expensive hit test on a list of rectangles that is hopefully smaller than the naive method.

此算法被称为空间散列，并且使用了大量用于加速碰撞检测​​在二维游戏。需要注意的是，当所有的矩形是每个细胞中发生了该算法的最坏的情况下，或当所有的矩形和你的点是在相同的小区。下面是一些粗糙的伪$ C $下如何适用于您。我读了空间散列不过，也有整个 文章，将描述要做到这一点的最好办法。

This algorithm is known as spatial hashing, and is used a lot for speeding up collision detection in 2D games. Note that the worst case of this algorithm occurs when all the rectangles are in every cell, or when all the rectangles and your point are in the same cell. Here's some rough pseudo code for how it applies to you. I would read up on spatial hashing though, there are whole articles that will describe the best way to do this.

rects = array of rectangles
grid = divide scene into n x m grid

for each cell in grid do
    cell.m_rects = determine_which_rects_intersect(cell, rects)
end

...

pt = some point in scene
pt_cell = grid.get_cell_for_pt(pt)

hits = empty array
for each rect in pt_cell.m_rects do
    if expensive_hit_test(pt, rect) then
        hits.append(rect)
    end
end

return hits