Скажем, что у нас есть два прямоугольника, определяемые их нижним и верхним правыми углами. Например: rect1 (x1, y1) (x2, y2) и rect2 (x3, y3) (x4, y4). Я пытаюсь найти координаты (внизу слева и справа вверху) пересекаемого прямоугольника.
Приветствуются любые идеи, алгоритмы, псевдокоды.
p.s. Я нашел похожие вопросы, но они проверяют, только если 2 прямоугольника пересекаются.
Если входные прямоугольники нормализованы, то есть вы уже знаете, что 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), который вы можете легко проверить.
P.S. Как обычно, мелкие детали будут зависеть от того, нужно ли рассматривать касание прямоугольников как пересекающихся.
Чтобы найти пересечение, вам нужно будет сделать простое сравнение точек:
Итак, как мы можем видеть из изображения, если 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;
}
Это вернет истинное значение для любого экземпляра пересечения или для прямоугольника 1, охватывающего прямоугольник 2 полностью.
Чтобы проверить только пересечения, просто удалите проверку равенства (возьмите все = из приведенного выше уравнения), и вы будете проверять только на пересечения. Если у вас есть пересечение, вы можете использовать линейную алгебру для оценки точных координат.
Скажем, что ящик имеет радиус 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
Теперь, если прямые средние точки находятся дальше, чем сумма их радиусов в соответствующем направлении - они не сталкиваются. В противном случае они делают - этого намека должно быть достаточно.
Теперь вы можете завершить свое задание.
UPDATE:
ОК - разрешите его для 1D - позже вы решите его для 2D. Посмотрите на этот кусок... art; -)
Вы видите 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:
Вы можете иметь дело с направлениями 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]
}
На всякий случай, простое решение С# подойдет любому:
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;
}
}