Как найти координаты пересечения двух прямоугольников

3

Rectangle r1 = rect1;
Rectangle r2 = rect2;
Rectangle intersectionRect = null;

int leftX   = Math.max( r1.getX(), r2.getX() );
int rightX  = Math.min( r1.getX() + r1.getWidth(), r2.getX() + r2.getWidth() );
int topY    = Math.max( r1.getY(), r2.getY() );
int bottomY = Math.min( r1.getY() + r1.getHeight(), r2.getY() + r2.getHeight() );

if ( leftX < rightX && topY < bottomY ) {
  intersectionRect = new Rectangle( leftX, topY, rightX-leftX, bottomY-topY );
} else {
  // Rectangles do not overlap, or overlap has an area of zero (edge/corner overlap)
}

Rectangle r1 = rect1;
Rectangle r2 = rect2;

int leftX   = Math.max( r1.getX(), r2.getX() );
int rightX  = Math.min( r1.getX()+r1.getWidth(), r2.getX()+r2.getWidth() );
int topY    = Math.max( r1.getY(), r2.getY() );
int bottomY = Math.min( r1.getY()+r1.getHeight(), r2.getY()+r2.getHeight() );

Rectangle intersectionRect = new Rectangle( leftX, topY, rightX-leftX, bottomY-topY );

You must log in to answer this question.

Not the answer you’re looking for? Browse other questions tagged

.

Допустим, у нас есть два прямоугольника, определенные их нижним левым и верхним правым углами. Например: rect1 (x1, y1) (x2, y2) а также rect2 (x3, y3) (x4, y4).
Я пытаюсь найти координаты (внизу слева и вверху справа) пересеченного прямоугольника.

Любые идеи, алгоритм, псевдокод, будет принята с благодарностью.

постскриптум Я нашел похожие вопросы, но они проверяют, только если 2 прямоугольника пересекаются.

23

Если входные прямоугольники нормализованы, то есть вы уже знаете, что 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), который вы можете легко проверить.

Постскриптум Как обычно, мелкие детали будут зависеть от того, нужно ли учитывать трогательный прямоугольники как пересекающиеся.

50

Чтобы найти пересечение, вам нужно сделать несколько простых сравнений точек:

Итак, как мы можем видеть из изображения, если x3, y3 больше или равно x1, y1 и меньше или равно x2, y2, то оно находится внутри первого прямоугольника, аналогично вам нужно будет проверить, попадает ли x4, y4 внутрь диапазон от х1, у1 до х2, у2, а также.

если оба условия оказываются верными, то вы можете быть уверены, что второй прямоугольник полностью охватывается первым.

Вам нужно будет проверить и обратное, если узнаете, что внутри, что важно для вас.

Также необходимо, чтобы прямоугольники были выровнены по оси, иначе это не будет работать надежно.

Дайте мне знать, если вам нужно больше подробностей, хотя я думаю, что быстрый поиск в 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.

Чтобы проверить только пересечения, просто удалите проверку на равенство (возьмите все = из вышеприведенного уравнения), и вы будете проверять только на пересечения. Если у вас есть пересечение, вы можете использовать линейную алгебру для оценки точных координат.

15

Скажем, у блока есть радиус 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 — две одномерные ситуации:

7

Вы можете иметь дело с 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]
}

3

Как проверить, пересекаются ли два прямоугольника?

Александр

Гуру

(3871),
закрыт

11 лет назад

Стороны прямоугольников параллельны осям координат. Прямоугольник определяется двумя точками, левой верхней и правой нижней: (x1,y1) и (x2,y2). Ось Ox направлена направо, ось Oy направлена вниз (как на мониторе).