找到重叠的矩形算法 [英] find overlapping rectangles algorithm

问题描述

让我们说我有一组不重叠的整数坐标，谁是固定的一次，长方形的巨大所有

let's say I have a huge set of non-overlapping rectangle with integer coordinates, who are fixed once and for all

我有一个矩形A和整数坐标的坐标移动（但你可以假设它的大小是不变的）

I have another rectangle A with integer coordinates whose coordinates are moving (but you can assume that its size is constant)

什么是最有效的方式找到其矩形相交（或内部）阿？ 我不能简单地遍历我的设置，因为它太大了。谢谢

What is the most efficient way to find which rectangles are intersecting (or inside) A? I cannot simply loop through my set as it is too big. Thanks

编辑：矩形都平行于轴线

edit : the rectangles are all parallel to the axis

推荐答案

就个人而言，我会解决这个问题的KD树或BIH树。它们是具有的log（n）的搜索时间既自适应空间数据结构。我有两个实现我的光线跟踪器，和他们尖叫。

Personally, I would solve this with a KD-Tree or a BIH-Tree. They are both adaptive spatial data structures that have a log(n) search time. I have an implementation of both for my Ray Tracer, and they scream.

- 更新 -

存储所有的KD-Tree的固定矩形。当您在测试十字路口，遍历KD树如下：

Store all of your fixed rectangles in the KD-Tree. When you are testing intersections, iterate through the KD-Tree as follows:

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);
    }
}

这个功能应该一次从伪code转换，但该算法是正确的。这是一个日志（n）的搜索算法，也可能是最慢的执行它（从递归转换为栈为基础）。

This function should work once converted from pseudo-code, but the algorithm is correct. This is a log(n) search algorithm, and possibly the slowest implementation of it (convert from recursive to stack based).

- 更新 - 增加了一个简单的KD树构建算法

-- UPDATE -- Added a simple KD-Tree building algorithm

这包含面积/体积形状的K D树的最简单形式是以下：

The simplest form of a KD tree that contains area/volume shapes is the following:

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;

还有一堆在这里明显的优化，但建立时间的一般的不一样的搜索时间很重要。话虽这么说，井建树是什么使得搜索速度快。查找SAH-KD-树，如果你想学习如何建立一个快速的kd树。

There a bunch of obvious optimizations here, but build time is usually not as important as search time. That being said, a well build tree is what makes searching fast. Look up SAH-KD-Tree if you want to learn how to build a fast kd-tree.

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