¿Adentro o afuera?

Para un procedimiento de donde trabajo había resolver la pregunta

¿Cómo saber si un punto está o no dentro de una región?

Reduciendo más el problema, la pregunta se convirtió en

¿Cómo saber si un punto está a la derecha o a la izquierda (o derecha) de una línea?

Y la respuesta apareció de las relaciones y operaciones entre vectores, desde una simple idea conceptual y de allí todo lo demás cayó por su peso, y es lo que sigue.

La famosa regla de la mano derecha

Empecemos con dos vectores, y , el primero está definido por dos puntos que conforman a la línea principal o de referencia; nótese que estos son puntos fijos. La segunda está definida por uno de los puntos de la línea principal y el punto del que deseamos evaluar saber si está o no a la derecha o izquierda de la línea principal; nótese que el punto a evaluar es un punto cualquiera.

Si recordamos la Regla de la mano derecha, esta indica que asignando el primer vector con el dedo índice, y el segundo con el dedo medio, el pulgar te indica la dirección del vector resultante tras operar con el producto cruz (o producto vectorial), que también indica hacia dónde habría que girar el primer vector para «ir» hacia el segundo; o también en qué dirección se cierra la mano.

Ahora, llevando esta idea hacia las líneas que definen los límites de la región que nos interesa, vemos que si en cada segmento de línea todas giran en la misma dirección hacia el punto a evaluar, entonces este punto está DENTRO de la región. Con una línea que gire en dirección contraria, tenemos que el punto está AFUERA.

Eso es conceptualmente. Ahora, para llevarlo a código la operación que nos define el giro es el producto cruz entre los vectores de referencia y el vector que contiene al punto a evaluar, i.e., : .

Dado que nuestros puntos están todos en el mismo plano, por lo que el producto cruz resultante tendrá siempre una sola componente, y es el signo de esta la que nos interesa. Definimos que un signo negativo implica girar hacia la izquierda.

De esta manera, si tenemos los puntos de los vértices que delimitan a nuestra región, podemos formar vectores de referencia que en secuencia evaluan si un punto P, tras formar un vector de evaluación, está a la izquierda y, por tanto, adentro.

¿Y si la región no es tan regular?

Si nuestra región no tiene una forma regular, tendríamos el problema de que un punto sea considerado afuera por alguno de nuestros productos cruz.

Para resolver o evadir ese problema, lo mejor es fragmentar la figura original en tantas figuras regulares como sea posible. De esta manera, si el punto está dentro de alguna subregión, entonces está dentro de la región completa.

Claro, aunque la idea sea sencilla, la fragmentación de regiones puede ser la tarea más engorrosa si esta es extensa (como un departamento/región). Pero de algún lado tienen que venir los datos y alguien tiene que hacerlo 🙂 Otro punto a mencionar es el tiempo que toma si se tiene una región muy fragmentada. Una táctica es encontrar maneras de focalizar la búsqueda, es decir, si un punto está por encima de los 14.5° pues la búsqueda ha de concentrarse en regiones que cumplan esas características.

Y bueno, esa es la idea sencilla. Podrán haber más eficientes o elegantes, pero eso ya será de cada quien.

Soundtrack del post

Anuncio publicitario