C++ 获取2个矩形的交点

Get the points of intersection from 2 rectangles

提问by NoSense

Let say that we have two rectangles, defined with their bottom-left and top-right corners. For example: rect1 (x1, y1)(x2, y2)and rect2 (x3, y3)(x4, y4). I'm trying to find the coordinates(bottom-left and top-right) of the intersected rectangle.

假设我们有两个矩形，定义为它们的左下角和右上角。例如：rect1 (x1, y1)(x2, y2)和 rect2 (x3, y3)(x4, y4)。我试图找到相交矩形的坐标（左下角和右上角）。

Any ideas, algorithm, pseudo code, would be greatly appreciated.

任何想法，算法，伪代码，将不胜感激。

p.s. I found similar questions but they check only if 2 rectangle intersect.

ps 我发现了类似的问题，但他们只检查 2 个矩形是否相交。

回答by AnT

If the input rectangles are normalized, i.e. you already know that x1 < x2, y1 < y2(and the same for the second rectangle), then all you need to do is calculate

如果输入矩形被归一化，即您已经知道x1 < x2，y1 < y2（第二个矩形也是如此），那么您需要做的就是计算

int x5 = max(x1, x3);
int y5 = max(y1, y3);
int x6 = min(x2, x4);
int y6 = min(y2, y4);

and it will give you your intersection as rectangle (x5, y5)-(x6, y6). If the original rectangles do not intersect, the result will be a "degenerate" rectangle (with x5 >= x6and/or y5 >= y6), which you can easily check for.

它会给你你的交集作为矩形(x5, y5)-(x6, y6)。如果原始矩形不相交，结果将是一个“退化”矩形（带有x5 >= x6和/或y5 >= y6），您可以轻松检查。

P.S. As usual, small details will depend on whether you have to consider touchingrectangles as intersecting.

PS 像往常一样，小细节将取决于您是否必须将触摸矩形视为相交。

回答by GMasucci

To look for an intersection, you will have to do some simple comparison of the points:

要寻找交点，您必须对点进行一些简单的比较：

So as we can see from the image if x3, y3 is greater or equal to x1, y1 and less than or equal to x2, y2 then it is inside the first rectangle, similarly you will need to check if x4, y4 falls inside the range of x1,y1 to x2,y2 as well.

所以从图中我们可以看到，如果 x3, y3 大于或等于 x1, y1 并且小于或等于 x2, y2 那么它在第一个矩形内，同样你需要检查 x4, y4 是否落在x1,y1 到 x2,y2 的范围也是如此。

if both conditions prove to be true then you can be sure that the second rectangle is totally encompassed by the first.

如果这两个条件都被证明为真，那么您可以确定第二个矩形完全被第一个矩形包围。

You will need to check the other way around as well, if finding out which is inside which is important to you.

如果找出里面哪个对您很重要，您还需要反过来检查。

You also have to have the rectangles be axis aligned, otherwise this will not work reliably.

您还必须让矩形轴对齐，否则这将无法可靠地工作。

Let me know if you need more detail, although I think a quick Google search will uncover much more detail for you very easily, but let me know and I can make a rectangle collision tutorial if you like.

如果您需要更多细节，请告诉我，虽然我认为快速的 Google 搜索会很容易为您发现更多细节，但如果您愿意，请告诉我，我可以制作矩形碰撞教程。

In More Detail:

更详细：

To find out if the rectangles have any intersections you can check the coordinates of their defining points, for our purposes we shall use top left and bottom right corner coordinates. We can utilise a class to make this easier for us, and to maximise on the usability of the code we can use a 2d Vector and a 2d Point: 2dVectorPoint.h

要确定矩形是否有任何交点，您可以检查其定义点的坐标，出于我们的目的，我们将使用左上角和右下角坐标。我们可以利用一个类来简化我们的工作，并最大限度地提高代码的可用性，我们可以使用 2d Vector 和 2d Point： 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

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;

Code used is adapted from hereto save my fingers.

