Descobrir se um ponto está dentro de um retângulo ou não

Eu quero descobrir se um ponto está dentro de um retângulo ou não. O retângulo pode ser orientado de qualquer forma e não precisa ser alinhado ao eixo.

Um método que eu poderia pensar era girar as coordenadas do retângulo e do ponto para alinhar o eixo do retângulo e, em seguida, simplesmente testar as coordenadas do ponto, se elas estão dentro daquelas do retângulo ou não.

O método acima requer rotação e, portanto, operações de ponto flutuante. Existe alguma outra maneira eficiente de fazer isso?

Como o retângulo é representado? Três pontos? Quatro pontos? Ponto, lados e ângulo? Dois pontos e um lado? Algo mais? Sem saber, qualquer tentativa de responder à sua pergunta terá apenas valor puramente acadêmico.

Em qualquer caso, para qualquer polígono convexo (incluindo retângulo) o teste é muito simples: verifique cada borda do polígono, assumindo que cada borda esteja orientada no sentido anti-horário, e teste se o ponto está à esquerda da aresta (à esquerda meia-mão). Se todas as arestas passarem no teste – o ponto está dentro. Se um falhar – o ponto está fora.

Para testar se o ponto (xp, yp) fica do lado esquerdo da aresta (x1, y1) - (x2, y2) , você precisa construir a equação de linha para a linha que contém a aresta. A equação é a seguinte

 A * x + B * y + C = 0 

Onde

 A = -(y2 - y1) B = x2 - x1 C = -(A * x1 + B * y1) 

Agora tudo que você precisa fazer é calcular

 D = A * xp + B * yp + C 

Se D > 0 , o ponto está no lado esquerdo. Se D < 0 , o ponto está no lado direito. Se D = 0 , o ponto está na linha.

No entanto, esse teste funciona novamente para qualquer polígono convexo, o que significa que pode ser muito genérico para um retângulo. Um retângulo pode permitir um teste mais simples ... Por exemplo, em um retângulo (ou em qualquer outro paralelogramo) os valores de A e B têm a mesma magnitude mas sinais diferentes para bordas opostas (isto é, paralelas), que podem ser exploradas para simplificar o teste.

Assumindo que o retângulo é representado por três pontos A, B, C, com AB e BC perpendiculares, você só precisa verificar as projeções do ponto de consulta M em AB e BC:

 0 < = dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC) 

AB é o vetor AB, com coordenadas (Bx-Axe, By-Ay), e dot(U,V) é o produto escalar dos vetores U e V: Ux*Vx+Uy*Vy .

Atualize . Vamos dar um exemplo para ilustrar isso: A (5,0) B (0,2) C (1,5) e D (6,3). Das coordenadas pontuais obtemos AB = (- 5,2), BC = (1,3), ponto (AB, AB) = 29, ponto (BC, BC) = 10.

Para o ponto de consulta M (4,2), temos AM = (- 1,2), BM = (4,0), ponto (AB, AM) = 9, ponto (BC, BM) = 4. M está dentro do retângulo.

Para o ponto de consulta P (6,1), temos AP = (1,1), BP = (6, -1), ponto (AB, AP) = - 3, ponto (BC, BP) = 3. P não está dentro do retângulo, porque sua projeção no lado AB não está dentro do segmento AB.

 # Pseudo code # Corners in ax,ay,bx,by,dx,dy # Point in x, y bax = bx - ax bay = by - ay dax = dx - ax day = dy - ay if ((x - ax) * bax + (y - ay) * bay < 0.0) return false if ((x - bx) * bax + (y - by) * bay > 0.0) return false if ((x - ax) * dax + (y - ay) * day < 0.0) return false if ((x - dx) * dax + (y - dy) * day > 0.0) return false return true 

Eu peguei emprestado da resposta de Eric Bainville:

 0 < = dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC) 

Que em javascript se parece com isso:

 function pointInRectangle(m, r) { var AB = vector(rA, rB); var AM = vector(rA, m); var BC = vector(rB, rC); var BM = vector(rB, m); var dotABAM = dot(AB, AM); var dotABAB = dot(AB, AB); var dotBCBM = dot(BC, BM); var dotBCBC = dot(BC, BC); return 0 < = dotABAM && dotABAM <= dotABAB && 0 <= dotBCBM && dotBCBM <= dotBCBC; } function vector(p1, p2) { return { x: (p2.x - p1.x), y: (p2.y - p1.y) }; } function dot(u, v) { return ux * vx + uy * vy; } 

