algorithm - 检查一个点是否位于矩形内

Question

我正在用 openCV 做一个项目。然而，语言不是问题。

比如说，我有一个矩形数组。我有一个坐标为 x 和 y 的点数组。我的问题除了使用蛮力技术并检查我拥有的每个矩形的点是否有更好、更优雅的解决方案。

我在这个链接看到了类似的问题，但不明白解决方案:

Check if an array of points is inside an array of rectangles?

背景信息(对于了解图像处理的人)

请看这个问题:Detecting Markers in a video Sequence我之所以在更好的时间限制内要求以上内容是因为这个。我想到的相同算法是在每个标记周围制作一个矩形，并在下一帧中搜索矩形内的标记。如果它位于一个矩形内，那么它很可能是从前一帧移动的同一个标记，然后重新对齐矩形以适应新的标记位置，依此类推。有这么多帧，这个问题可能会使处理速度变慢，因此这个问题。感谢和欢呼。

Answer 1

改进这种朴素方法的一种常见方法是使用 Spatial Indexing .有几个 data structures专门研究这个的。我敢打赌，OpenCV 已经为您提供了其中一些数据结构。

如何在空间上索引场景的一个简单示例是将场景分解为网格，然后对于每个矩形，确定矩形包含哪些网格单元或与之相交。然后您确定您的点位于哪个单元格，瞧，您现在可以在一个矩形列表上进行昂贵的 HitTest ，该列表有望比原始方法小。

这种算法被称为空间散列，在 2D 游戏中被广泛用于加速碰撞检测。请注意，当所有矩形都在每个单元格中，或者当所有矩形和您的点都在同一个单元格中时，此算法的最坏情况会发生。这是一些粗略的伪代码，说明它如何适用于您。不过，我会阅读空间哈希，有 whole articles这将描述执行此操作的最佳方法。

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