假设我们有两个矩形，分别定义了它们的左下角和右上角。例如：rect1 (x1, y1)(x2, y2)和 rect2 (x3, y3)(x4, y4)。我试图找到相交矩形的坐标（左下角和右上角）。
任何想法，算法，伪代码，将不胜感激。
ps我发现了类似的问题，但他们只检查2个矩形是否相交。
问问题
35059 次
5 回答
67
如果输入矩形是标准化的，即您已经知道x1 < x2, y1 < y2（第二个矩形也是如此），那么您需要做的就是计算
int x5 = max(x1, x3);
int y5 = max(y1, y3);
int x6 = min(x2, x4);
int y6 = min(y2, y4);
它会给你你的交集作为矩形(x5, y5)-(x6, y6)。如果原始矩形不相交，则结果将是一个“退化”矩形（带有x5 >= x6和/或y5 >= y6），您可以轻松检查它。
PS 像往常一样，小细节将取决于您是否必须将触摸矩形视为相交。
于 2013-11-03T16:03:43.157 回答
15
要查找交叉点，您必须对点进行一些简单的比较：
所以我们可以从图像中看到，如果 x3, y3 大于或等于 x1, y1 且小于或等于 x2, y2 那么它在第一个矩形内，同样您需要检查 x4, y4 是否在x1,y1 到 x2,y2 的范围也是如此。
如果这两个条件都成立，那么您可以确定第二个矩形完全被第一个包围。
如果找出里面哪个对你很重要，你也需要反过来检查。
您还必须让矩形轴对齐，否则这将无法可靠地工作。
如果您需要更多详细信息，请告诉我，虽然我认为快速 Google 搜索会很容易为您发现更多详细信息，但请告诉我，如果您愿意，我可以制作一个矩形碰撞教程。
更详细地说：
要找出矩形是否有任何交点，您可以检查它们定义点的坐标，出于我们的目的，我们将使用左上角和右下角坐标。我们可以利用一个类来使这对我们更容易，并最大限度地提高代码的可用性，我们可以使用 2d 矢量和 2d 点： 2dVectorPoint.h
#include <cmath>
class Vector2D
{
public:
float x;
float y;
Vector2D() {}
Vector2D(float inX, float inY)
{
x = inX;
y = inY;
}
Vector2D& Set(float inX, float inY)
{
x = inX;
y = inY;
return (*this);
}
float& operator [](long k) { return ((&x)[k]); }
const float& operator [](long k) const { return ((&x)[k]); }
Vector2D& operator +=(const Vector2D& v)
{
x += v.x;
y += v.y;
return (*this);
}
Vector2D& operator -=(const Vector2D& v)
{
x -= v.x;
y -= v.y;
return (*this);
}
Vector2D& operator *=(float t)
{
x *= t;
y *= t;
return (*this);
}
Vector2D& operator /=(float t)
{
float f = 1.0F / t;
x *= f;
y *= f;
return (*this);
}
Vector2D& operator &=(const Vector2D& v)
{
x *= v.x;
y *= v.y;
return (*this);
}
Vector2D operator -(void) const { return (Vector2D(-x, -y)); }
Vector2D operator +(const Vector2D& v) const { return (Vector2D(x + v.x, y + v.y)); }
Vector2D operator -(const Vector2D& v) const { return (Vector2D(x - v.x, y - v.y)); }
Vector2D operator *(float t) const { return (Vector2D(x * t, y * t)); }
Vector2D operator /(float t) const { float f = 1.0F / t; return (Vector2D(x * , y * f)); }
float operator *(const Vector2D& v) const { return (x * v.x + y * v.y); }
Vector2D operator &(const Vector2D& v) const { return (Vector2D(x * v.x, y * v.y)); }
bool operator ==(const Vector2D& v) const { return ((x == v.x) && (y == v.y)); }
bool operator !=(const Vector2D& v) const { return ((x != v.x) || (y != v.y)); }
Vector2D& Normalize(void) { return (*this /= sqrtf(x * x + y * y)); }
Vector2D& Rotate(float angle);
};
class Point2D : public Vector2D
{
public:
Point2D() {}
Point2D(float r, float s) : Vector2D(r, s) {}
Point2D& operator =(const Vector2D& v)
{
x = v.x;
y = v.y;
return (*this);
}
Point2D& operator *=(float t)
{
x *= t;
y *= t;
return (*this);
}
Point2D& operator /=(float t)
{
float f = 1.0F / t;
x *= f;
y *= f;
return (*this);
}
Point2D operator -(void) const{ return (Point2D(-x, -y)); }
Point2D operator +(const Vector2D& v) const { return (Point2D(x + v.x, y + v.y)); }
Point2D operator -(const Vector2D& v) const { return (Point2D(x - v.x, y - v.y)); }
Vector2D operator -(const Point2D& p) const { return (Vector2D(x - p.x, y - p.y)); }
Point2D operator *(float t) const { return (Point2D(x * t, y * t)); }
Point2D operator /(float t) const
{
float f = 1.0F / t;
return (Point2D(x * f, y * f));
}
};
inline Vector2D operator *(float t, const Vector2D& v){ return (Vector2D(t * v.x, t * v.y));}
inline Point2D operator *(float t, const Point2D& p){ return (Point2D(t * p.x, t * p.y));}
inline float Dot(const Vector2D& v1, const Vector2D& v2){ return (v1 * v2);}
inline float Magnitude(const Vector2D& v){ return (sqrtf(v.x * v.x + v.y * v.y));}
inline float InverseMag(const Vector2D& v){ return (1.0F / sqrtf(v.x * v.x + v.y * v.y));}
inline float SquaredMag(const Vector2D& v){ return (v.x * v.x + v.y * v.y);}
struct Origin2D_
{
const Point2D& operator +(const Vector2D& v) { return (static_cast<const Point2D&>(v)); }
Point2D operator -(const Vector2D& v) { return (Point2D(-v.x, -v.y)); }
};
2dVectorPoint.cpp
#include "2dVectorPoint.h"
Origin2D_ Origin2D;
Vector2D& Vector2D::Rotate(float angle)
{
float s = sinf(angle);
float c = cosf(angle);
float nx = c * x - s * y;
float ny = s * x + c * y;
x = nx;
y = ny;
return (*this);
}
extern Origin2D_ Origin2D;
使用的代码改编自这里以节省我的手指。
然后我们可以利用它轻松比较：我们可以将矩形 1 定义为以 P1 和 P2 作为其边界，将矩形 2 定义为以 P3 和 P4 作为其边界，给我们以下比较：
if ( P2.y <= P3.y && P1.y >= P4.y && P2.x>= P3.x && P1.x <= P4.x )
{
return true;
}
这将为任何相交实例或完全包含矩形 2 的矩形 1 返回一个真值。
要仅检查交叉点，只需删除相等检查（=从上述等式中取出所有内容），您将只检查交叉点。如果您有交集，则可以使用线性代数来评估确切的坐标。
于 2013-11-03T13:07:39.130 回答
8
假设一个盒子有一个半径 X 和半径 Y（我知道它没有，但这个术语在这里很有用）。
你将会有：
rect1_x_radius = (x2-x1)/2
rect1_y_radius = (y2-y1)/2
和
rect2_x_radius = (x4-x3)/2
rect2_y_radius = (y4-y3)/2
现在，如果矩形中点在适当方向上比它们的半径总和更远 - 它们不会发生碰撞。否则他们会这样做——这个提示就足够了。
你现在应该可以完成你的任务了。
更新：
好的 - 让我们为 1D 解决它 - 稍后您将为 2D 解决它。看看这件......艺术;-)
您会看到 2 个段 - 现在进行一些计算：
rA = (maxA-minA) / 2
rB = (maxB-minB) / 2
midA = minA + rA
midB = minB + rB
mid_dist = |midA - midB|
现在如何检查是否发生碰撞？正如我所说，如果“半径”的总和小于段的距离 - 没有碰撞：
if ( mid_dist > fabs(rA+rB) )
{
// no intersection
}
else
{
// segments intersect
}
现在您的工作是计算 1D 和 2D 中的交集/公共部分。现在由您决定（或者您可以阅读安德烈的答案）。
这是相同的情况，但在 2D 中 - 两种 1D 情况：
于 2013-11-03T13:02:18.767 回答
4
您可以分别处理x和y方向。
假设x1 <= x3（第一个框至少和第二个一样在左边）。那么，有重叠当且仅当x1 <= x3 <= x2。
同样，假设y1 <= y3（第一个框至少与第二个框一样远）。那么，有重叠当且仅当y1 <= y3 <= y2。
如果两个方向都有重叠，则有一个矩形重叠。您可以通过对x和y坐标进行排序并选择中间两个来找到坐标。
在伪代码中：
if (((x1 <= x3 && x3 <= x2) || (x3 <= x1 && x1 <= x4)) // x-overlap
&&
((y1 <= y3 && y3 <= y2) || (y3 <= y1 && y1 <= y4)) // y-overlap
) {
int[] xs = {x1, x2, x3, x4};
int[] ys = {y1, y2, y3, y4};
sort(xs);
sort(ys);
// bottom-left: xs[1], ys[1]
// top-right: xs[2], ys[2]
}
于 2013-11-03T13:15:07.853 回答
2
以防万一一个简单的 C# 解决方案适合任何人：
public struct Rectangle
{
public double Left { get; }
public double Top { get; }
public double Width { get; }
public double Height { get; }
public double Right => Left + Width;
public double Bottom => Top + Height;
public static Rectangle Empty { get; } = new Rectangle(0, 0, 0, 0);
public Rectangle(double left, double top, double width, double height)
{
Left = left;
Top = top;
Width = width;
Height = height;
}
public static bool RectanglesIntersect(Rectangle rectangle1, Rectangle rectangle2)
{
rectangle1 = rectangle1.Normalize();
rectangle2 = rectangle2.Normalize();
if (rectangle2.Left >= rectangle1.Right)
return false;
if (rectangle2.Right <= rectangle1.Left)
return false;
if (rectangle2.Top >= rectangle1.Bottom)
return false;
if (rectangle2.Bottom <= rectangle1.Top)
return false;
return true;
}
public static Rectangle GetIntersection(Rectangle rectangle1, Rectangle rectangle2)
{
rectangle1 = rectangle1.Normalize();
rectangle2 = rectangle2.Normalize();
if (rectangle1.IntersectsWith(rectangle2))
{
double left = Math.Max(rectangle1.Left, rectangle2.Left);
double width = Math.Min(rectangle1.Right, rectangle2.Right) - left;
double top = Math.Max(rectangle1.Top, rectangle2.Top);
double height = Math.Min(rectangle1.Bottom, rectangle2.Bottom) - top;
return new Rectangle(left, top, width, height);
}
return Empty;
}
public Rectangle GetIntersection(Rectangle rectangle)
{
return GetIntersection(this, rectangle);
}
public bool IntersectsWith(Rectangle rectangle)
{
return RectanglesIntersect(this, rectangle);
}
public Rectangle NormalizeWidth()
{
if (Width >= 0)
return this;
Rectangle result = new Rectangle(Left + Width, Top, -Width, Height);
return result;
}
public Rectangle NormalizeHeight()
{
if (Height >= 0)
return this;
Rectangle result = new Rectangle(Left, Top + Height, Width, -Height);
return result;
}
public Rectangle Normalize()
{
Rectangle result = NormalizeWidth().NormalizeHeight();
return result;
}
}
于 2019-07-13T22:13:01.743 回答