por exemplo:

 var r = { A: {x: 50, y: 0}, B: {x: 0, y: 20}, C: {x: 10, y: 50}, D: {x: 60, y: 30} }; var m = {x: 40, y: 20}; 

então:

 pointInRectangle(m, r); // returns true. 

Aqui está um codepen para desenhar a saída como um teste visual 🙂 http://codepen.io/mattburns/pen/jrrprN

insira a descrição da imagem aqui

Eu percebo que este é um tópico antigo, mas para qualquer um que esteja interessado em ver isso de uma perspectiva puramente matemática, há um excelente tópico na troca de pilha de matemática, aqui:

https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle

Edit: Inspirado por esta discussão, eu coloquei um método vetorial simples para determinar rapidamente onde está o seu ponto.

Suponha que você tenha um retângulo com pontos em p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) e p4 = (x4, y4), indo no sentido horário. Se um ponto p = (x, y) estiver dentro do retângulo, então o produto escalar (p – p1). (P2 – p1) ficará entre 0 e | p2 – p1 | ^ 2 e (p – p1). (p4 – p1) ficará entre 0 e | p4 – p1 | ^ 2. Isso equivale a tomar a projeção do vetor p – p1 ao longo do comprimento e largura do retângulo, com p1 como origem.

Isso pode fazer mais sentido se eu mostrar um código equivalente:

 p21 = (x2 - x1, y2 - y1) p41 = (x4 - x1, y4 - y1) p21magnitude_squared = p21[0]^2 + p21[1]^2 p41magnitude_squared = p41[0]^2 + p41[1]^2 for x, y in list_of_points_to_test: p = (x - x1, y - y1) if 0 < = p[0] * p21[0] + p[1] * p21[1] <= p21magnitude_squared: if 0 <= p[0] * p41[0] + p[1] * p41[1]) <= p41magnitude_squared: return "Inside" else: return "Outside" else: return "Outside" 

E é isso. Também funcionará para paralelogramos.

Se você não conseguir resolver o problema do retângulo, tente dividir o problema em problemas mais fáceis. Divida o retângulo em 2 triângulos e verifique se o ponto está dentro de qualquer um deles como eles explicam aqui

Essencialmente, você percorre as bordas em cada dois pares de linhas de um ponto. Em seguida, usando produto cruzado para verificar se o ponto está entre as duas linhas usando o produto cruzado. Se for verificado para todos os 3 pontos, o ponto estará dentro do triângulo. A coisa boa sobre esse método é que ele não cria nenhum erro de ponto flutuante, o que acontece se você verificar os ângulos.

 bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) { Point AB = vect2d(A, B); float C1 = -1 * (AB.y*Ax + AB.x*Ay); float D1 = (AB.y*mx + AB.x*my) + C1; Point AD = vect2d(A, D); float C2 = -1 * (AD.y*Ax + AD.x*Ay); float D2 = (AD.y*mx + AD.x*my) + C2; Point BC = vect2d(B, C); float C3 = -1 * (BC.y*Bx + BC.x*By); float D3 = (BC.y*mx + BC.x*my) + C3; Point CD = vect2d(C, D); float C4 = -1 * (CD.y*Cx + CD.x*Cy); float D4 = (CD.y*mx + CD.x*my) + C4; return 0 >= D1 && 0 >= D4 && 0 < = D2 && 0 >= D3;} Point vect2d(Point p1, Point p2) { Point temp; temp.x = (p2.x - p1.x); temp.y = -1 * (p2.y - p1.y); return temp;} 

Pontos dentro do polígono

Acabei de implementar a resposta da AnT usando c ++. Eu usei este código para verificar se a coordenação do pixel (X, Y) está dentro da forma ou não.

