Convex Hull

X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X.

The convex hull of a set X of points in the Euclidean plane is the smallest convex set that contains X. when
Formally, the convex hull may be defined as the intersection of all convex sets containing X or as the set of all convex combinations of points in X.
A set of points is defined to be convex if it contains the line segments connecting each pair of its points. The convex hull of a given set X may be defined as

1. The (unique) minimal convex set containing X
2. The intersection of all convex sets containing X
3. The set of all convex combinations of points in X.

void convexHull(InputArray points, OutputArray hull, bool clockwise=false, bool returnPoints=true )

Parameters:

• points – Input 2D point set, stored in std::vector or Mat.
• hull – Output convex hull. It is either an integer vector of indices or vector of points. In the first case, the hull elements are 0-based indices of the convex hull points in the original array (since the set of convex hull points is a subset of the original point set). In the second case, hull elements are the convex hull points themselves.
• hull_storage – Output memory storage in the old API (cvConvexHull2 returns a sequence containing the convex hull points or their indices).
• clockwise – Orientation flag. If it is true, the output convex hull is oriented clockwise. Otherwise, it is oriented counter-clockwise. The assumed coordinate system has its X axis pointing to the right, and its Y axis pointing upwards.
• orientation – Convex hull orientation parameter in the old API, CV_CLOCKWISE or CV_COUNTERCLOCKWISE.
• returnPoints – Operation flag. In case of a matrix, when the flag is true, the function returns convex hull points. Otherwise, it returns indices of the convex hull points. When the output array is std::vector, the flag is ignored, and the output depends on the type of the vector: std::vector<int> implies returnPoints=true, std::vector<Point> implies returnPoints=false.

A good example for Convex Hull implementation is provided in OpenCV Documentation. Below code is a modification of the same.

Example:

------------

#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace cv;
using namespace std;

int main( int argc, char** argv )
{
 Mat src; Mat src_gray;
 src = imread( "airplane1.jpg", 1 );
 resize(src, src, Size(640,480), 0, 0, INTER_CUBIC);
 cvtColor( src, src_gray, CV_BGR2GRAY );
 blur( src_gray, src_gray, Size(3,3) ); 
 namedWindow( "Source", CV_WINDOW_AUTOSIZE );
 imshow( "Source", src );

 

 // Convex Hull implementation
 Mat src_copy = src.clone();
 Mat threshold_output;
 vector<vector<Point> > contours;
 vector<Vec4i> hierarchy;

 // Find contours
 threshold( src_gray, threshold_output, 200, 255, THRESH_BINARY );
 findContours( threshold_output, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0, 0) );

 // Find the convex hull object for each contour
 vector<vector<Point> >hull( contours.size() );
 for( int i = 0; i < contours.size(); i++ )
 {  convexHull( Mat(contours[i]), hull[i], false ); }

 // Draw contours + hull results
 RNG rng;
 Mat drawing = Mat::zeros( threshold_output.size(), CV_8UC3 );
 for( int i = 0; i< contours.size(); i++ )
 {
  Scalar color = Scalar( rng.uniform(0, 255), rng.uniform(0,255), rng.uniform(0,255) );
  drawContours( drawing, contours, i, color, 1, 8, vector<Vec4i>(), 0, Point() );
  drawContours( drawing, hull, i, color, 1, 8, vector<Vec4i>(), 0, Point() );
 }

 // Show in a window
 namedWindow( "Hull demo", CV_WINDOW_AUTOSIZE );
 imshow( "Hull demo", drawing );

 waitKey(0);
 return(0);
}

------------

Result:

Sources:
http://en.wikipedia.org/wiki/Convex_hull