Algoritmo Para Determinar Si Un Punto Se encuentra dentro de un polígono

Determinar si un punto esta dentro de un poligono
Hay varios algoritmos para la determinación de si un punto está dentro de un polígono. La función más fácil de implementar es la del "trazado derayos", que consiste en trazar una línea con origen en el punto designado por el usuario paralela a alguno de los ejes (X ó Y, da igual). Analíticamente, cuentas el número de intersecciones que seproducen con cada una de las líneas del polígono. Si el número de intersecciones es impar, entonces está dentro. Si el número de intersecciones es par, entonces está fuera. El principio se puede ver enesta imagen:





Dado un poligono y un punto p, hallar si p esta dentro del poligono o no. Los puntos que estan en el borde se consideran que estan adentro
.
Ahora se presenta una simple idea siun punto esta dentro o fuera de un polígono
1) Dibuja un linea horizontal hacia la derache de cada punto y entiendala hasta el infinito

2) Cuente el numero de veces que la linea intersecta conlos lados del polígono

3) Un punto esta dentro de un polígono si el número de veces que la linea intersecta al polígono es impar o el punto esta en el lado del polígono.
Si ninguna de lascondiciones son ciertas entonces el punto esta afuera del polígono.

.Algoritmo en C++
// Programa en c++ para determinar si un punto dado se encuentra dentro o fuera de un polígono
#include
usingnamespace std;
 
// Definir infinito
#define INF 10000
 
struct Point
{
    int x;
    int y;
};
 
// dados 3 puntos colineales p, q, r, la función comprueba si
// el punto q esta en elsegmento pr
bool onSegment(Point p, Point q, Point r)
{
    if (q.x = min(p.x, r.x) &&
            q.y = min(p.y, r.y))
        return true;
    return false;
}
 
// para encontrar la orientaciónde la triple ordenada (p, q, r).
// la función regresa los siguientes valores
// 0 --> p, q y r son colineales
// 1 --> Sentido horario
// 2 --> Sentido antihorario
int orientation(Point p,...