algorithm - Encontrar si un punto se encuentra dentro de un rectángulo o no

geometry

Question

Quiero encontrar si un punto se encuentra dentro de un rectángulo o no. El rectángulo se puede orientar de cualquier manera y no necesita alinearse con el eje.

Un método en el que podía pensar era girar las coordenadas del rectángulo y del punto para alinear el eje del rectángulo y luego simplemente probando las coordenadas del punto, ya sea que estén dentro del rectángulo o no.

El método anterior requiere rotación y, por lo tanto, operaciones de coma flotante. ¿Hay alguna otra manera eficiente de hacer esto?

Answer 1

Si un punto está dentro de un rectángulo. En un avión. Para coordenadas de matemática o geodesia (GPS)

• Deje que el rectángulo sea establecido por los vértices A, B, C, D. El punto es P. Las coordenadas son rectangulares: x, y.
• Permite prolongar los lados del rectángulo. Entonces tenemos 4 líneas rectas l _AB , l _BC , l _CD , l _DA , o, para abreviar, l ₁ , l ₂ , l ₃ , l ₄ .

• Haz una ecuación para cada l _i . El tipo de ecuación de:

  f _i (P) = 0.

P es un punto. Para los puntos, que pertenecen a l _i , la ecuación es verdadera.

• Necesitamos las funciones en el lado izquierdo de las ecuaciones. Son f ₁ , f ₂ , f ₃ , f ₄ .
• Observe que para cada punto de un lado de l _i la función f _i es mayor que 0, para los puntos del otro lado f _i es menor que 0.
• Entonces, si estamos buscando que P esté en rectángulo, solo necesitamos que p esté en los lados correctos de las cuatro líneas. Entonces, tenemos que verificar cuatro funciones para sus signos.
• Pero, ¿qué lado de la línea es el correcto, al que pertenece el rectángulo? Es el lado, donde se encuentran los vértices del rectángulo que no pertenecen a la línea. Para verificar podemos elegir cualquiera de los dos vértices que no pertenecen.

• Entonces, tenemos que verificar esto:

  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

Las desigualdades no son estrictas, ya que si un punto está en el borde, también pertenece al rectángulo. Si no necesita puntos en el borde, puede cambiar las inecuaciones en las más estrictas. Pero mientras trabajas en operaciones de punto flotante, la elección es irrelevante.

• Por un punto, que está en el rectángulo, las cuatro inecuaciones son verdaderas. Tenga en cuenta que también funciona para todos los polígonos convexos, solo que el número de líneas / ecuaciones será diferente.

• Lo único que queda es obtener una ecuación para una línea que atraviesa dos puntos. Es una ecuación lineal bien conocida. Vamos a escribirlo para una línea AB y un punto P:

  f _AB (P) ≡ (x _A -x _B ) (y _P -y _B ) - (y _A -y _B ) (x _P -x _B )

La verificación podría simplificarse: recorramos el rectángulo en el sentido de las agujas del reloj : A, B, C, D, A. Luego, todos los lados correctos estarán a la derecha de las líneas. Entonces, no necesitamos comparar con el lado donde está el otro vertice. Y necesitamos verificar un conjunto de inecuaciones más cortas:

f _AB (P)> = 0

f _BC (P)> = 0

f _CD (P)> = 0

f _DA (P)> = 0

Pero esto es correcto para el conjunto de coordenadas normal, matemático (de las matemáticas de la escuela), donde X está a la derecha e Y a la cima. Y para las coordenadas de geodesia , como se usan en GPS, donde X está arriba, e Y está a la derecha, tenemos que cambiar las inecuaciones:

f _AB (P) <= 0

f _BC (P) <= 0

f _CD (P) <= 0

f _DA (P) <= 0

Si no está seguro con las direcciones de los ejes, tenga cuidado con este cheque simplificado: verifique un punto con la ubicación conocida, si ha elegido las inecuaciones correctas.

Answer 2

¿Cómo se representa el rectángulo? ¿Tres puntos? Cuatro puntos? Punto, lados y ángulo? Dos puntos y un lado? ¿Algo más? Sin saber eso, cualquier intento de responder a su pregunta tendrá solo un valor puramente académico.

En cualquier caso, para cualquier polígono convexo (incluido el rectángulo) la prueba es muy simple: verifique cada borde del polígono, suponiendo que cada borde esté orientado en sentido antihorario, y compruebe si el punto se encuentra a la izquierda del borde (a la izquierda -mano medio plano). Si todos los bordes superan la prueba, el punto está adentro. Si uno falla, el punto está afuera.

Para probar si el punto (xp, yp) encuentra en el lado izquierdo del borde (x1, y1) - (x2, y2) , necesita construir la ecuación de línea para la línea que contiene el borde. La ecuación es la siguiente

A * x + B * y + C = 0

dónde

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

Ahora todo lo que necesita hacer es calcular

D = A * xp + B * yp + C

Si D > 0 , el punto está en el lado izquierdo. Si D < 0 , el punto está en el lado derecho. Si D = 0 , el punto está en la línea.

Sin embargo, esta prueba, nuevamente, funciona para cualquier polígono convexo, lo que significa que podría ser demasiado genérico para un rectángulo. Un rectángulo podría permitir una prueba más simple ... Por ejemplo, en un rectángulo (o en cualquier otro paralelogramo) los valores de A y B tienen la misma magnitud pero diferentes signos para bordes opuestos (es decir, paralelos), que pueden explotarse para simplificar la prueba.

