Determinar se dois retângulos se sobrepõem uns aos outros?
https://stackoverflow.com/questions/306316
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou tentando escrever um programa em C ++ que leva as seguintes entradas do usuário para retângulos construto (entre 2 e 5): altura, largura x-pos, Y-pos. Todos esses retângulos vai existir paralelamente à x e do eixo y, que é todas as suas bordas terá encostas do 0 ou infinito.
Eu tentei implementar o que é mencionado no esta questão mas eu não estou tendo muito sorte.
Meu atual implementação faz o seguinte:
// 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;
No entanto, eu não estou muito certo se (a) Eu tenho implementado o algoritmo que eu ligado corretamente, ou se eu fiz exatamente como interpretar isso?
Todas as sugestões?
Solução
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
ou, usando coordenadas cartesianas
(Com X1 sendo coord esquerda, X2 sendo coord direita, aumentando da esquerda para a direita e sendo Y1 sendo Top coord e Y2 coord inferior, aumentando de baixo para cima) ...
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
Nota: Os utilizadores a todos para com autoridade de edição. Por favor, pare de mexer com isso.
Digamos que você tenha Rect A, e Rect B. A prova é por contradição. Qualquer uma das quatro condições garantias de que nenhuma sobreposição pode existir :
- COND1. Se a margem esquerda de A é à direita da margem direita do B, - então A é totalmente para a direita de B
- cond2. Se borda direita de A é para a esquerda da borda esquerda do B, - então A é totalmente à esquerda do B
- Cond3. Se a borda superior de A é inferior a borda inferior de B, - então A é totalmente abaixo B
- Cond4. Se borda inferior de A é acima da borda superior B, - então A é totalmente acima B
Assim condição para a não-sobreposição é
Cond1 Or Cond2 Or Cond3 Or Cond4
Portanto, uma condição suficiente para sobreposição é o oposto.
Not (Cond1 Or Cond2 Or Cond3 Or Cond4)
A lei de De Morgan diz
Not (A or B or C or D) é o mesmo que Not A And Not B And Not C And Not D
portanto, usando De Morgan, temos
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
Isto é equivalente a:
- borda esquerda da A à esquerda da margem direita do B, [
RectA.Left < RectB.Right], e - borda direita de A para a direita da borda esquerda do B, [
RectA.Right > RectB.Left], e - topo de A acima fundo do B, [
RectA.Top > RectB.Bottom], e - fundo de A abaixo Top de B [
RectA.Bottom < RectB.Top]
Nota 1 :. É bastante óbvio que este mesmo princípio pode ser estendido para qualquer número de dimensões
Nota 2 :. Também deve ser bastante óbvio para contar sobreposições de apenas um pixel, mudar o < e / ou o > em que limite a um <= ou um >=
Outras dicas
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;
}
É mais fácil verificar se um retângulo é completamente fora do outro, por isso, se é ou
na ...
esquerdo(r1.x + r1.width < r2.x)
ou à direita ...
(r1.x > r2.x + r2.width)
ou em cima ...
(r1.y + r1.height < r2.y)
ou no fundo ...
(r1.y > r2.y + r2.height)
do segundo retângulo, não pode, possivelmente, colidem com ele. Portanto, para ter uma função que retorna um tempo dizendo booleana os retângulos colidem, nós simplesmente combinar as condições pelas RUP lógicas e negar o resultado:
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);
}
Para já recebem um resultado positivo ao tocar somente, podemos mudar o "<" e ">" por "<=" e "> =".
Pergunte a si mesmo a pergunta oposta: Como posso determinar se dois retângulos não se cruzam em tudo? Obviamente, um retângulo Um completamente à esquerda do retângulo B não se cruzam. Além disso, se A é completamente para a direita. E da mesma forma, se A é completamente acima B ou completamente abaixo B. Em qualquer outro caso A e B se cruzam.
O que se segue pode ter erros, mas estou bastante confiante sobre o algoritmo:
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);
}
Suponha que você tenha definido as posições e tamanhos dos retângulos como esta:
implementação My C ++ é assim:
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;
}
Uma chamada de exemplo a função de acordo com o valor indicado acima:
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
As comparações dentro do bloco if será semelhante a seguir:
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 ))
Aqui está como é feito na API Java:
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));
}
Na pergunta, você ligar para a matemática para quando retângulos estão em ângulos arbitrários de rotação. Se eu entender o pouco sobre ângulos da questão, porém, eu interpretar que todos os retângulos são perpendiculares entre si.
Um geral saber a área de sobreposição fórmula é:
Usando o exemplo:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) recolher todas as coordenadas X (esquerda e direita) em uma lista, em seguida, classificá-lo e remover duplicatas
1 3 4 5 6
2) recolher todas as coordenadas Y (superior e inferior) em uma lista, em seguida, classificá-lo e remover duplicatas
1 2 3 4 6
3) criar uma matriz 2D pelo número de lacunas entre as coordenadas únicas x * número de espaços entre as coordenadas original y.
4 * 4
4) pintar todos os retângulos nessa grade, incrementando a contagem de cada célula que ocorre ao longo:
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) Como você pintar os retângulos, é fácil de interceptar as sobreposições.
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;
}
Não pense em coordenadas como indicando onde os pixels são. Pense neles como sendo entre os pixels. Dessa forma, a área de um retângulo 2x2 deve ser de 4 e não 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
A maneira mais fácil é
/**
* 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);
}
Primeiro de tudo colocá-lo em sua mente que em computadores o sistema de coordenadas está de cabeça para baixo. eixo x é a mesma que na matemática mas do eixo-y aumenta para baixo e diminuição na indo para cima .. se retângulo são desenhados do centro. se as coordenadas x1 é maior que x2 além de sua sua metade de Largura. então isso significa em meia eles tocam. e da mesma maneira indo para baixo + metade da sua altura. ele irá colidir ..
Vamos dizer que os dois retângulos são um retângulo e retângulo B. Vamos lá centers Seja A1 e B1 (coordenadas de A1 e B1 pode ser encontrada com facilidade), deixe as alturas ser Ha e Hb, largura ser Wa e Wb, vamos dx é a distância largura (x) entre A1 e B1 e Dy ser a distância de altura (y) entre A1 e B1.
Agora podemos dizer que podemos dizer A e B sobreposição: quando
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
Eu implementei uma versão C #, é facilmente convertido em 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;
}
Eu tenho uma solução muito fácil
deixar x1, x2 y1, y2, L1, b1, L2, ser cordinates e comprimentos e larguras deles respectivamente
considerar a condição ((x2
agora a única maneira estes rectângulo vai sobreposição é, se o ponto diagonal para x1, y1 irá estar dentro do outro rectângulo ou de forma semelhante a diagonal ponto de x2, y2 irão estar dentro do outro rectângulo. que é exatamente a condição acima implica.
A e B ser dois retângulo. C ser o seu rectângulo cobertura.
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)
É preciso cuidar todos os casos possíveis.
Esta é a partir do exercício 3.28 do livro Introdução ao Java Programação- Comprehensive Edition. Os testes de códigos se os dois rectângulos são indenticle, se um está dentro do outro e se um fora é o outro. Se nenhuma destas condições são atendidas, em seguida, os dois se sobrepõem.
** 3,28 (Geometria: dois retângulos) Escreva um programa que solicita ao usuário para entrar no x- centro, coordenadas y, a largura e a altura de dois rectângulos e determina se o segundo rectângulo está dentro do primeiro ou sobreposições com a primeira, como mostrado na Figura 3.9. Teste o seu programa para cobrir todos os casos. Aqui estão as amostras corridas:
Enter x- centro de R1, coordenadas y, largura e altura: 2,5 4 2,5 43 Introduzir x- centro de R2, coordenadas y, largura e altura: 1,5 5 0,5 3 r2 está dentro r1
Entre X- centro de R1, coordenadas y, largura e altura: 1 2 3 5,5 Introduzir x- centro de R2, coordenadas y, largura e altura: 4,5 3 4 5 r2 sobreposições r1
Entre X- centro de R1, coordenadas y, largura e altura: 1 2 3 3 Introduzir x- centro de R2, coordenadas y, largura e altura: 40 45 3 2 r2 não se sobrepõe 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;
}
Para aqueles de vocês que estão usando pontos centrais e tamanhos meio de seus dados retângulo, em vez do típico x, y, w, h, ou x0, y0, x1, x1, aqui está como você pode fazê-lo:
#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));
}
Esta resposta deve ser a resposta de topo:
Se os retângulos se sobrepõem, em seguida, a área de sobreposição será maior do que zero. Agora vamos encontrar a área de sobreposição:
Se eles se sobrepõem, em seguida, a borda esquerda de sobreposição-rect será o max(r1.x1, r2.x1) e borda direita será min(r1.x2, r2.x2). Assim, o comprimento da sobreposição será min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
Assim, a área será:
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
Se area = 0 então eles não se sobrepõem.
Simples não é?
Um olhar sobre o assunto a partir de um site diferente.
O caso acaba para ser bastante simples, se olharmos para o problema (algoritmo) do outro lado .
Isso significa que, em vez de responder à pergunta: "São os retângulos se sobrepõem?", Vamos responder à pergunta: "? São os retângulos fazer não sobreposição"
No final, ambas as perguntas resolver o mesmo problema, mas a resposta à segunda pergunta é mais simples de implementar , porque retângulos não se sobrepõem apenas quando se está sob o outro ou quando se está mais à esquerda do outro (é o suficiente para um desses casos a ter lugar, mas é claro que pode acontecer que ambos irão acontecer simultaneamente - aqui uma boa compreensão da condição lógica "ou" é importante) . Isso reduz muitos casos que precisam ser considerados na primeira pergunta.
A questão toda é também simplificado pelo uso de nomes de variáveis ??apropriadas :
#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;
}
Mesmo se temos uma representação diferente de um retângulo, é fácil de se adaptar a função acima para ele, modificando apenas a seção onde as variáveis ??mudanças estão definidas. A maior parte dos restos de função inalteradas (é claro, os comentários não são realmente necessário aqui, mas eu adicionei-los para que todos pudessem entender rapidamente este algoritmo simples).
Um equivalente , mas talvez um pouco menos legível forma da função acima pode ser parecido com isto:
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);
}
"Se você executar a subtração x ou y coordenadas correspondentes aos vértices dos dois enfrenta cada retângulo, se os resultados são o mesmo sinal, os dois retângulo não se sobrepõem eixos que" (Lamento, não estou certo minha tradução está correta)
Fonte: http : //www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
código Java para descobrir se retângulos está contatando ou sobrepostos uns aos outros
...
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;
}
}
}
}
...
