Point in Polygon

Solución

Para determinar si un punto está dentro de un polígono, podemos imaginar un rayo lanzado desde ese punto hacia cualquier dirección. Hay tres escenarios posibles:

1. Si el rayo intersecta un número impar de aristas, entonces el punto está adentro.
2. Si el rayo intersecta un número par de aristas, entonces el punto está afuera.
3. Si el punto de origen está sobre un segmento, entonces el punto está sobre el borde.

Este algoritmo se conoce como el algoritmo de Ray Casting.

Intersección de segmento con segmento

Dados dos segmentos $L_1 = (p_1,p_2)$ y $L_2 = (p_3,p_4)$, ¿cómo podemos comprobar de forma eficiente si se intersectan? Primero hay que usar un concepto de álgebra lineal llamado determinante.

Definiremos el determinante de dos vectores como $\times$. Dados dos vectores $\vec{a}=\langle x_1,y_1 \rangle$ y $\vec{b}=\langle x_2,y_2 \rangle$. Si $\vec{a}\times\vec{b}$ da un área positiva entonces $\vec{b}$ apunta a la izquierda de $\vec{a}$, si da un área negativa entonces $\vec{b}$ apunta a la derecha de $\vec{a}$, y si da un área cero entonces $\vec{b}$ y $\vec{a}$ son paralelos.

Comprobar si $L_1$ y $L_2$ se intersectan equivale a comprobar si $L_2$ intersecta la recta del segmento $L_1$, y comprobar si $L_1$ intersecta la recta del segmento $L_2$. Para que la primera de las dos condiciones sea cierta, $p_3$ y $p_4$ de $L_2$ deben estar en direcciones opuestas respecto de $L_1$. Para definirlo matemáticamente, sea

La condición será cierta si y solo si $\vec{a}\times\vec{b_1} \neq \vec{a}\times\vec{b_2}$. Verificar el segundo de los dos casos es equivalente al procedimiento de arriba, excepto que $p_1$ y $p_2$ se intercambian con $p_3$ y $p_4$.

Como en todo problema de geometría, los casos borde son inevitables. Un caso borde que uno podría considerar en el método de arriba es que si tanto $\vec{a}\times\vec{b_1}$ como $\vec{a}\times\vec{b_2}$ son iguales y son iguales a 0, entonces aún pueden intersectarse siempre que se superpongan. Pero hay un secreto: por cómo está estructurado este problema, todos los vértices están en puntos de retículo, es decir, tienen números enteros como coordenadas. Y como uno de los $L$ es personalizable (podemos elegir el punto hacia el que el punto lanza su rayo), podemos fijar su coordenada en $(\infty,1)$. De esta forma, el rayo tendrá una pendiente cercana a $0$, evitando con éxito todas las intersecciones posibles con puntos de retículo. Un truco para resolver todos los casos borde.

Implementación

Complejidad temporal: $\mathcal O(NM)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct Point {
	ll x, y;
};
 
// Compute the determinant of two vectors (p1,p2) and (p3,p4)
ll det(Point p1, Point p2, Point p3, Point p4) {
	return ((p2.x - p1.x) * (p4.y - p3.y) - (p2.y - p1.y) * (p4.x - p3.x));
}
 
// Check if point p3 is above or below line segment (p1,p2)
ll dir(Point p1, Point p2, Point p3) {
	ll result = det(p1, p2, p2, p3);
	if (result > 0) {
		return 1;
	} else if (result < 0) {
		return -1;
	} else {
		return 0;
	}
}
 
// Check if two line segments (p1,p2) and (p3,p4) intersect
bool intersect(Point p1, Point p2, Point p3, Point p4) {
	bool first = dir(p1, p2, p3) != dir(p1, p2, p4);
	bool second = dir(p3, p4, p1) != dir(p3, p4, p2);
	return first && second;
}
 
/*
 * If point p3 is collinear with points p1 and p2
 * Check if p3 is inside or outside the line segment (p1,p2)
 */
bool within(Point p1, Point p2, Point p3) {
	if (dir(p1, p2, p3) == 0) {
		bool xRange = (min(p1.x, p2.x) <= p3.x) && (p3.x <= max(p1.x, p2.x));
		bool yRange = (min(p1.y, p2.y) <= p3.y) && (p3.y <= max(p1.y, p2.y));
		return xRange && yRange;
	} else {
		return false;
	}
}
 
int main() {
	while (true) {
		int n, m;
		cin >> n;
		vector<Point> polygon(n);
		if (n == 0) { break; }
		for (int i = 0; i < n; i++) { cin >> polygon[i].x >> polygon[i].y; }
		cin >> m;
 
		/*
		 * Cast an ray and count # line segments that the ray intersected with:
		 *   If the amount is odd, then the point is inside
		 *   If the amount is even, then the point is outside
		 *   If the point is on a line segment, then it is on the boundary
		 */
		for (int i = 0; i < m; i++) {
			struct Point curr;
			cin >> curr.x >> curr.y;
			struct Point ray = {INT_MAX, curr.y + 1};
			int intersections = 0;
			for (int j = 0; j < n; j++) {
				if (intersect(polygon[j % n], polygon[(j + 1) % n], curr, ray)) {
					intersections++;
				}
				if (within(polygon[j % n], polygon[(j + 1) % n], curr)) {
					cout << "on\n";
					intersections = -1;
					break;
				}
			}
			if (intersections != -1) {
				if (intersections % 2) {
					cout << "in\n";
				} else {
					cout << "out\n";
				}
			}
		}
	}
}