Answer 3

He tomado prestado la respuesta de Eric Bainville:

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

Que en javascript se ve así:

function pointInRectangle(m, r) {
    var AB = vector(r.A, r.B);
    var AM = vector(r.A, m);
    var BC = vector(r.B, r.C);
    var BM = vector(r.B, 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 u.x * v.x + u.y * v.y; 
}

p.ej:

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};

entonces:

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

Aquí hay un códec para dibujar el resultado como una prueba visual :) http://codepen.io/mattburns/pen/jrrprN

Answer 4

La forma más fácil en que pensé fue simplemente proyectar el punto sobre el eje del rectángulo. Dejame explicar:

Si puede obtener el vector desde el centro del rectángulo hasta el borde superior o inferior y el borde izquierdo o derecho. Y también tiene un vector desde el centro del rectángulo hasta su punto, puede proyectar ese punto en sus vectores de ancho y alto.

P = vector de punto, H = vector de altura, W = vector de ancho

Obtiene el vector de unidad W '', H'' dividiendo los vectores por su magnitud

proj_P, H = P - (P.H '') H'' proj_P, W = P - (P.W '') W''

A menos que me equivoque, lo cual no creo que sea ... (Corrígeme si estoy equivocado) pero si la magnitud de la proyección de tu punto en el vector de altura es menor que la magnitud del vector de altura (que es la mitad de la altura del rectángulo) y la magnitud de la proyección de su punto en el vector de ancho es, entonces tiene un punto dentro de su rectángulo.

Si tiene un sistema de coordenadas universal, puede que tenga que calcular los vectores de altura / ancho / punto utilizando la resta vectorial. Las proyecciones de vectores son increíbles! recuerda eso.

Answer 5

Me doy cuenta de que este es un hilo viejo, pero para cualquiera que esté interesado en ver esto desde una perspectiva puramente matemática, hay un hilo excelente en el intercambio de pila de matemática, aquí:

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

Editar: Inspirado por este hilo, he creado un método vectorial simple para determinar rápidamente dónde se encuentra tu punto.

Supongamos que tiene un rectángulo con puntos en p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) y p4 = (x4, y4), yendo en el sentido de las agujas del reloj. Si un punto p = (x, y) se encuentra dentro del rectángulo, entonces el producto de puntos (p - p1). (P2 - p1) estará entre 0 y | p2 - p1 | ^ 2, y (p - p1). (p4 - p1) estará entre 0 y | p4 - p1 | ^ 2. Esto es equivalente a tomar la proyección del vector p - p1 a lo largo y ancho del rectángulo, con p1 como origen.

Esto puede tener más sentido si muestro un 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"

Y eso es. También funcionará para paralelogramos.

Answer 6

Si no puede resolver el problema del rectángulo intente dividir el problema en problemas más fáciles. Divide el rectángulo en 2 triángulos y revisa si el punto está dentro de cualquiera de ellos como lo explican here

Esencialmente, recorre los bordes en cada dos pares de líneas desde un punto. Luego, use producto cruzado para verificar si el punto está entre las dos líneas usando el producto cruzado. Si se verifica para los 3 puntos, entonces el punto está dentro del triángulo. Lo bueno de este método es que no crea ningún error de punto flotante que ocurra si se verifican los ángulos.

Answer 7

Suponiendo que el rectángulo está representado por tres puntos A, B, C, con AB y BC perpendiculares, solo necesita verificar las proyecciones del punto de consulta M en AB y BC:

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

AB es el vector AB, con coordenadas (Bx-Ax, By-Ay), y dot(U,V) es el producto escalar de los vectores U y V: Ux*Vx+Uy*Vy .

Actualización . Tomemos un ejemplo para ilustrar esto: A (5,0) B (0,2) C (1,5) y D (6,3). A partir de las coordenadas del punto, obtenemos AB = (- 5,2), BC = (1,3), punto (AB, AB) = 29, punto (BC, BC) = 10.

Para el punto de consulta M (4,2), tenemos AM = (- 1,2), BM = (4,0), punto (AB, AM) = 9, punto (BC, BM) = 4. M está dentro del rectángulo.

Para el punto de consulta P (6,1), tenemos AP = (1,1), BP = (6, -1), punto (AB, AP) = - 3, punto (BC, BP) = 3. P no está dentro del rectángulo, porque su proyección en el lado AB no está dentro del segmento AB.

Answer 8

# 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

Answer 9

bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) {
    Point AB = vect2d(A, B);  float C1 = -1 * (AB.y*A.x + AB.x*A.y); float  D1 = (AB.y*m.x + AB.x*m.y) + C1;
    Point AD = vect2d(A, D);  float C2 = -1 * (AD.y*A.x + AD.x*A.y); float D2 = (AD.y*m.x + AD.x*m.y) + C2;
    Point BC = vect2d(B, C);  float C3 = -1 * (BC.y*B.x + BC.x*B.y); float D3 = (BC.y*m.x + BC.x*m.y) + C3;
    Point CD = vect2d(C, D);  float C4 = -1 * (CD.y*C.x + CD.x*C.y); float D4 = (CD.y*m.x + CD.x*m.y) + 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;}

Acabo de implementar la Respuesta de AnT usando c ++. Usé este código para verificar si la coordinación del píxel (X, Y) se encuentra dentro de la forma o no.