找到重叠的矩形算法

Question

假设我有一组巨大的非重叠矩形和整数坐标,它们一劳永逸地固定

我有另一个矩形A,其整数坐标的坐标正在移动(但你可以假设它的大小是常数)

查找哪些矩形与A交叉(或内部)的最有效方法是什么？我不能简单地遍历我的设置,因为它太大了.谢谢

编辑:矩形都与轴平行

Answer 1

我敢打赌你可以使用某种四叉树的推导来做到这一点.看看这个例子.

Answer 2

就个人而言，我会用 KD-Tree 或 BIH-Tree 来解决这个问题。它们都是具有 log(n) 搜索时间的自适应空间数据结构。我为我的 Ray Tracer 实现了两者，他们尖叫起来。

- 更新 -

将所有固定矩形存储在 KD 树中。在测试交叉点时，按如下方式遍历 KD-Tree：

function FindRects(KDNode node, Rect searchRect, List<Rect> intersectionRects)

// searchRect is the rectangle you want to test intersections with
// node is the current node. This is a recursive function, so the first call
//    is the root node
// intersectionRects contains the list of rectangles intersected

int axis = node.Axis;

// Only child nodes actually have rects in them
if (node is child)
{
    // Test for intersections with each rectangle the node owns
    for each (Rect nRect in node.Rects)
    {
        if (nRect.Intersects(searchRect))
              intersectionRects.Add(nRect);
    }
}
else
{
    // If the searchRect's boundary extends into the left bi-section of the node
    // we need to search the left sub-tree for intersections
    if (searchRect[axis].Min  // Min would be the Rect.Left if axis == 0, 
                              // Rect.Top if axis == 1
                < node.Plane) // The absolute coordinate of the split plane
    {
        FindRects(node.LeftChild, searchRect, intersectionRects);
    }

    // If the searchRect's boundary extends into the right bi-section of the node
    // we need to search the right sub-tree for intersections
    if (searchRect[axis].Max  // Max would be the Rect.Right if axis == 0
                              // Rect.Bottom if axis == 1
                > node.Plane) // The absolute coordinate of the split plane
    {
        FindRects(node.RightChild, searchRect, intersectionRects);
    }
}

一旦从伪代码转换，这个函数应该可以工作，但算法是正确的。这是一个 log(n) 搜索算法，可能是它最慢的实现（从递归转换为基于堆栈）。

-- 更新 -- 添加了一个简单的 KD-Tree 构建算法

包含面积/体积形状的 KD 树的最简单形式如下：

Rect bounds = ...; // Calculate the bounding area of all shapes you want to 
              // store in the tree
int plane = 0; // Start by splitting on the x axis

BuildTree(_root, plane, bounds, insertRects);

function BuildTree(KDNode node, int plane, Rect nodeBds, List<Rect> insertRects)

if (insertRects.size() < THRESHOLD /* Stop splitting when there are less than some
                                      number of rects. Experiment with this, but 3
                                      is usually a decent number */)
{
     AddRectsToNode(node, insertRects);
     node.IsLeaf = true;
     return;
}

float splitPos = nodeBds[plane].Min + (nodeBds[plane].Max - nodeBds[plane].Min) / 2;

// Once you have a split plane calculated, you want to split the insertRects list
// into a list of rectangles that have area left of the split plane, and a list of
// rects that have area to the right of the split plane.
// If a rect overlaps the split plane, add it to both lists
List<Rect> leftRects, rightRects;
FillLists(insertRects, splitPos, plane, leftRects, rightRects); 

Rect leftBds, rightBds; // Split the nodeBds rect into 2 rects along the split plane

KDNode leftChild, rightChild; // Initialize these
// Build out the left sub-tree
BuildTree(leftChild, (plane + 1) % NUM_DIMS, // 2 for a 2d tree
          leftBds, leftRects);
// Build out the right sub-tree
BuildTree(rightChild, (plane + 1) % NUM_DIMS,
          rightBds, rightRects);

node.LeftChild = leftChild;
node.RightChild = rightChild;

这里有一堆明显的优化，但构建时间通常不如搜索时间重要。话虽如此，构建良好的树是使搜索快速的原因。如果您想学习如何构建快速 kd 树，请查找 SAH-KD-Tree。