Se um ponto estiver dentro de um retângulo. Em um avião. Para coordenadas matemáticas ou geodésicas (GPS)

  • Deixe o retângulo ser definido pelos vértices A, B, C, D. O ponto é P. As coordenadas são retangulares: x, y.
  • Vamos prolongar os lados do retângulo. Portanto, temos 4 linhas retas: AB , I BC , I CD , I DA , ou, abreviadamente, I 1 , I 2 , I 3 , I 4 .
  • Faça uma equação para cada l i . A equação é uma espécie de:

    f i (P) = 0.

P é um ponto. Para pontos, pertencentes a l i , a equação é verdadeira.

  • Precisamos das funções no lado esquerdo das equações. Eles são f 1 , f 2 , f 3 , f 4 .
  • Observe que, para cada ponto de um lado de l i, a function f i é maior que 0, para pontos do outro lado f i é menor que 0.
  • Portanto, se estivermos verificando se P está no retângulo, só precisamos que p esteja nos lados corretos de todas as quatro linhas. Então, temos que verificar quatro funções para seus sinais.
  • Mas qual lado da linha é o correto, ao qual o retângulo pertence? É o lado, onde estão os vértices do retângulo que não pertencem à linha. Para verificar, podemos escolher qualquer um dos dois vértices não pertencentes.
  • Então, temos que verificar isso:

    f AB (P) f AB (C)> = 0

    f BC (P) f BC (D)> = 0

    f CD (P) f CD (A)> = 0

    f DA (P) f DA (B)> = 0

As desigualdades não são estritas, pois se um ponto está na fronteira, ele também pertence ao retângulo. Se você não precisar de pontos na borda, poderá alterar as inequações para as estritas. Mas enquanto você trabalha em operações de ponto flutuante, a escolha é irrelevante.

  • Por um ponto, isto é, no retângulo, todas as quatro inequações são verdadeiras. Observe que ele funciona também para todo polígono convexo, apenas o número de linhas / equações será diferente.
  • A única coisa que resta é obter uma equação para uma linha passando por dois pontos. É uma equação linear bem conhecida. Vamos escrever para uma linha AB e ponto P:

    f AB (P) ≡ (x A- x B ) (y P -y B ) – (y A -y B ) (x P -x B )

O cheque poderia ser simplificado – vamos ao longo do retângulo no sentido horário – A, B, C, D, A. Então todos os lados corretos estarão à direita das linhas. Então, não precisamos comparar com o lado onde está outro vértice. E precisamos verificar um conjunto de desigualdades mais curtas:

f AB (P)> = 0

f BC (P)> = 0

f CD (P)> = 0

f DA (P)> = 0

Mas isso é correto para o conjunto de coordenadas normal, matemático (da matemática escolar), onde X é à direita e Y até o topo. E para as coordenadas geodésicas , como são usadas no GPS, onde X é para o topo, e Y é para a direita, temos que virar as inequações:

f AB (P) < = 0

f BC (P) < = 0

f CD (P) < = 0

f DA (P) < = 0

Se você não tiver certeza com as direções dos eixos, tenha cuidado com esta verificação simplificada – verifique um ponto com o posicionamento conhecido, se você tiver escolhido as inequações corretas.

A maneira mais fácil que pensei foi projetar o ponto no eixo do retângulo. Deixe-me explicar:

Se você puder obter o vetor do centro do retângulo até a borda superior ou inferior e a borda esquerda ou direita. E você também tem um vetor do centro do retângulo para o seu ponto, você pode projetar esse ponto em seus vetores de largura e altura.

P = vetor de pontos, H = vetor de altura, W = vetor de largura

Obter o vetor unitário W ‘, H’ dividindo os vetores por sua magnitude

proj_P, H = P – (P.H ‘) H’ proj_P, W = P – (P.W ‘) W’

A menos que eu esteja enganado, o que eu não acho que sou … (Corrija-me se estiver errado) mas se a magnitude da projeção do seu ponto no vetor de altura for menor que a magnitude do vetor de altura (que é metade da altura do retângulo) e a magnitude da projeção do seu ponto no vetor largura é, então você tem um ponto dentro do seu retângulo.

Se você tiver um sistema de coordenadas universal, talvez seja necessário descobrir os vetores de altura / largura / ponto usando a subtração vetorial. Projeções vetoriais são incríveis! lembre-se disso.