假设我有一组非重叠的整数坐标矩形，它们一旦固定就不再改变。我有另一个带有整数坐标的矩形 A，其坐标正在移动（但您可以假设其大小是恒定的）。最有效的方法是什么，以找到哪些矩形与 A 相交（或在其中）？由于我的集合太大，我不能简单地遍历它们。谢谢。
编辑：所有矩形都平行于坐标轴。
编辑：所有矩形都平行于坐标轴。
找出重叠矩形算法
12
- lezebulon
9
4这让我想起了一份美国移民表格上的问题。换句话说，“你是恐怖分子吗？” :D - Ilian
5四叉树：http://zh.wikipedia.org/wiki/四叉树 - i_am_jorf
@m0skit0：我在考虑使用一种变体的扫描和修剪算法，我觉得不需要检查所有的矩形。 - lezebulon
1也可以尝试搜索“R树”。 - Nemo
1因此，初始位置必须使用其中一种描述的方法进行搜索。但是，一旦您拥有该位置，如果您的对象具有上/下/左/右指针，则应能够在不再搜索的情况下找到下一个交叉点。 - Jan
显示剩余4条评论
12个回答
7
个人而言，我会使用KD树或BIH树来解决这个问题。它们都是自适应空间数据结构，具有对数（log）搜索时间。我已经在我的光线追踪器中实现了两者，并且它们的效果非常好。
-- 更新 --
将所有固定矩形存储在KD树中。当您测试交叉点时，请按以下方式遍历KD树：
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-tree，请查阅SAH-KD-Tree。
- Mranz
5
好的，我会尝试，但是如何在树中存储矩形呢？我应该将它们视为点对象并仅存储左上角位置吗？ - lezebulon
有很多种方法可以构建它。我会更新我的答案，介绍如何构建最简单的形式。 - Mranz
@Mranz，我有一个关于int axis = node.Axis的问题，node.Axis到底是什么，你是如何计算它的？还有这一部分FillLists(insertRects, splitPos, plane, leftRects, rightRects);我没有正确理解这两个部分。谢谢。 - Hani Goc
@HaniGoc 轴是节点分割的维度。如果树是三维的，则0-> x，1-> y，2-> z。fill lists函数将每个源矩形添加到leftRects或rightRects列表中，如果该矩形在分割平面的一侧，则会添加到该侧的列表中。如果矩形跨越平面，则会同时被添加到两个列表中。 - Mranz
很久以前，我使用了一对优先级搜索树来处理“刺穿”的（非重叠-对这种方法至关重要？）矩形。 - greybeard
2
您可以创建两个矩形索引向量（因为两个对角点唯一定义您的矩形），并按其中一个坐标进行排序。然后，使用这两个索引数组搜索重叠区域，这将具有对数复杂度而非线性复杂度。
- Slava
2
好吧，现在我想想我不明白你想说什么？我怎样才能只用两个数组来存储2个对角点？ - lezebulon
这仍然是最坏情况下的O(n)时间。 - roulette01
1
区间树：是将“lo”值作为区间的键设计的二叉搜索树。例如，如果要在树中插入（23, 46），则需使用BST中的“23”进行插入。
此外，在区间树中，我们在每个节点上保留以该节点为根的子树的最大端点（hi值）。
这种插入顺序使我们能够在R(logN)时间内搜索所有“R”交点。[我们在logN时间内搜索第一个交点，并在RlogN时间内搜索所有R]请参阅区间树文档，了解如何完成插入、搜索以及复杂性的详细信息。
现在，对于这个问题，我们使用一种称为扫描线算法的算法。想象一条垂直线（与y轴平行），它正在扫描2D空间，并在此过程中与矩形相交。
1）通过优先队列或排序将矩形按x坐标（从左边缘开始）递增排列。如果有N个矩形，则复杂度为NlogN。
2）当此线从左向右扫描时，以下是交点情况：
如果线段与一个从未见过的矩形的左侧相交，则将矩形边的y坐标添加到区间树中。[假设(x1,y1)和(x1,y2)是矩形的左边缘坐标，将区间(y1,y2)添加到区间树中] ---> (NlogN)
在区间树上进行范围搜索。[假设(x1,y1)和(x1,y2)是矩形的左边缘坐标，取区间(y1,y2)，并在树上执行区间交集查询以查找所有交点] ---> RlogN（实际应用中）
如果线段与矩形的右侧相交，则从区间树中删除其y坐标，因为矩形现在已完全处理。----> NlogN
总复杂度：NlogN + RlogN
- user1071840
1
Topcoder提供了一种确定点是否在矩形内的方法。它说，假设我们有一个点x1，y1和一个矩形。我们应该在矩形坐标系中选择一个离当前参考位置非常远的随机点，比如x2，y2。
现在，我们应该用点x1，y1和x2，y2构成一条线段。如果这条线段与给定矩形的奇数边相交（在我们的情况下为1，这种方法也可以扩展到一般多边形），则点x1，y1位于矩形内；如果它与偶数边相交，则点x1，y1位于矩形外。
给定两个矩形，我们需要对第一个矩形的每个顶点重复此过程，以确定可能位于第二个矩形内。这样，即使它们不与x或y轴对齐，我们也能确定两个矩形是否重叠。
- user1071840
1
你可以使用随机“行走”算法...基本上为所有固定位置的矩形创建邻居列表。 然后随机选择一个固定位置的矩形，检查目标矩形相对于当前固定位置矩形的位置。 如果它不在您随机选择的起点矩形内，则将在与当前固定位置矩形的给定邻居相对应的八个方向之一中的一个方向上。 （即，对于任何给定的矩形，都将有一个矩形在N，NE，E，SE，S，SW，W，NW方向上）。 选择最接近目标矩形的给定方向的相邻矩形，并重新测试。 这本质上是一种随机增量构造算法，对于几何问题的性能往往非常好（单次迭代通常为对数级别，重复迭代为O（nlogn））。
- Jason
2
2如果移动的盒子移动缓慢，则非常有效。如果它瞬间传送，则非常无效 :( - Mooing Duck
哈哈...那确实让我笑了 :) ... 话虽如此，在你搜索时，盒子是否在移动？难道搜索不应该在盒子移动模拟的给定时间片段内进行吗？ - Jason
1
创建一个矩阵，其中包含“象限”元素，每个象限代表系统中的一个N*M空间，其中N和M分别是最宽和最高矩形的宽度和高度。每个矩形将根据其左上角放置在一个象限元素中（因此，每个矩形将恰好位于一个象限中）。给定矩形A，请检查A所在象限和8个相邻象限中的矩形之间是否发生碰撞。
这是我记得看到的一种算法，用于游戏设计中的碰撞检测的简单优化。当您主要处理小对象时，它的效果最佳，但如果您有几个大对象，则可以通过单独执行碰撞检测并不将它们放置在象限中来降低象限大小，从而避免破坏其效率。
这是我记得看到的一种算法，用于游戏设计中的碰撞检测的简单优化。当您主要处理小对象时，它的效果最佳，但如果您有几个大对象，则可以通过单独执行碰撞检测并不将它们放置在象限中来降低象限大小，从而避免破坏其效率。
- Brian
1
从技术上讲，象限不必比矩形大，_如果_每个象限都知道与它相接触的所有矩形。然后你只需要检查你所在的象限。更快，但需要更多的内存。 - Mooing Duck
1
由于它们不重叠，我建议采用类似（但不完全相同）于Jason Moore（B）的方法。将您的数组按左上角的x排序。然后将副本按左上角的y排序。（当然，您只需对它们进行指针排序以节省内存）。
现在，您可以创建两个集合Sliding_Window_X和Sliding_Window_Y。
您可以使用二分搜索一次在x排序的数组中搜索A窗口的x坐标（左上角）和y坐标。将结果放入相应的Sliding_Window_Set中。现在，将有一个比A的右下角低的x（y）坐标的有序数组中的所有后续矩形添加到其中。
结果是，在Sliding_Window集中，您拥有与A在一个坐标上重叠的窗口。 A的重叠是Sliding_Window_X和_Y的交集。
Sliding_Window集可以通过仅使用2个数字（相应排序数组的开始和结束索引）轻松表示。
根据您所说的移动A，现在重新计算重叠区域非常容易。根据方向，您现在可以添加/删除滑动窗口集合中的元素。也就是说，您只需从集合前/后的排序数组中取下一个元素，可能会在末尾删除一个元素。
- flolo
0
让你的矩形集合为 (Xi1,Yi1,Xi2,Yi2)，其中 i 的取值范围从 0 到 N。
如果 Ax1 > Bx2 || Ay1 < By2 || Bx1 > Ax2 || By1 < Ay2，则矩形 A 和 B 不能相交。
创建一个针对范围/区间进行优化的树（例如：线段树或区间树） 请参见 http://w3.jouy.inra.fr/unites/miaj/public/vigneron/cs4235/l5cs4235.pdf
使用此树来查找一组三角形，同时您的三角形正在更改坐标。
- Jack
0
通过计算每个矩形的面积，并检查长度L、高度H和矩形的面积是否超过矩形A的长度、高度和面积，来判断是否超出。
- nurmurat
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接