从2个矩形中获取交点

Question

假设我们有两个矩形,用左下角和右上角定义.例如:rect1(x1,y1)(x2,y2)和 rect2(x3,y3)(x4,y4).我正在尝试找到相交矩形的坐标(左下角和右上角).

任何想法,算法,伪代码,将不胜感激.

ps我发现了类似的问题,但只检查了2个矩形是否相交.

Answer 1

如果输入的矩形进行归一化,即你已经知道了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像往常一样,小细节将取决于您是否必须考虑将矩形触摸为交叉.

Answer 2

为了寻找一个路口,你将不得不做点一些简单的比较:

所以,我们可以从图像看X3,Y3大于或等于X1,Y1和小于或等于X2,Y2那么它是第一个矩形内,同样你将需要检查是否X4,Y4落在里面的x1,y1到x2,y2的范围也是如此.

如果这两个条件被证明是真实的,那么你可以肯定的是第二个矩形完全由第一包围.

如果找出哪个对您来说很重要,您还需要检查相反的方向.

您还必须使矩形轴对齐,否则这将无法可靠地工作.

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

更多细节:

要确定矩形是否有任何交叉点,您可以检查其定义点的坐标,出于我们的目的,我们将使用左上角和右下角坐标.我们可以利用一个类来使我们更容易,并且为了最大化代码的可用性,我们可以使用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

#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返回一个真值.

要仅检查交叉点,只需删除相等性检查(=从上面的等式中取出所有内容),然后只检查交叉点.如果你有一个交叉点,那么你可以使用线性代数来评估确切的坐标.

Answer 3

假设一个盒子的半径为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情况:

Answer 4

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