Cómo determinar si un punto (x, y) está dentro de un polígono definido por una lista de puntos límite

Question

Tengo una gran lista de puntos que definen un límite de alguna forma (no necesariamente convexa). Luego tengo un punto de consulta (x, y) y quiero determinar si (x, y) está dentro de la región definida por mi límite de puntos.

Por lo tanto, pregunta bastante simple. ¿Cómo determino si el punto de consulta estaría dentro de la forma formada por mis puntos de frontera? ¿Y hay un buen módulo de impulso para esto? Estoy mirando a través de boost::geometry pero no he encontrado nada todavía ..

Answer 1

Parece que estás buscando within, ¿no?

http://www.boost.org/libs/geometry/doc/html/geometry/reference/algorithms/within/within_2.html

El ejemplo que dan en la página es, de hecho, un punto en el polígono:

#include <iostream> 
#include <list> 

#include <boost/geometry.hpp> 
#include <boost/geometry/geometries/point_xy.hpp> 
#include <boost/geometry/geometries/polygon.hpp> 

#include <boost/geometry/domains/gis/io/wkt/wkt.hpp> 


int main() 
{ 
    typedef boost::geometry::model::d2::point_xy<double> point_type; 
    typedef boost::geometry::model::polygon<point_type> polygon_type; 

    polygon_type poly; 
    boost::geometry::read_wkt(
     "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3)" 
      "(4.0 2.0, 4.2 1.4, 4.8 1.9, 4.4 2.2, 4.0 2.0))", poly); 

    point_type p(4, 1); 

    std::cout << "within: " << (boost::geometry::within(p, poly) ? "yes" : "no") << std::endl; 

    return 0; 
} 

ACTUALIZACIÓN: como @ildjarn señala, es posible que en lugar utilizar si covered_by querías puntos que están en el mismo borde de un polígono para contar:

http://www.boost.org/libs/geometry/doc/html/geometry/reference/algorithms/covered_by/covered_by_2.html

El comportamiento de within w.r.t. los bordes "dependen", así que tome nota de ese matiz en la documentación.