使用的代码改编自here以节省我的手指。

Then we can utilise this to easily compare: we can define rectangle 1 as having P1 and P2 as its bounds and rectangle 2 as having P3 and P4 as its bounds, giving us the following comparison:

然后我们可以利用它来轻松进行比较：我们可以将矩形 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;
}

This will return a true value for any instance of intersection or for rectangle 1 encompassing rectangle 2 totally.

这将为任何相交实例或完全包含矩形 2 的矩形 1 返回真值。

To only check for intersections just remove the equality check (take all the =out of the above equation), and you will be checking only for intersections. If you have an intersection you could then use linear algebra to evaluate the exact coordinates.

要仅检查交叉点，只需删除等式检查（=从上述等式中取出所有内容），您将只检查交叉点。如果您有交点，则可以使用线性代数来评估精确坐标。

回答by Artur

Let's say that a box has a radius X and radius Y (I know it has not but this term is useful here).

假设一个盒子有一个半径 X 和半径 Y（我知道它没有，但这个术语在这里很有用）。

You will have:

你将会有：

rect1_x_radius = (x2-x1)/2
rect1_y_radius = (y2-y1)/2

and

和

rect2_x_radius = (x4-x3)/2
rect2_y_radius = (y4-y3)/2

Now if rect middle points are further away than sum of their radiuses in appropriate direction - they do not collide. Otherwise they do - this hint should suffice.

现在，如果矩形中点在适当方向上比它们的半径总和更远 - 它们不会碰撞。否则他们会这样做 - 这个提示就足够了。

You should be now able to finish your assignment.

你现在应该可以完成你的任务了。

UPDATE:

更新：

OK - let's solve it for 1D - later you'll solve it for 2D. Look at this piece of ... art ;-)

好的 - 让我们为 1D 求解 - 稍后您将为 2D 求解。看看这件......艺术品;-)

You see 2 segments - now some calculations:

您会看到 2 个部分 - 现在进行一些计算：

rA = (maxA-minA) / 2
rB = (maxB-minB) / 2

midA = minA + rA
midB = minB + rB

mid_dist = |midA - midB|

Now how to check if collision occurs? As I said if sum of 'radiuses' is less than segments' distance - there is no collision:

现在如何检查是否发生碰撞？正如我所说，如果“半径”的总和小于段的距离 - 没有碰撞：

if ( mid_dist > fabs(rA+rB) )
{
    // no intersection
}
else
{
    // segments intersect
}

Now it is your work to calculate intersection / common part in 1D and 2D. It is up to you now (o ryou can read Andrey's answer).

现在您的工作是计算 1D 和 2D 中的交点/公共部分。现在由您决定（您可以阅读安德烈的回答）。

Here is the same situation but in 2D - two 1D situations:

这是相同的情况，但在 2D 中 - 两种 1D 情况：

回答by Vincent van der Weele

You can deal with the xand ydirection separately.

可以分别处理x和y方向。

Assume that x1 <= x3(the first box is at least as far to the left as the second). Then, there is overlap if and only if x1 <= x3 <= x2.

假设x1 <= x3（第一个框至少与第二个框向左一样远）。那么，存在重叠当且仅当x1 <= x3 <= x2。

Similarly, assume y1 <= y3(the first box is at least as far to the bottom as the second). Then, there is overlap if and only if y1 <= y3 <= y2.

类似地，假设y1 <= y3（第一个框至少与第二个框到底部一样远）。那么，存在重叠当且仅当y1 <= y3 <= y2。

If there is overlap in both directions, there is a rectangle overlapping. You can find the coordinates by sorting the xand ycoordinates and selecting the middle two.

如果两个方向都有重叠，则有一个矩形重叠。您可以通过对x和坐标进行排序y并选择中间两个来找到坐标。

In pseudocode:

在伪代码中：

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]
}

回答by Phil Brook

Just in case a straightforward C# solution would suit anyone:

以防万一一个简单的 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;
    }
}