Probar si un punto está dentro de un polígono es bastante difícil para un humano si el polígono es un poco más complejo. 
(imagen de http://www.ics.uci.edu/~eppstein…)
O (n) algoritmos:
- Proyección de rayos: dispara un rayo desde tu punto y observa cuántos lados del polígono se cruza. Si el número es par, su punto está fuera del polígono. Si es extraño, tu punto está adentro.
- Número de devanado: recorra los lados del polígono y sume la suma de los ángulos con signo que hacen los puntos en los lados con su punto actual. El resultado debe ser 2π si el punto está adentro y 0 si el punto está afuera
Algoritmo de polígono convexo / polígono estrellado O (log n ):
Elija un vértice del polígono convexo. Dispara n -1 rayos desde este vértice a cualquier otro vértice. Utilice la búsqueda binaria para encontrar dónde se encuentra su punto de consulta entre dos rayos consecutivos utilizando su ángulo. Entonces solo necesitas probar si el punto está dentro de un triángulo.
- Cómo estimar pi usando un hexágono unitario en Matlab
- ¿Qué algoritmos de programación utiliza cada sistema operativo común?
- Cómo entender un algoritmo de búsqueda CSP
- ¿Con qué tipo de algoritmo debo comenzar desde el principio?
- ¿Cuáles son los mejores algoritmos de partición de gráficos para gráficos grandes?
Solución de red:
Para una precisión fija, divida el plano en cuadrados y calcule si cada cuadrado está dentro o fuera del polígono.
¿Solución Quadtree O (log U ) ?:
Construya un quadtree para representar el plano para una precisión fija. Cada cuadrado en el quadtree está totalmente dentro, totalmente fuera del polígono o se cruza con el polígono. Si se cruza con el polígono, puede dividirlo en 4 subcuadrados o detenerse porque el nivel de precisión es lo suficientemente pequeño.
Losas verticales (O ( n ^ 2) preprocesamiento O (log n ) consulta):
Dibuja una línea vertical a través de cada vértice del polígono. Esto divide el plano en n losas verticales. Para cada losa, calcule los segmentos que cruzan la losa y ordénelos por la y de su punto medio.
Para un punto de consulta dado, primero use la búsqueda binaria para encontrar la losa en la que se encuentra su punto. Dentro de la losa puede buscar binariamente el segmento más bajo que cruza la losa y está por encima de nuestro punto de consulta. Ahora puede contar cuántos segmentos están intersectados por un rayo vertical que comienza desde el punto de consulta y saber si está dentro del polígono o no.
Este enfoque se puede mejorar al procesamiento previo de O ( n ) y al tiempo de consulta de O (log n ).
Hay otro enfoque inteligente que divide en cada nivel un triángulo en 3 más pequeños, pero no recuerdo los detalles exactamente.
