Определите, перекрываются ли два прямоугольника друг друга?
https://stackoverflow.com/questions/306316
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь написать программу на C++, которая принимает от пользователя следующие данные для построения прямоугольников (от 2 до 5):высота, ширина, X-поз., Y-поз.Все эти прямоугольники будут существовать параллельно осям x и y, то есть все их края будут иметь наклон 0 или бесконечности.
Я попытался реализовать то, что упомянуто в этот вопрос, но мне не очень повезло.
Моя текущая реализация делает следующее:
// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2
// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];
int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;
Однако я не совсем уверен, что (а) я правильно реализовал алгоритм, на который ссылаюсь, или я точно сделал, как это интерпретировать?
Какие-либо предложения?
Решение
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
или, используя декартовы координаты
(X1 — это левая координата, X2 — правая координата, увеличивающаяся слева направо, Y1 — верхняя координата, а Y2 — нижняя координата, увеличивающаяся снизу вверх)…
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
ПРИМЕЧАНИЕ:ВСЕМ ПОЛЬЗОВАТЕЛЯМ С ПРАВАМИ РЕДАКТИРОВАНИЯ.ПОЖАЛУЙСТА, ПЕРЕСТАНЬТЕ С ЭТИМ ЗАНИМАТЬСЯ.
Допустим, у вас есть Rect A и Rect B.Доказательство проводится от противного.Любое из четырех условий гарантирует, что никакого совпадения быть не может:
- Условие1.Если левый край А находится справа от правого края Б, - тогда A полностью справа от B
- Условия 2.Если правый край А находится слева от левого края Б, - тогда А полностью левее Б
- Условия3.Если верхний край А находится ниже нижнего края Б, - тогда A полностью ниже B
- Условия4.Если нижний край А находится над верхним краем Б, - тогда A полностью выше B
Таким образом, условие для неперекрытия
Cond1 Or Cond2 Or Cond3 Or Cond4
Следовательно, достаточным условием перекрытия является противоположное.
Not (Cond1 Or Cond2 Or Cond3 Or Cond4)
Закон де Моргана гласит
Not (A or B or C or D) такой же как Not A And Not B And Not C And Not D
поэтому, используя Де Моргана, мы имеем
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
Это эквивалентно:
- Левый край A слева от правого края B, [
RectA.Left < RectB.Right], и - Правый край A справа от левого края B, [
RectA.Right > RectB.Left], и - Верх А выше низа Б, [
RectA.Top > RectB.Bottom], и - Низ А ниже верха Б [
RectA.Bottom < RectB.Top]
Примечание 1:Совершенно очевидно, что этот же принцип можно распространить на любое количество измерений.
Заметка 2:Также должно быть достаточно очевидно подсчет перекрытий всего лишь одного пикселя, изменение < и/или > на этой границе с <= или >=.
Заметка 3:Этот ответ при использовании декартовых координат (X, Y) основан на стандартных алгебраических декартовых координатах (x увеличивается слева направо, а Y увеличивается снизу вверх).Очевидно, что там, где компьютерная система может механизировать координаты экрана по-другому (например, увеличивая Y сверху вниз или X справа налево), синтаксис необходимо будет соответствующим образом скорректировать.
Другие советы
struct rect
{
int x;
int y;
int width;
int height;
};
bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }
bool rectOverlap(rect A, rect B)
{
bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width);
bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height);
return xOverlap && yOverlap;
}struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
bool
overlap(const Rect &r1, const Rect &r2)
{
// The rectangles don't overlap if
// one rectangle's minimum in some dimension
// is greater than the other's maximum in
// that dimension.
bool noOverlap = r1.x1 > r2.x2 ||
r2.x1 > r1.x2 ||
r1.y1 > r2.y2 ||
r2.y1 > r1.y2;
return !noOverlap;
}
Проще проверить, находится ли прямоугольник полностью за пределами другого, поэтому если он либо
слева ...
(r1.x + r1.width < r2.x)
или справа ...
(r1.x > r2.x + r2.width)
или сверху ...
(r1.y + r1.height < r2.y)
или внизу ...
(r1.y > r2.y + r2.height)
второго прямоугольника, он не может столкнуться с ним. Таким образом, чтобы получить функцию, которая возвращает логическое значение, говорящее о столкновении прямоугольников, мы просто объединяем условия с помощью логических ИЛИ и отменяем результат:
function checkOverlap(r1, r2) : Boolean
{
return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}
Чтобы получить положительный результат только при касании, мы можем изменить " < " и " > " " < = " и " > = ".
Задайте себе противоположный вопрос: как я могу определить, не пересекаются ли два прямоугольника вообще? Очевидно, что прямоугольник A полностью слева от прямоугольника B не пересекается. Кроме того, если А полностью вправо. И точно так же, если A полностью выше B или полностью ниже B. В любом другом случае A и B пересекаются.
В дальнейшем могут быть ошибки, но я довольно уверен в алгоритме:
struct Rectangle { int x; int y; int width; int height; };
bool is_left_of(Rectangle const & a, Rectangle const & b) {
if (a.x + a.width <= b.x) return true;
return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
return is_left_of(b, a);
}
bool not_intersect( Rectangle const & a, Rectangle const & b) {
if (is_left_of(a, b)) return true;
if (is_right_of(a, b)) return true;
// Do the same for top/bottom...
}
bool intersect(Rectangle const & a, Rectangle const & b) {
return !not_intersect(a, b);
}
Предположим, что вы определили позиции и размеры прямоугольников следующим образом:
Моя реализация на C ++ выглядит следующим образом:
class Vector2D
{
public:
Vector2D(int x, int y) : x(x), y(y) {}
~Vector2D(){}
int x, y;
};
bool DoRectanglesOverlap( const Vector2D & Pos1,
const Vector2D & Size1,
const Vector2D & Pos2,
const Vector2D & Size2)
{
if ((Pos1.x < Pos2.x + Size2.x) &&
(Pos1.y < Pos2.y + Size2.y) &&
(Pos2.x < Pos1.x + Size1.x) &&
(Pos2.y < Pos1.y + Size1.y))
{
return true;
}
return false;
}
Пример вызова функции в соответствии с приведенным выше рисунком:
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
Сравнения внутри блока if будут выглядеть следующим образом:
if ((Pos1.x < Pos2.x + Size2.x) &&
(Pos1.y < Pos2.y + Size2.y) &&
(Pos2.x < Pos1.x + Size1.x) &&
(Pos2.y < Pos1.y + Size1.y))
↓
if (( 3 < 6 + 9 ) &&
( 7 < 4 + 4 ) &&
( 6 < 3 + 8 ) &&
( 4 < 7 + 5 ))
Вот как это делается в Java API:
public boolean intersects(Rectangle r) {
int tw = this.width;
int th = this.height;
int rw = r.width;
int rh = r.height;
if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
return false;
}
int tx = this.x;
int ty = this.y;
int rx = r.x;
int ry = r.y;
rw += rx;
rh += ry;
tw += tx;
th += ty;
// overflow || intersect
return ((rw < rx || rw > tx) &&
(rh < ry || rh > ty) &&
(tw < tx || tw > rx) &&
(th < ty || th > ry));
}
В этом вопросе вы ссылаетесь на математику, когда прямоугольники находятся под произвольными углами поворота. Однако если я немного разбираюсь в углах вопроса, я понимаю, что все прямоугольники перпендикулярны друг другу.
Общее знание формулы области перекрытия:
Используя пример:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) собрать все координаты х (как левые, так и правые) в список, затем отсортировать и удалить дубликаты
1 3 4 5 6
2) собрать все координаты y (как верхнюю, так и нижнюю) в список, затем отсортировать и удалить дубликаты
1 2 3 4 6
3) создать двумерный массив по количеству промежутков между уникальными координатами x * числу промежутков между уникальными координатами y.
4 * 4
4) закрасить все прямоугольники в эту сетку, увеличивая счетчик каждой ячейки, в которой она встречается:
1 3 4 5 6
1 +---+
| 1 | 0 0 0
2 +---+---+---+
| 1 | 1 | 1 | 0
3 +---+---+---+---+
| 1 | 1 | 2 | 1 |
4 +---+---+---+---+
0 0 | 1 | 1 |
6 +---+---+
5) Когда вы рисуете прямоугольники, легко перехватывать перекрытия.
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
r1.y1 < r2.y2 && r2.x1 < r1.y2;
}
//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}
Не думайте, что координаты указывают, где находятся пиксели. Думайте о них как о пикселях. Таким образом, площадь прямоугольника 2х2 должна быть 4, а не 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
Самый простой способ это
/**
* Check if two rectangles collide
* x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
* x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
*/
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}
Прежде всего, подумайте, что в компьютерах система координат перевернута. Ось X такая же, как в математике, но ось Y увеличивается вниз и уменьшается при движении вверх. если прямоугольник нарисован из центра. если координаты x1 больше, чем x2 плюс его половина видимости. тогда это означает, что половину они коснутся друг друга. и таким же образом идет вниз + половина его высоты. это столкнется ..
Допустим, два прямоугольника - это прямоугольник A и прямоугольник B. Пусть центрами являются A1 и B1 (координаты A1 и B1 можно легко определить), пусть высоты - Ha и Hb, ширина - Wa и Wb, пусть dx - расстояние по ширине (x) между A1 и B1, а dy - расстояние по высоте (y) между A1 и B1.
Теперь мы можем сказать, что мы можем сказать, что A и B перекрываются: когда
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
Я реализовал версию C #, она легко конвертируется в C ++.
public bool Intersects ( Rectangle rect )
{
float ulx = Math.Max ( x, rect.x );
float uly = Math.Max ( y, rect.y );
float lrx = Math.Min ( x + width, rect.x + rect.width );
float lry = Math.Min ( y + height, rect.y + rect.height );
return ulx <= lrx && uly <= lry;
}
У меня очень простое решение
пусть x1, y1 x2, y2, l1, b1, l2, будут кординаты и их длины и ширины соответственно
рассмотрим условие ((x2
теперь единственный способ перекрытия этих прямоугольников - это если точка, диагональная x1, y1, будет лежать внутри другого прямоугольника или аналогично точке, диагональной x2, y2, будет лежать внутри другого прямоугольника. что в точности соответствует приведенному выше условию.
A и B - два прямоугольника. C быть их покрывающим прямоугольником.
four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom)
four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom)
A.width = abs(xAleft-xAright);
A.height = abs(yAleft-yAright);
B.width = abs(xBleft-xBright);
B.height = abs(yBleft-yBright);
C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright);
C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom);
A and B does not overlap if
(C.width >= A.width + B.width )
OR
(C.height >= A.height + B.height)
Он заботится обо всех возможных случаях.
Это из упражнения 3.28 из книги Введение в программирование на Java - полное издание. Код проверяет, являются ли два прямоугольника одинаковыми, находится ли один внутри другого и находится ли один за другим. Если ни одно из этих условий не выполнено, то два перекрываются.
** 3.28 (Геометрия: два прямоугольника) Напишите программу, которая предлагает пользователю ввести центр x-, y-координаты, ширина и высота двух прямоугольников и определяет находится ли второй прямоугольник внутри первого или перекрывается с первым, как показано на рисунке & 3.9. Протестируйте свою программу, чтобы охватить все случаи. Вот примеры прогонов:
Введите x-, y-координаты, ширину и высоту центра r1: 2,5 4 2,5 43 Введите x-, y-координаты, ширину и высоту центра r2: 1,5 5 0,5 3 r2 находится внутри r1
Введите x-, y-координаты, ширину и высоту центра r1: 1 2 3 5.5 Введите x-, y-координаты, ширину и высоту центра r2: 3 4 4.5 5 r2 перекрывает r1
Введите x-, y-координаты, ширину и высоту центра r1: 1 2 3 3 Введите x-, y-координаты, ширину и высоту центра r2: 40 45 3 2 r2 не перекрывает r1
import java.util.Scanner;
public class ProgrammingEx3_28 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out
.print("Enter r1's center x-, y-coordinates, width, and height:");
double x1 = input.nextDouble();
double y1 = input.nextDouble();
double w1 = input.nextDouble();
double h1 = input.nextDouble();
w1 = w1 / 2;
h1 = h1 / 2;
System.out
.print("Enter r2's center x-, y-coordinates, width, and height:");
double x2 = input.nextDouble();
double y2 = input.nextDouble();
double w2 = input.nextDouble();
double h2 = input.nextDouble();
w2 = w2 / 2;
h2 = h2 / 2;
// Calculating range of r1 and r2
double x1max = x1 + w1;
double y1max = y1 + h1;
double x1min = x1 - w1;
double y1min = y1 - h1;
double x2max = x2 + w2;
double y2max = y2 + h2;
double x2min = x2 - w2;
double y2min = y2 - h2;
if (x1max == x2max && x1min == x2min && y1max == y2max
&& y1min == y2min) {
// Check if the two are identicle
System.out.print("r1 and r2 are indentical");
} else if (x1max <= x2max && x1min >= x2min && y1max <= y2max
&& y1min >= y2min) {
// Check if r1 is in r2
System.out.print("r1 is inside r2");
} else if (x2max <= x1max && x2min >= x1min && y2max <= y1max
&& y2min >= y1min) {
// Check if r2 is in r1
System.out.print("r2 is inside r1");
} else if (x1max < x2min || x1min > x2max || y1max < y2min
|| y2min > y1max) {
// Check if the two overlap
System.out.print("r2 does not overlaps r1");
} else {
System.out.print("r2 overlaps r1");
}
}
}
bool Square::IsOverlappig(Square &other)
{
bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
return result1 | result2 | result3 | result4;
}
Для тех из вас, кто использует центральные точки и половинные размеры для своих данных прямоугольника, вместо типичных x, y, w, h или x0, y0, x1, x1, вот как вы можете это сделать:
#include <cmath> // for fabsf(float)
struct Rectangle
{
float centerX, centerY, halfWidth, halfHeight;
};
bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b)
{
return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) &&
(fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight));
}
Этот ответ должен быть главным ответом:
Если прямоугольники перекрываются, то область перекрытия будет больше нуля. Теперь давайте найдем область перекрытия:
Если они перекрываются, то левый край прямоугольника перекрытия будет max(r1.x1, r2.x1), а правый - min(r1.x2, r2.x2). Таким образом, длина перекрытия будет min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
Таким образом, площадь будет:
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
Если area = 0, то они не перекрываются.
Просто не так ли?
Взгляд на это с другого сайта.
Случай оказывается довольно простым, если мы посмотрим на проблему (алгоритм) с другой стороны .
Это означает, что вместо ответа на вопрос: " прямоугольники перекрываются? " ;, мы ответим на вопрос: " прямоугольники не перекрытие? & "
В конце концов, оба вопроса решают одну и ту же проблему, но ответ на второй вопрос проще реализовать , потому что прямоугольники не перекрываются, только когда один находится под другим или когда один больше слева от другого (достаточно, чтобы один из этих случаев имел место, но, конечно, может случиться так, что оба будут происходить одновременно - здесь хорошее понимание логического условия & "; или & важно). Это уменьшает количество случаев, которые необходимо рассмотреть по первому вопросу.
Весь вопрос также упрощается за счет использования соответствующих имен переменных :
#include<bits/stdc++.h>
struct Rectangle
{
// Coordinates of the top left corner of the rectangle and width and height
float x, y, width, height;
};
bool areRectanglesOverlap(Rectangle rect1, Rectangle rect2)
{
// Declaration and initialization of local variables
// if x and y are the top left corner of the rectangle
float left1, top1, right1, bottom1, left2, top2, right2, bottom2;
left1 = rect1.x;
top1 = rect1.y;
right1 = rect1.x + rect1.width;
bottom1 = rect1.y - rect1.height;
left2 = rect2.x;
top2 = rect2.y;
right2 = rect2.x + rect2.width;
bottom2 = rect2.y - rect2.height;
// The main part of the algorithm
// The first rectangle is under the second or vice versa
if (top1 < bottom2 || top2 < bottom1)
{
return false;
}
// The first rectangle is to the left of the second or vice versa
if (right1 < left2 || right2 < left1)
{
return false;
}
// Rectangles overlap
return true;
}
Даже , если у нас другое представление прямоугольника, легко адаптировать вышеуказанную функцию к нему, изменяя только раздел, в котором определены изменения переменных. Остальная часть функции остается без изменений (конечно, комментарии здесь на самом деле не нужны, но я добавил их, чтобы каждый мог быстро понять этот простой алгоритм).
эквивалент , но, возможно, немного менее читаемая форма вышеуказанной функции может выглядеть следующим образом:
bool areRectanglesOverlap(Rectangle rect1, Rectangle rect2)
{
float left1, top1, right1, bottom1, left2, top2, right2, bottom2;
left1 = rect1.x;
top1 = rect1.y;
right1 = rect1.x + rect1.width;
bottom1 = rect1.y - rect1.height;
left2 = rect2.x;
top2 = rect2.y;
right2 = rect2.x + rect2.width;
bottom2 = rect2.y - rect2.height;
return !(top1 < bottom2 || top2 < bottom1 || right1 < left2 || right2 < left1);
}
" Если вы выполняете вычитание x или y координат, соответствующих вершинам двух, стоящих перед каждым прямоугольником, если результаты имеют одинаковый знак, два прямоугольника не перекрывают оси, которые " (извините, я не уверен, что мой перевод правильный)
Источник: http : //www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
Код Java, чтобы выяснить, соприкасаются ли прямоугольники или перекрывают друг друга
...
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < n; j++ ) {
if ( i != j ) {
Rectangle rectangle1 = rectangles.get(i);
Rectangle rectangle2 = rectangles.get(j);
int l1 = rectangle1.l; //left
int r1 = rectangle1.r; //right
int b1 = rectangle1.b; //bottom
int t1 = rectangle1.t; //top
int l2 = rectangle2.l;
int r2 = rectangle2.r;
int b2 = rectangle2.b;
int t2 = rectangle2.t;
boolean topOnBottom = t2 == b1;
boolean bottomOnTop = b2 == t1;
boolean topOrBottomContact = topOnBottom || bottomOnTop;
boolean rightOnLeft = r2 == l1;
boolean leftOnRight = l2 == r1;
boolean rightOrLeftContact = leftOnRight || rightOnLeft;
boolean leftPoll = l2 <= l1 && r2 >= l1;
boolean rightPoll = l2 <= r1 && r2 >= r1;
boolean leftRightInside = l2 >= l1 && r2 <= r1;
boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside;
boolean bottomPoll = t2 >= b1 && b2 <= b1;
boolean topPoll = b2 <= b1 && t2 >= b1;
boolean topBottomInside = b2 >= b1 && t2 <= t1;
boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside;
boolean topInBetween = t2 > b1 && t2 < t1;
boolean bottomInBetween = b2 > b1 && b2 < t1;
boolean topBottomInBetween = topInBetween || bottomInBetween;
boolean leftInBetween = l2 > l1 && l2 < r1;
boolean rightInBetween = r2 > l1 && r2 < r1;
boolean leftRightInBetween = leftInBetween || rightInBetween;
if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) {
path[i][j] = true;
}
}
}
}
...
