¿Cómo verificar si un punto está dentro de un rectángulo?

Question

Hay un punto $(x,y)$, y un rectángulo $a(x_1,y_1),b(x_2,y_2),c(x_3,y_3),d(x_4,y_4)$, ¿cómo se puede verificar si el punto está dentro del rectángulo?

Answer 1

$M$ de coordenadas $(x,y)$ está dentro del rectángulo si y solo si

$$(0<\textbf{AM}\cdot \textbf{AB}<\textbf{AB}\cdot \textbf{AB}) \land (0<\textbf{AM}\cdot \textbf{AD}<\textbf{AD}\cdot \textbf{AD})$$

(productos escalares de vectores, $\land$ representa el Y lógico).

Answer 2

Permite que $P(x,y)$, y el rectángulo $A(x_1,y_1),B(x_2,y_2),C(x_3,y_3),D(x_4,y_4)$

Calcular la suma de las áreas de $\triangle APD, \triangle DPC, \triangle CPB, \triangle PBA$.

1. Si esta suma es mayor que el área del rectángulo, entonces $P(x,y)$ está afuera del rectángulo.

2. De lo contrario, si esta suma es igual al área del rectángulo (observa que esta suma no puede ser menor que la última),

   1. si el área de alguno de los triángulos es $0$, entonces $P(x,y)$ está en el rectángulo (de hecho, en esa línea correspondiente al triángulo de área$=0$). Observa que la igualdad de la suma es necesaria; no es suficiente que el área$=0$),

   2. de lo contrario, $P(x,y)$ está dentro del rectángulo.

Aceptablemente este enfoque requiere una cantidad sustancial de cálculos. Este enfoque también se puede emplear para cualquier polígono irregular.

---

Otra forma es calcular las distancias perpendiculares de $P(x,y)$ desde todas las 4 líneas $AB,CD, AD,BC$

Para estar dentro del rectángulo, las distancias perpendiculares desde $AB, P_{AB}$(digamos) y desde $CD, P_{CD}$(digamos) deben ser menores que $|AD|=|BC|$ y las distancias perpendiculares desde $AD, P_{AD}$(digamos) y desde $BC, P_{BC}$(digamos) deben ser menores que $|CD|=|AB$. Aquí, las áreas de cada uno de los cuatro triángulos < $\frac{1}{2}$ el área del rectángulo.

1. Si una de las distancias perpendiculares es mayor que la longitud respectiva, entonces $P(x,y)$ está fuera del rectángulo.

   Esto implica y es implicado por la afirmación: el área del triángulo respectivo > $\frac{1}{2}$ el área del rectángulo (como comentó Ben Voigt) ya que $\triangle APD=\frac{1}{2}AD\cdot P_{AD}$.

2. De lo contrario, si $ P_{AB}=0$ y $P_{CD}=|AD|$, entonces $P(x,y)$ está en AB. Entonces, $\triangle PBA=0$ y $\triangle PCD=\frac{1}{2}$ el área del rectángulo.

   Observa que en este caso, las otras dos distancias perpendiculares $P_{AD}, P_{BC}$ deben ser ≤ $|AB|=|CD|$, $P_{BC}=|AB|\implies P(x,y)$ está en AD, es decir, P coincide con A ya que ya está en AB.

Answer 3

Yo usaría una función "punto-en-polígono-convexo"; esto funciona verificando si el punto está "a la izquierda de" cada una de las cuatro líneas.

Answer 4

Por ejemplo, si todos los triángulos $ABP$, $BCP$, $CDP$, $DAP$ están orientados positivamente; para $ABP$ esto se puede comprobar revisando el signo de $(x-x_1)\cdot(y-y_2)-(y-y_1)\cdot(x-x_2)$. Este método se generaliza a polígonos convexos.

Alternativamente, encuentra una transformación que haga que el rectángulo sea paralelo a los ejes. Aplica la misma transformación a tu punto y la prueba es simple. Esto es especialmente útil si deseas probar muchos puntos contra el mismo rectángulo.

Answer 5

Uno de los algoritmos más simples de la geometría del plano coordenado es un método de "¿Está el vector $\vec{w}$ en sentido horario o antihorario desde el vector $\vec{v}$?"

El algoritmo consiste en calcular el producto cruzado $\vec{v} \times \vec{w}$. Si el signo es positivo, entonces $\vec{w}$ está en sentido antihorario desde $\vec{v}$. Si es negativo, está en sentido horario.

Este método proporciona un algoritmo para responder a la pregunta "¿En qué lado de una línea se encuentra un punto?"

Por ejemplo, considera la línea izquierda de tu cuadro, línea $da$, dirigida de $d$ a $a$. El punto $p=(x, y)$ está en el lado derecho de esta línea si y solo si el vector $dp$ está en sentido horario desde $da$. Por lo tanto, simplemente podemos calcular el producto cruzado para saber si $p$ está en el lado correcto de $da$ o no.

Haz esto con las cuatro líneas y tendrás tu prueba.

---

Si estás usando los mismos cuatro puntos muchas veces, podemos ahorrar trabajo a la mitad. Podemos usar el producto punto para calcular "¿Qué tan largo es un vector en la dirección en la que apunta otro?"

Podemos calcular el producto punto de $da$ con $dp$. Si este número es mayor que el producto punto de $da$ consigo mismo, entonces tu punto está demasiado arriba para estar en el cuadro. Si este número es negativo, el punto está demasiado abajo para estar en el cuadro.

Debido a que esto verifica dos límites a la vez, solo tenemos que hacer esto dos veces: una vez con $da$ para obtener la ubicación arriba-abajo, y una vez con $dc$ para obtener la ubicación izquierda-derecha.

---

EDICIÓN: Una de las ideas generales en juego es tratar de aprovechar al máximo el producto punto y el producto cruzado, ya que son formas computacionalmente eficientes de calcular información geométrica relacionada con cosas como longitud, ángulo y área.

Entonces, una estrategia común para un problema de geometría computacional es tratar de plantear el problema en términos de cosas que se pueden responder con productos punto y cruz. Si eso no es inmediatamente obvio, plantéalo en términos de longitudes (dirigidas), ángulos y áreas, y trata de reformular esas en términos de productos punto y cruz.

Mi enfoque para la pregunta fue expresar "¿en qué lado de una línea?" como un ángulo dirigido, permitiendo el uso del producto cruzado.

Además, usé el producto punto para calcular la distancia a lo largo de una dirección paralela a uno de los lados del rectángulo. Podrías calcular lo mismo como "distancia perpendicular" desde un lado adyacente, lo que te permitiría usar el producto cruzado.

Algunas de las otras respuestas expresan las cosas en términos de las áreas de triángulos, las cuales se calculan naturalmente con productos cruzados. Una respuesta sumó sus magnitudes y las comparó con el área del rectángulo. Otra miró la dirección de las áreas en su lugar (es decir, si los triángulos estaban orientados positivamente).