読者です 読者をやめる 読者になる 読者になる

Boost.Geometry convex_hull

C++

convex_hull()は、図形の凸包を計算する関数です。
第1引数として渡した図形の凸包図形を第2引数で参照として返してくれます。

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

int main()
{
    namespace bg = boost::geometry;

    typedef bg::model::d2::point_xy<double> point;
    typedef bg::model::polygon<point> polygon;

    polygon poly;
    bg::exterior_ring(poly) = boost::assign::list_of<point>
        (2.0, 1.3)
        (2.4, 1.7)
        (3.6, 1.2)
        (4.6, 1.6)
        (4.1, 3.0)
        (5.3, 2.8)
        (5.4, 1.2)
        (4.9, 0.8)
        (3.6, 0.7)
        (2.0, 1.3)
        ;

    polygon hull;
    bg::convex_hull(poly, hull);
       
    std::cout
        << "polygon: " << bg::dsv(poly) << std::endl
        << "hull: "    << bg::dsv(hull) << std::endl;
}
polygon: (((2, 1.3), (2.4, 1.7), (3.6, 1.2), (4.6, 1.6), (4.1, 3), (5.3, 2.8), (5.4, 1.2), (4.9, 0.8), (3.6, 0.7), (2, 1.3)))
hull: (((2, 1.3), (2.4, 1.7), (4.1, 3), (5.3, 2.8), (5.4, 1.2), (4.9, 0.8), (3.6, 0.7), (2, 1.3)))


点線がconvex_hull()で計算された凸包です。



参照:
convex_hull algorithm