Punto contenido dentro de un polígono - bnl

[Pogacha]

Este esta bastante decente en realidad:

Código [Seleccionar] Expand

bool point_in_poly(int n, const float *xp, const float *yp, float x, float y)
{
    bool c = false;
    for (int i = 0, j = n-1; i < n; j = i++)
       if ((((yp[i] <= y) && (y < yp[j])) ||
          ((yp[j] <= y) && (y < yp[i]))) &&
          ((x - xp[i]) * (yp[j] - yp[i]) - (xp[j] - xp[i]) * (y - yp[i]) < 0.001f) c = !c;
  return c;
}
Igual falla con los colineales y vertices sobre vertices ...

[Esgaroth]

Acá les explico de manera gráfica el posible error que puede causar el método de trazar una línea para determinar si el punto está dentro o fuera del polígono.

**** Línea del polígono
____ Relleno1
....... Relleno2
------ Línea trazada
P       Punto

Número par de colisiones:

_***********************
_*______________________*
_*______*__P----*----------------*------
_*_____* *____*_*__________*
_******__*****__************

Salida ---> Está fuera.

Número impar de colisiones:

_***********************
_*______________________*
_*__P----*----------*---------------*------
_*_____* *____*_*__________*
_******__*****__************

Salida: ---> Está dentro.

Supuestamente la línea debe atravezar el vértice. Pero no podemos obviar los vértices, ya que podría llegar a suceder suceder esto:

__*******************
__*............................*
__*................P------*-----------
__*............................*
__*******************

Salida ---> Está fuera (ya que se obviaron los vértices).

Sé que no se entiende muy bien, es porque tuve que poner un "Relleno" para que el programa encargado de "corregir" no me cancele el relleno hecho con la tecla espacio (sirve para corregir el doble espacio).

Aún así me parece un método bastante simple y efectivo, solo debería solucionar el problema de los vértices.

[Pogacha]

OK,
Luego de repasar los libros un poco ...

La solución general es descomposición en triangulos, que es Nlg2N en el peor de los casos.
Pero no es muy práctica y tiene una constante elevada, para perfecta presición ese debes usar.

El metodo del winding number es el mas recomendado luego de esto, pero tienes que atender los casos especiales en donde el punto es colineal con algun segmento del poligono y la recta elegida y el otro caso especial cuando el punto coincide con algún vertice.

Saludos!

EDITO:
Olvide decir, y por supuesto si el poligono es estatico, y habrá muchas pruebas, el algoritmo a elegir es el arbol bsp, donde llegaras al resultado en de Log2N a N. Dependiendo de cuan convexo sea será mas cercano a N y sino mas cercano a Log2N.

Saludos!