Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

convex_hull

Calculates the convex hull of a geometry.

Description

The free function convex_hull calculates the convex hull of a geometry.

Synopsis

template<typename Geometry, typename OutputGeometry>
void convex_hull(Geometry const & geometry, OutputGeometry & hull)

Parameters

Type

Concept

Name

Description

Geometry const &

the input geometry type

geometry

A model of the specified concept, input geometry

OutputGeometry &

the output geometry type

hull

A model of the specified concept which is set to the convex hull

Header

Either

#include <boost/geometry/geometry.hpp>

Or

#include <boost/geometry/algorithms/convex_hull.hpp>

Conformance

The function convex_hull implements function ConvexHull() from the OGC Simple Feature Specification.

Supported geometries

Geometry

Status

Point

ok

Segment

ok

Box

ok

Linestring

ok

Ring

ok

Polygon

ok

MultiPoint

ok

MultiLinestring

ok

MultiPolygon

ok

Complexity

Logarithmic

Example

Shows how to generate the convex_hull of a geometry

#include <iostream>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/adapted/boost_tuple.hpp>

BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)


int main()
{
    typedef boost::tuple<double, double> point;
    typedef boost::geometry::model::polygon<point> polygon;

    polygon poly;
    boost::geometry::read_wkt("polygon((2.0 1.3, 2.4 1.7, 2.8 1.8, 3.4 1.2, 3.7 1.6,3.4 2.0, 4.1 3.0"
        ", 5.3 2.6, 5.4 1.2, 4.9 0.8, 2.9 0.7,2.0 1.3))", poly);

    polygon hull;
    boost::geometry::convex_hull(poly, hull);

    using boost::geometry::dsv;
    std::cout
        << "polygon: " << dsv(poly) << std::endl
        << "hull: " << dsv(hull) << std::endl
        ;


    return 0;
}

Output:

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)))
hull: (((2, 1.3), (2.4, 1.7), (4.1, 3), (5.3, 2.6), (5.4, 1.2), (4.9, 0.8), (2.9, 0.7), (2, 1.3)))

convex_hull

PrevUpHomeNext