So ermitteln Sie, ob ein (x, y) Punkt innerhalb eines durch eine Liste von Grenzpunkten definierten Polygons liegt

Question

Ich habe eine große Liste von Punkten, die eine Grenze einer (nicht notwendigerweise konvexen) Form definieren. Ich habe dann einen Abfragepunkt (x, y) und ich möchte feststellen, ob (x, y) innerhalb der durch meine Grenze der Punkte definierten Region ist.

Also, einfach genug Frage. Wie stelle ich fest, ob der Abfragepunkt innerhalb der Form liegt, die von meinen Grenzpunkten gebildet wird? Und gibt es dafür ein nettes Boost-Modul? Ich schaue durch boost::geometry aber habe noch nichts gefunden ..

Answer 1

Scheint, Sie suchen nach within, nein?

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

Das Beispiel, das sie auf der Seite geben wird, in der Tat, Point-in-Polygon:

#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; 
} 

UPDATE: als @ildjarn darauf hinweist, könnte man eher covered_by verwenden, wenn Sie wollten Punkte, die sich auf dem Polygonkante liegen zählen:

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

Das Verhalten von within w.r.t. Kanten "hängt" ab, notieren Sie diese Nuance in der Dokumentation.